Randomized online scheduling on two uniform machines

Leah Epstein, John Noga, Steve S. Seiden, Jirí Sgall, Gerhard Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

70 Citations (Scopus)


We study the problem of on-line scheduling on two uniform machines with speeds 1 and s⩾1. A ϕ≈1.61803 competitive deterministic algorithm was already known. We present the first randomized results for this problem: We show that randomization does not help for speeds s⩾2, but does help for all s<2. We present a simple memoryless randomized algorithm with competitive ratio (4−s)(1+s)/4⩽1.56250. We analyse other randomized algorithms that demonstrate that the randomized competitive ratio is at most 1.52778 for any s. These algorithms are barely random, i.e. they use only a constant number of random bits. Finally, we present a 1+s/(s2+s+1) competitive deterministic algorithm for the preemptive version of this problem. For any s, it is best possible even among randomized preemptive algorithms.
Original languageEnglish
Pages (from-to)71-92
Number of pages22
JournalJournal of scheduling
Issue number2
Publication statusPublished - 2001


  • METIS-201868


Dive into the research topics of 'Randomized online scheduling on two uniform machines'. Together they form a unique fingerprint.

Cite this