Scheduling batch processing machines with incompatible job families

Abstract

The problem of scheduling a single batch processing machine with incompatible job families was studied, where jobs of different families cannot be processed together in the same batch. First static problems where all jobs are available simultaneously were considered and showed that for a regular performance measure there will be no unnecessary partial batches. This allowed us to develop efficient optimal algorithms to minimize makespan (Cmax), maximum lateness (Lmax) and total weighted completion time and apply some of these results to problems with parallel identical batch processing machines. Then problems withdynamic job arrivals were considered and an efficient optimal algorithm for minimizing Cmax and several heuristics to minimize Lmax were provided. Computational experiments showed that the heuristics developed for the latter problem consistently improve on dispatching solutions in very reasonable CPU times.