| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 10523991 | Operations Research Letters | 2005 | 10 Pages |
Abstract
We present various complexity results for scheduling unit-time jobs subject to OR-precedence constraints. We prove that minimizing the total weighted completion time is strongly NP-hard, even on a single machine. In contrast, we give a polynomial-time algorithm for minimizing the makespan and the total completion time on identical parallel machines.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Berit Johannes,