Počet záznamů: 1
Optimal and online preemptive scheduling on uniformly related machines
- 1.0334957 - MÚ 2010 RIV US eng J - Článek v odborném periodiku
Ebenlendr, Tomáš - Sgall, J.
Optimal and online preemptive scheduling on uniformly related machines.
[Optimální a online preemptivní rozvrhování na uniformních počítačích.]
Journal of Scheduling. Roč. 12, č. 5 (2009), s. 517-527. ISSN 1094-6136. E-ISSN 1099-1425
Grant CEP: GA MŠMT(CZ) 1M0545; GA AV ČR IAA100190902; GA AV ČR IAA1019401
Výzkumný záměr: CEZ:AV0Z10190503
Klíčová slova: online scheduling * preemption * uniformly related machines
Kód oboru RIV: IN - Informatika
Impakt faktor: 1.265, rok: 2009
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.
Článek studuje optimální a online rozvrhování na uniformních počítačích. Najdeme 4-kompetitivní deterministický a 2.71-kompetitivní randomizovaný algoritmus.
Trvalý link: http://hdl.handle.net/11104/0179562
Název souboru Staženo Velikost Komentář Verze Přístup Ebenlendr.pdf 1 424.8 KB Vydavatelský postprint vyžádat
Počet záznamů: 1