Number of the records: 1
Optimal and online preemptive scheduling on uniformly related machines
- 1.
SYSNO ASEP 0334957 Document Type J - Journal Article R&D Document Type Journal Article Subsidiary J Článek ve WOS Title Optimal and online preemptive scheduling on uniformly related machines Title Optimální a online preemptivní rozvrhování na uniformních počítačích Author(s) Ebenlendr, Tomáš (MU-W) SAI, RID
Sgall, J. (CZ)Source Title Journal of Scheduling - ISSN 1094-6136
Roč. 12, č. 5 (2009), s. 517-527Number of pages 11 s. Language eng - English Country US - United States Keywords online scheduling ; preemption ; uniformly related machines Subject RIV IN - Informatics, Computer Science R&D Projects 1M0545 GA MŠMT - Ministry of Education, Youth and Sports (MEYS) IAA100190902 GA AV ČR - Academy of Sciences of the Czech Republic (AV ČR) IAA1019401 GA AV ČR - Academy of Sciences of the Czech Republic (AV ČR) CEZ AV0Z10190503 - MU-W (2005-2011) UT WOS 000270340900008 DOI 10.1007/s10951-009-0119-7 Annotation We consider the problem of preemtive scheduling on uniformly related machines. We present a semionline 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 an 2.71-competitive randomized online algorithm. In addition, it matches the performance of the previously known algorithms for the offline case, with a considerably simpler proof. Workplace Mathematical Institute Contact Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Year of Publishing 2010
Number of the records: 1