Un propagateur basé sur les positions pour le problème d'Open-Shop
(2007) Journées Francophones de Programmation par Contraintes (JFPC′07) — Location: Rocquencourt, France, (4.June.2006)
Files
jfpc07_openshop.pdf
Open Access - Adobe PDF
- 178.33 KB
Details
- Authors
- 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 logN), o`u 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´e aux techniques de l’état de l’art.
- Affiliations
Citations
Monette, J.-N., Deville, Y., & Dupont, P. (2007). Un propagateur basé sur les positions pour le problème d’Open-Shop. Journées Francophones de Programmation par Contraintes (JFPC′07), Rocquencourt, France,. https://hdl.handle.net/2078.5/226067