Competitive algorithms for the on-line inventory problem
Competitive algorithms for the on-line inventory problem
复制标题
DOI：
10.1109/icmlc.2004.1382313
复制
发表时间：
2004-08
期刊：
影响因子：
--
通讯作者：
Wei-Min Ma;Guo-Qing Chen
中科院分区：
文献类型：
--
作者：
Wei-Min Ma;Guo-Qing Chen
我们的团队提出并研究了一个在线库存问题，不同于传统版本的问题，即决策者应该知道销售的概率分布，所关注的在线库存问题是由于决策者只知道某一特定产品的日需求量的上下界的不确定性。博弈的目标是决定每天应该准备多少产品，以使竞争比最小化，竞争比表示在线算法的性能与相应的离线优化算法的性能有多接近。首先，建立了一个简化的在线库存问题模型。然后，给出了该问题的一般形式的竞争算法，即广义调和算法。此外，如果决策者从买家那里为任意数量序列选择一个固定数量的产品，则竞争比是最优的。最后，我们还研究了其他一些变种，并提出了相应的竞争算法。
An on-line inventory problem is proposed and studied by our team differing from the traditional version of the problem, in which probability distributions for sales are supposed to know to the decision-maker, the on-line inventory problem of concern is due to the uncertainty where decision-makers only know the upper bound and lower bound of the daily demand for a particular product. The objective of game is to decide how many products should be prepared everyday so that the competitive ratio, which shows how close the on-line algorithm's performance to that of the relevant off-line optimal algorithm, can be minimized. First, a simplified on-line inventory problem model is formulated. Then, a competitive algorithm for general version of the problem, namely the general harmonic algorithm is presented. Furthermore the competitive ratio is proved to be the best one if decision-makers choose a fixed quantity product for any sequence of quantities from buyers. Finally, some other variants are also investigated and relevant competitive algorithms are developed.