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):
Sitters, Renedblp

BibTeX cite key*:

Sitters2005

Title

Title*:

Complexity of preemptive minsum scheduling on unrelated parallel machines

Journal

Journal Title*:

Journal of Algorithms
Journal's URL:


Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:


Publisher's URL:


Publisher's
Address:


ISSN:


Vol, No, pp, Date

Volume*:

57
Number:

1

Publishing Date:

2005

Pages*:

37-48
Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) Abstract:

We show that the problems of minimizing total completion time and of minimizing the number of late jobs on unrelated parallel machines, when preemption is allowed, are both NP-hard in the strong sense. The former result settles a long-standing open question and is remarkable since the non-preemptive version is known to be solvable in polynomial time. A special case of the unrelated machine model is the identical machine model with the restriction that a job can only be processed on a specific subset of the machines. We show that in this model the problem of minimizing total completion time, when preemption is allowed, can be solved in polynomial time by proving that the use of preemption is redundant.

URL for the Abstract:


Categories,
Keywords:

NP-hard, Scheduling, Preemption, Total completion time

HyperLinks / References / URLs:

http://www.sciencedirect.com/science?_ob=MImg&_imagekey=B6WH3-4DFK6S9-2-1&_cdi=6839&_user=43521&_orig=search&_coverDate=09%2F30%2F2005&_sk=999429998&view=c&wchp=dGLbVtz-zSkzS&md5=a094e1c03eee38da2a0f8385477cd767&ie=/sdarticle.pdf

Copyright Message:


Personal Comments:


Download
Access Level:

Intranet

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:

@ARTICLE{Sitters2005,
AUTHOR = {Sitters, Rene},
 TITLE = {Complexity of preemptive minsum scheduling on unrelated parallel machines},
 JOURNAL = {Journal of Algorithms},
 YEAR = {2005},
 NUMBER = {1},
 VOLUME = {57},
 PAGES = {37--48},
}

Entry last modified by Christine Kiesel, 04/20/2006
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)
Rene Sitters		Created
03/07/2005 17:22:34
Revisions
4.
3.
2.
1.
0.		Editor(s)
Christine Kiesel
Rene Sitters
Rene Sitters
Rene Sitters
Rene Sitters		Edit Dates
20.04.2006 21:03:03
03/07/2005 05:44:48 PM
03/07/2005 05:38:20 PM
03/07/2005 05:23:34 PM
03/07/2005 05:22:34 PM