Constellation, le dépôt institutionnel de l'Université du Québec à Chicoutimi

Résumé

La théorie de l’ordonnancement a, depuis son avènement, suscité un grand intérêt de la part de chercheurs, de scientifiques, mais aussi d’industriels. Ceci est dû à la grande variété de problèmes réels pouvant être modélisés sous forme de problèmes d’ordonnancement. En effet, ce domaine peut trouver des applications aussi bien en gestion d’horaires qu’en informatique, ou encore en environnement de production. Les études relativement récentes dans le domaine ont vu l’introduction du paramètre humain et sa considération dans la prise de décision portant sur les ressources matérielles d’un problème d’ordonnancement. La présente thèse traite des problèmes d’ordonnancement d’ateliers avec opérateurs. Dans lesdits ateliers, des tâches devront être exécutées par plusieurs machines selon un ordre qui dépend du type d’atelier. Pour ce faire, lesdites tâches utilisent simultanément un opérateur et une machine. Le nombre d’opérateurs ainsi que leurs placements, i.e. leurs affectations aux machines, dépendra du modèle d’affectation choisi. Tout d’abord, nous considérons un problème de flow shop de permutation avec temps de réglages. Nous supposons que le nombre d’opérateurs est égal au nombre de machines et qu’ils s’occupent des opérations de réglage. Nous utilisons pour la résolution la métaheuristique Migrating Birds Optimization. Nous apportons des améliorations à l’algorithme de base et en présentons quatre versions, ce qui nous permet d’obtenir des résultats de relativement bonne qualité avec des configurations différentes qui apportent de la flexibilité lors de la prise de décision. Par la suite, nous étudions des problèmes où le nombre d’opérateurs est inférieur au nombre de machines. Nous étudions trois types d’ateliers : les flow shops, les job shops et les open shops. Nous commençerons d’abord par l’étude de complexité de nos problèmes. Nous présentons d’abord des cas résolubles en temps polynomial et exhibons les méthodes permettant de les résoudre. Pour les cas difficiles, nous proposons des méthodes de résolution ainsi que des bornes inférieures. Les résultats montrent que les méthodes proposées donnent de bons résultats, souvent proches des bornes théoriques.

Since its advent, scheduling theory has generated great interest amidst researchers, scientists but also industrialists. This is due to the great diversity of real problems that can be modeled as scheduling problems. Indeed, this field can find applications in timetabling, computer science but also in production systems. Recent studies in the field have introduced the human resources and considered them in decision making processes involving the material resources of scheduling problems. This thesis deals with scheduling shop problems with operators. In the aforementioned shops, tasks are to be processed according to orderings that depend on the type of shop. In order to do so, the tasks need simultaneously an operator and a machine. The number of operators and their positions in the shop, i.e. their assignements to machines, depends on the chosen assignment mode. First, we consider a permutation flow shop problem with setup times. We assume that the number of operators is equal to the number of machines and that they handle setup operations. We use the metaheuristic called the Migrating Birds Optimization to solve this problem. We improve the basic algorithm and present four versions, which allows us to obtain results of good quality with different structures, which provides flexibility in decision making. Next, we study problems where the number of operators is less than the number of machines. We study three types of shops : flow shops, job shops and open shops.We first start by studying the complexity of our problems. Then we present well-solvable cases as well as their solution methods. For some N P-hard cases, we propose solution methods and a lower bound. The results show that the proposed methods provide good results, often close to the theoretical lower bounds.