Un propagateur basé sur les positions pour le problème d'Open-Shop
Résumé
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 $\mathcal{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.
Domaines
Langage de programmation [cs.PL]
Origine : Fichiers produits par l'(les) auteur(s)