A lower bound for on-line scheduling on uniformly related machines

0174818 - MU-W 200010 RIV NL eng J - Článek v odborném periodiku
Sgall, Jiří - Epstein, L.
A lower bound for on-line scheduling on uniformly related machines.
Operations Research Letters. Roč. 26, č. 1 (2000), s. 17-22. ISSN 0167-6377. E-ISSN 1872-7468
Grant CEP: GA AV ČR IAA1019901; GA ČR GA201/97/P038
Výzkumný záměr: CEZ:AV0Z1019905; CEZ:A05/98:Z1-019-9ii
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 0.523, rok: 2000

We consider the problem of on-line scheduling of jobs arriving one by one on uniformly related machines, with or without preemption. We prove a lower bound of 2, both with and without preemption, for randomized algorithms working for an arbitrary number of machines. For a constant number of machines we give new lower bounds for the preemptive case.
Trvalý link: http://hdl.handle.net/11104/0071817