Scheduling a batch processing machine with incompatible job families

The problem of scheduling batch processors is important in some industries and, at a more fundamental level, captures an element of complexity common to many practical scheduling problems. We describe a branch and bound proce dure applicable to a batch processor model with incompatible job families. Jobs in a given family have identical job processing times, arbitrary job w eights, and arbitrary job sizes. Batches are limited to jobs from the same family. The scheduling objective is to minimize total weighted completion t ime. We find that the procedure returns optimal solutions to problems of up to about 25 jobs in reasonable CPU time, and can be adapted for use as a h euristic for larger problems. (C) 2001 Elsevier Science Ltd. All rights res erved.