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

Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F09%3A00334971" target="_blank" >RIV/67985840:_____/09:00334971 - isvavai.cz</a>
Výsledek na webu
—
DOI - Digital Object Identifier
—

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
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) approximate to 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
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) approximate to 1.58 for many machines, matching the performance of the best algorithm.

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)

Rok uplatnění
2009
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ů

Podobné výsledky(10)