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 language | English |
|---|---|
| Title of host publication | Integer Programming and Combinatorial Optimization - 8th International IPCO Conference, Proceedings |
| Publisher | Springer/Verlag |
| Pages | 396-405 |
| Number of pages | 10 |
| Volume | 2081 |
| ISBN (Print) | 3540422250, 9783540422259 |
| Publication status | Published - 2001 |
| Event | 8th International Integer Programming and Combinatorial Optimization Conference, IPCO 2001 - Utrecht, Netherlands Duration: 13 Jun 2001 → 15 Jun 2001 |
Publication series
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 2081 |
| ISSN (Print) | 03029743 |
| ISSN (Electronic) | 16113349 |
Conference
| Conference | 8th International Integer Programming and Combinatorial Optimization Conference, IPCO 2001 |
|---|---|
| Country/Territory | Netherlands |
| City | Utrecht |
| Period | 13/06/01 → 15/06/01 |
UN SDGs
This output contributes to the following UN Sustainable Development Goals (SDGs)
-
SDG 8 Decent Work and Economic Growth
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
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver