ICS Theory Group

ICS 269, Winter 1997: Theory Seminar

24 Jan 1997:
Online Multiprocessor Scheduling
Steve Seiden, ICS, UC Irvine

The problem of scheduling independent jobs on m machines in an online fashion was first studied 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 a randomized 4/3-competitive algorithm was found by Bartal, Fiat, Karloff and Vohra. I have recently developed two algorithms for m > 3. The first is 1.55871-competitive for m = 3. The second achieves competitive ratios of 1.67517, 1.74114, 1.78810 and 1.82082, for m = 4,5,6,7 respectively. These competitive ratios are less than the best deterministic lower bound for m = 3,4,5 and less than the best known deterministic competitive ratio for m = 3,4,5,6,7. In this talk, I explain the first algorithm, and outline a proof of its competitiveness.

I shall also talk about two models of multiprocessor scheduling with rejection. The first is the model of Bartal, Leonardi, Marchetti-Spaccamela, Sgall and Stougie. I have developed two randomized algorithms for this model. The first algorithm performs well for small m, achieving competitive ratios of 3/2, 1.83579, 2.05441 for m = 2,3,4, respectively. The second algorithm outperforms the first for m  > 5. It beats the deterministic algorithm of Bartal et al. for all m = 5, ... 1000. I am currently developing a proof that this is true for all m. The second model differs in that preemption is allowed. For this model, I have developed a deterministic algorithm which is 2.38743-competitive for all m. I have also developed randomized algorithms which outperform the best deterministic algorithms for small m. In this talk, I shall explain my non-preemptive algorithm for small m, and outline its analysis.

(Practice job interview talk.)