Top

Journal of Scheduling

Published in:

24-07-2019

Unary NP-hardness of single-machine scheduling to minimize the total tardiness with deadlines

Authors: Rubing Chen, Jinjiang Yuan

Published in: Journal of Scheduling | Issue 5/2019

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We revisit the classical single-machine scheduling problem to minimize total tardiness with deadlines. The problem is binary NP-hard even without the deadline restrictions. It was reported early in Koulamas and Kyparisis (Eur J Oper Res 133:447–453, 2001) that the exact complexity (unary NP-hardness or pseudo-polynomial-time solvability) of the problem is still open. We show that this problem is unary NP-hard.

previous article The complexity of CO-agent scheduling to minimize the total completion time and total number of tardy jobs

next article Two-agent scheduling with deteriorating jobs on a single parallel-batching machine: refining computational complexity

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

Du, J. Z., & Leung, J. Y. T. (1990). Minimizing total tardiness on one machine is NP-hard. Mathematics of Operations Research, 15, 483–495.CrossRef

Emmons, H. (1969). One-machine sequencing to minimize certain functions of job tardiness. Operations Research, 17, 701–715.CrossRef

Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. San Francisco: Freeman.

Graham, R. L., Lawler, E. L., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5, 287–326.CrossRef

Koulamas, C., & Kyparisis, G. J. (2001). Single machine scheduling with release times, deadlines and tardiness objectives. European Journal of Operational Research, 133, 447–453.CrossRef

Lawler, E. L. (1977). A pseudopolynomial algorithm for sequencing jobs to minimize total tardiness. Annals of Discrete Mathematics, 1, 331–342.CrossRef

Yuan, J. J. (2017). Unary NP-hardness of minimizing the number of tardy jobs with deadlines. Journal of Scheduling, 20, 211–218.CrossRef

Title: Unary NP-hardness of single-machine scheduling to minimize the total tardiness with deadlines
Authors: Rubing Chen
Jinjiang Yuan
Publication date: 24-07-2019
Publisher: Springer US
Published in: Journal of Scheduling / Issue 5/2019
Print ISSN: 1094-6136
Electronic ISSN: 1099-1425
DOI: https://doi.org/10.1007/s10951-019-00615-9

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 5/2019

Two-agent scheduling with deteriorating jobs on a single parallel-batching machine: refining computational complexity

A unified view of parallel machine scheduling with interdependent processing rates

The complexity of CO-agent scheduling to minimize the total completion time and total number of tardy jobs

Risk-averse single machine scheduling: complexity and approximation

Single-machine common due date total earliness/tardiness scheduling with machine unavailability

A decomposition-based approach to the scheduling of identical automated yard cranes at container terminals