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(n2) 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.

Awi Federgruen and Michal Tzur
Journal Article
Publication Date
Management Science

Full 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
, (August 01, 1991):