Abstract FR:

Nous proposons dans cette these des techniques de resolution de contraintes sur des structures ordonnees definies sur une collection d'objets que nous denomons sequences. Nous definissons sur la structure de sequences une axiomatique et proposons une approche fondee sur l'utilisation explicite des relations de groupe, de precedence et de diametre pour exprimer et raisonner d'une maniere intuitive sur les contraintes ensemblistes, potentielles et metriques definies sur des collections d'objets. Ces relations permettent d'exprimer des contraintes sur les sequences et sont traitees incrementalement par des techniques de consistance dans un langage de programmation en logique avec contraintes. Notre approche est fondee sur l'utilisation d'une structure algebrique canonique appelee arbre pqr pour la representation et la resolution des contraintes. Les principales proprietes de cette structure arborescente sont: (1) la reduction incrementale, (2) la forme canonique et, (3) le cout de reduction lineaire sur le fragment forme par les contraintes de definition, de groupe et potentielle. Nous validons notre travail en mettant en evidence l'interet de la structure de sequences pour la modelisation et la resolution des problemes lies au sequencement i. E. Principalement les problemes d'ordonnancement