LiveZilla Live Chat Software

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

Algorithmes évolutionnaires pour l'ordonnancement industriel : application à l'industrie automobile

Zinflou Arnaud. (2008). Algorithmes évolutionnaires pour l'ordonnancement industriel : application à l'industrie automobile. Thèse de doctorat, Université du Québec à Chicoutimi.

[img]
Prévisualisation
PDF
16MB

Résumé

Dans plusieurs secteurs d'activité comme l'aéronautique, l'informatique, les télécommunications, l'environnement, le transport et autres, les décideurs sont confrontés à des problèmes de complexité grandissante. Il peut s'agir d'optimiser le trajet d'un véhicule, de minimiser des coûts de production, de supporter la prise de décision, d'améliorer les performances d'un circuit électronique ou encore d'ordonnancer les processus dans un système informatique. Dans de nombreux cas, le problème à résoudre peut s'exprimer comme un problème d'optimisation combinatoire qui est rarement uni-objectif. En effet, la plupart des problèmes d'optimisation combinatoire rencontrés dans la pratique nécessitent l'optimisation simultanée de plusieurs objectifs souvent contradictoires. C'est par exemple le cas pour le problème d'ordonnancement de voitures. Toutefois, malgré l'intérêt indéniable d'aborder les problèmes industriels d'un point de vue multi-objectifs, plusieurs auteurs ont noté, en recensant la littérature, que les chercheurs s'attardaient principalement à des contextes théoriques de base. En contexte multi-objectifs, l'utilisation de métaheuristiques s'avère souvent d'une grande utilité.

Parmi les métaheuristiques, les algorithmes évolutionnaires, et plus particulièrement les algorithmes génétiques, se sont distingués comme étant des techniques bien adaptées à la résolution de problèmes multi-objectifs notamment à cause de leur faculté à exploiter de vastes espaces de recherche et à générer des compromis multiples en une seule étape d'optimisation. Les algorithmes génétiques tentent de simuler le processus de sélection naturelle dans un environnement hostile lié au problème à résoudre en s'inspirant des théories de l'évolution proposées par Darwin et des méthodes de combinaison de gènes introduites par Mendel.

Dans cette thèse, nous proposons des approches de résolution efficaces basées sur des algorithmes évolutionnaires permettant de supporter la prise de décision pour des problèmes d'ordonnancement industriel multi-objectifs comme le problème d'ordonnancement de voitures. En particulier, nous présentons dans un premier temps deux nouveaux opérateurs de croisement pour le problème théorique d'ordonnancement de voitures. Nous mettons ainsi en évidence l'importance d'utiliser des opérateurs génétiques dédiés à la problématique étudiée et ce, même lorsque l'emploi d'opérateurs naturels est possible. Une fois cette étape réalisée, nous proposons deux schémas de coopération entre algorithmes évolutionnaires et méthodes exactes pour résoudre le problème théorique d'ordonnancement de voitures. Par la suite, nous abordons la résolution du problème industriel d'ordonnancement de voitures en proposant un algorithme génétique efficace qui permet de résoudre le problème de manière îexicographique. Finalement, nous abordons la problématique industrielle d'ordonnancement de voitures d'un point de vue intégralement multi-objectifs en développant un algorithme Pareto générique qui hybride des concepts issus des algorithmes génétiques avec des concepts issus de la métaphore immune. C'est, à notre connaissance, le premier travail de recherche qui considère la problématique industrielle d'ordonnancement de voitures en traitant les objectifs simultanément sans leur attribuer d'ordre ou de poids. En plus d'avoir produit d'excellents résultats sur le problème industriel d'ordonnancement de voitures, l'approche proposée s'est aussi montrée particulièrement efficace sur un benchmark classique en optimisation multi-objectifs (le problème de sac à dos multi-objectifs). Ces résultats mettent en évidence l'intérêt pratique de ce genre d'approches en contexte industriel.

Type de document:Thèse ou mémoire de l'UQAC (Thèse de doctorat)
Date:2008
Lieu de publication:Chicoutimi
Programme d'étude:Doctorat en ingénierie
Nombre de pages:285
ISBN:9781412315272
Identifiant unique:10.1522/030084689
Sujets:Sciences naturelles et génie > Génie > Génie industriel
Département, module, service et unité de recherche:Départements et modules > Département des sciences appliquées > Programmes d'études de cycles supérieurs en ingénierie
Directeur(s), Co-directeur(s) et responsable(s):Gagné, Caroline
Mots-clés:Programmation évolutive, Ordonnancement (Gestion), Algorithmes génétiques, Automobiles--Industrie et commerce, Automobile industry and trade, Evolutionary programming (Computer science), Production scheduling, Genetic algorithms, ALGORITHME, EVOLUTIF, PRODUCTION, AUTOMOBILE, MULTIOBJECTIF, OPTIMISATION
Déposé le:01 janv. 2008 12:34
Dernière modification:20 sept. 2011 15:38
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