Dolní odhad pro rozvrhování jednotkových úloh s okamžitým rozhodnutím na paralelních počítačích
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F08%3A00318602" target="_blank" >RIV/67985840:_____/08:00318602 - isvavai.cz</a>
Výsledek na webu
—
DOI - Digital Object Identifier
—
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
A lower bound for scheduling of unit jobs with immediate decision on parallel machines KAM-DIMATIA Series 2008-896 and ITI Series 2008-417
Popis výsledku v původním jazyce
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. Thismeans 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)approx 1.58$ for many machines, matching the performance of the best algorithm.
Název v anglickém jazyce
A lower bound for scheduling of unit jobs with immediate decision on parallel machines KAM-DIMATIA Series 2008-896 and ITI Series 2008-417
Popis výsledku anglicky
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. Thismeans 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)approx 1.58$ for many machines, matching the performance of the best algorithm.
Klasifikace
Druh
O - Ostatní výsledky
CEP obor
BA - Obecná matematika
OECD FORD obor
—
Návaznosti výsledku
Projekt
Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)
Ostatní
Rok uplatnění
2008
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů