An efficient implementation of the Wagner-Whitin algorithm for dynamic lot-sizing

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:

$\text{M}{}_{\mathrm{jk}}\text{=A}{}_{\mathrm{j}}\text{+C}{}_{\mathrm{j}}\text{Q}{}_{\mathrm{j}}\text{+}\text{∑}\text{k?1}\text{t=j}\text{H}{}_{\mathrm{t}}\text{∑}\text{k}\text{r=t+1}\text{D}{}_{\mathrm{r}}$

$\text{F}{}_{\mathrm{k}}\text{=}\text{min}\text{1?j?k}\text{[F}{}_{\mathrm{j}}\text{+M}{}_{\mathrm{jk}}\text{];}\text{F}{}_0\text{=0}$

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:

$\text{M}{}_{\mathrm{j,k}}\text{=A}{}_{\mathrm{j}}\text{+C}{}_{\mathrm{j}}\text{D}{}_{\mathrm{j}}$

$\text{M}{}_{\mathrm{j,k+1}}\text{=M}{}_{\mathrm{jk}}\text{+D}{}_{\mathrm{k+1}}\text{(C}{}_{\mathrm{j}}\text{+}\text{∑}\text{k}\text{t=j}\text{H}{}_{\mathrm{t}}\text{,}\text{k?j}$

Using this recursive relationship, the number of computations can be greatly reduced. Specifically, $\text{3}\text{2}$N² ? $\text{1}\text{2}$N² additions and $\text{1}\text{2}$N² + $\text{1}\text{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². Problems with N = 500 were solved in under two seconds.