Abstract FR:

Dans cette étude, nous nous intéressons à la résolution des "Problèmes de Satisfaction de Contraintes valués" (CSP valués). Cette modélisation extrèmement simple, intuitive et riche s'adapte facilement à une grande variété de problèmes d'optimisation. De nombreux travaux ont par ailleurs fourni toute une bibliothèque d'algorithmes de résolution. Dans le cadre classique de la satisfaction des CSP, l'efficacité de ces méthodes n'est plus à démontrer et leur domaine d'application est assez bien connu. L'introduction d'une valuation des contraintes dans le modèle CSP, qui donne naissance aux CSP valués, est cependant trop récente pour que les possibilités et les limites d'efficacité soient clairement identifiées. L'ordonnancement des satellites d'observation de la Terre fait partie des CSP valués à la frontière des compétences actuelles en matière d'optimisation. Cette application est pour nous un prétexte au développement d'outils de résolution nouveaux étendant le champ des CSP valués accessibles. Notre travail est centré sur la notion de "contrainte induite", largement utilisée dans le cadre classique, et dont l'extension difficile aux CSP valués limite actuellement l'amélioration des algorithmes de recherche complets. Afin de dépasser ces difficultés, directement liées à la non-idempotence de l'agrégation des valuations des contraintes, nous proposons un formalisme minimal pour les contraintes induites. Nous montrons ensuite comment il peut être mis en oeuvre pour étendre l'essentiel des algotithmes développés dans le cadre classqiue. Enfin, l'utilité de ces nouveaux outils est illustré sur les problèmes d'ordonnancement du satellite SPOT 5.