This Article Full Text (PDF) e-companion References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Levi, R. Articles by Truong, V. A. Search for Related Content

Approximation Algorithms for Capacitated Stochastic Inventory Control Models

Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Mission Church of Jesus Christ of Latter Day Saints Apartado Aereo, Barranquilla, Colombia
School of Operations Research and Information Engineering, and Department of Computer Science, Cornell University, Ithaca, New York 14853
Fixed Income, Global Modelling, and Analytics Group, Credit Suisse Securities, New York, New York 10010
retsef{at}mit.edu
robin{at}orie.cornell.edu
shmoys{at}cs.cornell.edu
van.anh.truong{at}credit-suisse.com

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.

Subject classifications: stochastic inventory control; heuristics; approximation algorithms.
History: Received August 2005; revision received October 2007; accepted October 2007.