Počet záznamů: 1

A lower bound for scheduling of unit jobs with immediate decision on parallel machines

SYSNO ASEP	0334971
Druh ASEP	C - Konferenční příspěvek (mezinárodní konf.)
Zařazení RIV	D - Článek ve sborníku
Název	A lower bound for scheduling of unit jobs with immediate decision on parallel machines
Překlad názvu	Dolní odhad pro rozhodování jednotkových úloh s okamžitým rozhodnutím na paralelních počítačích
Tvůrce(i)	Ebenlendr, Tomáš (MU-W)_{SAI, RID} Sgall, Jiří (MU-W)_{RID, ORCID, SAI}
Zdroj.dok.	Approximation and online algorithms. - Berlin : Springer, 2009 / Bampis E. ; Skutella M. - ISBN 978-3-540-93979-5
Rozsah stran	s. 43-52
Poč.str.	10 s.
Akce	6th International Workshop on Approximation and Online Algorithms
Datum konání	18.09.2008-19.09.2008
Místo konání	Karlsruhe
Země	DE - Německo
Typ akce	WRD
Jazyk dok.	eng - angličtina
Země vyd.	DE - Německo
Klíč. slova	online 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)
UT WOS	000264413000004
Anotace	Consider scheduling of unit jobs with release times and deadlines on m. identical machines with the objective to maximize the number of jobs completed before their deadlines. We prove a new lower bound for online algorithms with immediate decision. This means that the jobs arrive over time and the algorithm has to decide the schedule of each job immediately upon its release. Our lower bound tends to e/(e-1) approximate to 1.58 for many machines, matching the performance of the best algorithm.
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