Number of the records: 1

Semi-online preemptive scheduling: one algorithm for all variants

SYSNO ASEP	0334967
Document Type	C - Proceedings Paper (int. conf.)
R&D Document Type	Conference Paper
Title	Semi-online preemptive scheduling: one algorithm for all variants
Title	Semi-online preemptivní rozvrhování: jeden algoritmus pro všechny varianty
Author(s)	Ebenlendr, Tomáš (MU-W)_{SAI, RID} Sgall, Jiří (MU-W)_{RID, ORCID, SAI}
Source Title	26th International Symposium on Theoretical Aspects of Computer Science. - Leibniz : Schloss Dagstuhl, 2009 / Albers S. ; Marion J.-Y. - ISBN 978-3-939897-09-5
Pages	s. 349-360
Number of pages	12 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	DE - Germany
Keywords	algorithms ; scheduling
Subject RIV	IN - Informatics, Computer Science
R&D Projects	1M0545 GA MŠMT - Ministry of Education, Youth and Sports (MEYS)
	GA201/05/0124 GA ČR - Czech Science Foundation (CSF)
	IAA1019401 GA AV ČR - Academy of Sciences of the Czech Republic (AV ČR)
CEZ	AV0Z10190503 - MU-W (2005-2011)
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	2010

Number of the records: 1