Optimal and online preemptive scheduling on uniformly related machines. ITI Series 2003-171

Number of the records: 1

1.

SYSNO ASEP	0175446
Document Type	V - Research Report
R&D Document Type	V - Research Report
Title	Optimal and online preemptive scheduling on uniformly related machines. ITI Series 2003-171
Author(s)	Ebenlendr, T. (CZ) Sgall, Jiří (MU-W)_{RID, ORCID, SAI}
Issue data	Praha: Charles University, 2003
Number of pages	21 s.
Language	eng - English
Country	CZ - Czech Republic
Keywords	online scheduling ; preemption ; uniformly related machines
Subject RIV	BA - General Mathematics BA - General Mathematics
R&D Projects	LN00A056 GA MŠMT - Ministry of Education, Youth and Sports (MEYS)
	ME 476 GA MŠMT - Ministry of Education, Youth and Sports (MEYS)
	GA201/01/1195 GA ČR - Czech Science Foundation (CSF)
	IAA1019401 GA AV ČR - Academy of Sciences of the Czech Republic (AV ČR)
CEZ	AV0Z1019905 - MU-W
	AV0Z1019905 - MU-W
Annotation	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......
Workplace	Mathematical Institute
Contact	Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757
Year of Publishing	2004

Number of the records: 1