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.
Document type :
Book sections
Complete list of metadatas

https://hal-emse.ccsd.cnrs.fr/emse-00712628
Contributor : Florent Breuil <>
Submitted on : Wednesday, June 27, 2012 - 3:20:13 PM
Last modification on : Monday, April 29, 2019 - 5:03:21 PM

Links full text

Identifiers

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⟩

Share

Metrics

Record views

145