Number of the records: 1
Semi-online preemptive scheduling: one algorithm for all variants
- 1.
SYSNO ASEP 0370277 Document Type J - Journal Article R&D Document Type Journal Article Subsidiary J Článek ve WOS Title Semi-online preemptive scheduling: one algorithm for all variants Author(s) Ebenlendr, Tomáš (MU-W) SAI, RID
Sgall, J. (CZ)Source Title Theory of Computing Systems. - : Springer - ISSN 1432-4350
Roč. 48, č. 3 (2011), s. 577-613Number of pages 37 s. Action 26th International Symposium on Theoretical Aspects of Computer Science Event date 26.02.2009-28.02.2009 VEvent location Freiburg Country DE - Germany Event type WRD Language eng - English Country US - United States Keywords online algorithms ; scheduling ; preemption ; linear program Subject RIV BA - General Mathematics R&D Projects IAA100190902 GA AV ČR - Academy of Sciences of the Czech Republic (AV ČR) 1M0545 GA MŠMT - Ministry of Education, Youth and Sports (MEYS) CEZ AV0Z10190503 - MU-W (2005-2011) UT WOS 000287199100008 EID SCOPUS 79751530145 DOI 10.1007/s00224-010-9287-2 Annotation We present a unified optimal semi-online algorithm for preemptive scheduling on uniformly related machines with the objective to minimize the makespan. This algorithm works for all types of semi-online restrictions, including the ones studied before, like sorted (decreasing) jobs, known sum of processing times, known maximal processing time, their combinations, and so on. Based on the analysis of this algorithm, we derive some global relations between various semi-online restrictions and tight bounds on the approximation ratios for a small number of machines. Workplace Mathematical Institute Contact Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Year of Publishing 2012
Number of the records: 1