Calcul de produits cartésiens minimaux d'intervalles : application au problème d'ordonnancement d'atelier / Jianyang Zhou ; sous la direction d'Alain Colmerauer

Cette thèse n'a pas de quatrième de couverture

Bibliogr. p. 88-92

Thèse de doctorat informatique et mathématiques 1997 université Aix-Marseille II

La partie théorique de notre travail consiste à définir un modèle d'exécution pour résoudre les contraintes sur les entiers. (1) Nous donnons la syntaxe et la sémantique d'un ensemble de contraintes qui sont essentiellement des conjonctions de contraintes primitives avec d'éventuelles quantifications existentielles. (2) Nous décrivons les algorithmes de résolution et d'optimisation par un ensemble de règles de réécriture. Ces règles, notamment, réduisent et coupent en deux les intervalles de valeurs attribuées aux variables. (3) Enfin, nous étudions longuement la résolution de la contrainte primitive être n entiers tous distincts dont nous avons besoin pour résoudre 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 consacrée aux applications de notre langage de contraintes présenté dans la partie théorique. (1) Nous résolvons un ensemble de problèmes relativement simples qui sont des benchmarks classiques dans la littérature de programmation par contraintes. (2) Nous abordons le fameux problème d'ordonnancement d'atelier, étudié depuis de nombreuses années en raison de sa complexité (NP-difficile au sens fort). Nous présentons un schéma basé sur la permutation d'ordre des tâches, qui en niveau d'abstraction diffère de la méthode classique de Carlier et Pinson. En particulier, on précise les différences à la fois sur la façon de poser les contraintes (utilisation des contraintes de tri) et sur l'heuristique du choix des variables à instancier (coupure des intervalles d'ordre des tâches). En outre, nous étudions quelques techniques spéciales comme le bound trimming qui nous permettent de résoudre notamment deux exemples difficiles: la21 et la38. Les deux derniers étaient des problèmes ouverts dans un papier publié par Applegate et Cook