# 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.)