Article ID: | iaor20053106 |
Country: | Netherlands |
Volume: | 9 |
Issue: | 2 |
Start Page Number: | 167 |
End Page Number: | 186 |
Publication Date: | Mar 2005 |
Journal: | Journal of Combinatorial Optimization |
Authors: | Yu Wenci, Poon Chung Keung |
We study the problem of on-line scheduling jobs with release dates on a batch machine of finite capacity with the objective of minimizing the makespan. We generalize several existing algorithms for the problem to a class of on-line algorithms that are 2-competitive for any arbitrary finite machine capacity. Then, we show that one of these generalized algorithms is in fact 7/4-competitive for machine capacity 2. This is the first on-line algorithm for a finite machine capacity with competitive ratio less than 2.