Article ID: | iaor20072287 |
Country: | United Kingdom |
Volume: | 58 |
Issue: | 1 |
Start Page Number: | 80 |
End Page Number: | 90 |
Publication Date: | Jan 2007 |
Journal: | Journal of the Operational Research Society |
Authors: | Wirth A., Khammuang K., Abdekhodaee A. |
In various manufacturing and computing contexts there may be a certain period in each time interval, during which processing may continue but may not be initiated. We examine the problem of on-line scheduling in the presence of such forbidden zones, whose complements are starting time windows. We show that no on-line algorithm is better than 9/7-competitive, when minimizing the number of intervals used (essentially the makespan), whereas list scheduling is shown to be 2-competitive. We also investigate adaptations of the first fit, next fit and harmonic bin packing algorithms and test all four empirically.