On the complexity of scheduling unit-time jobs with OR-precedence constraints |
| |
Authors: | Berit Johannes |
| |
Affiliation: | Institut für Mathematik, Sekr. MA 6-1, Technische Universität Berlin, Strasse des 17. Juni 136, 10623 Berlin, Germany |
| |
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. |
| |
Keywords: | Scheduling Precedence constraints O smallcaps" >R-networks Computational complexity |
本文献已被 ScienceDirect 等数据库收录! |
|