Dans nos travaux, nous travaillons sur le problème de l’équilibrage de la ligne d’assemblage (ALBP). C’est un problème d’optimisation combinatoire qui permet de définir la répartition des opérations et leur affectation aux stations qui constituent la ligne d’assemblage tout en respectant différentes contraintes de façon à optimiser un critère d’efficacité donné. Deux types de problèmes sont définis d’après l’objectif à minimiser. Le problème de type I (SALBP-1) minimise le nombre de stations sous un temps de cycle donné. Et le problème de type II (SALBP-2) minimise le temps de cycle déterminé par le temps de station le plus grand avec un nombre donné de stations. Nous considérons dans nos travaux uniquement des problèmes de type II. Nous proposons d’abord une méthode pour déterminer la borne inférieure du temps de cycle qui assure de respecter le nombre donné de stations. Cette méthode combine la relaxation lagrangienne et la génération de colonnes. La relaxation lagrangienne est utilisée pour relaxer les contraintes de précédence. Le problème lagrangien de la relaxation lagrangienne est résolu par la génération de colonnes. Ensuite, nous proposons un heuristique pour résoudre les problèmes SALBP-2. L’heuristique proposé se compose de deux phases. Dans la première phase, une solution initiale est produite par un heuristique basé sur un poids correspondant à la position des opérations et d'un certain seuil défini selon les poids pour chaque station. La solution est ensuite améliorée par un procédé de transfert et d’échange dans la deuxième phase. Enfin, les méta-heuristiques sont utilisés pour résoudre le problème déterministe ainsi que le problème stochastique. Ainsi deux méthodes basées sur la génération sont utilisées : l’algorithme de electromagnetism-like mechanism (EM) et l’estimation de distribution (ED). Les résultats de simulation sont comparés avec ceux du recuit simulé (SA). De part sa meilleure performance, EM est choisi pour équilibrer les lignes stochastiques qui considèrent les temps des opérationsomme aléatoires. Dans ce cas, les temps de cycle sont minimisés de façon à assurer que la fiabilité de la ligne est supérieure à une valeur donnée. EM est aussi utilisé pour résoudre les problèmes de type multi-objectif avec minimisation du temps de cycle et maximisation de la fiabilité de la ligne en déterminant un ensemble de solutions Pareto-optimales / Our work considers the problem of balancing the assembly line (ALBP). This is a combinatorial optimization problem which consists in assigning operations to stations of the assembly line while respecting various constraints in order to optimize a criterion of efficiency. Two types of problems are defined, based on the objective to minimize. The type I problem (SALBP-1) minimizes the number of stations in a given cycle time. And the problem of type II (SALBP-2) minimizes the cycle time given by the largest time station with a given number of stations. Problems of type II are only considered in our work. Firstly, a method for determining the lower bound of the cycle time which respects the number of stations is determined. This method combines the Lagrangian relaxation and the columns generation method. The Lagrangian relaxation is used to relax the constraints of precedence. The problem of the Lagrangian relaxation is given by the columns generation. Then, a new heuristic is proposed for solving the SALBP-2 problem. This heuristic consists of two steps. In the first step, an initial solution is produced by an heuristic based on a weight corresponding to the position of operations and a threshold defined for each station. The, in the second step, the solution is improved by a process of transfer and exchange. Finally, meta-heuristics are used to solve deterministic and stochastic problems.Two main meta-heuristics are considered: the electromagnetism-like mechanism algorithm (EM) and the estimated distribution (ED). The performance of our method is confirmed via simulation and it is compared with simulated annealing (SA). Due to its better performance, EM was chosen to balance the stochastic lines with random operation times. In this case, the cycle time is minimized under constraint of the reliability of the line which must be greater than a given value. EM is also used to solve multi-objective problems such as minimizing the cycle time and maximizing the reliability of the line by determining a set of Pareto-optimal solutions

Actuellement, les fabricants sont soumis à une pression économique importante et à une concurrence internationale accrue due à la globalisation des marchés. Pour réussir, les fabricants doivent être capables de répondre rapidement aux changements de la demande en adaptant leurs systèmes de production. Cette adaptation aux changements peut être réalisée à travers multiples reconfigurations du système de production.Les travaux présentés dans ce mémoire portent sur l'élaboration des méthodes de recherche opérationnelle permettant d'accompagner le décideur lors de la reconfiguration d'une ligne de transfert ou d'assemblage. Ce problème apparaît lorsqu'un nouveau produit doit être fabriqué par une ligne existante ou lorsqu'il y a eu des changements dans les caractéristiques du produit. Par conséquent, il devient nécessaire de modifier la configuration du système de production tout en minimisant les coûts induits. Ces coûts sont évalués différemment pour les systèmes automatisésou manuels. Dans le premier cas, qui correspond au cas des lignes de transfert, pour limiter les investissements, il est souhaitable de réutiliser au maximum les équipements existants à condition que les contraintes techniques et technologiques soient respectées. Dans le cas des lignes manuelles qui sont représentées dans notre étude par les lignes d'assemblage, l'objectif est de minimiser les coûts liés à l'apprentissage des opérateurs causés par la réaffectation de leurs tâches.Les méthodes de résolution exactes basées sur la modélisation mathématique et la programmation linéaire en nombre mixtes ainsi qu'une méthode de type goal programming sont développées dans ce travail pour argumenter la prise de décisions lors de la reconfiguration des lignes de production. Les méthodes proposées ont été testées avec succès sur des échantillons de problèmes proches des cas industriels et ont montré leur efficacité. / Global competition causes fluctuations in product demand and requires more frequent modifications of product characteristics. As a consequence, the production systems have to be frequently adapted to new production requirements.This work develops new combinatorial optimization methods for supporting decision makers at the reconfiguration stage considered for transfer and assembly lines. If new products have to be manufactured at the line or existing products are modified, then the line has to be reconfigured in order to meet new production requirements. In highly automated lines, as the transfer lines, the reconfiguration problem is focused on the readjustment of the equipment. To reduce the investment costs, the decision makers aim to reuse the available equipment as much as possible. The existence of compatibility constraints between new operations to be performed and existing facilities makes the reconfiguration problem hard and combinatorial.In manual assembly lines also studied in this thesis, the reconfiguration problem mostly concerns the reassignment of tasks to workers ant the minimization of the cost of retraining operators.The developed methods are based on the mathematical modelling and mixed integer programming, a goal programming approach is designed as well. These methods were successfully tested on a dataset of problem instances close to real industrial problems. The obtained results show the effectiveness and the efficiency of the solution methods proposed.

Si le problème d'équilibrage lors de la conception de lignes d'assemblage est largement étudié dans la littérature sous le nom d’ALBP (Assembly Line Balancing Problems), peu de travaux concernent leur rééquilibrage dans un horizon court terme et en-ligne. Les travaux présentés dans ce mémoire portent donc sur le rééquilibrage dynamique des lignes d’assemblage en réaction aux événements court terme perturbants la production. L’objectif étant de changer l’allocation des taches sur les postes de travail afin de lisser la charge induite par la perturbation. Le délai court sans arrêt de production étant plus important que l'optimalité de la solution, le temps de résolution rapide des méthodes de résolution approchées nous a intéressé. Deux approches ont été étudiées pour leur simplicité et leur nouveauté dans le domaine du ALBP : la méthode ILS (Iterated Local Search) et la recherche d’atteignabilité sur un réseau d’automates communicants. Cela nous a montré qu'elles peuvent répondre au besoin de réactivité imposé par notre problème mais qu’elles sont difficilement adaptables lorsque les leviers d’action pour rééquilibrer la ligne sont modifiés. Notre proposition pour répondre à ce besoin d’adaptabilité est une méthodologie de modélisation et de résolution des problèmes de rééquilibrage des lignes d’assemblage s’appuyant sur un réseau d’automates communicants et une recherche d’atteignabilité sur celui-ci. Pour assurer la généricité, la méthodologie est décomposée en deux niveaux d’abstraction : l'étude de la classe du problème ALBP considéré et al résolution du problème spécifique. Les travaux ont été validés sur des exemples industriels issus de la société Trane. / Assembly lines are flow-oriented production systems. They are still typical in industrial production systems despite the evolution from mass-production to more personalized and fluctuating production. In order to meet customer demand (quantity, time, etc.) and to reduce manufacturing costs, the lines must be well balanced. In other words, the products need to move from one workstation to another with the same pace, usually called takt time. This assembly line design problem is widely studied in the literature under the name of ALBP (Assembly Line Balancing Problems). Nonetheless, few studies concern the on-line reconfiguration and in particular, the dynamic rebalancing. The work presented in this thesis focuses on the dynamic rebalancing of assembly lines in response to short-term events disturbing production. Two approaches have been studied for their simplicity, speed of implementation and innovation in the field of ALBP: the ILS approach (Iterated Local Search) and the reachability analysis approach based on a network of communicating automata. This study showed that both approaches can address the need for a quick resolution required by dynamic rebalancing problem but lacked for adaptation when model constraints or objectives are changed. A methodological approach for assembly line balancing problems modeling and resolution is proposed to bridge the gap of adaptability. To ensure the genericity of obtained models., the methodology is composed of two levels of abstraction: a study of the class of the considered problem and a focus on the specific problem to solve. Studies have been validated on industrial examples from Trane factories.

Une vue d'ensemble des problèmes et des méthodes pour la conception des lignesd'assemblage et d'usinage est donnée. Un nouveau problème d'affectation de la main-d’œuvrepour une ligne d'assemblage multi-produit cadencée avec un objectif de minimiser lenombre d'opérateurs est étudié. Diverses relations de priorité entre les opérations et lesdifférentes fonctions définissant les temps d'opérations, en fonction du nombre d'opérateurssont considérés. Un nouveau problème d'optimisation multiobjectif pour une ligne d'usinagemono-produit est formulé. Plusieurs méthodes exactes et heuristiques et leursimplémentations informatiques pour les deux problèmes sont développées par l'auteur. Unmodule logiciel d'aide à la décision pour résoudre ces problèmes est développé et implémentédans un environnement d'un nouveau PLM d'IBM dans le cadre du projet européen amePLM.Ce module est testé sur un exemple réel de conception d'une ligne de montage des moteurschez Mercedes Benz en Allemagne. / An overview of existing problems and methods for the design of assembly and transfer lines is given. A new workforce assignment problem for a paced multi-product assembly line with a goal of minimizing the number of workers is studied. Various precedence relations between operations and functions of operation processing times dependent on the number of workers areconsidered. A new problem of multi-objective optimization for a single product transfer line is solved. Several exact and heuristic methods and their computer implementations for both problems are developed by the author. An application of developed approaches to solving a real production problem relevant to the European project amePLM is demonstrated.

No description available.