Online scheduling of jobs with fixed start times on related machines

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F12%3A10127267" target="_blank" >RIV/00216208:11320/12:10127267 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/67985840:_____/12:00387295

Výsledek na webu

<a href="http://dx.doi.org/10.1007/978-3-642-32512-0_12" target="_blank" >http://dx.doi.org/10.1007/978-3-642-32512-0_12</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-642-32512-0_12" target="_blank" >10.1007/978-3-642-32512-0_12</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Online scheduling of jobs with fixed start times on related machines

Popis výsledku v původním jazyce

We consider online preemptive scheduling of jobs with fixed starting times revealed at those times on m uniformly related machines, with the goal of maximizing the total weight of completed jobs. Every job has a size and a weight associated with it. A newly released job must be either assigned to start running immediately on a machine or otherwise it is dropped. It is also possible to drop an already scheduled job, but only completed jobs contribute their weights to the profit of the algorithm. In the most general setting, no algorithm has bounded competitive ratio, and we consider a number of standard variants. We give a full classification of the variants into cases which admit constant competitive ratio (weighted and unweighted unit jobs, and C-benevolent instances, which is a wide class of instances containing proportional-weight jobs), and cases which admit only a linear competitive ratio (unweighted jobs and D-benevolent instances). In particular, we give a lower bound of m on th

Název v anglickém jazyce

Online scheduling of jobs with fixed start times on related machines

Popis výsledku anglicky

We consider online preemptive scheduling of jobs with fixed starting times revealed at those times on m uniformly related machines, with the goal of maximizing the total weight of completed jobs. Every job has a size and a weight associated with it. A newly released job must be either assigned to start running immediately on a machine or otherwise it is dropped. It is also possible to drop an already scheduled job, but only completed jobs contribute their weights to the profit of the algorithm. In the most general setting, no algorithm has bounded competitive ratio, and we consider a number of standard variants. We give a full classification of the variants into cases which admit constant competitive ratio (weighted and unweighted unit jobs, and C-benevolent instances, which is a wide class of instances containing proportional-weight jobs), and cases which admit only a linear competitive ratio (unweighted jobs and D-benevolent instances). In particular, we give a lower bound of m on th

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

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)

Rok uplatnění

2012

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ů

Název statě ve sborníku

15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2012 and the 16th International Workshop on Randomization and Computation, RANDOM 2012

ISBN

978-3-642-32511-3

ISSN

—

e-ISSN

—

Počet stran výsledku

12

Strana od-do

134-145

Název nakladatele

Springer

Místo vydání

Berlin

Místo konání akce

Cambridge, MA

Datum konání akce

15. 8. 2012

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—