Abstract FR:

La programmation par contraintes est un outil puisant qui permet de resoudre de facon assez naturelle des problemes complexes. En effet, l'idee de ce type de programmation est de decrire les proprietes que doivent remplir les solutions aux moyens d'un systeme de contraintes plutot que les mecanismes qui menent a ces solutions. Toutefois, afin de maintenir des performances acceptables, les langages de cette categorie reposent sur des algorithmes de resolution qui ne peuvent fournir que des solutions approchees (p. Ex. Exprimees au moyen d'intervalles). Ainsi, l'obtention de solutions exactes necessite soit des systemes de contraintes plus complexes soit l'emploi de contraintes specifiques. Pour ce travail de recherche, nous nous sommes interesses a un probleme d'ordonnancement difficile, le probleme du job-shop, pour lequel nous avons essaye de concevoir une approche programmation par contraintes. Cette etude nous a conduit a l'elaboration de deux nouveaux concepts, les ensembles-index et les patrons de contraintes, qui permettent la production automatique de contraintes en cours de resolution. Ce document comprend deux parties. Dans un premier temps nous etudions les mecanismes de resolution usuels employes pour traiter les problemes discrets. L'accent est mis sur les particularites et les limitations de ces algorithmes. Les ensembles-index associes aux patrons de contraintes sont ensuite presentes comme un moyen de lever les restrictions precedemment soulignees. Les algorithmes requis sont alors presentes puis vient une description detaillee du prototype que nous avons realise. La seconde partie presente l'application de notre systeme au probleme d'ordonnancement a contraintes disjonctives (ou job-shop). Apres un tour d'horizon des diverses techniques de resolution classiques, nous exposons notre methode qui exploite les mecanismes developpes auparavant. Bien qu'essentiellement constitue d'un systeme de contraintes et d'une strategie d'enumeration, notre algorithme offre des performances comparables voire meme superieures a des implantations dediees qui utilisent pourtant des methodologies sensiblement plus sophistiquees