FORECAST HORIZONS FOR THE DISCOUNTED DYNAMIC LOT SIZE PROBLEM ALLOWING SPECULATIVE MOTIVE James C. Bean Robert L. Smith Candace A. Yano Department of Industrial & Operations Engineering The University of Michigan Ann Arbor, Michigan 48109 Technical Report 84-9 Revised January: 1987

Forecast Horizons for the Discounted Dynamic Lot Size Problem Allowing Speculative Motive James C. Bean Robert L. Smith Candace A. Yano Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, Michigan 48109 ABSTRACT This paper considers the dynamic lot size problem under discounting, allowing speculative motive for holding inventory. A variable rolling horizon procedure is presented which, under certain regularity conditions, is guaranteed to generate an infinite horizon optimal production plan. A fixed rolling horizon procedure is also discussed which provides a production plan that achieves an infinite horizon cost within a user specified tolerance, G, of optimality. The fixed horizon length, T., needed in this procedure is given in terms of a closed form formula that is independent of specific forecasted demands. We also present computational results for problems with a range of cost parameters and demand characteristics.

1.0 Introduction Recent research on the Dynamic Lot Size Problem (DLSP) in a rolling horizon environment has focused on determining study horizons long enough to ensure optimal or near-optimal results. The study horizon is the number of periods of problem data considered. Rolling horizon procedures involve the solution of a series of finite study horizon problems, from which the current decision of each problem is implemented. The plans obtained from these finite horizon problems will, in general, be sensitive to the horizon length. That is, the "optimal" production plan for the current period may change as the horizon is lengthened, so that in general the solution obtained is sub-optimal. An exact approach utilizes horizons long enough to insure that the current decision stabilizes to the optimal current decision for the infinite horizon problem. Such study horizons are called forecast horizons and algorithms that are assured to discover them are called protective. The dynamic lot size problem has the objective of minimizing the sum of production or order setup costs, inventory holding costs, and variable unit production or purchase costs, subject to the constraint that all demand be satisfied. Wagner and Whitin (1958) developed a forward dynamic programming algorithm to solve the undiscounted finite horizon DLSP when unit production costs are constant over time. They also characterized forecast horizons for this problem. Blackburn and Kunreuther (1974) characterized forecast horizons for the DLSP with backlogging. Other related results for the DLSP have been obtained by Zabel (1964), Eppen, Gould, and Pashigian (1969), and Zangwill (1969). Research by Chand and Morton (1983), Lundin and Morton (1975), Baker (1977), Chand (1982), Carlson, Beckman and Kropp (1982), Blackburn and Millen (1980), and Schwarz (1977) has contributed to the determination of horizons which provide optimal or near optimal results. 1

This work has included the requirement that there be no speculative motive to hold inventory. That is, if the decision is made in isolation, it is always better to produce in the period of demand rather than producing earlier and holding the product. This paper extends problem solution capability to include cases of speculative motive. This extension is non-trivial since cases of speculative motive occur in actual problems. For example, if a strike can be predicted at some future time, production costs during the strike might be sufficiently high to warrant stockpiling product, contrary to normal production plans. This behavior is witnessed frequently. The aims of this paper are threefold. First, we give a rolling variable horizon algorithm that uses forecast horizons to generate an optimal infinite horizon production plan allowing speculative motive. Second, we provide a formula to determine a fixed study horizon for use in a rolling fixed horizon procedure that will generate a production plan within a cost error e of optimality. Finally, we provide computational results for problems with a range of parameter values. In Section 2 we provide a formulation of the problem. In Section 3 we discuss conditions necessary for the existence of decision and forecast horizons. Section 4 details both rolling horizon procedures for solving the DLSP. Experimental results are discussed in Section 5. We provide a summary and conclusions in Section 6. 2.0 Problem Description The discounted DLSP can be formulated as follows. Parameters dt = demand in period t ht = inventory holding cost per unit charged on inventory at end of period t 2

St = setup cost in period t Ct = variable unit production or purchase cost in period t a = one period discount factor M = a large number Decision Variables It = inventory at end of period t Xt = production or purchase quantity in period t (decision variable) f 1 if Xt > 0 Yt = { otherwise The problem can be stated: T minimize at-l(StYt + CtXt + ahtI) t=l s.t. It = It-1 + Xt dt for all t 0 < X < MYt for all t Yt s {0,1} for all t It > 0 for all t where Io 0. We make the conventional assumptions that setup costs and production or purchase costs are incurred at the beginning of the period, while inventory holding costs are incurred at the end of the period. We also assume that there are no production or storage capacity constraints (i.e., M = A). Observe that this problem can be modeled as a single-source, concave cost network flow problem. Zangwill (1969) has shown that the optimal solution to such problems is an extreme flow. In the context of dynamic lot sizing problems, this means that the optimal solution satisfies XtIt_1 = 0 for all t. Therefore, production occurs only when there is zero inventory so that each production quantity satisfies demand for an integral number of consecutive periods. This property is sometimes referred to as the Wagner-Whitin property. 3

We utilize this result in the remainder of the paper by examining only solutions that satisfy this property. 3.0 Conditions for the Existence of Forecast Horizons Bean and Smith (1984) show that sufficient conditions for the existence of forecast horizons for a very general class of discounted infinite horizon problems are (1) finiteness of the number of options at each decision epoch, (2) sufficient discounting, and (3) a countable set of potentially optimal strategies. With these conditions, forecast horizons exist for all but at most a countable number of interest rates. The first two conditions are needed to ensure that an optimal solution exists. The third condition ensures that it is unique for all but at most a countable number of interest rates. Since the DLSP is a special case of the problem class they considered for all parameter values, we may establish existence of forecast horizons for almost all interest rates by first establishing when conditions (1), (2), and (3) hold. In order to establish existence of an optimal solution, some preliminary conditions related to finiteness of lot sizes and costs are necessary. These finiteness conditions are discussed in Section 3.1. Existence results follow in Section 3.2. 3.1 Conditions Related to Finiteness Two preliminary conditions must be satisfied: finite candidate lot sizes and sufficient discounting. These conditions are discussed in sections 3.1.1 and 3.1.2. 3.1.1 Finiteness of Candidate Lot Sizes We must determine conditions which will ensure that all candidate lot sizes are finite to guarantee a finite number of options in each period. This can be achieved by determining a relationship among the various costs such that for 4

each time period t, there exists some j < X such that it is preferable to set up in period t + j than not to set up. The existence of positive setup costs encourages less frequent setups. The presence of positive inventory holding costs encourages more frequent setups. Variable unit production costs may encourage either depending upon the relations among Ct. Ct+1av Ct+2a,..., Ct+ma,.... Lemma 2 in the Appendix gives conditions leading to finite candidate lot sizes. We henceforth assume that these regularity conditions are satisfied; namely, that lim sup dt > 0 and that there exist bounds h > 0, S < w, and C < X such that ht > h, St < S, and Ct < C for all t. In section 4.2 we demonstrate how to calculate this uniform upper bound on the periods covered by one lot. There are other non-economic conditions in a more general framework which can provide an upper bound on lot sizes. If the item is produced, capacity constraints may limit lot sizes. Even if we assume that one setup occurs and production continues indefinitely without another setup, planned maintenance, unplanned breakdowns, model or style changes, etc., all will precipitate another setup, hence limiting the lot size. If the item is purchased, warehouse capacity or vendor capacity surely will limit the maximum lot size. 3.1.2 Finiteness of Total Discounted Costs The condition that guarantees convergence of total discounted costs is analogous to the convergence criteria in Bean and Smith (1984). Cost flows must be sufficiently discounted. For most realistic problems we will see that sufficiently means any a < 1. This condition is used to prove the existence of forecast horizons, but is not necessary to implement the algorithm that follows. 5

Defn: For some sequence {at}t=, define t t Y(at) = lim sup In Z a |I = lim su In i Z as. t o) s =1 s r= t> s1 s ~ t t From Bean and Smith (1984) the total discounted costs converge if a < e-Y where Y = Y(Kt) where Kt = StYt + CtXt + ahtIt. In most realistic applications this restriction is very mild. If the costs increase as any polynomial, this restriction reduces to a < 1. In particular, since there is a uniform upper bound on Xt and hence on It from the previous section, uniform upper bounds on St, Ct, and ht reduces the restriction to a < 1. Traditionally, the DLSP is undiscounted. In the case above simply use infinitesimal discounting to ensure existence. Hence, the requirement of sufficient discounting is actually a regularity condition. 3.2 Existence Results We have obtained the regularity conditions on costs and demand so that the conditions in (1) and (2) in Section 3.0 are satisfied. From Bean and Smith (1984), condition (3) will be satisfied whenever the problem data is eventually cyclic. In any problem that is expressed in finite information, all data sequences are eventually cyclic. Hence, any problem solved on a computer is addressed by the following result. Defn.: A sequence tat}t=1 is eventually cyclic if and only if there exists a time T and period p such that for all t > T, at+p = at. For example, if at becomes constant, p=1. If at becomes 5,4,3,7,5,4,3,7,5,4,3,7... after some T, it is eventually cyclic with p=4. By Lemma 2 in the Appendix, for any realistic problem the optimal production schedule is eventually cyclic. Hence, there is a one-to-one correspondence between all such schedules and the rationals. Then, the set of potentially optimal strategies is countable and condition (3) is satisfied. Hence, we have proven the following theorem. 6

Theorem 1: If {St}, tdt}, {ht}, and {Ct} are eventually cyclic and uniformly bounded away from zero and infinity, then forecast and decision horizons exist for all but countably many a < 1. Any problem solved digitally must be expressed in finite information and hence must be eventually cyclic. One consequence of the above result is that, within the mild regularity conditions above, a discounted DLSP solved by this code will stop in finite time for all but a countable number of interest rates. The rate of convergence, however, is still an issue. The next section discusses an algorithm for finding forecast horizons in a rolling horizon procedure. 4.0 Rolling Horizon Algorithms 4.1 An Optimal Procedure From Section 3.1.1 we know that there is a finite maximum potential lot size for all times, t. Let m(t) be the maximum potential lot size at time t in number of periods of supply. An algorithm for calculating m(t) is clear. Compare the relevant costs of satisfying the demand for periods t through t + m- 1 by a) setting up once at time t, versus, b) setting up at time t and some intermediate time t' where t < t' < t + m. If for any such t' the latter cost is less than the former cost, then m(t) is this value of m. Otherwise, increment m and repeat. Having determined the maximum candidate lot size for each period, we can use this information to find forecast horizons. Let ft(T) be the policy for period t in a T period problem. For the DLSP, wt(T) represents the optimal production quantity in period t for the T period problem. We want to find a period T such that Ir1(T ) = r 1(X) = "r1, where r1 is the infinite horizon optimal policy for period 1. For any finite T, the Eppen, Gould and Pashigian (1969) algorithm can be used to determine wr(T), provided that the conditions on unit production costs 7

required for their algorithm hold. If not, a network algorithm such as Zangwill (1968) can be used to determine ri1(T). Given some Ts, let Tw = min(t: t + m(t) > Ts). Theorem 2: For any Ts > m(1), if ir(T) = l(Ts) for Tw < T < Ts then 1 (T) = X1. Proof: By construction there is no production level at time t < Tw that carries the system beyond time Ts. Hence, all infinite horizon strategies have a production point in [Tw, Ts]. Because production points are dynamic programming state variables, any infinite horizon optimal strategy begins with the optimal strategy from time zero to that production point in [TW, Ts]. If all of these begin with the same current production level, so must the infinite horizon optima. E] The following is a forward dynamic programming algorithm which uses the result of Theorem 2 as a stopping rule. (A weak forecast horizon is a study horizon for which solving the problem for any T beyond that horizon gives the infinite horizon optimal solution for the first decision. A strong forecast horizon is a horizon for which demand and cost information beyond that horizon has no impact on the optimal first decision for any well-defined problem.) (1) Find m(1). (2) Set Ts = m(1) + 1 and t' = 1. (3) Find m(t, Ts) s min{m(t), Ts} for t' < t < Ts. (4) Set t' = Ts - 1. (5) Find min{t: t + m(t, Ts) > Ts} = Tw. (6) Find Irl(t) for Tw < t < Ts. (7) If R?(T \ )If (Tw) =... = "(Ts) then ** w)... (T) then r- = 1r1(Ts). Tw is a weak forecast horizon and Ts is a strong forecast horizon. Otherwise set Ts = Ts + 1 and go to step 3. 8

Note that to find m(t, Ts) no information beyond Ts is necessary. The algorithm to find m(t) need only be run to m(t), or to discover that m(t) > Ts, whichever comes first. 4.2 An c-Optimal Fixed Horizon Procedure The following algorithm uses a general result in Bean, Birge, and Smith (1984). They showed that in a sequential decision making problem, under mild regularity conditions, a rolling fixed horizon algorithm using horizon Te will achieve a discounted cost within 6 of optimality where K ln(1 + ) T = ------- ln(-) a where K corresponds to the largest single decision cost that one can feasibly incur. It should be noted that in this procedure we must roll forward T periods. In the optimal variable horizon algorithm we rolled forward to the decision horizon (also called planning horizon). We will use this result to establish a horizon sufficiently long to guarantee a given relative error bound e expressed as a percentage of optimal total discounted costs. Following are bounds on K and the infinite horizon cost which can be used to select e corresponding to the maximum allowable percentage error. The upper and lower bars on C, d, h, and S denote the upper and lower bounds of the respective parameter values where we here assume d > 0. We make two observations. First, the maximum savings of variable production costs to be gained by producing dt+m in some period t rather than in period t+m is (arF - C)d. Similarly, the minimum holding cost incurred by producing dt+m in period t rather than in t+m is hda(1 - am) / (1 - a). 9

Therefore, an upper bound on the largest lot size, in periods, would be the largest value of m such that a m > hd a(1 - am) / (1 - a) - (aIm-C)d > 0. (1) Let m be a uniform upper bound on the time supply covered by one lot. Then K S + m(m-1) hd/2 + mCd (2) We also make the observation that if Ct = 0 for all t, then for the infinite horizon problem < 2S (3) since otherwise it would be more economical to setup twice. We turn now to determining a value of e which ensures that total discounted costs are within a specified percentage of optimality. Observe that if we can obtain a lower bound on total cost per period, we can discount this stream of cash flows to the present to obtain a lower bound on total discounted costs. Let TC represent total discounted costs. Then, TC > [1/(1-a)] (S/m + Cd) The term in brackets discounts the infinite stream of cash flows to the present. Since m is the largest time supply, the average setup cost per period is at least S/m. Observe that since the setup cost is incurred when the lot is produced, the average cost per period, discounted to the present, represents a lower bound on the actual cost. The average variable production cost per period is greater than or equal to Cd. We therefore only need to find, m, the largest value satisfying (1), compute K according to (2) or (3) and to choose E such that [1/(1-a)][S/m + Cd] The value of T* will ensure a rolling horizon solution within the specified a 10

percentage of optimality. 5.0 Experimental Results We constructed sets of problems in an attempt to ascertain characteristics of forecast horizons under a variety of conditions. Specifically, we had the goal of answering the following questions: (1) In discounted problems, are forecast horizons found within a reasonable period of time for problems in which forecast horizons do not exist for the undiscounted problem? (2) How does T~ vary with the discount factor a? (3) What is the relationship between the forecast horizon and the natural cycle (the average number of periods between setups)? (4) How does the performance of this algorithm compare with other algorithms? For problems used to answer the third and fourth questions, we assumed a = 1 (no discounting), and demand is randomly generated for the entire horizon, so we cannot ensure the existence of forecast horizons. However, as noted earlier, it has been observed empirically that forecast horizons usually exist even in undiscounted problems. Since most experimental results in the literature involve undiscounted problems, we selected similar problems to facilitate qualitative comparison of results. We present results from an algorithm proposed by Chand and Morton (1983), and the algorithm outlined in Section 4. These are abbreviated as "CM" and "BSY," respectively, in the tables that follow. When applicable, we determine both strong and weak forecast horizons. We constructed a small set of problems for which decision horizons do not exist in the absence of discounting. Specifically, we determined conditions necessary for the absence of decision horizons when the natural cycle is 2 and 11

used these conditions to construct a problem set. The natural cycle is the average number of periods between setups or /'-i-~ h. We set St = 20, Ct=O and ht = 1 for all t, dt = 10 for t > 3, and d2 and d3 so that undiscounted forecast horizons did not exist. Note that for d1 > 0, the timing of production runs is independent of d1 since a setup is required in period 1. The problem data and forecast horizons for a =.985 are exhibited in Table 1. It is evident that the forecast horizons (when found) are relatively long but that they can be found in most cases by including some discounting. Recall that these are contrived problems, and therefore one would expect better results in real problems. TABLE 1 These problems also are used to demonstrate the effect of the discount factor, a, on T6. We first note that these problems have the characteristic that it is uneconomical to produce to satisfy demand for more than two periods. Since d2 and d3 are at most 19, from (2), K for all 20 problems is 39. We observe next that with the exception of the first 2 periods, the undiscounted cost incurred per batch is S + 10h, or approximately 30 every other period. By calculating the present value of this infinite stream, and adding the discounted costs for the first two periods, we can obtain a bound for total discounted costs of an optimal solution. We use these values to choose appropriate values for E. Table 2 lists upper bounds for TG expressed as a multiple of the natural cycle as a function of a and the percentage e above optimal, or /total discounted costs. The discount factors a =.995,.985, and.975 correspond roughly to annual discount rates r =.06,.181, and.304, respectively, if one assumes that the data reflect monthly demand. The values of T* are upper 12

bounds because we have used K = 39 which exceeds the actual values for these problems. TABLE 2 The results indicate that even a small tolerance for suboptimality significantly reduces data collection requirements. Moreover, data requirements can be reduced further by using rather modest discount rates, particularly when the tolerance for suboptimality is low. The results corroborate the rule of thumb that five EOQ's worth of data will provide results within one percent of optimum (Schwarz (1975)). However, they also indicate that no more than three to four EOQ's of data are needed to obtain the same results with moderate discount rates. We next constructed a set of problems with constant costs and randomly generated demands to test the performance of the algorithm and to evaluate the relationship between the forecast horizon and the natural cycle. We set d=200, h=1, c=O, and S so that the natural cycle takes values of 2,3,4,6, and 8 (i.e., S=400, 900, 1600, 3600, 6400, respectively). For one set of problems, demand is distributed uniformly around 200 with a range of 75, which is the same as in Baker (1977). In the second set of problems, demand is distributed normally with p = 200 and a = 20. The median forecast horizons for 5 randomly generated problems for each combination of natural cycle and demand distribution are presented in Table 3, expressed as a multiple of the natural cycle. TABLE 3 We also randomly generated a set of problems using the same demand distributions, setup costs, and production costs as described above, but with speculative motive for holding inventory. This was accomplished by randomly generating inventory holding costs having a normal distribution with mean 1.0 13

and standard deviation 1.0. This resulted in approximately 1/6 of the periods (on average) having negative holding costs, and thus speculative motive for holding inventory. Median forecast horizons are expressed as a multiple of the natural cycle. TABLE 4 We make several observations concerning the results. First, the Chand and Morton algorithm and the algorithm presented here perform almost identically on problems that fit within the more restrictive assumptions of the former. Our algorithm locates weak forecast horizons no later than the Chand algorithm. This is evident in the medians but the statement is true for all specific problems as well since Chand and Morton locate the minimum strong forecast horizon. This results from the fact that our algorithm finds the minimum of weak forecast horizons while the Chand procedure locates one weak horizon. On the other hand, the Chand algorithm locates a strong forecast horizon no later than our algorithm. This is true both for the medians and for each specific problem. This relationship arises because our procedure is designed to handle more general cost structures and thereby loses some of its power when applied to specific cases that do not require all the generalities. Nevertheless, the differences between the horizons found by the two algorithms tend to be small. Since the Chand algorithm could be easily altered to also find the minimum weak forecast horizon, the merit of our procedure rests with its ability to handle all dynamic lot size problems including those with speculative motive for holding inventory. Second, the ratio of the forecast horizon to the natural cycle does not appear to be monotonic. This creates some difficulty in selecting a rule of thumb horizon length which is either a constant multiple of the natural cycle, or a multiple which is a function of the natural cycle. 14

Third, the forecast horizons for problems with speculative motive for holding inventory are the same order of magnitude as for problems without speculative motive. In fact, in many cases, the median forecast horizons are smaller. This is partially attributable to the fact that while inventory holding costs could be negative, they could also be larger than the mean. These large holding costs contribute to reducing the length of the forecast horizon by limiting the the maximum economic lot sizes. Overall, the results indicate the forecast horizons do exist when there are time-varying inventory holding costs with speculative motive, and that the algorithm can find them. Our final observation is that the coefficient of variation for all these sets of problems is small, so demand is relatively smooth. Forecast horizons would be discovered more quickly, on average, for problems with "lumpier" demand since demands much larger than average tend to induce setups. Most real-world problems have lumpy demand. Therefore, one may view these results as representing conservative estimates of the length of forecast horizons. 6.0 Summary and Conclusions We have developed conditions for the existence of decision and forecast horizons for the dynamic lot size problem with discounting and have presented a rolling variable horizon algorithm which is guaranteed to find these horizons when they exist. The conditions for forecast horizon discovery are milder than required by other approaches. We also make no assumption about the lack of a speculative motive for holding inventory (i.e., that Ct + ht > Ct+1 for all t) as required in most of the other algorithms. We therefore are able to locate decision and forecast horizons for a very general class of problems. Experimental evidence indicates that forecast horizons typically are located within reasonable periods of time even in contrived problems and in the absence of discounting. 15

We also provided a rolling fixed horizon procedure that is guaranteed to achieve a cost within a user specified error. The procedure is unique in that the selection of horizon time can be made in the absence of specific forecasted demand information. Acknowledgement The work of James C. Bean and Robert L. Smith was supported by the National Science Foundation under Grant No. ECS-8409682. We would like to thank an anonymous referee for many valuable suggestions. 16

Table 1 Forecast Horizons Given Various Demand Levels in Problems Where No Horizons Exist in the Undiscounted Case d2 d3 Forecast Horizon 11 9 35 12 11 17 13 10 61 14 9 > 100 15 6 18 15 12 63 15 14 17 16 10 >100 16 12 >100 16 15 17 17 8 18 17 13 >100 17 16 19 18 9 18 18 15 65 18 17 19 19 10 18 19 18 19 17

(expressed as e (% Above Optimal).1.5 1 2 5 10 Table 2 Upper Bounds for T a multiple of the natural cycle r) a.995.985.975 22.0 10.2 6.9 10.7 6.0 4.4 7.0 4.4 3.3 4.2 3.0 2.4 2.0 1.6 1.4 1.0.9.8 Note: t = 2 18

Table 3 Median Forecast Horizons for Problems with Randomly Generated Demands (expressed as a multiple of the natural cycle ') Uniform Demand Distribution 2 3 4 6 8 CM BSY Weak 1.5 7.7 3.3 6.5 7.4 Strong 1.5 8.3 3.7 7.2 8.1 Weak 1.5 7.1 2.7 6.2 7.0 Strong 1.5 8.3 3.7 7.5 8.3 Normal Demand Distribution 'U CM BSY 2 3 4 6 8 Weak 2.5 5.3 3.0 3.8 6.9 Strong 3.0 6.0 3.5 4.5 7.7 Weak 2.0 5.0 2.5 3.7 6.8 Strong 3.0 6.0 3.5 4.8 8.0 19

Table 4 Median Forecast Horizons for Problems with Randomly Generated Demands and Speculative Motive for Holding Inventory (expressed as a multiple of the natural cycle t) Uniform Demand Distribution T 2 3 4 6 8 Weak 2.0 1.7 1.8 2.7 2.0 Strong 3.0 2.3 3.0 3.7 3.0 Normal Demand Distribution 2 3 4 6 8 Weak 0.5 1.3 1.3 2.7 3.9 Strong 1.0 2.3 2.3 3.7 5.1 20

APPENDIX The following lemma states that if problem data is eventually cyclic, then so are the production schedules. Lemma 1: If {St}, {dt}, {ht}, {Ct} are all eventually cyclic then so is the optimal production schedule. Proof: Let p, pd' Ph, and PC be the periods of the above sequences and TS, Td, Th, and TC be the times where periodicity begins. Let p = PS Pd Ph PC' From T = max(Ts,Td,Th,Tc), consider the sequence of times {T + ip}i=1. Since production is uniformly bounded, so is inventory. Assume that bound to be I. At all times inventory is an element of the set {0,1,2,...,I}. Some inventory level in this set must occur infinitely often in the sequence of times {T + ip}i1. At each of these occurrences the problem encountered is identical. Hence, the optimal decision made will be identical. Then the optimal production schedule is eventually cyclic with period some finite integral multiple of p. [ In the following we establish conditions for the existence of a uniform upper bound on the number of periods of demand in a single production run. Let Tt be the optimal production size at time t, in periods. Recall that wt is the optimal production quantity. Lemma 2: If d' = limsup dt > 0 and there exist bounds such that h > h > 0, St S < a, Ct < C < <, then there exists m < X such that t < m for all t. Proof: It suffices to show that at any t, the cost to produce the demand for period t + m in period t and hold it for m periods is greater than the cost to set up and produce in period t + m. A sufficient condition for this is 21

t+m-1 Ctdt+m + d+m it hiat1 > (St+m + Ct+mdt+m)am But the left hand side of this inequality is bounded from below by t +m-1 mm(Ctdt+m + dt+m it hi) Hence, a sufficient condition is that t+m-1 dt+m > St+m (Ct -Ct+m + t hi)-l ( Now t+m-1 t+m (Ct Ct+m + it hi )1 < (mh )1 as m goes to infinity by the hypotheses. Since d' > 0, there exists an m where (4) is satisfied. To this point, the upper bound on production time length depends on t. If the additional condition is imposed that the number of consecutive periods with zero demand is bounded, then the conclusion can be strengthened to a uniform upper bound. This corresponds to the assumption made in Section 3.1.1. 2 22

REFERENCES Baker, Kenneth R., "An Experimental Study of the Effectiveness of Rolling Schedules in Production Planning", Decision Sciences, 8(1977), 19-27. Bean, James C., John R. Birge, and Robert L. Smith, "Aggregation in Dynamic Programming", Technical Report 84-10, Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, April, 1984. Bean, James C. and Robert L. Smith, "Conditions for the Existence of Planning Horizons", Mathematics'of Operations Research (1984) Vol. 9, pp. 391-401 Blackburn, Joseph D. and Howard Kunreuther, "Planning Horizons for the Dynamic Lot Size Model with Backlogging", Management Science (1974), 251-255. Blackburn, Joseph D. and Robert A. Millen, "Heuristic Lot-Sizing Performance in a Rolling-Schedule Environment", Decision Sciences, (1980), 691-701. Carlson, Robert C., Sara L. Beckman, and Dean H. Kropp, "The Effectiveness of Extending the Horizon in Rolling Production Scheduling", Decision Sciences, 13 (1982), 129-146. Chand, Suresh, "A Note on Dynamic Lot-Sizing in a Rolling Horizon Environment", Decision Sciences, 13 (1982), 11 3-118. Chand, Suresh and T. E. Morton, "Minimal Forecast Horizon Procedures for Dynamic Lot Size Models", Working Paper, Purdue University, 1983. Eppen, Gary D., F.J. Gould, and B. Peter Pashigian, "Extension of the Planning Horizon Theorem in the Dynamic Lot Size Model", Management Science, 15 (1969), 268-277. Lundin, R. and Thomas Morton, "Planning Horizons for the Dynamic Lot Size: Zabel vs. Protective Procedures and Computational Results", Operations Research, 23 (1975), 711-733. Schwarz, Leroy B., "A Note on the Near Optimality of '5-EOQ's Worth' Forecast Horizons", Operations Research, 25 (1977), 533-536. Wagner, Harvey M. and Thomas Whitin, "Dynamic Version of the Economic Lot Size Model", Management Science, 5 (1958), 89-96. Zabel, Edward, "Some Generalizations of an Inventory Planning Horizon Theorem", Management Science, 11 (1964), 465-471. Zangwill, Willard I., "A Backlogging Model and a Multi-Echelon Model of a Dynamic Economic Lot Size Production System - A Network Approach", Management Science, 15 (1969), 506-527. Zangwill, Willard I., "Minimum Concave Cost Flows in Certain Networks," Management Science, 14 (1968), 429-450. 23

UNIVERSITY OF MICHIGAN 3 9015 03994 8347