Two NP-hardness results for preemptive minsum scheduling of unrelated parallel machines

Renè Sitters*

*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

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.

Original languageEnglish
Title of host publicationInteger Programming and Combinatorial Optimization - 8th International IPCO Conference, Proceedings
PublisherSpringer/Verlag
Pages396-405
Number of pages10
Volume2081
ISBN (Print)3540422250, 9783540422259
Publication statusPublished - 2001
Event8th International Integer Programming and Combinatorial Optimization Conference, IPCO 2001 - Utrecht, Netherlands
Duration: 13 Jun 200115 Jun 2001

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2081
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

Conference8th International Integer Programming and Combinatorial Optimization Conference, IPCO 2001
CountryNetherlands
CityUtrecht
Period13/06/0115/06/01

Fingerprint

Dive into the research topics of 'Two NP-hardness results for preemptive minsum scheduling of unrelated parallel machines'. Together they form a unique fingerprint.

Cite this