Počet záznamů: 1

Semi-online preemptive scheduling: one algorithm for all variants

SYSNO ASEP	0334967
Druh ASEP	C - Konferenční příspěvek (mezinárodní konf.)
Zařazení RIV	D - Článek ve sborníku
Název	Semi-online preemptive scheduling: one algorithm for all variants
Překlad názvu	Semi-online preemptivní rozvrhování: jeden algoritmus pro všechny varianty
Tvůrce(i)	Ebenlendr, Tomáš (MU-W)_{SAI, RID} Sgall, Jiří (MU-W)_{RID, ORCID, SAI}
Zdroj.dok.	26th International Symposium on Theoretical Aspects of Computer Science. - Leibniz : Schloss Dagstuhl, 2009 / Albers S. ; Marion J.-Y. - ISBN 978-3-939897-09-5
Rozsah stran	s. 349-360
Poč.str.	12 s.
Akce	26th International Symposium on Theoretical Aspects of Computer Science
Datum konání	26.02.2009-28.02.2009
Místo konání	Freiburg
Země	DE - Německo
Typ akce	WRD
Jazyk dok.	eng - angličtina
Země vyd.	DE - Německo
Klíč. slova	algorithms ; scheduling
Vědní obor RIV	IN - Informatika
CEP	1M0545 GA MŠMT - Ministerstvo školství, mládeže a tělovýchovy
	GA201/05/0124 GA ČR - Grantová agentura ČR
	IAA1019401 GA AV ČR - Akademie věd
CEZ	AV0Z10190503 - MU-W (2005-2011)
Anotace	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.
Pracoviště	Matematický ústav
Kontakt	Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757
Rok sběru	2010

Počet záznamů: 1