科研之友
微信
新浪微博
Facebook
分享链接
摘要
It is known that the single machine scheduling problem of minimizing the number of tardy jobs is polynomially solvable. However, it becomes NP-hard if each job has a deadline. Recently, Huo et al. solved some special cases by a backwards scheduling approach. In this note we present a dual approach-forwards greedy algorithms which may have better running time. For example, in the case that the due dates, deadlines, and processing times are agreeable, the running time of the backwards scheduling algorithm is O(n(2)), while that of the forwards algorithm is O(n log n).
- 出版日期2010-3-16
- 单位中国人民解放军信息工程大学; 郑州大学
