The Periodic Joint Replenishment Problem Is Strongly NP-Hard

• 成果类型: Article
• 署名作者: Cohen-Hillel, Tamar; Yedidsion, Liron
• 署名单位: Technion Israel Institute of Technology
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2017.0904
• 发表日期: 2018
• 页码: 1269-1289
• 关键词: determining order quantities; one-warehouse; algorithm; frequency

摘要

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 NP-hard.