A note on solving the concave cost dynamic lot‐sizing problem in almost linear time
扩展了Wagner-Whitin算法，针对凹采购成本结构提出一种极快的微计算机实现，计算结果显示该算法能在线性时间内求解问题，并给出准理论解释。
Abstract 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 2 ) 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 behavior under the assumption that data are randomly distributed.