Approximation algorithms for the joint replenishment problem with deadlines

作者：Bienkowski Marcin; Byrka Jaroslaw; Chrobak Marek^*; Dobbs Neil; Nowicki Tomasz; Sviridenko Maxim; Swirszcz Grzegorz; Young Neal E

来源：Journal of Scheduling, 2015, 18(6): 545-560.

DOI：10.1007/s10951-014-0392-y

• Joint replenishment problem
• NP-completeness
• APX-hardness
• Approximation algorithms

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

• 出版日期2015-12
• 单位IBM