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.
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.
Each author name for a Columbia Business School faculty member is linked to a faculty research page, which lists additional publications by that faculty member.
Each topic is linked to an index of publications on that topic.