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%2F67985840%3A_____%2F16%3A00457321" target="_blank" >RIV/67985840:_____/16:00457321 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/00216208:11320/16:10331547

Výsledek na webu

<a href="http://dx.doi.org/10.1007/s00453-014-9940-2" target="_blank" >http://dx.doi.org/10.1007/s00453-014-9940-2</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00453-014-9940-2" target="_blank" >10.1007/s00453-014-9940-2</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).

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).

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

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)<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2016

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 periodika

Algorithmica

ISSN

0178-4617

e-ISSN

—

Svazek periodika

74

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

21

Strana od-do

156-176

Kód UT WoS článku

000367622200006

EID výsledku v databázi Scopus

2-s2.0-84953283240