Metaheuristiques hybrides pour la resolution du probleme d'ordonnancement de voitures dans une chaine d'assemblage automobile.

摘要

La litterature scientifique propose une grande variete de strategies pour la resolution des problemes d'optimisation combinatoire (POC). Ces problemes sont d'une grande complexite et demandent des methodes evoluees pour les resoudre. Les algorithmes exacts, comme la programmation lineaire en nombres entiers (PLNE) a l'aide de l'algorithme Branch and Bound (B&B), arrivent a trouver une solution optimale pour certaines instances de problemes. Par contre, plus la taille du probleme a resoudre est grande, plus ces algorithmes ont de la difficulte a en venir a bout. Les metaheuristiques representent alors une alternative interessante pour trouver une solution de qualite acceptable dans des delais tres courts. Toutefois, il est impossible de garantir qu'une metaheuristique trouvera la solution optimale d'un probleme. Parmi ces methodes, on retrouve l'optimisation par colonies de fourmis (OCF), qui a su faire ses preuves pendant les dernieres annees pour la resolution de differents problemes d'optimisation combinatoire. Une autre avenue consiste a creer des algorithmes hybrides. L'objectif principal de ce memoire est de proposer trois algorithmes hybridant un OCF et la PLNE pour resoudre le probleme d'ordonnancement de voitures ( POV).;Le premier algorithme hybride propose consiste a creer un sous-probleme a partir de la meilleure solution de chaque cycle de l'OCF et de resoudre ce sous-probleme avec le B&B. Cette methode ne s'est pas averee tres performante, car aucune intensification n'est effectuee sur une solution. Le second algorithme tente de combler cette lacune en appelant le B&B de maniere repetitive a un intervalle regulier de cycles de l'OCF. Cet appel repete du B&B represente, en fait, une recherche locale exacte (RLE). Pour l'ensemble des problemes utilises pour tester cette hybridation, des resultats de qualite legerement superieure ou egale a l'OCF, integrant une recherche locale, ont ete obtenus pour environ deux problemes sur trois. On peut en dire autant de la troisieme hybridation proposee, qui consiste, dans un premier temps, a executer l'OCF et a fournir la meilleure solution trouvee comme solution de depart a la RLE.;Les objectifs fixes dans cette recherche ont ete atteints en concevant des methodes de resolution hybrides, adaptees au POV, combinant une metaheuristique et une methode exacte. On avait aussi pour but d'etablir la performance des methodes hybrides face a leurs contreparties singulieres. En regle generale, les hybridations parviennent a donner des resultats de qualite equivalente a celle des resultats de l'OCF avec recherche locale mais avec un cout en temps d'execution. Il s'agit tout de meme d'une conclusion rejouissante puisque des ameliorations pourraient etre apportees a ces algorithmes pour les rendre encore plus performants. On a aussi explore quelques facons de creer des sous-problemes plus faciles a resoudre par un algorithme exact. Ceci ouvre donc une porte a une autre approche de la resolution de POC.;Le POV est un POC qui consiste a determiner dans quel ordre placer un ensemble de voitures a produire sur une chaine d'assemblage en se soumettant a un ensemble de contraintes. On cherche parfois la sequence minimisant le nombre de conflits, ou un conflit represente une surcharge de travail occasionnee a un poste particulier de l'atelier de montage par l'arrivee successive de plusieurs voitures similaires, ou encore minimisant le nombre de changements de couleurs a l'atelier de peinture. Pour simplifier le probleme, on ne s'attardera qu'aux contraintes liees a l'atelier de montage ou sont installees les differentes options des voitures. Cette version theorique du POV que l'on retrouve dans la litterature est une simplification du probleme industriel. Differentes methodes ont ete proposees pour solutionner ce probleme. Celles qui attirent notre attention sont l' OCF et la PLNE. On cherchera, dans ce memoire, a concevoir des approches hybrides exploitant les forces de ces deux approches. Il sera egalement possible de comparer la performance des algorithmes hybrides avec les resultats obtenus avec l'OCF pour etablir l'apport de telles hybridations.