Open Access Publications from the University of California

## 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://doi.org/10.1007/s10951-014-0392-y
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.