Resolution d'un probleme de satisfaction de contraintes pour l'ordonnancement d'une chaine d'assemblage automobile.

摘要

Plusieurs avenues existent dans la litterature pour la resolution des problemes d'ordonnancement de la production. La complexite de ces problemes rend necessaire l'emploi de strategies de recherche de solutions evoluees. Parmi celles-ci figurent leur modelisation sous la forme de probleme de satisfaction de contraintes (CSP). Ce travail de recherche a pour but d'integrer les formalismes des methodes de resolution des CSP pour la resolution d'un probleme d'ordonnancement de la production soit le probleme de "carsequencing". Les travaux effectues s'inscrivent dans une optique d'exploration des algorithmes de resolution de CSP et de leur application aux problemes d'ordonnancement de la production.; Dans un premier temps, les algorithmes de resolution de CSP existants sont etudies et une comparaison entre ceux-ci est effectuee afin de deceler les avantages et les inconvenients de chacune des differentes methodes de resolution suggerees dans la litterature. Entre autres, les algorithmes bases sur un principe de retour en arriere lors des situations d'inconsistance tels le BackTracking et le BackJumping sont etudies. De plus, l'ajout d'heuristiques guidant la recherche de solutions ainsi que les methodes d'apprentissage lors de la recherche sont exposees dans ce memoire. Les algorithmes de diminution de domaines developpes dans la litterature tels le Forward-Checking et les algorithmes de propagation de contraintes (AC) sont decrits et leurs implications sur la recherche sont quantifiees. Finalement, quelques methodes de parallelisation de la recherche sont definies dans le cadre du present travail de recherche. (Abstract shortened by UMI.)