The Periodic Joint Replenishment Problem Is Strongly 𝒩𝒫-Hard

Tamar Cohen-Hillel () and Liron Yedidsion ()
Additional contact information
Tamar Cohen-Hillel: Operations Research Center, Massachusetts Institute of Technology–Hillel, Cambridge, Massachusetts 02139
Liron Yedidsion: Faculty of Industrial Engineering and Management, Technion–Israel Institute of Technology, Haifa 3200003, Israel

Mathematics of Operations Research, 2018, vol. 43, issue 4, 1269-1289

Abstract: In this paper, we study the long-standing open question regarding the computational complexity of one of the core problems in supply chains management, the periodic joint replenishment problem. This problem has received a lot of attention over the years, and many heuristic and approximation algorithms have been suggested. However, in spite of the vast effort, the complexity of the problem remains unresolved. In this paper, we provide a proof that the problem is indeed strongly 𝒩𝒫-hard.

Keywords: computational complexity; joint replenishment problem; supply chain management; twin primes (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://doi.org/10.1287/moor.2017.0904 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:43:y:2018:i:4:p:1269-1289

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().