Online scheduling of equal-length jobs: Randomization and restarts help

0106922 - MU-W 20040129 RIV DE eng C - Konferenční příspěvek (zahraniční konf.)
Sgall, Jiří - Chrobak, M. - Jawor, W. - Tichý, Tomáš
Online scheduling of equal-length jobs: Randomization and restarts help.
[Online rozvrhování úloh stejné délky.]
Proceedings of the 31st International Colloquium on Automata, Languages, and Programming (ICALP). Berlin: Springer, 2004, s. 358-370.
[International Colloquium on Automata, Languages, and Programming/31./. Turku (FI), 12.07.2004-16.07.2004]
Grant CEP: GA MŠMT LN00A056; GA AV ČR IAA1019401
Výzkumný záměr: CEZ:AV0Z1019905
Klíčová slova: online scheduling * deadlines * randomization
Kód oboru RIV: BA - Obecná matematika

We consider the following scheduling problem. The input is a set of jobs with equal processing times, where each job is specified by its release time and deadline. The goal is to determine a single-processor, non-preemptive schedule of these jobs that maximizes the number of completed jobs. In the online version, each job arrives at its release time.

Článek studuje online rozvrhování úloh stejné délky.
Trvalý link: http://hdl.handle.net/11104/0014094