Better Approximation Bounds for the Joint Replenishment Problem

DOI10.1137/1.9781611973402.4MaRDI QIDQ5383963zbMATH OpenOpenAlexFDO

Authors Marcin Bienkowski, Jaroslaw Byrka, Łukasz Jeż, Dorian Nogneng, Jiří Sgall, Marek Chrobak

Publication date 20 June 2019

Published in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27) Inventory, storage, reservoirs (90B05) Transportation, logistics and supply chain management (90B06)

Abstract: The Joint Replenishment Problem (JRP) deals with optimizing shipments of goods from a supplier to retailers through a shared warehouse. Each shipment involves transporting goods from the supplier to the warehouse, at a fixed cost C, followed by a redistribution of these goods from the warehouse to the retailers that ordered them, where transporting goods to a retailer $ho$ has a fixed cost $c_{h}o$. In addition, retailers incur waiting costs for each order. The objective is to minimize the overall cost of satisfying all orders, namely the sum of all shipping and waiting costs. JRP has been well studied in Operations Research and, more recently, in the area of approximation algorithms. For arbitrary waiting cost functions, the best known approximation ratio is 1.8. This ratio can be reduced to 1.574 for the JRP-D model, where there is no cost for waiting but orders have deadlines. As for hardness results, it is known that the problem is APX-hard and that the natural linear program for JRP has integrality gap at least 1.245. Both results hold even for JRP-D. In the online scenario, the best lower and upper bounds on the competitive ratio are 2.64 and 3, respectively. The lower bound of 2.64 applies even to the restricted version of JRP, denoted JRP-L, where the waiting cost function is linear. We provide several new approximation results for JRP. In the offline case, we give an algorithm with ratio 1.791, breaking the barrier of 1.8. In the online case, we show a lower bound of 2.754 on the competitive ratio for JRP-L (and thus JRP as well), improving the previous bound of 2.64. We also study the online version of JRP-D, for which we prove that the optimal competitive ratio is 2.

Recommendations

• An efficient polynomial-time approximation scheme for the joint replenishment problem
• On optimal algorithms for the joint replenishment problem
• The Joint Replenishment Problem: New Heuristics and Worst Case Performance Bounds
• A New Optimal Algorithm for the Joint Replenishment Problem
• An approximate dynamic-programming approach to the joint replenishment problem
• APPROXIMATING THE JOINT REPLENISHMENT PROBLEM WITH DEADLINES
• An Algorithm for Determining the Best Lower Bound for the Stochastic Joint Replenishment Problem
• An efficient optimal solution method for the joint replenishment problem

Cited in

(29)

• Approximation algorithms for \(k\)-echelon extensions of the one warehouse multi-retailer problem
• The dynamic-demand joint replenishment problem with approximated transportation costs
• Online inventory replenishment scheduling of temporary orders
• New results on multi-level aggregation
• The submodular joint replenishment problem
• Approximation algorithms and hardness results for the joint replenishment problem with constant demands
• Constant approximation algorithms for the one warehouse multiple retailers problem with backlog or lost-sales
• APPROXIMATING THE JOINT REPLENISHMENT PROBLEM WITH DEADLINES
• Approximation algorithms for inventory problems with submodular or routing costs
• A 5/3-Approximation Algorithm for Joint Replenishment with Deadlines
• A new method for joint replenishment problems
• Improved approximation algorithms for inventory problems
• Combinatorial heuristics for inventory routing problems
• Online Algorithms for Multilevel Aggregation
• Integrated Supply Chain Management via Randomized Rounding
• Online make-to-order joint replenishment model: primal-dual competitive algorithms
• Approximation algorithms for replenishment problems with fixed turnover times
• Approximation algorithms for replenishment problems with fixed turnover times
• Joint replenishment meets scheduling
• An online joint replenishment problem combined with single machine scheduling
• Improved and deterministic online service with deadlines or delay
• Matheuristics for scheduling of maintenance service with linear operation cost and step function maintenance cost
• List update with delays or time windows
• Universal optimization for non-clairvoyant subadditive joint replenishment
• Universal optimization for non-clairvoyant subadditive joint replenishment
• Online multi-level aggregation with delays and stochastic arrivals
• Online matching with delays and size-based costs
• Nearly-optimal algorithm for non-clairvoyant service with delay
• A tight lower bound for online service with deadlines and lazy server

This page was built for publication: Better Approximation Bounds for the Joint Replenishment Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5383963)