A New Approach To Job Shop Scheduling With Due Dates

The classical formulation of the static job shop scheduling problem with job due dates implies that: the question of interest to the manager is: What is the best that can be done to meet due dates with fixed resources? In this paper, two alternative formulations of the problem are proposed; one because of its practical appeal, the other because of its methodological appeal The latter is used to develop a multi-pass heuristic scheduling procedure aimed at providing a practical tool for attacking any of the three formulations of the problem. The procedure was programmed and applied to a set of nineteen test problems for which solutions satisfying all job due dates are known to exist. The problems range in size up to 10 jobs, 9 machines and 14 jobs, 7 machines. Solutions were attained for each of the test problems. The average and maximum IBM 360-91 computing times were 1.23 and 3.28 seconds, respectively.