Single Machine Scheduling with Deadlines to Minimize the Weighted Number of Tardy Jobs

A. M. A. Hariri and C. N. Potts
Additional contact information
A. M. A. Hariri: Department of Statistics, King Abdul-Aziz University, Jeddah, Saudi Arabia
C. N. Potts: Faculty of Mathematical Studies, University of Southamption, United Kingdom

Management Science, 1994, vol. 40, issue 12, 1712-1719

Abstract: This paper considers as single machine scheduling problem in which jobs have due dates and deadlines. A job may be completed after its due date, but not after its deadline, in which case it is tardy. A branch and bound algorithm is proposed to find a schedule which minimizes the weighted number of tardy jobs. It uses lower bounds which are derived using the dynamic programming state-space relaxation method. Computational experience with test problems having up to 300 jobs indicates that the lower bounds are extremely effective in restricting the size of the branch and bound search tree.

Keywords: single machine scheduling; due date; deadline; dynamic programming; state-space relaxation; branch and bound (search for similar items in EconPapers)
Date: 1994
References: Add references at CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.40.12.1712 (application/pdf)

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:inm:ormnsc:v:40:y:1994:i:12:p:1712-1719

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().