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.
