MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Epstein, Leah
Jez, Lukasz
Sgall, Jiri
van Stee, Rob		dblp
dblp
dblp
dblp
Not MPG Author(s):
Epstein, Leah
Jez, Lukasz
Sgall, Jiri
Editor(s):
Gupta, Anupam
Jansen, Klaus
Rolim, José
Servedio, Rocco		dblp
dblp
dblp
dblp
Not MPII Editor(s):
Gupta, Anupam
Jansen, Klaus
Rolim, José
Servedio, Rocco
BibTeX cite key*:
EpJeSS12
Title, Booktitle
Title*:
Online Scheduling of Jobs with Fixed Start Times on Related Machines
Booktitle*:
Approximation, Randomization, and Combinatorial Optimization : Algorithms and Techniques ; 15th International Workshop, APPROX 2012 and 16th International Workshop, RANDOM 2012
Event, URLs
Conference URL::
http://cui.unige.ch/tcs/random-approx/2012/index.php
Downloading URL:
Event Address*:
Boston, USA
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
15 August 2012
Event End Date:
17 August 2012
Publisher
Name*:
Springer
URL:
http://www.springer-ny.com/
Address*:
Berlin
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
7408
Number:
Month:
August
Pages:
134-145
Year*:
2012
VG Wort Pages:
12
ISBN/ISSN:
978-3-642-32511-3
Sequence Number:
DOI:
10.1007/978-3-642-32512-0_12
Note, Abstract, ©
(LaTeX) Abstract:
We consider online preemptive throughput scheduling of jobs with fixed
starting times on $m$ uniformly related machines, with the goal of
maximizing the profit of the completed jobs. In this problem, jobs are
released over time. 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 the competitive ratio for
scheduling unit weight jobs with varying sizes, which is tight. For
unit size and weight we show that a natural greedy algorithm is
$4/3$-competitive and optimal on $m=2$ machines, while for a large
$m$, its competitive ratio is between $1.56$ and $2$. Furthermore, no
algorithm is better than $1.5$-competitive.
Download
Access Level:
Internal

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{EpJeSS12,
AUTHOR = {Epstein, Leah and Jez, Lukasz and Sgall, Jiri and van Stee, Rob},
 EDITOR = {Gupta, Anupam and Jansen, Klaus and Rolim, Jos{\'e} and Servedio, Rocco},
 TITLE = {Online Scheduling of Jobs with Fixed Start Times on Related Machines},
 BOOKTITLE = {Approximation, Randomization, and Combinatorial Optimization : Algorithms and Techniques ; 15th International Workshop, APPROX 2012 and 16th International Workshop, RANDOM 2012},
 PUBLISHER = {Springer},
 YEAR = {2012},
 VOLUME = {7408},
 PAGES = {134--145},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Boston, USA},
 MONTH = {August},
 ISBN = {978-3-642-32511-3},
 DOI = {10.1007/978-3-642-32512-0_12},
}

Entry last modified by Anja Becker, 02/06/2013
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]		Created
11/14/2012 11:58:51
Revisions
2.
1.
0.

Editor(s)
Anja Becker
Rob van Stee
Rob van Stee

Edit Dates
31.01.2013 16:48:11
11/14/2012 03:02:23 PM
11/14/2012 11:58:51 AM