Abstract FR:

L'approche csp (constraint satisfaction problems) proposee par l'intelligence artificielle offre un cadre de representation general et rigoureux, permettant de formuler simplement de nombreux types de problemes combinatoires, et une palette de techniques de resolution de ces problemes. En particulier, on peut etablir que la modelisation de problemes de raisonnement temporel symbolique avec les algebres d'instants ou d'intervalles est formellement une approche de type csp et que les graphes non-conjonctifs utilises pour la resolution de problemes d'ordonnancement sont des csp. Une comparaison entre regles d'analyse sous contraintes et methodes de filtrage des csp permet non seulement d'interpreter les premieres en termes de consistance locale, mais aussi de decouvrir de nouvelles regles. Cependant, le cadre formel fourni par les csp est encore trop restrictif: en particulier, il interdit la prise en compte des caracteristiques flexibles ou incertaines de certains problemes ou une formulation sous forme de contraintes parait interessante. C'est pourquoi nous avons defini un nouveau formalisme qui generalise l'approche csp, tant au niveau theorique qu'algorithmique. Etant fonde sur la theorie des ensembles flous et la theorie des possibilites, le modele fcsp (fuzzy contraint satisfaction problems) autorise le traitement de contraintes souples ou a priorite, de contraintes incertaines ainsi que la prise en compte de parametres non-controlables. Ce modele a ensuite ete specialise aux problemes d'ordonnancement de production de type job-shop. Il permet de representer des dates de disponibilite, d'echeance et des durees d'operations flexibles ou imprecises. Les regles classiques d'analyse sous contraintes, les procedures de propagation de date et de construction incrementale d'ordonnancement ont facilement ete etendues a ce nouveau formalisme. Les outils de resolution issus de ce travail ont ete experimentes: il apparait que la prise en compte de la flexibilite d'un probleme de job-shop n'augmente pas le temps moyen de resolution, et peut dans certains cas le diminuer