Approximating the Joint replenishment Problem with Deadlines
Approximating the Joint replenishment Problem with Deadlines
复制标题
用最后期限来近似联合补货问题
DOI：
10.1142/s1793830909000130
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Alexander Souza
中科院分区：
文献类型：
--
作者：
Tim Nonner;Alexander Souza
经典联合补货问题（JRP）的目的是通过在两个阶段组合订单，首先在一些零售商处，然后在仓库中最小化订单成本。需要这些订单来满足零售商随时间出现的需求。我们调查了自然的特殊情况，即每个需求都有一个截止日期，直到需要满足。对于这种情况，我们提出了一种随机的5/3-抗氧化算法。而且，我们证明了截止日期的JRP是APX-HARD。最后，我们通过表明具有线性延迟成本函数的JRP是NP-HARD，即使每个零售商都必须满足三个需求，我们扩展了已知的硬度结果。
The objective of the classical Joint Replenishment Problem (JRP) is to minimize ordering costs by combining orders in two stages, first at some retailers, and then at a warehouse. These orders are needed to satisfy demands that appear over time at the retailers. We investigate the natural special case that each demand has a deadline until when it needs to be satisfied. For this case, we present a randomized 5/3-approximation algorithm. We moreover prove that JRP with deadlines is APX-hard. Finally, we extend the known hardness results by showing that JRP with linear delay cost functions is NP-hard, even if each retailer has to satisfy only three demands.