Alternative Formulation of the Job Shop Problem with Due Dates

Abstract

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? Here, 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. This paper describes the basic structure of the scheduling procedure, the machine coding of a specific version of the procedure, and computational experience with a set of test problems ranging in size up to fourteen jobs and seven machines.