Un Modele De Resolution De Contraintes Adapte Aux Problemes D Ordonnancement Un Prototype Et Une Application

Principles and Practice of Constraint Programming - CP98

Constraints have emerged as the basis of a representational and computational paradigm that draws from many disciplines and can be brought to bear on many problem domains. This volume contains papers dealing with all aspects of c- puting with constraints. In particular, there are several papers on applications of constraints, re?ecting the practical usefulness of constraint programming. The papers were presented at the 1998 International Conference on Principles and Practice of Constraint Programming (CP’98), held in Pisa, Italy, 26{30 - tober, 1998. It is the fourth in this series of conferences, following conferences in Cassis (France), Cambridge (USA), and Schloss Hagenberg (Austria). We received 115 high quality submissions. In addition, 7 abstracts submissions were not followed by a full paper, hence were not counted as submissions. The program committee selected 29 high quality papers after thorough refereeing by at least 3 experts and further discussion by committee members. We thank the referees and the program committee for the time and e ort spent in reviewing the papers. The program committee invited three speakers: { Joxan Ja ar { Peter Jeavons { Patrick Prosser Their papers are in this volume.

Un modele de resolution de contraintes adapte aux problemes d'ordonnancement : un prototype et une application

Un modèle de résolution de contraintes adapté aux problèmes d'ordonnancement

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