LiveZilla Live Chat Software

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

Résolution d'un problème de satisfaction de contraintes pour l'ordonnancement d'une chaîne d'assemblage automobile

Boivin Simon. (2005). Résolution d'un problème de satisfaction de contraintes pour l'ordonnancement d'une chaîne d'assemblage automobile. Mémoire de maîtrise, Université du Québec à Chicoutimi..

[img]
Prévisualisation
PDF
3MB

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.

Type de document:Thèse ou mémoire de l'UQAC (Mémoire de maîtrise)
Date:2005
Lieu de publication:Montréal
Programme d'étude:Maîtrise en informatique
Nombre de pages:118
ISBN:1412312329
Identifiant unique:10.1522/24050106
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
Mots-clés:Résolution de problème--Modèles mathématiques, Travail à la chaîne, Automobiles--Industrie et commerce, Problem solving--Mathematical models, Assembly-line methods, Automobile industry and trade, THESE, CHAINE, ASSEMBLAGE, MONTAGE, AUTOMOBILE, ORDONNANCEMENT, PROBLEME, SATISFACTION, CONTRAINTE, PRODUCTION, METHODE, RESOLUTION, CSP, MODELISATION, ALGORITHME, INFORMATIQUE
Déposé le:01 janv. 2005 12:34
Dernière modification:20 sept. 2011 15:32
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