Dynamic Economic Lot-Sizing Problem: A new O(T) Algorithm for the Wagner-Whitin Model

Wagner and Whitin (1958) develop an algorithm to solve the dynamic Economic Lot-Sizing Problem (ELSP), which is widely applied in inventory control, production planning, and capacity planning. The original algorithm runs in O(T2) time, where T is the number of periods of the problem instance. Subsequently, other researchers develop linear-time algorithms to solve the Wagner-Whitin (WW) lot-sizing problem; examples include the ELSP and equivalent Single Machine Batch-Sizing Problem (SMBSP). This paper revisits the algorithms for the ELSP and SMBSP under WW cost structure, presents a new efficient linear-time algorithm, and compares the developed algorithm with equivalent algorithms in the literature. The developed algorithm employs a lists and stacks data structure, which is a completely different approach than that of the comparable algorithms for the ELSP and SMBSP. Analysis of the developed algorithm shows that it executes fewer different actions throughout and hence it improves execution time by a maximum of 51.40% for the ELSP and 29.03% for the SMBSP.