Division of Research School of Business Administration April 1988 PRACTICAL ISSUES IN IMPLEMENTING WAGNER-WHITIN PROCEDURE FOR LOT SIZING DECISIONS Working Paper #568 Ram Rachamadugu The University of Michigan FOR DISCUSSION PURPOSES ONLY None of this material is to be quoted or reproduced without the expressed permission of the Division of Research Copyright 1988 University of Michigan School of Business Administration Ann Arbor Michigan 48109

Practical Issues in Using Wagner-Whitin Procedure for Lot Sizing Decisions Executive Summary In a recent study, it was pointed out that the Wagner Whitin [9] procedure (WW) is impractical due to its computational burden vis-a-vis other procedures. Further, in yet another study, through computational tests it was shown that WW procedure yields poor solutions when all units quantity discounts are available. We show how computational speed of WW procedure can be increased by data transformation and drawing upon certain analytical results. Also, we show that though WW procedure yields poor rasults in all units discount situation, it can be used to find optimal solutions when incremental quantity discounts are available. Further, we identify when it is appropriate to use WW procedure and how it needs to be modified for various environments. Introduction Recently, based on computational experiments, Chong [4] pointed out that the W14 procedure is slow compared to other competing procedures. He used an implementation of WW procedure suggested by Evans [7]. In this paper, we show that Evans implementation can further be improved by certain data transformations and also drawing upon planning horizon results derived by Wagner and Whitin [9] and Eppen, Gould and Pashigian [6]. These changes reduce arithmetic operations to be performed in each recursion. They also reduce the search space for finding optimal solutions. Yet another aspect that has been addressed recently is the lot size determination in dynamic demand environment when all units quantity discounts are available. Chung et al. [5], based on their computational study, conclude that the WI4 procedure yielded optimal solutions less than 50% of the time. Firstly, we point out why WW procedure need not necessarily yield optimal solutions for

-2 - all units discount situations. Next, we show that the WWV procedure, though inappropriate to use in all units discount situations, can still be used to find optimal solutions when incremental quantity discounts are available. Finally, we discuss other considerations such as optimality in multistage systems, decision environments, demand variability, lumpiness of demand and forecast window size which need to be considered while using IW procedure. Notation used in the paper is explained in Table 1. Improvements to WW Implementation Evans [7] suggested an implementation of Wagner-Whitin procedure. This 32 1 2 implementation requires 2 N 2 N additions and N /2 + N/2 multiplications. We show how this implementation can be further improved and thus make the WW procedure more competitive vis-a-vis other procedures. Consider the following transformation of the original data. HK = CK + HK +1 K = 1,2,....N-1 (1) H' = HN HI is the surrogate holding cost that we will use in solving the problem. K Drawing upon Evans notation, recursive equations can be written as follows: M. = A. for all j = 1,2,....N (2) K HjK+ MjK + DK S H' K > j (3) Mj,K+1 JK K+1 t=j t Analytical details of this transformation process and its validity are shown in Appendix I. The advantage of this transformation process is that the unit variable cost of purchasing the item in different time periods can be ignored in the analysis. This leads to computational time savings. Note that preprocessing of the data for this purpose requires only a 2(N-1) additions/

-3 - Table 1 Notation DK = Demand in period i K = Index for time periods K = 1,2....N CK = Variable cost per unit in time period K AK = Set up or order cost in time period K FK = Minimum cost for K period problem HK = Holding cost per unit in period K (charged on ending inventory) H' = Surrogate holding cost per unit in period K K L(K) = Last time period in which production occurred in the best solution for K period problem K SUMH(K) = E H. i=1 1 K SUMH'(K) = Z H: i=l 1 Mj = Cost of meeting all the demands of periods j jk through k with set up in period j

-4 - substractions. It can also be verified that no additional memory is required in using the transformation suggested here. In Evans [7, p. 230, eqn 2] analysis, minimum cost for periods 1 through K is determined by FK = min [Fj. + Mj ] for K = 1,2....N (4) K vgjj1K J K Additional computational savings in determining FK can be realized if one or more of the following conditions are satisfied (i) Speculative motive does not exist for holding inventories. Cost of purchasing an item (excluding order cost) and holding it in invenventory for future use is more expensive than buying it in a later period (excluding order cost in that later period). If all H! are nonnegative, this condition is satisfied. (ii) Set up costs are monotone nondecreasing in time. If one or more of the above conditions are satisfied, then additional savings in computational results can be achieved as shown below. F K= min {Fj + Mj K = 2,3....N (5) K L(K-1)<j<K j- K L(1) = 1 Where L(K) represents the last time period in which production took place in the best solution for K period problem. The effect of this property is that the search space for j in equation (4) becomes almost linear in time. (i) is true because of the fact that if H! are nonnegative after the transformation suggested by us, transformed problem is still in a form solvable using Wagner Whitin procedure. (ii) is the consequence of a result obtained by Eppen et al. [6]. These savings are illustrated in Figure 1. Whereas Evans formulation searches for the best value of j in the area below the diagonal, exploiting the characterizations described above leads to search only in the 'staircase' area.

-5 - Figure 1 As an illustration, consider the example problem cited by Evans. Example problem and the transformed problem are shown in Tables 2 and 3 respectively. Table 2 Period t 1 2 3 4 Dt 60 100 140 200 At 150 140 160 160 Ct 7 7 8 7 Ht 1 1 2 2 Cf7787~ -

-6 - Table 3 Period t 1 2 3 4 Dt 60 100 140 200 At 150 140 160 160 Hi 1 1 3 2 Note: Ct is irrelevant in the transformed problem. Assume that Ct = 0 for simplification of the computations. F1 = 150 L(1) = 1 F2 = 250 L(2) = 1 F3 = 290 L(3) = 2 F4 = 450 L(4) = 4 Note that the search for j in four period problem had been made only periods 2 through 4 (instead of 1 through 4). The power of the transformation becomes obvious in larger horizon problems. If indeed we were solving 5 period problem, search for j in five period problem has to be done only in periods 4 and 5. This explains the staircase structure depicted in Figure 1. In most situations either condition (i) and/or (ii) are satisfied. This is largely true over short horizons when high inflation does not exist. If both conditions are not satisfied, then we can invoke the results derived by Eppen et al. to save computational time. When Eppen et al. [6, Theorem 1, p. 273] results are used on the transformed problem, recursive equation (4) can be rewritten as follows: F= min[F._ + M ] (6) K jeJ 1 L %K

-7 - where J represents the set of time periods satisfying the following condition SUMH'(j - 1) > SIUH'(K - 1) for j = 1,2....N-1 (7) K = 2,.....N j < K Details of how the condition derived by Eppen et al. reduce to (7) are shown in Appendix II. Our discussion in this section detailed how computational time savings can be achieved using data transformation suggested by us and prior analytical results. These are shown in the form of a flowchart in Figure 2. Quantity Discounts In this section, we will place in proper perspective the usefulness of WIJ procedure when quantity discounts are available. We will also discuss the limitations of a procedure suggested by Chung et al. Recently, they studied lot size determination in discrete time environment with all unit quantity discounts. They devised a procedure to find optimal solution which appears to be better than earlier methods in its computational requirements. Further, through computational studies, they found that the 1,W procedure yielded optimal solutions in less than 50% of the cases. Firstly, we wish to point out that the characterization presented by Wagner and Whitin are valid for concave cost structures. Since all unit discounting results in a cost structure that is neither concave nor convex, there is no apriori reason believe that it would give good solutions for the all unit discount problem. It would be a misapplication of the an procedure. A limitation of the analysis done by Chung et al. is that in their analysis, they force the ending inventories to be zero. We dispute this on two grounds —firstly, there is no reason to suppose that the ending investories are zero in an optimal solution to the all unit discount problem. However, zero

-8 - ending inventories are a natural result for the problem when no quantity discounts are available. In view of the fact that all unit quantity discounts are available, it is conceivable that the ending inventory may be positive in an optimal solution in order to reduce the total costs. Because of the above mentioned reasons, the optimal solution procedure suggested by Chung et al. seems to be incomplete. Further, the analysis provided by Chung et al. holds good only when discounting scheme is stationary over time. Hence the case studied by them warrants further investigation. Yet another aspect of the procedure devised by Chung et al. which merits attention is the fact that they assume initial inventory to be zero. This can be unrealistic in most practical situations. In many situations, the result of lot sizing exercise is to determine when orders are to be placed and in what quantities. Any order that is to be released immediately is released. As we progress in time, more forecasts are made and the result of our past decisions and demand realizations is that we may as well start off the next planning exercise with an initial inventory. Note that this does not pose any complications in the undiscounted version since we can offset demands in initial periods until initial inventory is used up. It is not clear how Chung et al. procedure can be used when initial inventory is positive, as is likely to be the case in practical situations. An alternate pricing scheme that has been investigated before, but remained undiscussed in Chung et al. article is incremental quantity discounts. Under this scheme, price discount is provided for the units above the price break as shown in Figure 3.

-9 - yes Transform the data as per our suggestion in equations (1) and (2) yes Are all surrogate holding costs (H!) nonnegative? no Use the result in equation (5) to reduce computations Flowchart for choosing appropriate form of WW procedure Figure 2

-10 - Variable Ooto I of ftm i // /" /X~~ I~~ I bf, i Pi_ I IOrE!l' ______ Figure 3 When this pricing scheme prevails, it can be seen that the characterizations of optimal policies stated by Wagner and Whitin still hold good. This follows directly from the concave cost structure of the problem (Zangwill [9]). In this case, it is unnecessary to impose the restriction of ending inventory being zero. Also, note that the WW procedure can be used in incremental unit quantity discounting scheme even when the parameters of the cost scheme vary from one period to another. Initial inventories can be offset against earlier demands. Thus WW procedure is useful and provides optimal solutions when incremental quantity discounts are available. However, based on computational studies performed by Chung et al. it appears that it is of limited use in all unit discount schemes. Effect of Decision Environment Even when WW procedure is computationally attractive vis-a-vis other procedures, it may be inappropriate in certain environments. Firstly, we wish to point out that the W1W procedure yields optimal solutions for single stage systems and for fixed horizon situations only. This does not necessarily imply

-11 - that it will yield the best solutions for multi-stage systems such as MRP when lot sizes are determined sequentially (higher level to lower level). Usefulfulness of 4WW procedure further depends on the manner in which decisions are implemented in the organization. Suppose that the firm makes forecasts for T periods into future. Lot sizes are determined based on this forecast and all orders are released at various times. This exercise is repeated every T periods. In such a decision enviornment, we are essentially solving a stationary problem every T time periods. Even if the forecasts are perfect, this does not necessarily imply that WW procedure will necessarily yield good results for infinite horizon situations. Yet another approach to lot sizing decisions is to plan for orders in a 'rolling horizon'. In this case, we implement only the immediate decision (orders to be released in the current period) and as time progresses, more future forecasts are revealed to us. Based on further available information, future decisions are made and the process is repeated over time. In this type of environment, there is no reason to suppose that Wt1 procedure will yield best solutions, let alone optimal solutions. Prior studies by Baker [6], Blackburn and Miller [7] and Silver and Meal [8] and recent extensive compuational studies reported by Zoller and Robrade [11] provide evidence in this rgard. Under these circumstances NWW procedure may perform worse than other well known heuristics such as Silver Meal heuristic. However, in rolling environments, performance of NWW procedure can be improved by implementing modifications to it suggested by Chand [3]. Yet another aspect which merits attention in the choice of lot sizing procedure is the stability of the schedule. It is well known that MRP systems are 'nervous' in the sense that extending the forecast horizon and/or perturbing demand data can lead to changes in order timing and size. Wagner-Whitin

-12 - procedure particularly appears to be susceptiable to this tendency (Blackburn and Miller [2]). This is very important in J-1-T environments where logistical systems of vendors and customers are tightly linked. Above comments do not necssarily imply that the WW procedure is of limited applicability. On the contrary, when demand variability is high, long forecasts are available, and demands are lumpy (as is likely to be the case in MRP systems where lot sizes at a particular level determine lot sizes at the next lower level) prior computational evidence shows that the lWWI procedure provides good results. If forecast horizons are of short length, then the modifications to WW procedure suggested by Chand are more appropriate to implement. Summary In this paper, we identified modifications to data structures which reduce the compuattional burden of implementing WW procedure. Depending on the nature of set up costs and variable costs of ordering, additional conditions were identified which further reduce computational time requirements of WW procedure. Appropriate choices to be made were outlined in a flowchart for user convenience. We also showed that though WW procedure is not appropriate where all unit discounts are available, it can still be used when incremental quantity discounts are available. Further, we showed that the method is powerful enough to handle incremental quantity discount scheme even when it varies over time. Various factors such as decision environment, demand stability, forecast window length, demand lumpiness and demand variability were identified which determine the suitability of using WW procedure.

-13 - References 1. Baker, K. R. (1977), "An Experimental Study of Rolling Schedules in Production Planning," Decision Sciences, Vol. 8, p. 19-27. 2. Blackburn, J. D. and R. A. Miller (1980), "Heuristic Lot Sizing Performance in a Rolling Schedule Environment," Decision Sciences, Vol. 11, p. 691-701. 3. Chand, S. (1982), "A Note on Dynamic Lot Sizing in a Rolling-Horizon Environment," Decision Sciences, Vol. 13, p. 113-119. 4. Chong, P. S. (1987), "A Dispute on James R. Evans' an Efficient Implementation of the Wagner-Whitin Algorithm for Dynamic Lot Sizing," Journal of Operations Management, Vol. 7, p. 27-29. 5. Chung, C. S., D. T. Chiang and C. Y. Lu (1987), "An Optimal Algorithm for the Quantity Discount Problem," Journal of Operations Management, Vol. 7 p. 165-177. 6. Eppen, G. D., F. J. Gould and B. Peter Pashigian (1969), "Extensions of the Planning Horizon Theorem in the Dynamic Hot Size Model," Management Science, Vol. 15, No. 5, p. 268-277. 7. Evans, J. R. (1985), "An Efficient Implementation of the Wagner-Whitin Algorithm for Dynamic Lot Sizing," Journal of Operations Management, Vol. 5, p. 229-235. 8. Silver, E. A. and H. C. Meal (1973), "A Heuristic for Selecting Lot Size Quantities for the Case of a Deterministic Time Varying Demand Rate and Discrete Opportunities for Replenishment," Production and Inventory Management, Vol. 14, p. 64-74. 9. Wagner, H. M. and T. M. Whitin (1958), "Dynamic Version of the Economic Lot-Size Model," Mangement Science, Vol 5, p. 89-96. 10. Zangwill, W. I. (1968), "Minimum Concave Cost Flows in Certain Networks," Management Science, Vol. 14, p. 429-450. 11. Zoller, K. and A. Robrade (1988), "Efficient Heuristics for Dynamic Lot Sizing," International Journal of Production Rsearch, Vol. 26, No. 2, 249-265.

-14 - APPENDIX I Transformation of the Original Problem Notation Ai = Set up cost in period i Qi = Order quantity in period i C. ='Unit variable cost of the item in period i 1 D. = Demand in period i 1 6(Qi) = 1 if Qi < 0 0 otherwise. Total cost for any feasible policy is given by N 1=1 N + Z C.Q. i=1 1 1 + N i H Hi{ (Qj i=l 1 =l - D )} I I can be rewritten as N = A.6(Q ) i=l 1 i N + s Qi(C i=l i1 N + Z Qi(C. i=1 l + + N Z H.) j=i J N j H.) N - Z D. i=l 1 N E H. j=i J II N = E i=l Ai6(Qi) N Z D.(Ci i=l i N + Z H) J=i J N + Z C D i=l i i III det CK+ "-1i CK-1 + HK-1 K = 1,2,....N-1 "N = HN N N Substituting the above in III, III may be rewritten as N _= A. (Qi) i=l 1 i N + S Qi(CN+ i=l 1CN N N E H!) - Z D.(C j=l i=l 1 N N + Z HI) j=i 3 N + Z C.D. i=1 1 1

-15 - N N N N N = E A 6(Q ) + E Q (C + r H') - Z D E H' i=l i i 1 i N j=i j i=l i j=i j N + S D (C - CN) IV i=l i N Note that IV is identical to II except for the last term which is a constant. Hence the last term in IV discarded in minimization. Thus the transformation we suggested here preserves the problem and entirely eliminates the need to consider unit variable costs in the minimization. Thus minimizing IV is same as minimizing N N N = E A.S(Q.) + Z (Q - D ) Z H' i=1 1 1 i1 i i j=i j N N i = - A 6(Q ) + Z ' Z (Q -D ) =l1 i i i=l i j=l 3 i Above expression is same as the original problem with zero unit variable cost in all time periods and H. substituted with HI. Since the unit variable 1 1 costs disappear from this version, transformed problem reduces the computational burden.

-16 - APPENDIX II Eppen, Gould and Pashigian [6, p. 273] state the following: "....for any periods tl, t2, such that t1 < t2, either F(t2) = F(Z(tl), t2) or t(t2) e m(L(tl), t2)" where P(tl) = last period in which production took place in optimal solution to t period problem y-1 y-1 m(x,y) = {t E [1,2....y] | Ct + z H < C + Z H} t v=t x r=x v Note that in the transformed problem, unit variable cost of production is zero. Holding costs are substituted by HW. Hence the above condition reduces ~~~~~to~~1 to m(x,y) = {t e [1,2...y] | y-1 y-1 Z H' < Z H } v=1 v r=x v = {t e [1,2...y] I y-1 t-1 Z H' - E r=l v r=l ~Y-1 x-1 H' < y H' - S H'} v r=l r r=l i = {t e [1,2...y] J = {t E [1,2...y] | t-1 - Z H' r=l r x-1 < - Z H'} r=l r CH_' > CHi' } t-1 x-1 where CH' represents the cumulative sum of surrogate holding costs. t-1