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%2F00216208%3A11320%2F12%3A10127267" target="_blank" >RIV/00216208:11320/12:10127267 - isvavai.cz</a>
Alternative codes found
RIV/67985840:_____/12:00387295
Result on the web
<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>
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). In particular, we give a lower bound of m on th
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
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)
Others
Publication year
2012
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
Article name in the collection
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
—
Number of pages
12
Pages from-to
134-145
Publisher name
Springer
Place of publication
Berlin
Event location
Cambridge, MA
Event date
Aug 15, 2012
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—