ICS Theory Group

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.