Skip to Main content Skip to Navigation
Conference papers

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
Complete list of metadatas

Cited literature [25 references]  Display  Hide  Download

https://hal.inria.fr/inria-00085777
Contributor : Laurent Henocque <>
Submitted on : Friday, July 14, 2006 - 9:51:04 AM
Last modification on : Tuesday, January 14, 2020 - 10:38:05 AM
Document(s) archivé(s) le : Tuesday, April 6, 2010 - 12:08:14 AM

File

Identifiers

  • 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. ⟨inria-00085777⟩

Share

Metrics

Record views

307

Files downloads

2249