05222189

j

05222189 Boudhar, Mourad Finke, Gerd Scheduling on a batch machine with job compatibilities. Belg. J. Oper. Res. Stat. Comput. Sci. 40, No. 1-2, 69-80 (2000). 2000 EN Summary: We consider the problem of minimizing the makespan on a single batch processing machine in which jobs are not all compatible, i.e., in which there are at least two jobs that cannot be processed simultaneously in the same batch. The capacity of the batch processing machine can be finite or infinite. The processing time of a batch is given by the processing time of the longest jobs in the batch. We prove the NP-hardness of the general problem and present polynomial algorithms for several special cases.