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 Google Scholar Google Scholar Articles by Chan, C. W. Articles by Farias, V. F. Search for Related Content

Stochastic Depletion Problems: Effective Myopic Policies for a Class of Dynamic Optimization Problems

Department of Electrical Engineering, Stanford University, Stanford, California 94305
Sloan School of Management and Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02142
cwchan{at}stanford.edu
vivekf{at}mit.edu

This paper presents a general class of dynamic stochastic optimization problems we refer to as stochastic depletion problems. A number of challenging dynamic optimization problems of practical interest are stochastic depletion problems. Optimal solutions for such problems are difficult to obtain, both from a pragmatic computational perspective as well as from a theoretical perspective. As such, simple heuristics are desirable. We isolate two simple properties that, if satisfied by a problem within this class, guarantee that a myopic policy incurs a performance loss of at most 50% relative to the optimal adaptive control policy for that problem. We are able to verify that these two properties are satisfied for several interesting families of stochastic depletion problems and, as a consequence, we identify computationally efficient approximations to optimal control policies for a number of interesting dynamic stochastic optimization problems.

Key Words: stochastic optimization; scheduling; approximations
History: Received: January 17, 2008; revision received: August 15, 2008;