Abstract FR:

La partie theorique de notre travail consiste a definir un modele d'execution pour resoudre les contraintes sur les entiers. (1) nous donnons la syntaxe et la semantique d'un ensemble de contraintes qui sont essentiellement des conjonctions de contraintes primitives avec d'eventuelles quantifications existentielles. (2) nous decrivons les algorithmes de resolution et d'optimisation par un ensemble de regles de reecriture. Ces regles, notamment, reduisent et coupent en deux les intervalles de valeurs attribuees aux variables. (3) enfin, nous etudions longuement la resolution de la contrainte primitive etre n entiers tous distincts dont nous avons besoin pour resoudre d'autres contraintes, comme la contrainte de tri qui dit qu'un n-uplet d'entiers est obtenu par tri d'un autre n-uplet d'entiers. La partie pratique de notre travail est consacree aux applications de notre langage de contraintes presente dans la partie theorique. (1) nous resolvons un ensemble de problemes relativement simples qui sont des benchmarks classiques dans la litterature de programmation par contraintes. (2) nous abordons le fameux probleme d'ordonnancement d'atelier, etudie depuis de nombreuses annees en raison de sa complexite (np-difficile au sens fort). Nous presentons un schema base sur la permutation d'ordre des taches, qui en niveau d'abstraction differe de la methode classique de carlier et pinson. En particulier, on precise les differences a la fois sur la facon de poser les contraintes (utilisation des contraintes de tri) et sur l'heuristique du choix des variables a instancier (coupure des intervalles d'ordre des taches). En outre, nous etudions quelques techniques speciales comme le bound trimming qui nous permettent de resoudre notamment deux exemples difficiles: la21 et la38. Les deux derniers etaient des problemes ouverts dans un papier publie par applegate et cook