Article ID: | iaor20053067 |
Country: | Germany |
Volume: | 39 |
Issue: | 2 |
Start Page Number: | 155 |
End Page Number: | 174 |
Publication Date: | Feb 2004 |
Journal: | Algorithmica |
Authors: | Poon Chung Keung, Zhang Pixing |
We study the scheduling of a set of n jobs, each characterized by a release (arrival) time and a processing time, for a batch processing machine capable of running at most B jobs at a time. We obtain an O(n log n)-time algorithm when B is unbounded. When there are only m distinct release times and the inputs are integers, we obtain an O(n(BR