On-line scheduling with forbidden zones

On-line scheduling with forbidden zones

0.00 Avg rating0 Votes
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: , ,
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.