ICS 269, Winter 1996: Theory Seminar
26 January 1996:
A Randomized Algorithm for Three Machine Scheduling
Steve Seiden, ICS, UC Irvine
The problem of scheduling independent jobs on m parallel
machines in an online fashion was introduced by Graham in 1966.
While the deterministic case of this problem has been studied
extensively, little work has been done on the randomized case. For
m = 2 an algorithm achieving a competitive ratio of 4/3 has
been found by Bartal, Fiat, Karloff and Vohra. These same authors
show a matching lower bound. Chen, van Vliet and Woeginger, and
independently Sgall, have shown a lower bound which converges to
e/(e-1) as m goes to infinity. Prior to this
work, no randomized algorithm for m > 2 was known. An
algorithm for m = 3 is presented, and it is shown that this
algorithm is 3/2-competitive.