Scheduling a batch processing machine with bipartite compatibility graphs

We consider the problem of minimizing the makespan on a batch processing machine, in which jobs are not all compatible. Only compatible jobs can be included into the same batch. This relation of compatibility is represented by a graph (called compatibility graph), which is assumed to be bipartite. The capacity of the batch processing machine is equal to 2. Furthermore, the jobs have release dates. The processing time of a batch is given by the processing time of the longest job in the batch. We establish that the general problem is NP-hard in the strong sense, but that several special cases can be solved in polynomial time. A heuristic is also presented. Copyright Springer-Verlag Berlin Heidelberg 2003