Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2023) | last year (2022) | two years ago (2021) | Notes URL

Action:

login to update
Options:








Author, Editor(s)
Author(s):
Hoogeveen, Han
Skutella, Martin
Woeginger, Gerhard J.		dblp
dblp
dblp
Not MPG Author(s):
Hoogeveen, Han
Woeginger, Gerhard J.

BibTeX cite key*:

HoogeveenSkutellaWoeginger2003

Title

Title*:

Preemptive scheduling with rejection

Journal

Journal Title*:

Mathematical Programming
Journal's URL:

http://www.springerlink.com/link.asp?id=103081

Download URL
for the article:

http://www.springerlink.com/link.asp?id=cf68mtx6vn2c5qa2
Language:

English

Publisher

Publisher's
Name:

Springer
Publisher's URL:

http://www.springer.de/

Publisher's
Address:

Berlin, Germany
ISSN:

0025-5610

Vol, No, pp, Date

Volume*:

94
Number:

2-3

Publishing Date:

January 2003

Pages*:

361-374
Number of
VG Pages:

20

Page Start:

361
Page End:

374

Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) Abstract:

We consider the problem of preemptively scheduling a set of $n$ jobs
on $m$ (identical, uniformly related, or unrelated) parallel
machines. The scheduler may reject a subset of the jobs and thereby
incur job-dependent penalties for each rejected job, and he must
construct a schedule for the remaining jobs so as to optimize the
preemptive makespan on the $m$ machines plus the sum of the
penalties of the jobs rejected.

We provide a complete classification of these scheduling problems
with respect to complexity and approximability. Our main results
are on the variant with an arbitrary number of unrelated machines.
This variant is \apx-hard, and we design a $1.58$-approximation
algorithm for it. All other considered variants are weakly
\np-hard, and we provide fully polynomial time approximation schemes
for them. Finally, we argue that our results for unrelated machines
can be carried over to the corresponding preemptive open shop
scheduling problem with rejection.

URL for the Abstract:


Categories,
Keywords:

scheduling, preemption, approximation algorithm, worst case ratio, computational complexity, in-approximability

HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Intranet

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


BibTeX Entry:

@ARTICLE{HoogeveenSkutellaWoeginger2003,
AUTHOR = {Hoogeveen, Han and Skutella, Martin and Woeginger, Gerhard J.},
 TITLE = {Preemptive scheduling with rejection},
 JOURNAL = {Mathematical Programming},
 PUBLISHER = {Springer},
 YEAR = {2003},
 NUMBER = {2-3},
 VOLUME = {94},
 PAGES = {361--374},
 ADDRESS = {Berlin, Germany},
 MONTH = {January},
 ISBN = {0025-5610},
}

Entry last modified by Christine Kiesel, 06/15/2004
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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)
Martin Skutella		Created
01/19/2004 13:14:06
Revisions
3.
2.
1.
0.
Editor(s)
Christine Kiesel
Christine Kiesel
Martin Skutella
Martin Skutella
Edit Dates
15.06.2004 18:03:12
09.06.2004 16:44:38
04.05.2004 16:11:41
19.01.2004 13:14:06