## Awi Federgruen

*A simple forward algorithm to solve general dynamic lot sizing models with **n* periods in 0(*n* log *n*) or 0(*n*) time

Coauthor(s): Michal Tzur.

#### Download:

Adobe Acrobat PDF

**Abstract:**

This paper is concerned with the general *dynamic lot size* model, or (generalized) Wagner-Whitin model. Let n denote the number of periods into which the planning horizon is divided. We describe a simple forward algorithm which solves the general model in 0(*n* log *n*) time and 0(*n*) space, as opposed to the well-known shortest path algorithm advocated over the last 30 years with 0(*n*^{2}) time.

A linear, i.e., 0(*n*)-time and space algorithm is obtained for two important special cases: (a) models *without* speculative motives for carrying stock, i.e., where in each interval of time the per unit order cost increases by less than the cost of carrying a unit in stock; (b) models with non-decreasing setup costs.

We also derive conditions for the existence of *monotone* optimal policies and relate these to known (planning horizon and other) results from the literature.

**Source:** *Management Science*

**Exact Citation:**

Federgruen, Awi, and Michal Tzur. "A simple forward algorithm to solve general dynamic lot sizing models with *n* periods in 0(*n* log *n*) or 0(*n*) time." *Management Science* 37, no. 8 (August 1991): 909-925.

**Volume:** 37

**Number:** 8

**Pages:** 909-925

**Date:**
8
1991