Počet záznamů: 1
Optimal and online preemptive scheduling on uniformly related machines
- 1.
SYSNO ASEP 0334957 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název Optimal and online preemptive scheduling on uniformly related machines Překlad názvu Optimální a online preemptivní rozvrhování na uniformních počítačích Tvůrce(i) Ebenlendr, Tomáš (MU-W) SAI, RID
Sgall, J. (CZ)Zdroj.dok. Journal of Scheduling - ISSN 1094-6136
Roč. 12, č. 5 (2009), s. 517-527Poč.str. 11 s. Jazyk dok. eng - angličtina Země vyd. US - Spojené státy americké Klíč. slova online scheduling ; preemption ; uniformly related machines Vědní obor RIV IN - Informatika CEP 1M0545 GA MŠMT - Ministerstvo školství, mládeže a tělovýchovy IAA100190902 GA AV ČR - Akademie věd IAA1019401 GA AV ČR - Akademie věd CEZ AV0Z10190503 - MU-W (2005-2011) UT WOS 000270340900008 DOI 10.1007/s10951-009-0119-7 Anotace We consider the problem of preemtive scheduling on uniformly related machines. We present a semionline 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 an 2.71-competitive randomized online algorithm. In addition, it matches the performance of the previously known algorithms for the offline case, with a considerably simpler proof. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2010
Počet záznamů: 1