Constant approximation algorithms for the one warehouse multiple retailers problem with backlog or lost-sales - Gestion et Conduite des Systèmes de Production Access content directly
Journal Articles European Journal of Operational Research Year : 2016

Constant approximation algorithms for the one warehouse multiple retailers problem with backlog or lost-sales

Abstract

We consider the One Warehouse Multi-Retailer (OWMR) problem with deterministic time-varying demand in the case where shortages are allowed. Demand may be either backlogged or lost. We present a simple combinatorial algorithm to build an approximate solution from a decomposition of the system into single-echelon subproblems. We establish that the algorithm has a performance guarantee of 3 for the OWMR with backlog under mild assumptions on the cost structure. In addition, we improve this guarantee to 2 in the special case of the Joint-Replenishment Problem (JRP) with backlog. As a by-product of our approach, we show that our decomposition provides a new lower bound of the optimal cost. A similar technique also leads to a 2-approximation for the OWMR problem with lost-sales. In all cases, the complexity of the algorithm is linear in the number of retailers and quadratic in the number of time periods, which makes it a valuable tool for practical applications. To the best of our knowledge, these are the fisrt constant approximations for the OWMR with shortages.
Fichier principal
Vignette du fichier
OWMR_Shortages.pdf (222 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

hal-01284347 , version 1 (04-04-2024)

Identifiers

Cite

Jean-Philippe Gayon, Guillaume Massonnet, Christophe Rapine, Gautier Stauffer. Constant approximation algorithms for the one warehouse multiple retailers problem with backlog or lost-sales. European Journal of Operational Research, 2016, 250 (1), pp.155-163. ⟨10.1016/j.ejor.2015.10.054⟩. ⟨hal-01284347⟩
306 View
10 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More