A note on the single machine scheduling to minimize the number of tardy jobs with deadlines
A note on the single machine scheduling to minimize the number of tardy jobs with deadlines
复制标题
关于单机调度的注意事项，以最大限度地减少有期限的迟到作业数量
DOI：
10.1016/j.ejor.2009.05.013
复制
发表时间：
2010-03
影响因子：
6.4
通讯作者：
Yuan, Jinjiang
中科院分区：
文献类型：
--
作者：
He, Cheng;Lin, Yixun;Yuan, Jinjiang
已知最小化拖期工件数的单机排序问题是多项式可解的。然而，如果每个任务都有一个截止日期，它就变成了NP难的。最近，Huo等人通过向后调度方法解决了一些特殊情况。在本说明中，我们提出了一种双重方法-向前贪婪算法，它可能具有更好的运行时间。例如，在交货期、截止日期和处理时间都一致的情况下，向后调度算法的运行时间是O（n2），而向前调度算法的运行时间是O（nlogn）。
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(n2), while that of the forwards algorithm is O(nlogn).
登录
查看更多内容
DOI：
10.1016/j.ejor.2005.06.067
发表时间：
2007-02
期刊：
Eur. J. Oper. Res.
影响因子：
--
作者：
Yumei Huo;J. Leung;Hairong Zhao
通讯作者：
Yumei Huo;J. Leung;Hairong Zhao
DOI：
10.1201/9781420049503-c36
发表时间：
2004-12
期刊：
Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture
影响因子：
--
作者：
David R Karger;C. Stein;J. Wein
通讯作者：
David R Karger;C. Stein;J. Wein
DOI：
--
发表时间：
1983
期刊：
--
影响因子：
--
作者：
E. Lawler
通讯作者：
E. Lawler
DOI：
10.1016/j.ejor.2005.09.017
发表时间：
2007-01
期刊：
Eur. J. Oper. Res.
影响因子：
--
作者：
Yixun Lin;Xiumei Wang
通讯作者：
Yixun Lin;Xiumei Wang
DOI：
10.1007/978-3-662-56039-6
发表时间：
2007-11
期刊：
--
影响因子：
--
作者：
B. Korte;J. Vygen
通讯作者：
B. Korte;J. Vygen