Deterministic, stochastic and multi-criteria models for balancing assembly lines
Modèles déterministe, stochastique et multicritère pour l'équilibrage de lignes d'assemblage
Résumé
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
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
| Origine | Fichiers produits par l'(les) auteur(s) |
|---|
Loading...