A note on the single machine scheduling to minimize the number of tardy jobs with deadlines

Cheng He, Yixun Lin and Jinjiang Yuan

European Journal of Operational Research, 2010, vol. 201, issue 3, 966-970

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), while that of the forwards algorithm is O(nlogn).

Keywords: Scheduling; Number; of; tardy; jobs; Deadline; Independent; set (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377-2217(09)00345-2
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:201:y:2010:i:3:p:966-970

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().