The DOI matches its Crossref record; 9 of the 9 references it cites were found in a registry or an index.
Minimizing Total Tardiness on One Machine is NP-Hard
Abstract
The problem of minimizing the total tardiness for a set of independent jobs on one machine is considered. Lawler has given a pseudo-polynomial-time algorithm to solve this problem. In spite of extensive research efforts for more than a decade, the question of whether it can be solved in polynomial time or it is NP-hard (in the ordinary sense) remained open. In this paper the problem is shown to be NP-hard (in the ordinary sense).
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1979) · Cited by 43,841
Introduction to Sequencing and Scheduling
Clewett, A. J., & Baker, K. R. (1977) · Operational Research Quarterly (1970-1977) · doi:10.2307/3009192 · Cited by 2,597
Computer and job-shop scheduling theory
Coffman, E. G., & Bruno, J. L. (1976) · Medical Entomology and Zoology · Cited by 1,107
Scheduling with Deadlines and Loss Functions
McNaughton, R. (1959) · Management Science · doi:10.1287/mnsc.6.1.1 · Cited by 848
A “Pseudopolynomial” Algorithm for Sequencing Jobs to Minimize Total Tardiness
Lawler, E. L. (1977) · Annals of Discrete Mathematics · doi:10.1016/s0167-5060(08)70742-8 · Cited by 610
Machine Scheduling Problems: Classification, complexity and computations
Kan, R. (1976) · Medical Entomology and Zoology · Cited by 478
One-Machine Sequencing to Minimize Certain Functions of Job Tardiness
Emmons, H. (1969) · Operations Research · doi:10.1287/opre.17.4.701 · Cited by 348
Recent Developments in Deterministic Sequencing and Scheduling: A Survey
Lawler, E. L., Lenstra, J. K., & Kan, A. H. G. R. (1982) · Springer eBooks · doi:10.1007/978-94-009-7801-0_3 · Cited by 325
Minimizing Total Costs in One-Machine Scheduling
Kan, A. H. G. R., Lageweg, B. J., & Lenstra, J. K. (1975) · Operations Research · doi:10.1287/opre.23.5.908 · Cited by 205
Cited by
A state-of-the-art review on scheduling with learning effects
Biskup, D. (2008) · European Journal of Operational Research · doi:10.1016/j.ejor.2007.05.040 · Cited by 704
Scheduling jobs on parallel machines with sequence-dependent setup times
Lee, Y. H., & Pinedo, M. (1997) · European Journal of Operational Research · doi:10.1016/s0377-2217(95)00376-2 · Cited by 273
Quantum Approximate Optimization with Hard and Soft Constraints
Hadfield, S., Wang, Z., Rieffel, E. G., O'Gorman, B., Venturelli, D., & Biswas, R. (2017) · Proceedings of the Second International Workshop on Post Moores Era Supercomputing · doi:10.1145/3149526.3149530 · Cited by 51
Minimizing Total Weighted Tardiness on a Single Machine with Release Dates and Equal-Length Jobs
van den Akker, J. M., Diepen, G., & Hoogeveen, J. A. (2010) · Journal of Scheduling · doi:10.1007/s10951-010-0181-1 · Cited by 30
Combining predictive and prescriptive techniques for optimizing electric vehicle fleet charging
Mahyari, E., Freeman, N., & Yavuz, M. (2023) · Transportation Research Part C: Emerging Technologies · doi:10.1016/j.trc.2023.104149 · Cited by 13
Metadata
- Authors
- Du, J., & Leung, J. Y.-T.
- Venue
- Mathematics of Operations Research
- Published
- 1990-08
- Volume
- 15
- Issue
- 3
- Pages
- 483-495
- ISSN
- 0364-765X (ISSN-L)
- 1526-5471
- OpenAlex
- W2030250600
- Cited by
- 744
- References
- 9
- FWCI
- 40.93
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Minimizing Total Tardiness on One Machine is NP-Hard. https://app.cochat.ai/papers/10.1287/moor.15.3.483
- The paper
- Du, J., & Leung, J. Y.-T. (1990). Minimizing Total Tardiness on One Machine is NP-Hard. Mathematics of Operations Research. https://doi.org/10.1287/moor.15.3.483
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.