A New Exact Solution Algorithm for the Job Shop Problem with Sequence-Dependent Setup Times - Mines Saint-Étienne Access content directly
Book Sections Year : 2004

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.

Dates and versions

emse-00712628 , version 1 (27-06-2012)

Identifiers

Cite

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⟩
114 View
0 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More