CS 789 THEORY SEMINAR [main page]

Speaker:     Retsef Levi
Date:          October 3, 2005
Title:          Provably Near-Optimal Dual-Balancing Policies for Lost-Sales Models


In this talk, we address one of the fundamental models in stochastic inventory theory, the single-item, single location, periodic-review stochastic inventory control model with lost-sales (or the lost-sales model in short). The goal is to coordinate a sequence of orders over a planning horizon of finitely many discrete periods, aiming to supply a sequence of random demands with minimum expected cost. The cost consists of a per-unit holding cost for carrying excess inventory from one period to the next and a per-unit lost-sales penalty cost that is incurred for each unit of demand that is not satisfied on time. The assumption is that unsatisfied units of demand are lost (i.e., leave the system). The goal is to find an ordering policy that minimizes the overall expected cost. This model has challenged researchers and practitioners for over five decades as very little is known about the structure of the optimal policies, and computing computationally efficient good policies has been a very hard task even in the most simple settings.

We build on some of the ideas from the joint work with Pa'l, Roundy and Shmoys in which we have introduced what we call dual-balancing policies, for a class of inventory models where unsatisfied demand is backlogged rather than lost (i.e., inventory models with backlogged demand). These dual-balancing policies admit worst-case performance guarantees, that is, for each instance of the problem, the expected cost of the policy is guaranteed to be at most twice the optimal expected cost .

In this talk, we address the implementation of dual-balancing policies in inventory models with lost-sales and discuss their worst-case analysis. These lost-sales models have very different characteristics than models with backlogged demand. This requires a fundamentally different worst-case analysis which incorporates several novel ideas. We shall present the first computationally efficient policies for inventory models with lost-sales which admit a worst-case performance guarantee. In particular, we show that, under relatively general assumptions on the demand distributions, the dual-balancing policy for lost-sales models provides a performance guarantee of 2. The analysis we present provides new insights on lost-sales models that we believe will contribute to the future study of this hard class of models.

This is joint work with Ganesh Janakiraman and Mahesh Nagarajan.


[main page]