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: | Sgall Ji, Ebenlendr Tom |
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