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.
Abstract

The Joint Replenishment Problem ($${\hbox {JRP}}$$JRP) 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 $${\hbox {JRP-D}}$$JRP-D, the version of $${\hbox {JRP}}$$JRP 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 $$1.207$$1.207, a stronger, computer-assisted lower bound of $$1.245$$1.245, as well as an upper bound and approximation ratio of $$1.574$$1.574. The best previous upper bound and approximation ratio was $$1.667$$1.667; no lower bound was previously published. For the special case when all demand periods are of equal length, we give an upper bound of $$1.5$$1.5, a lower bound of $$1.2$$1.2, and show APX-hardness.

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.

Main Content
Current View