科研之友
微信
新浪微博
Facebook
分享链接
摘要
For single machine scheduling to minimize the number of tardy jobs with deadlines, Lawler showed in 1983 that the problem is binary NP-hard. But the exact complexity (unary NP-hard or pseudo-polynomial-time solvability) is a long- standing open problem. We show in this paper that the problem is unary NP-hard. Our research also implies that the scheduling problem for finding an optimal schedule to minimize the number of tardy jobs that also satisfies the restriction of deadlines is unary NP-hard. As a consequence, some multi-agent scheduling problems related to minimizing the number of tardy jobs and maximum lateness are unary NP-hard.
- 出版日期2017-4
- 单位郑州大学
