Multiprocessor Randomized On-line Scheduling

0175451 - MU-W 20030203 RIV CZ eng V - Research Report
Tichý, Tomáš
Multiprocessor Randomized On-line Scheduling.
Praha: Institute for Theoretical Computer Science, Charles University, 2002. 10 s. ITI Series 2002-069.
R&D Projects: GA MŠMT LN00A056; GA ČR GA201/01/1195; GA MŠMT ME 476
Institutional research plan: CEZ:AV0Z1019905; CEZ:AV0Z1019905
Keywords : online * randomized * scheduling
Subject RIV: BA - General Mathematics

This paper studies randomized on-line non-preemptive scheduling in multiprocessor systems. In this problem each task is specified by its processing time andscheduled on any of $m$ identical processors. The objective is to minimize theexpected mekespan. We prove lemmas and theorems describing $sigma_m$-competitive randomized algorithms on $m$ processors. The main result is an........
Permanent Link: http://hdl.handle.net/11104/0072434