## Awi Federgruen

*Probabilistic analysis of capacitated multi-item lot sizing models*

Coauthor(s): Joern Meissner.

**Abstract:**

This paper conducts a probabilistic analysis of an important class of heuristics for multi-item capacitated lot sizing problems.

We characterize the asymptotic performance of so-called progressive interval heuristics as *T*, the length of the planning horizon, goes to infinity, assuming the data are realizations of a stochastic process of the following type: the vector of cost parameters follows an arbitrary process with bounded support, while the sequence of aggregate demand and capacity pairs is generated as an independent sequence with a common general bivariate distribution, which may be of *unbounded* support. We show that important subclasses of the class of progressive interval heuristics can be designed to be asymptotically optimal *with probability one*, while running with a complexity bound which grows *linearly* with the number of items N and slightly faster than *quadratically* with *T*.

We generalize our results for the case where the items' shelf life is uniformly bounded, e.g., because of perishability considerations.

**Source:** *Working paper*

**Exact Citation:**

Federgruen, Awi, and Joern Meissner. "Probabilistic analysis of capacitated multi-item lot sizing models." Working paper, Columbia Business School, 2005.

**Date:**
2005