English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 Local TagsRelease HistoryDetailsSummary
  Complexity of preemptive minsum scheduling on unrelated parallel machines

Sitters, R. (2005). Complexity of preemptive minsum scheduling on unrelated parallel machines. Journal of Algorithms, 57, 37-48.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-2618-8 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-2619-6
Genre: Journal Article

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Sitters, Rene1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2006-04-202005
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: Peer
 Identifiers: eDoc: 279132
Other: Local-ID: C1256428004B93B8-C0B54335904FA68CC1256FBD0059F527-Sitters2005
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Journal of Algorithms
Source Genre: Journal
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 57 Sequence Number: - Start / End Page: 37 - 48 Identifier: -