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.

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.