Gomes Monteiro Stefan Manuel. (2010). Mode de construction à rebours dans un algorithme d'optimisation par colonie de fourmis pour la minimisation du retard total. Mémoire de maîtrise, Université du Québec à Chicoutimi.
Prévisualisation |
PDF
2MB |
Résumé
Le problème de machine unique avec temps de réglage dépendants de la séquence est un problème d'ordonnancement industriel où il y a une machine qui peut exécuter différentes tâches. Le changement de tâches à exécuter entraîne un réglage de la machine comme c'est le cas pour les industries de transformation de papier ou les industries pharmaceutiques. De plus, le temps pour réaliser ce réglage dépend de la tâche courante et de la tâche suivante. Le but du problème d'ordonnancement à l'étude est de déterminer l'ordre des tâches de façon à minimiser le retard total.
Ce problème est de nature NP - difficile et sa résolution passe par l'utilisation des métaheuristiques. Plusieurs métaheuristiques ont été proposées dans la littérature comme les algorithmes d'optimisation par colonie de fourmis (OCF), plus précisément les ACS. Ce mémoire propose un nouveau mode de construction de solutions pour l'ACS pour le problème de machine unique avec temps de réglage dépendants de la séquence pour la minimisation du retard total. En effet, compte tenu de la nature de l'objectif à optimiser, nous privilégions un mode de construction de solution à rebours. Pour amorcer une construction à rebours de la séquence, un nouveau concept de visibilité est proposé, avec l'utilisation d'une marge arrière qui permet de favoriser le placement des tâches en retard à la fin de la séquence. Cette nouvelle visibilité a été intégrée à une version ACS existant dans la littérature et a été nommée ACS à rebours. Des modifications ont été apportées à l'ACS à rebours pour améliorer son efficacité. La première modification a pour objectif de rendre l'ACS à rebours plus intelligent au niveau du choix des paramètres associés à la règle de transition et de rendre ainsi son utilisation plus facile. La seconde modification consiste à utiliser une règle de priorité au moment où les tâches restantes à placer ne sont plus en retard pour tenter d'accélérer la construction d'une solution.
Des expérimentations numériques ont été réalisées pour comparer la performance de l'ACS à rebours avec celle de l'un des ACS présentés dans la littérature pour le problème à l'étude. Pour les instances de problème de petite taille, la performance de l'ACS à rebours est semblable à celle de l'ACS classique. Ceci nous porte à croire que l'idée de base ouvre une voie intéressante pour le développement des travaux futurs avec les ACS qui utilisent un mode de construction à rebours de la séquence. Pour les instances de problème de grande taille, un avantage doit être accordé à l'ACS classique, ce qui atteste que des améliorations peuvent être apportées à l'ACS à rebours surtout au niveau de la diversification des solutions produites.
Ce travail de recherche représente une première exploitation du concept de construction de solutions à rebours de la séquence pour les ACS. Le présent mémoire est une contribution non seulement à une meilleure connaissance des ACS, mais aussi à la connaissance de nouveaux modes de construction pour les ACS.
Type de document: | Thèse ou mémoire de l'UQAC (Mémoire de maîtrise) |
---|---|
Date: | 2010 |
Lieu de publication: | Chicoutimi |
Programme d'étude: | Maîtrise en informatique |
Nombre de pages: | 94 |
ISBN: | 9781412316620 |
Identifiant unique: | 10.1522/030145839 |
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 Gagné, Caroline |
Mots-clés: | Ordonnancement (Informatique), Computer scheduling, Algorithmes de colonies de fourmis, Ant algorithms |
Déposé le: | 01 janv. 2010 12:34 |
---|---|
Dernière modification: | 17 déc. 2012 21:00 |
Éditer le document (administrateurs uniquement)