Název:
Optimal and online preemptive scheduling on uniformly related machines. ITI Series 2003-171
Autoři:
Ebenlendr, T. ; Sgall, Jiří Typ dokumentu: Výzkumné zprávy
Rok:
2003
Jazyk:
eng
Abstrakt: We consider the problem of preemptive scheduling on uniformly related machines.We present a semi-online algorithm which, if the optimal makespan is given in advance, produces an optimal schedule. Using the standard doubling technique, this yields a 4 competitive deterministic and 2.71 competitive randomized online algorithms. In addition, it matches the performance of the previously......
Klíčová slova:
online scheduling; preemption; uniformly related machines Číslo projektu: CEZ:AV0Z1019905 (CEP), CEZ:AV0Z1019905 (CEP), LN00A056 (CEP), ME 476, GA201/01/1195 (CEP), IAA1019401 (CEP) Poskytovatel projektu: GA MŠk, GA MŠk, GA ČR, GA AV ČR
Instituce: Matematický ústav AV ČR
(web)
Informace o dostupnosti dokumentu:
Dokument je dostupný v příslušném ústavu Akademie věd ČR. Původní záznam: http://hdl.handle.net/11104/0072429