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.


Publié dans:
Journal Of Scheduling, 14, 89-101
Présenté à:
Workshop on New Challenges in Scheduling Theory, Marseilles, FRANCE, 2008
Année
2011
Mots-clefs:
Laboratoires:




 Notice créée le 2011-12-16, modifiée le 2018-01-28


Évaluer ce document:

Rate this document:
1
2
3
 
(Pas encore évalué)