LiveZilla Live Chat Software

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

Approches hybrides pour la résolution d'un problème d'ordonnancement industriel

Sioud Aymen. (2011). Approches hybrides pour la résolution d'un problème d'ordonnancement industriel. Thèse de doctorat, Université du Québec à Chicoutimi.

[img]
Prévisualisation
PDF
6MB

Résumé

Dans plusieurs secteurs d'activités industrielles comme la sidérurgie, la métallurgie, la pétrochimie, la papeterie, l'aéronautique, l'industrie de la céramique ou celle de l'automobile, le système de production contient toujours une machine dite goulot d'étranglement {bottleneck) et c'est par cette machine que passe la majorité, voire la totalité, des travaux dans plusieurs des cas. La gestion de cette machine est cruciale pour l'entreprise, car elle est responsable des retards dans la livraison des commandes aux clients. L'ordonnancement des travaux sur cette machine représente une manière d'aborder le problème et de traiter l'ensemble du système de production. De même, c'est à partir du traitement de cette machine qu'il est possible de s'étendre vers des configurations de systèmes de production plus complexes qui sont rencontrées de plus en plus de nos jours. D'un autre côté, plusieurs études ont démontré que plusieurs des travaux en usine, voire la totalité, possèdent des temps de réglages dépendants de la séquence. Les décideurs doivent donc organiser et planifier l'ordonnancement des travaux sur ladite machine en cherchant à minimiser les temps improductifs tout en respectant les différents délais. De plus, ces problèmes étant NP-difficiles, plusieurs travaux dans la littérature les abordent à l'aide de méthodes approchées, telles les métaheuristiques ou à l'aide de méthodes hybrides intégrant des méthodes exactes. Cette thèse s'inscrit dans cette direction de recherche.

Nous proposons dans cette thèse plusieurs approches de résolution efficaces pour le problème d'une machine unique (machine-goulot) avec temps de réglages dépendants de la séquence dans le but de minimiser le retard total. Dans un premier temps, nous présentons un algorithme génétique doté d'un nouvel opérateur de croisement qui se veut plus performant que les opérateurs de croisement classique de la littérature. Cela met ainsi en évidence l'importance d'adapter les divers opérateurs génétiques au problème traité. Toutefois, les résultats obtenus démontrent que l'algorithme génétique n'atteint pas encore la performance de certaines approches de résolution contenues dans la littérature. Effectivement, nous avons pu remarquer qu'il manquait un processus d'intensification performant au sein de l'algorithme proposé. Pour remédier à cette lacune, nous explorons une classe de méthodes de résolution qui a montré des avenues très prometteuses au cours de la dernière décennie. En effet, les algorithmes hybrides ont permis d'obtenir des résultats très intéressants dans une grande variété de problèmes. Plusieurs recherches ont introduit l'hybridation de métaheuristiques avec des méthodes exactes. En effet, ce genre d'hybridation peut devenir une alternative très intéressante car, les deux méthodes ont des particularités bien différentes qui peuvent être associées pour produire de meilleurs résultats. C'est ainsi que nous explorons la conception d'algorithmes génétiques hybrides améliorant le processus d'intensification de l'algorithme proposé en intégrant une méthode exacte et des mécanismes appartenant à d'autres méthodes de résolution afin d'en améliorer la performance. Parmi toutes les approches répertoriées dans la littérature pour résoudre des problèmes d'ordonnancement, peu d'approches hybridant des métaheuristiques et la programmation par contraintes sont retrouvées.

Dans une deuxième étape, nous proposons une modélisation et une résolution du problème traité avec l'ordonnancement basé sur les contraintes, qui est une branche de la programmation par contraintes dédiée aux problèmes d'ordonnancement. Nous utilisons pour cela la plateforme commerciale ILOG CP par l'intermédiaire d'API C++ dédiées. Nous démontrons que le choix de l'algorithme de résolution, de la procédure de parcours de l'arbre de recherche et de l'heuristique de choix du travail à ordonnancer ont tous un impact majeur sur la performance de cette approche de résolution. Les résultats obtenus, avec des temps de calculs prohibitifs, sont généralement très loin des meilleures solutions connues. Cependant, nous avons constaté des performances intéressantes pour cette méthode sur de petites instances, ce qui permet d'envisager son hybridation avec d'autres méthodes de résolution.

Ainsi, dans une troisième étape, nous introduisons un schéma d'hybridation collaboratif intégrant la méthode d'ordonnancement basé sur les contraintes dans un algorithme génétique, et ce au niveau d'un croisement et d'une procédure d'intensification en utilisant les caractéristiques du problème traité. Finalement, nous proposons un algorithme hybride intégratif qui utilise des concepts de la programmation par contraintes, de la résolution multi-objectifs et de l'optimisation par colonies de fourmis au niveau d'un opérateur de croisement dans un algorithme génétique.

Les algorithmes hybrides proposés démontrent une excellente performance sur des problèmes tests de la littérature en améliorant plusieurs des meilleurs résultats connus pour certains d'entre eux.

Type de document:Thèse ou mémoire de l'UQAC (Thèse de doctorat)
Date:2011
Lieu de publication:Chicoutimi
Programme d'étude:Doctorat en ingénierie
Nombre de pages:222
ISBN:9781412317368
Identifiant unique:10.1522/030188922
Sujets:Sciences naturelles et génie > Génie > Génie industriel
Sciences naturelles et génie > Sciences mathématiques > Mathématiques appliquées
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):Gravel, Marc
Gagné, Caroline
Mots-clés:MACHINE-GOULOT, ORDONNANCEMENT, HYBRIDE, ALGORITHME
Déposé le:30 janv. 2012 11:52
Dernière modification:30 janv. 2012 16:52
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