Model and algorithms for the Cyclic Hoist Design and Scheduling Problem

Dans un environnement industriel compétitif, les entreprises sont en concurrence pour produire des biens de qualité, avec des coûts moindres et des délais raccourcis. Dans ce contexte, l'ordonnancement des activités permet d’améliorer les processus de production. Parmi la multitude des problèmes étudiés dans la littérature scientifique, l'ordonnancement des ateliers de traitement de surface cherche à planifier les déplacements des robots pour maximiser la productivité. Dans les lignes de galvanoplastie, les pièces doivent tremper dans plusieurs cuves contenant des solutions chimiques en suivant une gamme spécifique de production. Les robots programmables qui circulent en général au-dessus de la ligne, assurent la manutention et le transfert des pièces entre les cuves. Ils constituent souvent les ressources critiques de la ligne, quand le nombre de cuves et/ou des produits à manipuler devient grand. Le traitement des pièces, à la différence d'autres ateliers de production, se réalise à durées variables qui doivent se situer dans des fenêtres temporelles définies. Nous considérons des ateliers de production de masse où un nombre important de pièces doit être traité. Les robots répètent alors indéfiniment une même séquence de mouvements, formant un cycle, pour assurer la manutention des pièces tout au long de la ligne. Le problème qui recherche la séquence cyclique minimisant la période du cycle est connu sous le nom de problème d'ordonnancement cyclique des ateliers de traitement de surface (Cyclic Hoist Scheduling Problem ou CHSP).Dans cette thèse, nous étudions les problèmes conjoints de dimensionnement et d’ordonnancement des ateliers de traitement de surface à plusieurs robots. Il s’agit d’une variante du CHSP, appelée Cyclic Hoist Design and Scheduling Problem (CHDSP). Notre objectif est d’optimiser le couple temps de cycle/nombre de robots. Sur ce problème bi-objectif, nous souhaitons apporter une contribution qui conduirait à terme à l'élaboration d'un système d'aide à la décision. Pour résoudre le CHDSP, nous développons des méthodes approchées adaptées, pour lesquelles nous proposons tout d'abord une nouvelle approche de codage des solutions basée sur les mouvements à vide des robots. Un algorithme génétique hybridé avec un programme linéaire en nombres entiers mixte (MILP), est élaboré, qui nous permet de valider ce nouveau codage et d’obtenir de premiers résultats intéressants. Nous développons également une deuxième métaheuristique hybride basée sur la recherche à voisinage variable et faisant appel au même MILP, pour optimiser la recherche des meilleures solutions dans un espace de recherche très vaste. Nous avons conduit une série de tests pour déterminer les meilleurs paramétrages de l’algorithme. Ce dernier a été testé sur plusieurs instances de la littérature sur lesquelles il montre sa performance et sa robustesse. Enfin, nous étendons la modélisation du problème CHDSP pour prendre en compte les contraintes d'évitement des collisions entre les robots qui partagent la même voie de circulation. Les tests réalisés sur les benchmarks de la littérature montrent l’efficacité de ce modèle complet.In a competitive industrial environment, companies compete to provide products of good quality, with lower costs and shorter lead times. In this context, the scheduling of activities allows to improve the production processes. Among the numerous problems studied in the scientific literature, the scheduling of surface treatment workshops seeks to plan the movements of hoists to maximize productivity. In electroplating lines, parts must soak in several tanks containing chemical solutions according to a given processing sequence. Programmable robots, called hoists, circulate above the line to ensure the handling and transfer of parts between the tanks. They often represent the line critical resources, when the number of tanks and/or products to be handled becomes large. The processing of parts, unlike other production workshops, is carried out at times which must be within defined time windows. We consider mass production systems where numerous parts must be processed. The hoists then repeat the same sequence of movements indefinitely, forming a cycle, to ensure the handling of parts throughout the line. The problem that searches the cyclic sequence which minimizes the cycle period is known as the Cyclic Hoist Scheduling Problem (CHSP).In this work, we study the joint sizing and scheduling problems of multiple hoists in surface treatment facilities. This is a variant of CHSP, called Cyclic Hoist Design and Scheduling Problem (CHDSP). Our goal is to optimize both criteria cycle time and number of hoists. For this bi-objective problem, our contribution should ultimately lead to the development of a decision support system. To solve the CHDSP, we develop appropriate approximate methods, for which we first propose a new approach for coding solutions based on empty hoist moves. A genetic algorithm hybridized with a mixed integer linear program (MILP) is developed, which allows to validate this new encoding and to obtain interesting first results. We also develop a second hybrid metaheuristic based on variable neighborhood search and using the same MILP to optimize the search for the best solutions in a very large search space. We have conducted a series of tests to determine the best settings for the algorithm. The latter has been run on several instances of the literature for which it shows its performance and robustness. Finally, we extend the modeling of the CHDSP to consider the collisions avoidance constraints between hoists that share the same traffic rail. Tests carried out on benchmarks show the effectiveness of our complete model