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

Résumé

Plusieurs avenues existent dans la littérature pour la résolution des problèmes d'ordonnancement de la production. La complexité de ces problèmes rend nécessaire l'emploi de stratégies de recherche de solutions évoluées. Parmi celles-ci figurent leur modélisation sous la forme de problème de satisfaction de contraintes (CSP). Ce travail de recherche a pour but d'intégrer les formalismes des méthodes de résolution des CSP pour la résolution d'un problème d'ordonnancement de la production soit le problème de "carsequencing". Les travaux effectués s'inscrivent dans une optique d'exploration des algorithmes de résolution de CSP et de leur application aux problèmes d'ordonnancement de la production.

Dans un premier temps, les algorithmes de résolution de CSP existants sont étudiés et une comparaison entre ceux-ci est effectuée afin de déceler les avantages et les inconvénients de chacune des différentes méthodes de résolution suggérées dans la littérature. Entre autres, les algorithmes basés sur un principe de retour en arrière lors des situations d'inconsistance tels le BackTracking et le BackJumping sont étudiés. De plus, l'ajout d'heuristiques guidant la recherche de solutions ainsi que les méthodes d'apprentissage lors de la recherche sont exposées dans ce mémoire. Les algorithmes de diminution de domaines développés dans la littérature tels le Forward-Checking et les algorithmes de propagation de contraintes (AC) sont décrits et leurs implications sur la recherche sont quantifiées. Finalement, quelques méthodes de parallélisation de la recherche sont définies dans le cadre du présent travail de recherche.

Suite à l'énumération des méthodes de résolution développées et à leur comparaison, ce travail de recherche couvre le développement d'un algorithme de résolution de CSP appliqué au problème de "car-sequencing". Premièrement, une étude de ce problème ainsi que des formulations possibles pour celui-ci est effectuée. Par la suite, le graphe de contraintes associé au problème de "car-sequencing" est défini et une stratégie de résolution du problème est décrite. Plus particulièrement, une méthode de diminution de l'espace de recherche de solutions possibles induit par les contraintes de ce problème est définie. L'algorithme de Forward-Checking est alors utilisé pour la résolution de ce problème particulier. De plus, une étude sur l'utilisation d'heuristiques guidant la recherche de solutions est effectuée. Finalement, une méthode de subdivision du problème initial en sous-problèmes indépendants a été développée afin de favoriser la diversification de la recherche de solutions lors d'une résolution concurrente.

Les instances de problèmes suggérées dans la librairie de problèmes CSPLib sont utilisées comme base d'évaluation des méthodes développées. Les résultats obtenus dans le cadre de ce projet de recherche ont été comparés aux meilleurs résultats obtenus dans la littérature sur ces instances de problème. De plus, les résultats ont été comparés avec un outil de résolution commercial soit ILOG Solver 6.O.

Les méthodes développées ont obtenu des résultats intéressants. En effet, pour un premier groupe de 70 instances du problème de "car-sequencing", le Forward-Checking développé a permis de surpasser les résultats obtenus par le solveur commercial ILOG Solver 6.O. Par contre, sur un deuxième groupe de problèmes, certaines bonifications des méthodes développées s'avèrent nécessaires. La diminution de l'espace de recherche représente une voie à explorer dans des recherches futures pour ainsi favoriser la résolution d'instances de problèmes non-satisfiables.