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.
Type de document :
Communication dans un congrès
Troisièmes Journées Francophones de Programmationpar Contraintes (JFPC07), Jun 2007, INRIA, Domaine de Voluceau, Rocquencourt, Yvelines France, 2007, JFPC07
Liste complète des métadonnées

https://hal.inria.fr/inria-00151226
Contributeur : Sylvain Soliman <>
Soumis le : vendredi 1 juin 2007 - 18:26:41
Dernière modification le : vendredi 1 juin 2007 - 21:41:38
Document(s) archivé(s) le : vendredi 21 septembre 2012 - 16:05:43

Fichier

37.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00151226, version 1

Collections

Citation

Jean-Noël Monette, Yves Deville, Pierre Dupont. Un propagateur basé sur les positions pour le problème d'Open-Shop. Troisièmes Journées Francophones de Programmationpar Contraintes (JFPC07), Jun 2007, INRIA, Domaine de Voluceau, Rocquencourt, Yvelines France, 2007, JFPC07. 〈inria-00151226〉

Partager

Métriques

Consultations de la notice

83

Téléchargements de fichiers

63