Approximation Algorithms for Capacitated Stochastic Inventory Control Models
成果类型：
Article
署名作者：
Levi, Retsef; Roundy, Robin O.; Shmoys, David B.; Truong, Van Anh
署名单位：
Massachusetts Institute of Technology (MIT); Cornell University; Cornell University
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.1080.0580
发表日期：
2008
页码：
1184-1199
关键词：
摘要：
we develop the first algorithmic approach to compute provably good ordering policies for a multiperiod, capacitated, stochastic inventory system facing stochastic nonstationary and correlated demands that evolve over time. Our approach is computationally efficient and guaranteed to produce a policy with total expected cost no more than twice that of an optimal policy. As part of our computational approach, we propose a novel scheme to account for backlogging costs in a capacitated, multiperiod environment. Our cost-accounting scheme, called the forced marginal backlogging cost-accounting scheme, is significantly different from the period-by-period accounting approach to backlogging costs used in dynamic programming; it captures the long-term impact of a decision on system performance in the presence of capacity constraints. In the likely event that the per-unit order costs are large compared to the holding and backlogging costs, a transformation of cost parameters yields a significantly improved guarantee. We also introduce new semimyopic policies based on our new cost-accounting scheme to derive bounds on the optimal base-stock levels. We show that these bounds can be used to effectively improve any policy. Finally, empirical evidence is presented that indicates that the typical performance of this approach is significantly stronger than these worst-case guarantees.