Optimal and online preemptive scheduling on uniformly related machines

Optimal and online preemptive scheduling on uniformly related machines

0.00 Avg rating0 Votes
Article ID: iaor200971286
Country: United Kingdom
Volume: 12
Issue: 5
Start Page Number: 517
End Page Number: 527
Publication Date: Oct 2009
Journal: Journal of Scheduling
Authors: ,
Abstract:

We consider the problem of preemptive scheduling on uniformly related machines. We present a semi-online algorithm which, if the optimal makespan is given in advance, produces an optimal schedule. Using the standard doubling technique, this yields a 4-competitive deterministic and an e≈2.71-competitive randomized online algorithm. In addition, it matches the performance of the previously known algorithms for the offline case, with a considerably simpler proof. Finally, we study the performance of greedy heuristics for the same problem.

Reviews

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