| Accueil > Competitive ratio of List Scheduling on uniform machines and randomized heuristics |
We study online scheduling on m uniform machines, where m - 1 of them have a reference speed 1 and the last one a speed s with 0 <= s <= 1. The competitive ratio of the well-known List Scheduling (LS) algorithm is determined. For some values of s and m = 3, LS is proven to be the best deterministic algorithm. We describe a randomized heuristic for m machines. Finally, for the case m = 3, we develop and analyze the competitive ratio of a randomized algorithm which outperforms LS for any s.