The Periodic Joint Replenishment Problem Is Strongly NP-Hard

被引：14
作者：
Cohen-Hillel, Tamar [1 ]
Yedidsion, Liron [2 ]
机构：
[1] Massachusetts Inst Technol Hillel, Operat Res Ctr, Cambridge, MA 02139 USA
[2] Technion Israel Inst Technol, Fac Ind Engn & Management, IL-3200003 Haifa, Israel
来源：
MATHEMATICS OF OPERATIONS RESEARCH | 2018年 / 43卷 / 04期
基金：
以色列科学基金会;
关键词：
computational complexity; joint replenishment problem; supply chain management; twin primes; DETERMINING ORDER QUANTITIES; ONE-WAREHOUSE; ALGORITHM; FREQUENCY;
D O I：
10.1287/moor.2017.0904
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
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.
引用
收藏
页码：1269 / 1289
页数：21
相关论文
共 49 条
12345