Loading...
conference paper
Competitive ratio of List Scheduling on uniform machines and randomized heuristics
Musitelli, Antoine
•
Nicoletti, Jean-Marc
2011
Journal Of Scheduling
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.
Loading...
Name
10951_2010_Article_177.pdf
Type
Publisher's version
Access type
openaccess
Size
464.01 KB
Format
Adobe PDF
Checksum (MD5)
a3b3c424d0668eacdaedabe0b6ba0f8f