Earliness-Tardiness Scheduling Problems, I: Weighted Deviation of Completion Times About a Common Due Date

Nicholas G. Hall and Marc E. Posner
Additional contact information
Nicholas G. Hall: The Ohio State University, Columbus, Ohio
Marc E. Posner: The Ohio State University, Columbus, Ohio

Operations Research, 1991, vol. 39, issue 5, 836-846

Abstract: This paper and its companion (Part II) concern the scheduling of jobs with cost penalties for both early and late completion. In Part I, we consider the problem of minimizing the weighted sum of earliness and tardiness of jobs scheduled on a single processor around a common due date, d . We assume that d is not early enough to constrain the scheduling decision. The weight of a job does not depend on whether the job is early or late, but weights may vary between jobs. We prove that the recognition version of this problem is NP-complete in the ordinary sense. We describe optimality conditions, and present a computationally efficient dynamic programming algorithm. When the weights are bounded by a polynomial function of the number of jobs, a fully polynomial approximation scheme is given. We also describe four special cases for which the problem is polynomially solvable. Part II provides similar results for the unweighted version of this problem, where d is arbitrary.

Keywords: dynamic programming; deterministic: earliness and lateness costs; production/scheduling: deterministic sequencing; single machine (search for similar items in EconPapers)
Date: 1991
References: Add references at CitEc
Citations: View citations in EconPapers (76)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.39.5.836 (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:39:y:1991:i:5:p:836-846

Access Statistics for this article

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