History

Please fill in your query. A complete syntax description you will find on the General Help page.
Competitive ratio of list scheduling on uniform machines and randomized heuristics. (English)
J. Sched. 14, No. 1, 89-101 (2011).
Summary: 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\leq s\leq 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$.