nach oben

Journal of Scheduling

Erschienen in:

24.07.2019

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

verfasst von: Rubing Chen, Jinjiang Yuan

Erschienen in: Journal of Scheduling | Ausgabe 5/2019

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

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

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

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

Nur mit Berechtigung zugänglich

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

Titel: Unary NP-hardness of single-machine scheduling to minimize the total tardiness with deadlines
verfasst von: Rubing Chen
Jinjiang Yuan
Publikationsdatum: 24.07.2019
Verlag: Springer US
Erschienen in: Journal of Scheduling / Ausgabe 5/2019
Print ISSN: 1094-6136
Elektronische ISSN: 1099-1425
DOI: https://doi.org/10.1007/s10951-019-00615-9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 5/2019

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

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

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

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

Risk-averse single machine scheduling: complexity and approximation

Premium Partner