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.
No takes yet. Share an insight, caveat, or question.
Lenstra et al. (1978) studied this question.
Synapse has enriched 3 closely related papers on similar clinical questions. Consider them for comparative context: