Two-Approximation Algorithm for Dynamic Stochastic
Lost-Sales Inventory Problem with Lead Time
Retsef Levi
Postdoctoral Fellow
T.J. Watson Research Center
IBM
(Sloan School of Management, MIT)
Wednesday, February 8, 2006
5:00 - 6:15 PM
Terman Engineering Center, Room 453
Abstract:
We address the single-item single-location periodic-review stochastic
inventory problem where unsatisfied demands are lost and there is a
lead time for delivery of orders. There are linear costs of storage
and of lost sales. The goal is to find a minimum-expected-cost
ordering policy for a finite planning horizon to supply a sequence of
random demands with known joint distribution. Except for the case
where the lead times are zero or one, little is known about the
structure of optimal policies. Heretofore, computing good policies has
been hard unless the lead times are short--even with independent
demands. We show how to find "dual-balancing" policies whose expected
cost is at most twice that of the optimal policy.
Our result builds on ideas from joint work with Pa'l, Roundy and
Shmoys which obtained a similar result for the backorders
problems. Since the lost-sales problem has very different
characteristics than the backorders problem, our result requires a
fundamentally different worst-case analysis.
This is joint work with Ganesh Janakiraman and Mahesh Nagarajan.
Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html