Online scheduling of jobs with fixed start times on related machines
The result's identifiers
Result code in 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>
Alternative codes found
RIV/00216208:11320/16:10331547
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Online scheduling of jobs with fixed start times on related machines
Original language description
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).
Czech name
—
Czech description
—
Classification
Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2016
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Algorithmica
ISSN
0178-4617
e-ISSN
—
Volume of the periodical
74
Issue of the periodical within the volume
1
Country of publishing house
US - UNITED STATES
Number of pages
21
Pages from-to
156-176
UT code for WoS article
000367622200006
EID of the result in the Scopus database
2-s2.0-84953283240