Premium
An efficient implementation of the Wagner‐Whitin algorithm for dynamic lot‐sizing
Author(s) -
Evans James R
Publication year - 1985
Publication title -
journal of operations management
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 3.649
H-Index - 191
eISSN - 1873-1317
pISSN - 0272-6963
DOI - 10.1016/0272-6963(85)90009-9
Subject(s) - computation , sizing , computer science , procurement , dynamic programming , time horizon , economic order quantity , holding cost , algorithm , scheduling (production processes) , material requirements planning , mathematical optimization , inventory cost , arithmetic , parallel computing , mathematics , economics , art , supply chain , management , production (economics) , political science , law , visual arts , macroeconomics
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:M jk =A j + C j Q j + ∑ t = j k − 1H t∑ r = t + 1 kD rF k =min 1 ⩽ j ⩽ k [ F j + M jk ] ; F 0 = 0where 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:M jj= A j + C j D jM j,k + 1= M jk + D k + 1 ( C j + ∑ t = j kH t) , k ⩾ jUsing this recursive relationship, the number of computations can be greatly reduced. Specifically,3 2 N 2 − 1 2 N 2additions and1 2 N 2 + 1 2 N 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.