SINGLE FACILITY MULTICLASS JOB SCHEDULING

This paper considers a single facility scheduling problem where jobs can be divided into several mutually exclusive classes (groups). Here all jobs within a group share a common setup activity. Unlike many previous works in this area, we also assume that the jobs in a given class need not be identical (other than sharing setups) and need not be processed together. For this class of problems, we first establish a simple yet powerful necessary condition for optimality, the intergroup shortest processing time (SPT) property. Using this result, we show a slightly modified Psaraftis' dynamic programming (DP) algorithm to solve our problem. Recognizing that this DP algorithm is severely constrained by the storage requirement as the number of classes increases, we develop alternatively an efficient iterative heuristic algorithm that alleviates the memory problem. Our computational experiences for 540 randomly generated problems show that (1) the proposed heuristic finds near-optimal solutions quite quickly with average 0.07% deviations from the true optima, (2) worst case solutions of the proposed heuristic do not exceed 3% deviation from optimal solutions, and do not deteriorate as the problem size grows, (3) our proposed heuristic gains substantial improvement at the first iteration. With its substantial per iteration improvement of objective values and with its flexible structure, this algorithm might be well accommodated in the interactive scheduling environments. © 1990.