Name
Abstract | ||
|---|---|---|
Precedence constraints between jobs that have to be respected in every feasible schedule generally increase the computational complexity of a scheduling problem. Occasionally, their introduction may turn a problem that is solvable within polynomial time into an NP-complete one, for which a good algorithm is highly unlikely to exist. We illustrate the use of these concepts by extending some typical NP-completeness results and simplifying their correctness proofs for scheduling problems involving precedence constraints. |
Year | DOI | Venue |
|---|---|---|
1978 | 10.1287/opre.26.1.22 | Operations Research |
Field | DocType | Volume |
Mathematical optimization,Correctness proofs,Job shop scheduling,Scheduling (computing),Precedence diagram method,Time complexity,Mathematics,Computational complexity theory | Journal | 26 |
Issue | ISSN | Citations |
1 | 0030-364X | 213 |
PageRank | References | Authors |
35.98 | 9 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| J. K. Lenstra | 1 | 1689 | 329.39 |
| A. H. G. Rinnooy Kan | 2 | 2109 | 497.45 |