Cette thèse traite des lignes de traitement de surface qui sont des lignes dans lesquelles les pièces sont immergées dans une succession de cuves. Chaque cuve contient des bains qui affectent les propriétés mécaniques ou électriques des pièces. Ce type de ligne est utilisé, par exemple, pour la galvanoplastie. Les pièces sont montées sur des porteurs et transportées d'une cuve à l'autre par un robot. Le temps opératoire (ou temps pendant lequel la pièce reste dans la cuve) est borné. La borne inférieure est le temps minimum qui permet le traitement et la borne supérieure dépend du type de traitement (attaque acide, rinçage...).<br />Un objectif classique est de trouver les mouvements du robot qui maximisent la productivité, ce problème est communément appelé “hoist scheduling problem” (HSP). Lors de ce travail nous nous sommes attachés à une production cyclique. Nous avons proposé dans le cas d'une ligne à deux cuves une méthode permettant d'obtenir les cycles optimaux. Nous avons démontré, pour le cas d'une ligne équilibrée à trois cuves pour une production mono-produit, les caractéristiques des cycles optimaux ainsi qu'une méthode pour les obtenir. Ensuite, nous avons étudié le problème sur quatre machines dans le cas où les temps de trempe sont égaux et sans attente. Nous avons proposé les cycles optimaux dans le cas d'une production mono-produit. Enfin nous avons proposé une conjecture sur les cycles optimaux et en avons démontré certaines parties, dans le cas d'une ligne équilibrée avec un nombre de cuves quelconque et où les marges sur les temps de process sont nulles.

Dans cette thèse, nous nous intéressons principalement à l'étude du fonctionnement cyclique mono-produit des ateliers de traitement de surface. Notre contribution porte sur le problème d'ordonnancement associé connu dans la littérature sous le nom Cyclic Hoist Scheduling Problem (CHSP). L'objet de cette thèse est de proposer des méthodes efficaces pour la résolution des problèmes de traitement de surface dans le cas où les produits à traiter sont du même type. Nous traitons en particulier le cas où le nombre des robots présents sur la ligne est égal à deux, ce qui augmente le nombre des contraintes du problème, sachant que dans le cas mono robot, ce problème a été prouvé NP-Complet. Pour cela, nous proposons une méthode qui combine deux heuristiques et un programme linéaire mixte. Cette méthode permet notamment d'affecter les mouvements de transport à l'un des deux robots tout en gérant les risques de collision entre eux, lorsque la gamme opératoire des produits à traiter suit l'implantation des cuves.Par la suite, nous proposons une extension du modèle au cas de lignes complexes. Enfin, nous étudions le cas d'un fonctionnement mixte, pour lequel il est nécessaire de traiter dans une même installation des produits différents et des rafales de produits identiques. Dans ces conditions, la solution la plus intéressante pour les industriels est de pouvoir alterner des modes de production dynamiques et cycliques. Pour cela, nous proposons une méthode efficace permettant de résoudre le problème d'ordonnancement associé à la phase transitoire relative à ce type de fonctionnement. Elle consiste en particulier à chercher les dates d'entrée au plus tôt des produits. La principale difficulté identifiée consiste ici à passer du mode dynamique au mode cyclique, c'est-à-dire à rejoindre un cycle à partir d'une solution courante donnée, en supposant que ce cycle est connu à priori. Les méthodes élaborées dans les divers cas traités sont validées par des tests sur des benchmarks de la littérature.

Cette thèse s’intéresse au fonctionnement cyclique multi-produits des ateliers de traitement de surface, et au problème d’ordonnancement associé (HSP), caractérisé par des contraintes fortes et atypiques, dont certaines sont liées aux ressources de transport. Dans le cas de productions en grandes séries, une commande cyclique de ces systèmes est particulièrement adaptée, permettant notamment de réduire la combinatoire de résolution, et sous réserve que les ratios de produits soient connus à l’avance. Notre objectif est de trouver le meilleur ordonnancement des tâches de traitement et de transport en un temps raisonnable. Pour cela, nous proposons une première approche, basée sur un modèle linéaire et une méthode de résolution arborescente de type séparation et évaluation. Nous présentons des modélisations pour différentes extensions du problème dit de base et nous fournissons des exemples illustratifs et des résultats sur des benchmarks. Par la suite et compte tenu de l’analyse de la littérature relative aux ordonnancements cycliques mono-produit et multi-produits, nous proposons tout d’abord une heuristique dédiée au cas multi-produits étudié, et basée sur un algorithme de liste. Avec ce dernier, nous obtenons un ordonnancement cyclique dont le degré du cycle n’est pas fixé au préalable. Enfin, nous présentons une deuxième modélisation approchée sous la forme d’un algorithme génétique pour résoudre un HSP 2-cyclique. Ces différents modèles sont validés par des tests sur des benchmarks de la littérature pour lesquels nous avons obtenus des résultats prometteurs. Nous terminons par une analyse critique des avantages et inconvénients des modèles élaborés et par quelques propositions de perspectives pour ce travail. / In this thesis, we study the Cyclic Hoist Scheduling Problem (CHSP) in automated electroplating lines, when a mass production must be achieved. The CHSP is characterized by specific constraints related to processing and transport resources. To solve it in a multi-parts context, we first elaborate a 2-degree cyclic model and an associated branch and bound algorithm. Then we extend it to more complex configurations. Then, we develop a dedicated heuristic to find a feasible repetitive sequence of hoist moves that minimizes the cycle time, without a priori fixing the cycle degree. Comparisons with existing algorithms are presented to show the efficiency of the proposed heuristic. To reduce the cycle time, we integrate in the general heuristic an algorithm with a set of Minimum Part Set (MPS) configurations’. This one allows us to find the best order in which jobs should be introduced into the line. Finally, we describe a genetic algorithm approach to find a schedule which can reach the optimal 2-cycle. We finally discuss the interest of those various models, based on the promising results obtained and we provide some perspectives which could be explored.

Dans cette thèse, nous nous intéressons principalement à l’étude du fonctionnement cyclique mono-produit des ateliers de traitement de surface. Notre contribution porte sur le problème d’ordonnancement associé connu dans la littérature sous le nom Cyclic Hoist Scheduling Problem (CHSP). L’objet de cette thèse est de proposer des méthodes efficaces pour la résolution des problèmes de traitement de surface dans le cas où les produits à traiter sont du même type. Nous traitons en particulier le cas où le nombre des robots présents sur la ligne est égal à deux, ce qui augmente le nombre des contraintes du problème, sachant que dans le cas mono robot, ce problème a été prouvé NP-Complet. Pour cela, nous proposons une méthode qui combine deux heuristiques et un programme linéaire mixte. Cette méthode permet notamment d’affecter les mouvements de transport à l’un des deux robots tout en gérant les risques de collision entre eux, lorsque la gamme opératoire des produits à traiter suit l’implantation des cuves.Par la suite, nous proposons une extension du modèle au cas de lignes complexes. Enfin, nous étudions le cas d’un fonctionnement mixte, pour lequel il est nécessaire de traiter dans une même installation des produits différents et des rafales de produits identiques. Dans ces conditions, la solution la plus intéressante pour les industriels est de pouvoir alterner des modes de production dynamiques et cycliques. Pour cela, nous proposons une méthode efficace permettant de résoudre le problème d’ordonnancement associé à la phase transitoire relative à ce type de fonctionnement. Elle consiste en particulier à chercher les dates d’entrée au plus tôt des produits. La principale difficulté identifiée consiste ici à passer du mode dynamique au mode cyclique, c’est-à-dire à rejoindre un cycle à partir d’une solution courante donnée, en supposant que ce cycle est connu à priori. Les méthodes élaborées dans les divers cas traités sont validées par des tests sur des benchmarks de la littérature. / In this thesis, our interest is focused on the Cyclic Hoist Scheduling Problem (CHSP) in automated electroplating lines. The aim of this study is to propose an algorithm to solve the two-hoists cyclic scheduling problem. This one consists in finding a repetitive sequence of hoists’ moves, while avoiding collision between the hoists which share a common track. The objective is to minimize the period of this repetitive cycle for single part-type production. This problem was proved to be NP-complete for lines with a single hoist. The fact that two hoists are available on the line increases the number of constraints of the problem. Then we propose a solving method combining two heuristics and a Mixed Integer Linear Program. It enables us to solve both assignment and sequencing problems, while considering spatial constraints related to hoist’moves.Subsequently, we propose an extension of the model which is adapted to complex lines. Finally, our interest is focused on solving a HSP for which it is necessary to treat in the same facility a batch of various products and a batch of identical products. Under these conditions, the most interesting solution for manufacturers is to be able to alternate the production of two batches. For this goal, we propose an efficient method to solve the scheduling problem associated. Finally, our proposed methods are validated by experimentations based on benchmarks from the literature.

Les ateliers de traitement de surface automatisés, qui utilisent des robots de manutention commandés par ordinateur pour le transport de la pièce, ont été largement mis en place dans différents types d'entreprises industrielles, en raison de ses nombreux avantages par rapport à un mode de production manuel, tels que : une plus grande productivité, une meilleure qualité des produits, et l’impact sur les rythmes de travail. Notre recherche porte sur trois types de problèmes d'ordonnancement associés à ces systèmes, appelés Hoist Scheduling Problems, caractérisés par des contraintes de fenêtres de temps de traitement: (I) un problème à une seule ressource de transport où l’objectif est de minimiser le temps de cycle; (II) un problème bi-objectif avec une seule ressource de transport où il faut minimiser le temps de cycle et la consommation de ressources de traitement (et par conséquent le coût de production); et (III) un problème d'ordonnancement cyclique mono-objectif mais multi-robots.En raison de la NP-complétude des problèmes étudiés et de nombreux avantages de les outils de type quantum-inspired evolutionary algorithm (QEA), nous proposons d'abord un QEA hybride comprenant un mécanisme de décodage amélioré et une procédure réparation dédiée pour trouver le meilleur temps de cycle pour le premier problème. Après cela, afin d'améliorer à la fois la performance économique et environnementale qui constituent deux des trois piliers de la stratégie de développement durable de nos jours déployée dans de nombreuses industries, nous formulons un modèle mathématique bi-objectif pour le deuxième problème en utilisant la méthode de l'intervalle interdit. Ensuite, nous proposons un QEA bi-objectif couplé avec une procédure de recherche locale pour minimiser simultanément le temps de cycle et les coûts de production, en générant un ensemble de solutions Pareto-optimales pour ce problème. Quant au troisième problème, nous constatons que la plupart des approches utilisées dans les recherches actuelles, telles que la programmation entière mixte (MIP), peuvent conduire à l’obtention d’une solution non optimale en raison de la prise en compte courante d’une hypothèse limitant l’exploration de l’espace de recherche et relative aux mouvements en charge des robots. Par conséquent, nous proposons une approche de MIP améliorée qui peut garantir l'optimalité des solutions obtenues pour ce problème, en relaxant l'hypothèse mentionnée ci-dessus.Pour chaque problème, une étude expérimentale a été menée sur des cas industriels ainsi que sur des instances générées aléatoirement. Les résultats obtenus montrent que l’efficacité des algorithmes d'ordonnancement proposés, ce qui justifie les choix que nous avons faits. / Automated treatment surface facilities, which employ computer-controlled hoists for part transportation, have been extensively established in various kinds of industrial companies, because of its numerous advantages over manual system, such as higher productivity, better product quality, and reduced labor intensity. Our research investigates three typical hoist scheduling problems with processing time windows in treatment surface facilities, which are: (I) cyclic single-hoist scheduling problem to minimize the cycle time; (II) cyclic single-hoist scheduling problem to minimize the cycle time and processing resource consumption (and consequently production cost); and (III) cyclic multi-hoist scheduling problem to minimize the cycle time.Due to the NP-completeness of the studied problems and numerous advantages of quantum-inspired evolutionary algorithm (QEA), we first propose a hybrid QEA with improved decoding mechanism and repairing procedure to find the best cycle time for the first problem. After that, to enhance with both the economic and environmental performance, which constitute two of the three pillars of the sustainable strategy nowadays deployed in many industries, we formulate a bi-objective mathematical model for the second problem by using the method of prohibited interval. Then we propose a bi-objective QEA with local search procedure to simultaneously minimize the cycle time and production cost, and we find a set of Pareto-optimal solutions for this problem. As for the third problem, we find that most existing approaches, such as mixed integer programming (MIP) approach, may identify a non-optimal solution to be an optimal one due to an assumption related to the loaded hoist moves which is made in many existing researches. Consequently, we propose an improved MIP approach for this problem by relaxing the above-mentioned assumption. Our approach can guarantee the optimality of its obtained solutions.For each problem, experimental study on industrial instances and random instances has been conducted. Computational results demonstrate that the proposed scheduling algorithms are effective and justify the choices we made.