Job Shop Scheduling with Deadlines

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. 1 Introduction In this paper we deal with a variant of the Job Shop Scheduling (JSS) Problem. The proposed model has all usual features of the well known Job Shop model with the addition of release dates and deadlines which must be met by all jobs. The objective is still the makespan minimization. We refer to this model simply as the Job Shop Scheduling Problem with Deadlines (JSSD). There are practical reasons for introducing deadlines. The fir..