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 e ≃ 2.71 competitive randomized online algorithms. 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.
['Tomáš Ebenlendr', 'Jirí Sgall']
Optimal and online preemptive scheduling on uniformly related machines