TY - JOUR
T1 - Job Shop Scheduling with Deadlines
AU - Balas, Egon
AU - Lancia, Giuseppe
AU - Serafini, Paolo
AU - Vazacopoulos, Alkiviadis
PY - 1998
Y1 - 1998
N2 - In this paper we deal with a variant of the Job Shop Scheduling Problem. We consider the addition of release dates and deadlines to be met by all jobs. The objective is makespan minimization if there are no tardy jobs, and tardiness minimization otherwise. The problem is approached by using a Shifting Bottleneck strategy. The presence of deadlines motivates an iterative use of a particular one machine problem which is solved optimally. The overall procedure is heuristic and exhibits a good trade-off between computing time and solution quality.
AB - In this paper we deal with a variant of the Job Shop Scheduling Problem. We consider the addition of release dates and deadlines to be met by all jobs. The objective is makespan minimization if there are no tardy jobs, and tardiness minimization otherwise. The problem is approached by using a Shifting Bottleneck strategy. The presence of deadlines motivates an iterative use of a particular one machine problem which is solved optimally. The overall procedure is heuristic and exhibits a good trade-off between computing time and solution quality.
KW - Deadlines
KW - Scheduling
KW - Shifting bottleneck
UR - http://www.scopus.com/inward/record.url?scp=0031704308&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0031704308&partnerID=8YFLogxK
U2 - 10.1023/A:1009750409895
DO - 10.1023/A:1009750409895
M3 - Article
AN - SCOPUS:0031704308
SN - 1382-6905
VL - 1
SP - 329
EP - 353
JO - Journal of Combinatorial Optimization
JF - Journal of Combinatorial Optimization
IS - 4
ER -