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, the authors 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, they first establish a simple yet powerful necessary condition for optimality, the intergroup shortest processing time (SPT) property. Using this result, the authors show a slightly modified Psaraftis’ dynamic programming (DP) algorithm to solve their problem. Recognizing that this DP algorithm is severely constrained by the storage requirement as the number of classes increases, they develop alternatively an efficient iterative heuristic algorithm that alleviates the memory problem. The present 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) the 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.
