A Simple Forward Algorithm to Solve General Dynamic Lot Sizing Models with n Periods in 0(n log n) or 0(n) Time

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 nondecreasing 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.dynamic lot sizing models, dynamic programming, complexity