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.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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 248
Cited by
Chapter 9 Sequencing and scheduling: Algorithms and complexity
Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G., & Shmoys, D. B. (1993) · Handbooks in Operations Research and Management Science · doi:10.1016/s0927-0507(05)80189-6 · Cited by 761
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
A Survey of Traffic Control With Vehicular Communications
Li, L., Wen, D., & Yao, D. (2014) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2013.2277737 · Cited by 304
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
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
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.