LiveZilla Live Chat Software

Constellation, le dépôt institutionnel de l'Université du Québec à Chicoutimi

Métaheuristiques hybrides pour la résolution du problème d'ordonnancement de voitures dans une chaîne d'assemblage automobile

Noël Sébastien. (2007). Métaheuristiques hybrides pour la résolution du problème d'ordonnancement de voitures dans une chaîne d'assemblage automobile. Mémoire de maîtrise, Université du Québec à Chicoutimi.

[img]
Prévisualisation
PDF
4MB

Résumé

La littérature scientifique propose une grande variété de stratégies pour la résolution des problèmes d'optimisation combinatoire (POC). Ces problèmes sont d'une grande complexité et demandent des méthodes évoluées pour les résoudre. Les algorithmes exacts, comme la programmation linéaire en nombres entiers (PLNE) à l'aide de l'algorithme Branch and Bound (B&B), arrivent à trouver une solution optimale pour certaines instances de problèmes. Par contre, plus la taille du problème à résoudre est grande, plus ces algorithmes ont de la difficulté à en venir à bout. Les métaheuristiques représentent alors une alternative intéressante pour trouver une solution de qualité acceptable dans des délais très courts. Toutefois, il est impossible de garantir qu'une métaheuristique trouvera la solution optimale d'un problème. Parmi ces méthodes, on retrouve l'optimisation par colonies de fourmis (OCF), qui a su faire ses preuves pendant les dernières années pour la résolution de différents problèmes d'optimisation combinatoire. Une autre avenue consiste à créer des algorithmes hybrides. L'objectif principal de ce mémoire est de proposer trois algorithmes hybridant un OCF et la PLNE pour résoudre le problème d'ordonnancement de voitures (POV).

Le POV est un POC qui consiste à déterminer dans quel ordre placer un ensemble de voitures à produire sur une chaîne d'assemblage en se soumettant à un ensemble de contraintes. On cherche parfois la séquence minimisant le nombre de conflits, où un conflit représente une surcharge de travail occasionnée à un poste particulier de l'atelier de montage par l'arrivée successive de plusieurs voitures similaires, ou encore minimisant le nombre de changements de couleurs à l'atelier de peinture. Pour simplifier le problème, on ne s'attardera qu'aux contraintes liées à l'atelier de montage où sont installées les différentes options des voitures. Cette version théorique du i*0F que l'on retrouve dans la littérature est une simplification du problème industriel. Différentes méthodes ont été proposées pour solutionner ce problème. Celles qui attirent notre attention sont Y OCF et la PLNE. On cherchera, dans ce mémoire, à concevoir des approches hybrides exploitant les forces de ces deux approches. Il sera également possible de comparer la performance des algorithmes hybrides avec les résultats obtenus avec Y OCF pour établir l'apport de telles hybridations.

Le premier algorithme hybride proposé consiste à créer un sous-problème à partir de la meilleure solution de chaque cycle de l'OCF et de résoudre ce sous-problème avec le B&B. Cette méthode ne s'est pas avérée très performante, car aucune intensification n'est effectuée sur une solution. Le second algorithme tente de combler cette lacune en appelant le B&B de manière répétitive à un intervalle régulier de cycles de Y OCF. Cet appel répété du B&B représente, en fait, une recherche locale exacte (RLE). Pour l'ensemble des problèmes utilisés pour tester cette hybridation, des résultats de qualité légèrement supérieure ou égale à l'OCF, intégrant une recherche locale, ont été obtenus pour environ deux problèmes sur trois. On peut en dire autant de la troisième hybridation proposée, qui consiste, dans un premier temps, à exécuter YOCF et à fournir la meilleure solution trouvée comme solution de départ à la RLE.

Les objectifs fixés dans cette recherche ont été atteints en concevant des méthodes de résolution hybrides, adaptées au POV, combinant une métaheuristique et une méthode exacte. On avait aussi pour but d'établir la performance des méthodes hybrides face à leurs contreparties singulières. En règle générale, les hybridations parviennent à donner des résultats de qualité équivalente à celle des résultats de YOCF avec recherche locale mais avec un coût en temps d'exécution. Il s'agit tout de même d'une conclusion réjouissante puisque des améliorations pourraient être apportées à ces algorithmes pour les rendre encore plus performants. On a aussi exploré quelques façons de créer des sous-problèmes plus faciles à résoudre par un algorithme exact. Ceci ouvre donc une porte à une autre approche de la résolution de POC,

Type de document:Thèse ou mémoire de l'UQAC (Mémoire de maîtrise)
Date:2007
Lieu de publication:Chicoutimi
Programme d'étude:Maîtrise en informatique
Nombre de pages:115
ISBN:9781412314558
Identifiant unique:10.1522/030008563
Sujets:Sciences naturelles et génie > Sciences mathématiques > Informatique
Département, module, service et unité de recherche:Départements et modules > Département d'informatique et de mathématique > Programmes d'études de cycles supérieurs en informatique
Directeur(s), Co-directeur(s) et responsable(s):Gravel, Marc
Mots-clés:Métaheuristiques, THESE, METAHEURISTIQUE, ORDONNANCEMENT, CHAINE, PRODUCTION, ASSEMBLAGE, AUTOMOBILE, VOITURE, OPTIMISATION, COMBINATOIRE, ALGORITHME
Déposé le:01 janv. 2007 12:34
Dernière modification:20 sept. 2011 15:36
Afficher les statistiques de telechargements

Éditer le document (administrateurs uniquement)

Creative Commons LicenseSauf indication contraire, les documents archivés dans Constellation sont rendus disponibles selon les termes de la licence Creative Commons "Paternité, pas d'utilisation commerciale, pas de modification" 2.5 Canada.

Bibliothèque Paul-Émile-Boulet, UQAC
555, boulevard de l'Université
Chicoutimi (Québec)  CANADA G7H 2B1
418 545-5011, poste 5630