Mode de construction à rebours dans un algorithme d'optimisation par colonie de fourmis pour la minimisation du retard total /

Le probleme de machine unique avec temps de reglage dependants de la sequence est un probleme d'ordonnancement industriel ou il y a une machine qui peut executer differentes tâches. Le changement de tâches a executer entraine un reglage de la machine comme c'est le cas pour les industries de transformation de papier ou les industries pharmaceutiques. De plus, le temps pour realiser ce reglage depend de la tâche courante et de la tâche suivante. Le but du probleme d'ordonnancement a l'etude est de determiner l'ordre des tâches de facon a minimiser le retard total. Ce probleme est de nature NP - difficile et sa resolution passe par l'utilisation des metaheuristiques. Plusieurs metaheuristiques ont ete proposees dans la litterature comme les algorithmes d'optimisation par colonie de fourmis (OCF), plus precisement les ACS. Ce memoire propose un nouveau mode de construction de solutions pour l'ACS pour le probleme de machine unique avec temps de reglage dependants de la sequence pour la minimisation du retard total. En effet, compte tenu de la nature de l'objectif a optimiser, nous privilegions un mode de construction de solution a rebours. Pour amorcer une construction a rebours de la sequence, un nouveau concept de visibilite est propose, avec l'utilisation d'une marge arriere qui permet de favoriser le placement des tâches en retard a la fin de la sequence. Cette nouvelle visibilite a ete integree a une version ACS existant dans la litterature et a ete nommee ACS a rebours. Des modifications ont ete apportees a l'ACS a rebours pour ameliorer son efficacite. La premiere modification a pour objectif de rendre l'ACS a rebours plus intelligent au niveau du choix des parametres associes a la regle de transition et de rendre ainsi son utilisation plus facile. La seconde modification consiste a utiliser une regle de priorite au moment ou les tâches restantes a placer ne sont plus en retard pour tenter d'accelerer la construction d'une solution. Des experimentations numeriques ont ete realisees pour comparer la performance de l'ACS a rebours avec celle de l'un des ACS presentes dans la litterature pour le probleme a l'etude. Pour les instances de probleme de petite taille, la performance de l'ACS a rebours est semblable a celle de l'ACS classique. Ceci nous porte a croire que l'idee de base ouvre une voie interessante pour le developpement des travaux futurs avec les ACS qui utilisent un mode de construction a rebours de la sequence. Pour les instances de probleme de grande taille, un avantage doit etre accorde a l'ACS classique, ce qui atteste que des ameliorations peuvent etre apportees a l'ACS a rebours surtout au niveau de la diversification des solutions produites. Ce travail de recherche represente une premiere exploitation du concept de construction de solutions a rebours de la sequence pour les ACS. Le present memoire est une contribution non seulement a une meilleure connaissance des ACS, mais aussi a la connaissance de nouveaux modes de construction pour les ACS.