Earliness–Tardiness Scheduling Problems, II: Deviation of Completion Times About a Restrictive Common Due Date

Nicholas G. Hall, Wieslaw Kubiak and Suresh Sethi
Additional contact information
Nicholas G. Hall: The Ohio State University, Columbus, Ohio
Wieslaw Kubiak: Memorial University of Newfoundland, St. John's, Newfoundland, Canada

Operations Research, 1991, vol. 39, issue 5, 847-856

Abstract: A companion paper (Part I) considers the problem of minimizing the weighted earliness and tardiness of jobs scheduled on a single machine around a common due date, d , which is unrestrictively late. This paper (Part II) considers the problem of minimizing the unweighted earliness and tardiness of jobs, allowing the possibility that d is early enough to constrain the scheduling decision. We describe several optimality conditions. The recognition version of the problem is shown to be NP-complete in the ordinary sense, confirming a well known conjecture. Moreover, this complexity definition is precise, since we describe a dynamic programming algorithm which runs in pseudopolynomial time. This algorithm is also extremely efficient computationally, providing an improvement over earlier procedures, of almost two orders of magnitude in the size of instance that can be solved. Finally, we describe a special case of the problem which is polynomially solvable.

Keywords: production/scheduling: deterministic; single machine sequencing (search for similar items in EconPapers)
Date: 1991
References: Add references at CitEc
Citations: View citations in EconPapers (68)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.39.5.847 (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:847-856

Access Statistics for this article

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