Top

Journal of Scheduling

Published in:

11-07-2019

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

Authors: Mikhail Y. Kovalyov, Dmitrij Šešok

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

Tang et al. (Eur J Oper Res 263:401–411, 2017) have recently introduced a parallel-batching machine scheduling problem with linearly deteriorating jobs of two agents and presented a computational complexity classification of various special cases of this problem, including a number of NP-hardness proofs. We refine these results by demonstrating strong NP-hardness of several special cases, which are proved NP-hard in the ordinary sense in Tang et al. (Eur J Oper Res 263:401–411, 2017). Our reduction employs the problem studied in the first issue of Journal of Scheduling.

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

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

Brucker, P., Gladky, A., Hoogeveen, H., Kovalyov, M. Y., Potts, C. N., Tautenhahn, T., et al. (1998). Scheduling a batching machine. Journal of Scheduling, 1, 31–54.CrossRef

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

Li, S. S., Ng, C. T., Cheng, T. C. E., & Yuan, J. J. (2011). Parallel-batch scheduling of deteriorating jobs with release dates to minimize the makespan. European Journal of Operational Research, 210, 482–488.CrossRef

Tang, L., Zhao, X., Liu, J., & Leung, J. Y.-T. (2017). Competitive two-agent scheduling with deteriorating jobs on a single parallel-batching machine. European Journal of Operational Research, 263, 401–411.CrossRef

Title: Two-agent scheduling with deteriorating jobs on a single parallel-batching machine: refining computational complexity
Authors: Mikhail Y. Kovalyov
Dmitrij Šešok
Publication date: 11-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-00613-x

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

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

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

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