de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch

Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt

# Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Zeitschriftenartikel

#### Online randomized multiprocessor scheduling

##### MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45451

Seiden,  Steve S.
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

##### Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
##### Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
##### Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
##### Zitation

Seiden, S. S. (2000). Online randomized multiprocessor scheduling. Algorithmica, 28(2), 173-216.

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 &lt; 1.83579$ , $(5 + 2 \sqrt{22})/7 &lt; 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 .