Algorithms for Scheduling a Single Machine to Minimize the Weighted Number of Late Jobs

C. N. Potts and L. N. Van Wassenhove
Additional contact information
C. N. Potts: Faculty of Mathematical Studies, University of Southampton, Southampton, England
L. N. Van Wassenhove: Afdeling Industrieel Beleid, Katholieke Universiteit Leuven, Belgium

Management Science, 1988, vol. 34, issue 7, 843-858

Abstract: This paper considers the problem of scheduling n jobs, each having a processing time, a due date and a weight, on a single machine to minimize the weighted number of late jobs. An O(n log n) algorithm is given for solving the linear programming problem obtained by relaxing the integrality constraints in a zero-one programming formulation of the problem. This linear programming lower bound is used in a reduction algorithm that eliminates jobs from the problem. Also, a branch and bound algorithm that uses the linear programming lower bound is proposed. Computational results with branch and bound algorithms that use this and other lower bounds and with a dynamic programming algorithm for problems with up to 1000 jobs are given.

Keywords: scheduling; reduction; dynamic programming; branch and bound (search for similar items in EconPapers)
Date: 1988
References: Add references at CitEc
Citations: View citations in EconPapers (22)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.34.7.843 (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:34:y:1988:i:7:p:843-858

Access Statistics for this article

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