Résumé: L’approche par contraintes est de plus en plus appliquée pour la modélisation et la résolution des problèmes d’ordonnancement de la vie réels. Cet enthousiasme est dû essentiellement à l’efficacité et l’efficience des algorithmes utilisés pour propager les contraintes de ressources. Alors que les algorithmes de filtrage utilisés dans le cas disjonctif sont de faible complexité (entre O(n) et O(nlog n)), la complexité des algorithmes analogues dans le cas cumulatif sont encore de l’ordre O(n3) en moyenne. Cette différence est due au fait que dans le cas cumulatif, plusieurs tâches ou activités peuvent s’exécuter en parallèle tant que la capacité de la ressource n’est pas violée. Dans ce contexte, l’un des défis consiste alors à réduire la complexité de ces différents algorithmes tout en augmentant leur pouvoir de filtrage. Après une brève introduction à la programmation par contraintes et à l’ordonnancement, nous présenterons et illustrerons les règles utilisées pour propager les contraintes de ressource en ordonnancement disjonctif et cumulatif. On s’intéressera particulièrement à l’edge-finder, au not-first/not-last et au raisonnement énergétique.
http://www2.ift.ulaval.ca/~quimper/Seminaires/