A New Exact Solution Algorithm for the Job Shop Problem with Sequence-Dependent Setup Times

Abstract : We propose a new solution approach for the Job Shop Problem with Sequence Dependent Setup Times (SDST-JSP). The problem consists in scheduling jobs, each job being a set of elementary operations to be processed on different machines. The objective pursued is to minimize the completion time of the set of operations. We investigate a relaxation of the problem related to the traveling salesman problem with time windows (TSPTW). Our approach is based on a Branch and Bound procedure, including constraint propagation and using this relaxation. It compares favorably over the best available approaches from the literature on a set of benchmark instances.
Type de document :
Chapitre d'ouvrage
Régin, Jean-Charles; Rueher, Michel. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Springer Berlin / Heidelberg, pp. 37-49, 2004, Lecture Notes in Computer Science, 978-3-540-21836-4. 〈10.1007/978-3-540-24664-0_3〉
Liste complète des métadonnées

https://hal-emse.ccsd.cnrs.fr/emse-00712628
Contributeur : Florent Breuil <>
Soumis le : mercredi 27 juin 2012 - 15:20:13
Dernière modification le : mercredi 28 février 2018 - 10:22:50

Lien texte intégral

Identifiants

Citation

Christian Artigues, Sana Belmokhtar, Dominique Feillet. A New Exact Solution Algorithm for the Job Shop Problem with Sequence-Dependent Setup Times. Régin, Jean-Charles; Rueher, Michel. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Springer Berlin / Heidelberg, pp. 37-49, 2004, Lecture Notes in Computer Science, 978-3-540-21836-4. 〈10.1007/978-3-540-24664-0_3〉. 〈emse-00712628〉

Partager

Métriques

Consultations de la notice

111