Competitive ratio of List Scheduling on uniform machines and randomized heuristics

Musitelli, AntoineNicoletti, Jean-Marc2011-12-162011-12-162011-12-16201110.1007/s10951-010-0177-xhttps://infoscience.epfl.ch/handle/20.500.14299/74261WOS:000289166500007We 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.Analysis of algorithmsOnline algorithmsCompetitive ratioRandomized schedulingAlgorithmCompetitive ratio of List Scheduling on uniform machines and randomized heuristicstext::conference output::conference proceedings::conference paper