You are here

A New Approach To Job Shop Scheduling With Due Dates

A New Approach To Job Shop Scheduling With Due Dates

By Charles A. Holloway, Rosser Nelson
1971Working Paper No. 11

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 pro- blems. The average and maximum IBM 360-91 computing times were 1.23 and 3.28 seconds, respectively.