| Article ID: | iaor20042056 |
| Country: | Netherlands |
| Volume: | 7 |
| Issue: | 3 |
| Start Page Number: | 247 |
| End Page Number: | 257 |
| Publication Date: | Sep 2003 |
| Journal: | JCO |
| Authors: | Deng Xiaotie, Zhang Yuzhong, Poon Chung Keung |
| Keywords: | batch processes |
A polynomial approximation scheme for minimizing makespan in a batch processing system under dynamic job arrivals is presented. A lower bound of (√5+1)/2 on the competitive ratio of any on-line algorithm is proved. This is matched by an on-line algorithm for the special case of unbounded machine capacity.