|<
<< Page précédente
1
Page suivante >>
>|
5
10
15
20
25
30
35
40
documents par page
Tri :
Date
Editeur
Auteur
Titre
Ecole Nationale Supérieure de l'Aéronautique et de l'Espace
/ 12-06-1997
Dago Pierre
Voir le résumé
Voir le résumé
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 œuvre pour étendre l'essentiel des algorithmes développés dans le cadre classique. Enfin, l'utilité de ces nouveaux outils est illustré sur les problèmes d'ordonnancement du satellite SPOT 5.
|
Texte intégral
|<
<< Page précédente
1
Page suivante >>
>|
5
10
15
20
25
30
35
40
documents par page