You are here

Un propagateur basé sur les positions pour le problème d'Open-Shop

TitleUn propagateur basé sur les positions pour le problème d'Open-Shop
Publication TypeConference Paper
Year of Publication2007
AuthorsMonette, Jean-Noël, Deville Yves, and Dupont Pierre
Conference NameJournées Francophones de Programmation par Contraintes (JFPC'07)
Abstract

L'Open-Shop est un problème difficile qui peut être résolu par des méthodes de Programmation par Contraintes ou de Recherche Opérationnelle. Les techniques existantes réduisent efficacement l'arbre de recherche mais elles prennent rarement en compte l'ordre d'exécution des tâches. Dans ce travail, nous développons un nouveau propagateur pour le problème d?ordonnancement sans interruption sur une machine, la contrainte de base de l'Open-Shop. Ce propagateur prend l'ordre des tâches en compte ce qui permet dans de nombreux cas de réduire la taille de l'arbre de recherche. Sa complexité temporelle pour une machine est de O(N^2 log N), où N est le nombre de tâches sur la machine. Les expériences menées sur le problème d'Open-Shop montrent que le nouveau propagateur permet de détecter de nouvelles valeurs inconsistantes lorsqu'il est ajouté aux techniques de l'état de l'art.