CS 789 THEORY SEMINAR [main page]
Speaker: Retsef Levi
Date: October 3, 2005
Title: Provably
Near-Optimal Dual-Balancing Policies for Lost-Sales Models
Abstract:
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.