Minimizing the number of tardy jobs with precedence constraints and agreeable due dates

✍ Scribed by George Steiner

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 713 KB
• Volume: 72
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(96)00043-1

✦ Synopsis

Minimizing

the number of precedence constrained, unit-time tardy jobs is strongly NP-hard on a single machine. We study a special case of the problem where a job is tardy if it is finished more than a fixed K time units after its earliest possible completion time under the precedence constraints. We prove that the problem remains strongly NP-hard even with these special due dates. We also present polynomial time solutions for the weighted version of the problem if the precedence constraints are out-forests or interval orders. In the process, we also present a polynomial time solution for a special case of the minimum weight hitting set problem.