Number of the records: 1
Optimal and online preemptive scheduling on uniformly related machines. ITI Series 2003-171
- 1.0175446 - MU-W 20030199 RIV SIGLE CZ eng V - Research Report
Ebenlendr, T. - Sgall, Jiří
Optimal and online preemptive scheduling on uniformly related machines. ITI Series 2003-171.
Praha: Charles University, 2003. 21 s.
R&D Projects: GA MŠMT LN00A056; GA MŠMT ME 476; GA ČR GA201/01/1195; GA AV ČR IAA1019401
Institutional research plan: CEZ:AV0Z1019905; CEZ:AV0Z1019905
Keywords : online scheduling * preemption * uniformly related machines
Subject RIV: BA - General Mathematics
We consider the problem of preemptive scheduling on uniformly related machines.We present a semi-online 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 2.71 competitive randomized online algorithms. In addition, it matches the performance of the previously......
Permanent Link: http://hdl.handle.net/11104/0072429
Number of the records: 1