The periodic joint replenishment problem is strongly NP -hard

DOI10.1287/MOOR.2017.0904MaRDI QIDQ5219699zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Tamar Cohen-Hillel, Liron Yedidsion

Publication date 12 March 2020

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.02454

zbMATH Keywords

computational complexitysupply chain managementtwin primesjoint replenishment problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Inventory, storage, reservoirs (90B05)

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.

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

Cites work

• scientific article; zbMATH DE number 1185840 (Why is no real title available?)
• scientific article; zbMATH DE number 3657869 (Why is no real title available?)
• scientific article; zbMATH DE number 44978 (Why is no real title available?)
• scientific article; zbMATH DE number 861252 (Why is no real title available?)
• 98%-Effective Integer-Ratio Lot-Sizing for One-Warehouse Multi-Retailer Systems
• A 5/3-Approximation Algorithm for Joint Replenishment with Deadlines
• A New Optimal Algorithm for the Joint Replenishment Problem
• A Note on the Joint Replenishment Problem under Constant Demand
• A Simple Method of Determining Order Quantities in Joint Replenishments Under Deterministic Demand
• A constant approximation algorithm for the one-warehouse multiretailer problem
• A global optimum search algorithm for the joint replenishment problem under power-of-two policy.
• A new method for joint replenishment problems
• A review of the joint replenishment problem literature: 1989--2005
• An approximate dynamic-programming approach to the joint replenishment problem
• An efficient optimal solution method for the joint replenishment problem
• An efficient optimal solution method for the joint replenishment problem with minimum order quantities
• An efficient polynomial-time approximation scheme for the joint replenishment problem
• Analysis of Joint Replenishment Inventory Systems with Resource Restriction
• Approximate formulas for some functions of prime numbers
• Approximation Procedures for the One-Warehouse Multi-Retailer System
• Approximation algorithms and hardness results for the joint replenishment problem with constant demands
• Bounded gaps between primes
• Bounded gaps between primes in special sequences
• Computational complexity of uncapacitated multi-echelon production planning problems
• Determination of Economic Packaging Frequency for Items Jointly Replenished
• Foundations of inventory management
• Joint replenishment inventory control: Deterministic and stochastic models
• Multistage Lot Sizing Problems via Randomized Rounding
• On optimal algorithms for the joint replenishment problem
• Primal-Dual Algorithms for Deterministic Inventory Problems
• The Joint Replenishment Problem: New Heuristics and Worst Case Performance Bounds
• The joint replenishment problem with resource restriction

Cited in

(8)

• The joint replenishment problem with trade credits
• Optimizing a multi-echelon location-inventory problem with joint replenishment: a Lipschitz \(\epsilon\)-optimal approach using Lagrangian relaxation
• Integer factorization: Why two-item joint replenishment is hard
• On product covering in 3-tier supply chain models: natural complete problems for W[3] and W[4]
• NP-hardness proof for the assembly problem with stationary setup and additive holding costs
• Optimization of a stochastic joint replenishment inventory system with service level constraints
• Efficient methods for stochastic joint replenishment and delivery problem
• Complexity of the Project Sequencing Problem

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)