Single Machine Scheduling to Minimize Total Late Work

C. N. Potts and L. N. Van Wassenhove
Additional contact information
C. N. Potts: University of Southampton, Southampton, United Kingdom
L. N. Van Wassenhove: INSEAD, Fontainebleau, France

Operations Research, 1992, vol. 40, issue 3, 586-595

Abstract: In the problem of scheduling a single machine to minimize total late work, there are n jobs to be processed for which each has an integer processing time and a due date. The objective is to minimize the total late work, where the late work for a job is the amount of processing of this job that is performed after its due date. For the preemptive total late work problem, an O ( n log n ) algorithm is derived. The nonpreemptive total late work problem is shown to be NP-hard, although efficient algorithms are derived for the special cases in which all processing times are equal and all due dates are equal. A pseudopolynomial dynamic programming algorithm is presented for the general nonpreemptive total late work problem; it requires O ( n UB) time, where UB is any upper bound on the total late work. Computational results for problems with up to 10,000 jobs are given.

Keywords: production/scheduling: single machine scheduling; programming; integer; algorithms: dynamic programming (search for similar items in EconPapers)
Date: 1992
References: Add references at CitEc
Citations: View citations in EconPapers (27)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.40.3.586 (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:oropre:v:40:y:1992:i:3:p:586-595

Access Statistics for this article

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