Počet záznamů: 1

Optimal and online preemptive scheduling on uniformly related machines

  1. 1.
    0334957 - MU-W 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
    Grant CEP: GA MŠk(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 souboruStaženoVelikostKomentářVerzePřístup
    Ebenlendr.pdf1424.8 KBVydavatelský postprintvyžádat