Název:
A Lower Bound for Restricted Randomized On-line Algorithms for Scheduling
Překlad názvu:
Dolní odhad pro omezené pravděpodobnostní online algoritmy pro rozvrhování
Autoři:
Tichý, Tomáš Typ dokumentu: Příspěvky z konference Konference/Akce: Week for Doctoral Studentďs 2002, Praha (CZ), 2002-06-11 / 2002-06-14
Rok:
2002
Jazyk:
eng
Abstrakt: [eng][cze] This paper studies a restricted class of randomized on-line non-preemptive algorithms for scheduling in multiprocessor systems. In this class each task is specified by its processing time and scheduled to a processor with the smallest or $h$th biggest load for a fixed $h$. The competitive ratio is the maximum of the ratios of the expected makespan and the optimal makespan over all.Článek dokazuje dolní odhad pro omezené prqvděpodobnostní online algoritmy pro rozvrhování.
Klíčová slova:
online; randomized; scheduling Číslo projektu: CEZ:AV0Z1019905 (CEP), LN00A056 (CEP), GA201/01/1195 (CEP), ME 476 Poskytovatel projektu: GA MŠk, GA ČR, GA MŠk Zdrojový dokument: Proceedings of the Week for Doctoral Studentďs 2002
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/0013991