Skip to main content
eScholarship
Open Access Publications from the University of California

UC Riverside

UC Riverside Previously Published Works bannerUC Riverside

Approximation algorithms for the joint replenishment problem with deadlines

  • Author(s): Bienkowski, M
  • Byrka, J
  • Chrobak, M
  • Dobbs, N
  • Nowicki, T
  • Sviridenko, M
  • Świrszcz, G
  • Young, NE
  • et al.

Published Web Location

https://arxiv.org/pdf/1212.3233
No data is associated with this publication.
Abstract

The Joint Replenishment Problem ((Formula presented.)) is a fundamental optimization problem in supply-chain management, concerned with optimizing the flow of goods from a supplier to retailers. Over time, in response to demands at the retailers, the supplier ships orders, via a warehouse, to the retailers. The objective is to schedule these orders to minimize the sum of ordering costs and retailers' waiting costs. We study the approximability of (Formula presented.), the version of (Formula presented.) with deadlines, where instead of waiting costs the retailers impose strict deadlines. We study the integrality gap of the standard linear-program (LP) relaxation, giving a lower bound of (Formula presented.), a stronger, computer-assisted lower bound of (Formula presented.), as well as an upper bound and approximation ratio of (Formula presented.). The best previous upper bound and approximation ratio was (Formula presented.); no lower bound was previously published. For the special case when all demand periods are of equal length, we give an upper bound of (Formula presented.), a lower bound of (Formula presented.), and show APX-hardness. © 2014 Springer Science+Business Media New York.

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Item not freely available? Link broken?
Report a problem accessing this item