This Article Full Text (PDF) 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 HighWire Citing Articles via Google Scholar Google Scholar Articles by Levi, R. Articles by Shmoys, D. B. Search for Related Content

Approximation Algorithms for Stochastic Inventory Control Models

Sloan School of Management, Massachusetts Institute of Technology, Cambridge, MA 02139
Google, Inc., 1440 Broadway, 21st Floor, New York, New York 10018
School of Operations Research and Information Engineering, Cornell University, Ithaca, New York 14853
School of Operations Research and Information Engineering and Department of Computer Science, Cornell University, Ithaca, New York 14853
retsef{at}mit.edu
martin{at}palenica.com
robin{at}orie.cornell.edu
shmoys{at}cs.cornell.edu

We consider two classical stochastic inventory control models, the periodic-review stochastic inventory control problem and the stochastic lot-sizing problem. The goal is to coordinate a sequence of orders of a single commodity, aiming to supply stochastic demands over a discrete, finite horizon with minimum expected overall ordering, holding, and backlogging costs. In this paper, we address the important problem of finding computationally efficient and provably good inventory control policies for these models in the presence of correlated, nonstationary (time-dependent), and evolving stochastic demands. This problem arises in many domains and has many practical applications in supply chain management.

Our approach is based on a new marginal cost accounting scheme for stochastic inventory control models combined with novel cost-balancing techniques. Specifically, in each period, we balance the expected cost of overordering (i.e., costs incurred by excess inventory) against the expected cost of underordering (i.e., costs incurred by not satisfying demand on time). This leads to what we believe to be the first computationally efficient policies with constant worst-case performance guarantees for a general class of important stochastic inventory control models. That is, there exists a constant C such that, for any instance of the problem, the expected cost of the policy is at most C times the expected cost of an optimal policy. In particular, we provide a worst-case guarantee of two for the periodic-review stochastic inventory control problem and a worst-case guarantee of three for the stochastic lot-sizing problem. Our results are valid for all of the currently known approaches in the literature to model correlation and nonstationarity of demands over time.

Key Words: inventory; approximation; dual-balancing; algorithms
History: Received: October 6, 2004; revision received: February 1, 2006;

This article has been cited by other articles:

				N. Halman, D. Klabjan, M. Mostagir, J. Orlin, and D. Simchi-Levi A Fully Polynomial-Time Approximation Scheme for Single-Item Stochastic Inventory Control with Discrete Demand Mathematics of Operations Research, August 1, 2009; 34(3): 674 - 685. [Abstract] [PDF]

				W. T. Huh, G. Janakiraman, J. A. Muckstadt, and P. Rusmevichientong Asymptotic Optimality of Order-Up-To Policies in Lost Sales Inventory Systems Management Science, March 1, 2009; 55(3): 404 - 420. [Abstract] [PDF]

				R. Levi, R. O. Roundy, D. B. Shmoys, and V. A. Truong Approximation Algorithms for Capacitated Stochastic Inventory Control Models Operations Research, September 1, 2008; 56(5): 1184 - 1199. [Abstract] [PDF]

				R. Levi, G. Janakiraman, and M. Nagarajan A 2-Approximation Algorithm for Stochastic Inventory Control Models with Lost Sales Mathematics of Operations Research, May 1, 2008; 33(2): 351 - 374. [Abstract] [PDF]