Scheduling on a batch machine with job compatibilities

Scheduling on a batch machine with job compatibilities

0.00 Avg rating0 Votes
Article ID: iaor20021178
Country: Belgium
Volume: 40
Issue: 1/2
Start Page Number: 70
End Page Number: 80
Publication Date: Jan 2000
Journal: Belgian Journal of Operations Research, Statistics and Computer Science
Authors: ,
Keywords: batch processes
Abstract:

We consider the problem of minimizing the makespan on a single batch processing machine, in which jobs are not all compatible, i.e. there are at least two jobs that can not 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 NP-hardness of the general problem and present polynomial algorithms for several special cases.

Reviews

Required fields are marked *. Your email address will not be published.