Relaxation lagrangienne pour le problème de conception de lignes de désassemblage sous incertitudes

International audienceLe problème de conception des lignes de désassemblage orientée profit est traité sous incertitudes des durées opératoires des tâches de désassemblage. Les cas de désassemblage partiel et présence de composants polluants des produits en fin de vie sont pris en compte. Dans la littérature, peu de travaux ont étudié le problème de conception de lignes de désassemblage sous incertitudes. Les approches de résolution adoptées dans ces derniers sont essentiellement des heuristiques ou métaheuristiques sans information quant à la qualité des solutions obtenues. De plus, les relations de précédence entre les opérations de désassemblage sont modélisées avec un graphe de précédence simple. Le but de ce présent travail et de concevoir une ligne de désassemblage, sous incertitudes, maximisant le profit généré par les parties récupérées des produits en fin de vie. Un graphe AND/OR est utilisé pour la modélisation de toutes les alternatives possibles de désassemblage d'un produit ainsi que les relations de précédence à la fois entre les tâches et les parties générées pendant le processus de désassemblage. Les tâches de la meilleure alternative de désassemblage sont à affecter à une séquence ordonnée de postes de travail, à déterminer, sous contraintes de précédence et temps de cycle où les espérances des temps des postes sont considérées. Les durées opératoires sont prises comme des variables aléatoires avec des lois de probabilité connues. Le profit de la ligne à concevoir est la différence entre les revenus des parties du produit réutilisées et les coûts opératoires de la ligne. Un programme stochastique binaire est développé pour la modélisation du problème défini et une approche exacte de résolution, basée sur la relaxation lagrangienne et l'algorithme du sous- gradient, est proposée. La Relaxation lagrangienne associée à l'algorithme du sous-gradient a permis la résolution efficace de problèmes de grandes tailles. Dans le cas de sous-optimalité d'une solution, son écart de l'optimum est déterminé