A Lower Bound on Deterministic Online Algorithms for Scheduling on Related Machines Without Preemption
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F15%3A10316162" target="_blank" >RIV/00216208:11320/15:10316162 - isvavai.cz</a>
Nalezeny alternativní kódy
RIV/67985840:_____/15:00440693
Výsledek na webu
<a href="http://dx.doi.org/10.1007/s00224-013-9451-6" target="_blank" >http://dx.doi.org/10.1007/s00224-013-9451-6</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s00224-013-9451-6" target="_blank" >10.1007/s00224-013-9451-6</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
A Lower Bound on Deterministic Online Algorithms for Scheduling on Related Machines Without Preemption
Popis výsledku v původním jazyce
We consider one-by-one online scheduling on uniformly related machines. The input is a sequence of machines with different speeds and a sequence of jobs with different processing times. The output is a schedule which assigns the jobs to the machines; thecompletion time of a machine is the sum of the processing times of jobs assigned to it divided by its speed. The objective is to minimize the maximal completion time. The jobs arrive one by one and each has to be assigned to one machine immediately andirrevocably without the knowledge of the future jobs. We prove a new lower bound of 2.564 on the competitive ratio of deterministic online algorithms for this problem, improving the previous lower bound of 2.438.
Název v anglickém jazyce
A Lower Bound on Deterministic Online Algorithms for Scheduling on Related Machines Without Preemption
Popis výsledku anglicky
We consider one-by-one online scheduling on uniformly related machines. The input is a sequence of machines with different speeds and a sequence of jobs with different processing times. The output is a schedule which assigns the jobs to the machines; thecompletion time of a machine is the sum of the processing times of jobs assigned to it divided by its speed. The objective is to minimize the maximal completion time. The jobs arrive one by one and each has to be assigned to one machine immediately andirrevocably without the knowledge of the future jobs. We prove a new lower bound of 2.564 on the competitive ratio of deterministic online algorithms for this problem, improving the previous lower bound of 2.438.
Klasifikace
Druh
J<sub>x</sub> - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP obor
IN - Informatika
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
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2015
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ů
Údaje specifické pro druh výsledku
Název periodika
Theory of Computing Systems
ISSN
1432-4350
e-ISSN
—
Svazek periodika
56
Číslo periodika v rámci svazku
1
Stát vydavatele periodika
DE - Spolková republika Německo
Počet stran výsledku
9
Strana od-do
73-81
Kód UT WoS článku
000348448100005
EID výsledku v databázi Scopus
2-s2.0-84957968096