The periodic joint replenishment problem is strongly NP -hard
From MaRDI portal
Publication:5219699
DOI10.1287/MOOR.2017.0904zbMATH Open1440.90096DBLPjournals/mor/Cohen-HillelY18arXiv1511.02454OpenAlexW2964198111WikidataQ59281086 ScholiaQ59281086MaRDI QIDQ5219699FDOQ5219699
Authors: Tamar Cohen-Hillel, Liron Yedidsion 
Publication date: 12 March 2020
Published in: Mathematics of Operations Research (Search for Journal in Brave)
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 were suggested. However, in spite of the vast effort, the complexity of the problem remained unresolved. In this paper, we provide a proof that the problem is indeed strongly NP-hard.
Full work available at URL: https://arxiv.org/abs/1511.02454
Recommendations
- NP-hardness proof for the assembly problem with stationary setup and additive holding costs
- Approximation algorithms and hardness results for the joint replenishment problem with constant demands
- Algorithmic Applications in Management
- On the computational complexity of uncapacitated multi-plant lot-sizing problems
- Computational complexity of uncapacitated multi-echelon production planning problems
Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Inventory, storage, reservoirs (90B05)
Cites Work
- Joint replenishment inventory control: Deterministic and stochastic models
- A review of the joint replenishment problem literature: 1989--2005
- Title not available (Why is that?)
- A Simple Method of Determining Order Quantities in Joint Replenishments Under Deterministic Demand
- On optimal algorithms for the joint replenishment problem
- A new method for joint replenishment problems
- A New Optimal Algorithm for the Joint Replenishment Problem
- A Note on the Joint Replenishment Problem under Constant Demand
- Computational complexity of uncapacitated multi-echelon production planning problems
- A constant approximation algorithm for the one-warehouse multiretailer problem
- Title not available (Why is that?)
- Primal-Dual Algorithms for Deterministic Inventory Problems
- Approximate formulas for some functions of prime numbers
- Bounded gaps between primes
- Bounded gaps between primes in special sequences
- Foundations of inventory management
- Approximation algorithms and hardness results for the joint replenishment problem with constant demands
- The Joint Replenishment Problem: New Heuristics and Worst Case Performance Bounds
- Multistage Lot Sizing Problems via Randomized Rounding
- A 5/3-Approximation Algorithm for Joint Replenishment with Deadlines
- 98%-Effective Integer-Ratio Lot-Sizing for One-Warehouse Multi-Retailer Systems
- An efficient polynomial-time approximation scheme for the joint replenishment problem
- An approximate dynamic-programming approach to the joint replenishment problem
- A global optimum search algorithm for the joint replenishment problem under power-of-two policy.
- An efficient optimal solution method for the joint replenishment problem
- The joint replenishment problem with resource restriction
- Analysis of Joint Replenishment Inventory Systems with Resource Restriction
- Title not available (Why is that?)
- An efficient optimal solution method for the joint replenishment problem with minimum order quantities
- Title not available (Why is that?)
- Approximation Procedures for the One-Warehouse Multi-Retailer System
- Determination of Economic Packaging Frequency for Items Jointly Replenished
Cited In (7)
- Complexity of the Project Sequencing Problem
- NP-hardness proof for the assembly problem with stationary setup and additive holding costs
- Efficient methods for stochastic joint replenishment and delivery problem
- On product covering in 3-tier supply chain models: natural complete problems for W[3] and W[4]
- Optimization of a stochastic joint replenishment inventory system with service level constraints
- Optimizing a multi-echelon location-inventory problem with joint replenishment: a Lipschitz \(\epsilon\)-optimal approach using Lagrangian relaxation
- The joint replenishment problem with trade credits
This page was built for publication: The periodic joint replenishment problem is strongly \(\mathcal{NP} \)-hard
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5219699)
