A note on solving the concave cost dynamic lot-sizing problem in almost linear time

The heavily-debated Wagner-Whitin algorithm is known to produce optimal ordering policies for minimal-cost dynamic lot-sizing problems. In an earlier paper in this journal, Evans showed that the Wagner-Whitin algorithm is essentially a shortest path computation on an acyclic network, and presented a simple O(n²) computer implementation with low storage requirements. As an extension, in this paper we present a very fast microcomputer implementation of the algorithm for the case of concave procurement cost structures. Our extensive computational results show that for this cost structure, the algorithm will solve problems in linear time. A quasi-theoretical argument is given to explain this behaviour under the assumption that data are randomly distributed. [See abstract 45385.]