SCHEDULING BATCH PROCESSING MACHINES WITH INCOMPATIBLE JOB FAMILIES

The problem of scheduling a single batch processing machine with incom patible job families was studied, where jobs of different families can not be processed together in the same batch. First static problems whe re all jobs are available simultaneously were considered and showed th at for a regular performance measure there will be no unnecessary part ial batches. This allowed us to develop efficient optimal algorithms t o minimize makespan (Cmax), maximum lateness (Lmax) and total weighted completion time and apply some of these results to problems with para llel identical batch processing machines. Then problems with dynamic j ob arrivals were considered and an efficient optimal algorithm for min imizing Cmax and several heuristics to minimize Lmax were provided. Co mputational experiments showed that the heuristics developed for the l atter problem consistently improve on dispatching solutions in very re asonable CPU times.