An efficient implementation of the Wagner‐Whitin algorithm for dynamic lot‐sizing
提出一种低存储需求的Wagner-Whitin算法计算机实现，能在微机上快速求解N期动态批量问题，计算时间随N平方增长，N=500时不到2秒。
Abstract We consider an N‐period planning horizon with known demands D t ordering cost A t , procurement cost, C t and holding cost H t in period t. The dynamic lot‐sizing problem is one of scheduling procurement Q t in each period in order to meet demand and minimize cost. The Wagner‐Whitin algorithm for dynamic lot sizing has often been misunderstood as requiring inordinate computational time and storage requirements. We present an efficient computer implementation of the algorithm which requires low core storage, thus enabling it to be potentially useful on microcomputers. The recursive computations can be stated as follows: urn:x-wiley:02726963:joom229:equation:joom229-math-0001 where M jk is the cost incurred by procuring in period j for all periods j through k, and F k is the minimal cost for periods 1 through k. Our implementation relies on the following observations regarding these computations: urn:x-wiley:02726963:joom229:equation:joom229-math-0002 Using this recursive relationship, the number of computations can be greatly reduced. Specifically, additions and multiplications are required. This is insensitive to the data. A FORTRAN implementation on an Amdahl 470 yielded computation times (in 10 −3 seconds) of T = −.249 + .0239N + .00446N 2 . Problems with N = 500 were solved in under two seconds.