Une méthode exacte pour le problème d'ordonnancement d'atelier avec temps de préparation

Résumé : Nous présentons une nouvelle méthode exacte pour résoudre le problème d'ordonnancement d'atelier avec temps de préparation dépendant de la séquence. Pour résoudre ce problème NP-difficile au sens fort, nous proposons une méthode de recherche arborescente où, à chaque noeud, des techniques de propagation de contraintes temporelles et de ressources sont appliquées et la relaxation du problème à un ensemble de problèmes de voyageurs de commerce avec fenêtres de temps est résolue par programmation dynamique. Testée sur les problèmes proposés par Brucker et Thiele [10], la méthode améliore significativement les meilleures bornes inférieures et supérieures connues sur la plupart des instances auparavant non résolues
Type de document :
Communication dans un congrès
Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Nîmes - Ecole des Mines d'Alès / France, 2006
Liste complète des métadonnées

Littérature citée [25 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00085777
Contributeur : Laurent Henocque <>
Soumis le : vendredi 14 juillet 2006 - 09:51:04
Dernière modification le : lundi 19 mars 2018 - 22:38:02
Document(s) archivé(s) le : mardi 6 avril 2010 - 00:08:14

Fichier

Identifiants

  • HAL Id : inria-00085777, version 1

Collections

Citation

Christian Artigues, Dominique Feillet. Une méthode exacte pour le problème d'ordonnancement d'atelier avec temps de préparation. Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Nîmes - Ecole des Mines d'Alès / France, 2006. 〈inria-00085777〉

Partager

Métriques

Consultations de la notice

257

Téléchargements de fichiers

1943