Optimal and online preemptive scheduling on uniformly related machines

0334957 - MÚ 2010 RIV US eng J - Journal Article
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
R&D Projects: GA MŠMT(CZ) 1M0545; GA AV ČR IAA100190902; GA AV ČR IAA1019401
Institutional research plan: CEZ:AV0Z10190503
Keywords : online scheduling * preemption * uniformly related machines
Subject RIV: IN - Informatics, Computer Science
Impact factor: 1.265, year: 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.
Permanent Link: http://hdl.handle.net/11104/0179562