Abstract
The use of randomization in online multiprocessor scheduling is studied. The
problem of scheduling independent jobs on m machines online originates with
Graham [16]. 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 et al. A randomized
algorithm for m 3 is presented. It achieves competitive ratios of 1.55665,
1.65888, 1.73376, 1.78295, and 1.81681, for m = 3, 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 . Two
models of multiprocessor scheduling with rejection are studied. The first is
the model of Bartal et al. Two randomized algorithms for this model are
presented. The first algorithm performs well for small m , achieving
competitive ratios of 3/2 , $(7 + \sqrt{129})/10 < 1.83579$ , $(5 + 2
\sqrt{22})/7 < 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 . It is conjectured that this is true
for all m . The second model differs in that preemption is allowed. For this
model, randomized algorithms
are presented which outperform the best deterministic algorithm for small m .
