Top

Journal of Scheduling

Published in:

12-08-2021

A note on the complexity of two supply chain scheduling problems

Authors: Yuan Zhang, Jinjiang Yuan

Published in: Journal of Scheduling | Issue 4/2021

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

search-config

AI-assisted search

Off

Abstract

We consider two supply chain scheduling problems in which s suppliers preprocess different parts of the jobs to be assembled by the manufacturer under the common sequence constraint, with the goal of minimizing the total weighted number of tardy parts and minimizing the total late work of the parts, respectively. Ren et al. (Information Processing Letter 113: 609-601, 2013) showed that both of the above two problems are unary NP-hard. But their proof is invalid. In this paper, we present a new proof of the unary NP-hardness for the same problems.

previous article Online scheduling to minimize total weighted (modified) earliness and tardiness cost

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

Agnetis, A., Hall, N. G., & Pacciarelli, D. (2006). Supply chain scheduling: sequence coordination. Discrete Applied Mathematics, 154, 2044–2063.

Chen, Z. L., & Hall, N. G. (2007). Supply chain scheduling: conflict and cooperation in assembly systems. Operations Research, 55, 1072–1089.CrossRef

Dawande, M., Geismar, H. N., Hall, N. G., & Sriskandarajah, C. (2006). Supply chain scheduling: distribution systems. Production and Operations Management, 15, 243–261.CrossRef

Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: a guide to the theory of np-completeness. NewYork: W.H. Freeman.

Hall, N. G., & Potts, C. N. (2003). Supply chain scheduling: batching and delivery. Operations Research, 51, 566–584.CrossRef

Ng, C. T., Cheng, T. C. E., & Yuan, J. J. (2003). Concurrent open shop scheduling to minimize the weighted number of tardy jobs. Journal of Scheduling, 6, 405–412.CrossRef

Ren, J. F., Du, D. L., & Xu, D. C. (2013). The complexity of two supply chain scheduling problems. Information Processing Letters, 113, 609–612.CrossRef

Sarmieto, A. M., & Nagi, R. (1999). A review of integrated analysis of production-distribution systems. IIE Transactions, 31, 1061–1074.

Thomas, D. J., & Griffin, P. M. (1996). Coordinated supply chain managament. European Journal of Operational Research, 94, 1–15.CrossRef

Title: A note on the complexity of two supply chain scheduling problems
Authors: Yuan Zhang
Jinjiang Yuan
Publication date: 12-08-2021
Publisher: Springer US
Published in: Journal of Scheduling / Issue 4/2021
Print ISSN: 1094-6136
Electronic ISSN: 1099-1425
DOI: https://doi.org/10.1007/s10951-021-00692-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 4/2021

Scheduling with gaps: new models and algorithms

A new algorithm for the two-machine open shop and the polynomial solvability of a scheduling problem with routing

Routing two stacking cranes with predetermined container sequences

Online scheduling to minimize total weighted (modified) earliness and tardiness cost

A memetic algorithm to address the multi-node resource-constrained project scheduling problem