Un cadre général intégrant les techniques d'ordonnancement sous incertitudes Julien Bidot ILOG L'élaboration et la mise en œuvre d'un ordonnancement dans un contexte industriel doivent souvent prendre en compte le caractère non déterministe de l'environnement d'exécution pour pouvoir assurer une certaine performance. Pour cela, il est important de produire et de maintenir un ordonnancement avec une qualité satisfaisante tout en respectant des contraintes sur le temps de recherche et sur la mémoire. La littérature scientifique en planification de tâches (AI planning) et en ordonnancement sous incertitudes est riche mais structurée de façon incomplète. Nous proposons donc une nouvelle classification des techniques utilisées pour construire des ordonnancements sous incertitudes qui permet de comparer toutes les approches et les systèmes de planification et d'ordonnancement en fonction de la manière dont sont prises les décisions : elles prennent en compte l'incertitude (proaction) ou non ; elles sont en cause (révision) ou non ; elles sont prises au fur et à mesure sur un horizon glissant plus ou moins long (progression). Nous présentons aussi un modèle d'élaboration et d'exécution d'ordonnancements basé sur notre classification. Il s'agit d'un automate qui se développe au fur et à mesure de l'exécution. Les états de cet automate sont des ordonnancements flexibles, plus ou moins complets et représentés sous forme de réseaux de contraintes. On passe d'un état à un autre de cet automate lorsque des contraintes sont violées ou lorsque certaines conditions sont vérifiées ; par exemple, on doit sélectionner et ordonnancer un nouveau groupe d'opérations pour anticiper l'exécution. Les approches proactives, progressives et de révision sont intégrées dans cet automate. Enfin, nous proposons une instanciation de notre modèle de génération et d'exécution en utilisant les composants ILOG Solver et Scheduler. Il s'agit de résoudre un problème d'ordonnancement d'atelier à cheminements multiples. Un modèle probabiliste du problème est utilisée et une approche de révision est proposée pour sa résolution. Des techniques de propagation de contraintes permettent une résolution efficace du problème à chaque fois que l'on réordonnance en ligne. Des résultats expérimentaux montrent l'intérêt d'utiliser une telle approche en termes de qualité.