Approximation algorithms for the joint replenishment problem with deadlines
Approximation algorithms for the joint replenishment problem with deadlines
复制标题
带期限联合补货问题的近似算法
DOI：
10.1007/s10951-014-0392-y
复制
发表时间：
2014
影响因子：
2
通讯作者：
Bienkowski M
中科院分区：
文献类型：
--
作者：
Bienkowski M
联合补货问题(简称联合补货问题)是供应链管理中的一个基本优化问题，涉及优化从供应商到零售商的货物流动。随着时间的推移，为了回应零售商的需求，供应商通过仓库向零售商发货。目标是安排这些订单，使订购成本和零售商的等待成本之和最小。我们研究了有最后期限的模型的逼近性，其中零售商强加严格的最后期限，而不是等待成本。我们研究了标准线性规划松弛的积分间隙，给出了的一个下界，一个较强的计算机辅助下界，以及的上界和逼近比。以前最好的上界和逼近比是；以前没有发表过下界。对于所有需求周期长度相等的特殊情况，我们给出了的上界和下界，并证明了它的APX-硬度。
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 ofwith 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.
登录
查看更多内容
DOI：
--
发表时间：
2013
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Marcin Bienkowski;J. Byrka;M. Chrobak;Lukasz Jez;Dorian Nogneng;J. Sgall
通讯作者：
J. Sgall
用最后期限来近似联合补货问题
DOI：
10.1142/s1793830909000130
发表时间：
2009
期刊：
Discret. Math. Algorithms Appl.
影响因子：
--
作者：
Tim Nonner;Alexander Souza
通讯作者：
Alexander Souza
DOI：
--
发表时间：
2002
期刊：
International Colloquium on Automata, Languages and Programming
影响因子：
--
作者：
S. Khanna;J. Naor;D. Raz
通讯作者：
D. Raz
组织网络或多播确认的竞争分析：需要等待多久？
DOI：
--
发表时间：
2004
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
C. Brito;E. Koutsoupias;Shailesh Vaya
通讯作者：
Shailesh Vaya
影响因子：
1.1
作者：
Alimonti, P;Kann, V
通讯作者：
Kann, V