Minimizing makespan on a single batch processing machine with nonidentical job sizes

Minimizing makespan on a single batch processing machine with nonidentical job sizes

0.00 Avg rating0 Votes
Article ID: iaor20021714
Country: United States
Volume: 48
Issue: 3
Start Page Number: 226
End Page Number: 240
Publication Date: Apr 2001
Journal: Naval Research Logistics
Authors: , , ,
Keywords: combinatorial analysis
Abstract:

We deal with the problem of minimizing makespan on a single batch processing machine. In this problem, each job has both processing time and size (capacity requirement). The batch processing machine can process a number of jobs simultaneously as long as the total size of these jobs being processed does not exceed the machine capacity. The processing time of a batch is just the processing time of the longest job in the batch. An approximation algorithm with worst-case ratio 3/2 is given for the version where the processing times of large jobs (with sizes greater than 1/2) are not less than those of small jobs (with sizes not greater than 1/2). This result is the best possible unless P = NP. For the general case, we propose an approximation algorithm with worst-case ratio 7/4. A number of heuristics by Uzosy are also analyzed and compared.

Reviews

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