Stochastic scheduling of a batch processing machine with incompatible job families

The authors consider the control of a single batch processing machine with random processing times and incompatible job families (jobs from different families cannot be processed together in the same batch). Holding costs are incurred for each unit of time that a job waits in the system before being served, and the objective is to minimize the long-run average cost per unit time. The authors first determine optimal policies for the static problem where all jobs are available simultaneously. They next characterize the optimal policies for certain problems with dynamic arrivals of jobs under the restriction that the machine is not allowed to idle. Finally, the authors develop a simple heuristic scheduling policy to control the machine. Simulation results are provided to demonstrate the effectiveness of the present heuristic over a wide range of problem instances and to compare its performance with existing heuristics.