A simple forward algorithm to solve general dynamic lot sizing models with n periods in 0(n log n) or 0(n) timeCoauthor(s): Michal Tzur.
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.
Source: Management Science
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.
Date: 8 1991