Two-Approximation Algorithms for Stochastic Inventory

Robin Roundy
Department of Industrial Engineering and Operations Research
Cornell University

Joint colloquium with Production and Operations Management


Tuesday, October 11, 2005
4:45 - 6:00 PM
Terman Engineering Center, Room 453


Abstract:

We consider stochastic control inventory models in which 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 talk, we address the long-standing problem of finding computationally efficient and provably good inventory control policies for these models in the presence of correlated and non-stationary (time-dependent) demands. Here the correlation is inter-temporal, i.e., what we observe in a period changes our forecast for the demand in future periods. We will focus on two classical models, the periodic-review stochastic inventory control problem with order capacity constraints, and the uncapacitated serial system.

We provide computationally efficient two-approximation algorithms for these problems, i.e., we find a policy whose expected cost is at most twice the expected cost of an optimal policy. These are the first constant-factor approximation algorithms for these problems. These algorithms are based on several novel ideas: we present new marginal cost accounting techniques for stochastic inventory models; we use cost-balancing techniques; and we consider non base-stock policies that are easy to implement on-line. Our results are valid for all approaches used in the literature to model correlation of demands over time.

This is joint work with Retsef Levi, Martin Pal, David Shmoys and Van Anh Troung.

---

Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html