Hal will be stopped for maintenance from friday on june 10 at 4pm until monday june 13 at 9am. More information
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 metadata

Cited literature [25 references]  Display  Hide  Download

https://hal.inria.fr/inria-00085777
Contributor : Laurent Henocque Connect in order to contact the contributor
Submitted on : Friday, July 14, 2006 - 9:51:04 AM
Last modification on : Monday, July 20, 2020 - 12:34:51 PM
Long-term archiving on: : 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

127

Files downloads

1500