Normal view MARC view ISBD view

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

Auteur principal : Zhou, Jianyang, AuteurAuteur secondaire : Colmerauer, Alain, 1941-, Directeur de thèseAuteur secondaire collectivité : Université d'Aix-Marseille II, 1969-2011, Etablissement de soutenanceType de document : ThèseLangue : français ; anglais.Pays : France.Éditeur : [S.l.] : [s.n.], 1997Description : 1 vol. (92 p.) ; 30 cmBibliographie : Bibliogr. p. 88-92.Sujet MSC : 68R05, Computer science -- Discrete mathematics in relation to computer science, Combinatorics
68Q25, Computer science -- Theory of computing, Analysis of algorithms and problem complexity
68M20, Computer science -- Computer system organization, Performance evaluation; queueing; scheduling
Note de thèse: Thèse de doctorat, informatique et mathématiques, 1997, université Aix-Marseille II
Tags from this library: No tags from this library for this title. Log in to add tags.
Current location Call number Status Date due Barcode
CMI
Salle S
Thèses ZHO (Browse shelf) Available 00210-01

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

There are no comments for this item.

Log in to your account to post a comment.