Original title: Optimal and online preemptive scheduling on uniformly related machines. ITI Series 2003-171
Authors: Ebenlendr, T. ; Sgall, Jiří
Document type: Research reports
Year: 2003
Language: eng
Abstract: 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......
Keywords: online scheduling; preemption; uniformly related machines
Project no.: CEZ:AV0Z1019905 (CEP), CEZ:AV0Z1019905 (CEP), LN00A056 (CEP), ME 476, GA201/01/1195 (CEP), IAA1019401 (CEP)
Funding provider: GA MŠk, GA MŠk, GA ČR, GA AV ČR

Institution: Institute of Mathematics AS ČR (web)
Document availability information: Fulltext is available at the institute of the Academy of Sciences.
Original record: http://hdl.handle.net/11104/0072429

Permalink: http://www.nusl.cz/ntk/nusl-26044


The record appears in these collections:
Research > Institutes ASCR > Institute of Mathematics
Reports > Research reports