Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
478733 | European Journal of Operational Research | 2010 | 5 Pages |
Abstract
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)O(n2), while that of the forwards algorithm is O(nlogn)O(nlogn).
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Cheng He, Yixun Lin, Jinjiang Yuan,