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: | Lee C.-Y., Cai Xiaoqiang, Zhang Guochuan, Wong C.K. |
Keywords: | combinatorial analysis |
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