TY - JOUR
T1 - Job shop scheduling with setup times, deadlines and precedence constraints
AU - Balas, Egon
AU - Simonetti, Neil
AU - Vazacopoulos, Alkis
PY - 2008/8
Y1 - 2008/8
N2 - In the last 15 years several procedures have been developed that can find solutions of acceptable quality in reasonable computing time to Job Shop Scheduling problems in environments that do not involve sequence-dependent setup times of the machines. The presence of the latter, however, changes the picture dramatically. In this paper we adapt one of the best known heuristics, the Shifting Bottleneck Procedure, to the case when sequence dependent setup times play an important role. This is done by treating the single machine scheduling problems that arise in the process as Traveling Salesman Problems with time windows, and solving the latter by an efficient dynamic programming algorithm. The model treated here also incorporates precedence constraints, release times and deadlines. Computational experience on a vast array of instances, mainly from the semiconductor industry, shows our procedure to advance substantially the state of the art.
AB - In the last 15 years several procedures have been developed that can find solutions of acceptable quality in reasonable computing time to Job Shop Scheduling problems in environments that do not involve sequence-dependent setup times of the machines. The presence of the latter, however, changes the picture dramatically. In this paper we adapt one of the best known heuristics, the Shifting Bottleneck Procedure, to the case when sequence dependent setup times play an important role. This is done by treating the single machine scheduling problems that arise in the process as Traveling Salesman Problems with time windows, and solving the latter by an efficient dynamic programming algorithm. The model treated here also incorporates precedence constraints, release times and deadlines. Computational experience on a vast array of instances, mainly from the semiconductor industry, shows our procedure to advance substantially the state of the art.
KW - Dynamic programming
KW - Sequence-dependent setup times
KW - Traveling salesman problem with time windows shifting bottleneck
UR - http://www.scopus.com/inward/record.url?scp=49549100881&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=49549100881&partnerID=8YFLogxK
U2 - 10.1007/s10951-008-0067-7
DO - 10.1007/s10951-008-0067-7
M3 - Article
AN - SCOPUS:49549100881
SN - 1094-6136
VL - 11
SP - 253
EP - 262
JO - Journal of Scheduling
JF - Journal of Scheduling
IS - 4
ER -