INFINITE HORIZON PRODUCTION PLANNING IN TIME VARYING SYSTEMS WITH CONVEX PRODUCTION AND INVENTORY COSTS Robert L. Smith and Rachel Q. Zhang Department of Industrial & Operations Engineering The University of Michigan Ann Arbor, Michigan 48109-2117 Technical Report 96-11 September 1996

INFINITE HORIZON PRODUCTION PLANNING IN TIME VARYING SYSTEMS WITH CONVEX PRODUCTION AND INVENTORY COSTS Robert L. Smith and Rachel Q. Zhang Technical Report 96-11 Department of Industrial and Operations Engineering University of Michigan, Ann Arbor, Michigan 48109 September 1996 This work was supported by the National Science Foundation under grants DDM-9214894 and DMI-9501740.

Infinite Horizon Production Planning in Time Varying Systems with Convex Production and Inventory Costs* Robert L. Smith and Rachel Q. Zhang Department of Industrial and Operations Engineering University of Michigan Ann Arbor, Michigan 48109 September 6, 1996 Abstract We consider the planning of production over the infinite horizon in a system with time varying convex production and inventory holding costs. This production lot size problem is frequently faced in industry where a forecast of the future demand must be made and a production is to be scheduled based on the forecast. Since forecasts of the future are expensive and difficult to validate, a firm would like to minimize the number of periods into the future it needs to forecast in order to make an optimal production decision today. In this paper, we first prove that under very general conditions finite horizon versions of the problem exists that lead to an optimal production level at any decision epoch. In particular, we show it suffices to solve for a horizon that exceeds the longest time interval over which it can prove profitable to carry inventory. We then develop a closed-form expression for computing such a horizon and provide a simple finite algorithm to recursively compute an infinite horizon optimal production schedule. 1 Introduction The production lot sizing problem is a model for the control of production over a multiperiod planning horizon (Denardo [1982]). It is one of the most frequently used single item deterministic inventory planning models (Federgruen and Tzur [1991]). The objective is to schedule production over the planning horizon so that demand is satisfied at minimum cost. Standard assumptions are that demand is deterministic (i.e., known in advance) and backordering is not allowed (i.e., demand cannot be satisfied by future production). The fundamental economic tradeoff here is the balance of reductions in cost of production against corresponding increases in costs of carrying inventory. In the presence of economies of scale on the cost of production, it can prove profitable to produce more than the current periods demand and carry inventory forward to satisfy future demand, thereby lowering the average cost of production (cycle stock motive). Even in the absence of economies of scale in production costs, the future cost of production may exceed the cost of current 'This work was supported by the National Science Foundation under grants DDM-9214894 and DMI9501740. 1

production plus inventory carrying costs again leading to current production that exceeds current demand (speculative motive (Chand and Morton [1986])). The choice of planning horizon to employ is a difficult issue since the system being modeled typically has a long but otherwise indefinite lifespan. A resolution of this problem is to utilize an infinite horizon to model the underlying long but unknown finite horizon lifespan of the system. In the general case of time-varying demand and cost, the resulting model presents a challenging problem to solve (the stationary case reduces to the classic economic lot size (ELS) model (Harris [1990])). Early efforts to solve infinite horizon versions of the problem were restricted to the case of stationary, and usually linear, production cost, although demand was allowed to be time-varying (Kunreuther and Morton [1973, 1974], Lee and Orr [1977], Modigliani and Hohn [1955], Morton [1978a,1978b], and Thompson and Sethi [1980]). The so-called dynamic lot size version of the problem where production costs are fixed-plus-linear and inventory holding costs are linear has been extensively studied in the non-stationary case. Although the recent focus has been on computational breakthroughs in solving finite horizon versions of the problem (see e.g. Aggarwal and Park [1990], Federgruen and Tzur [1991], and Wagelmans, Van Hoesel and Kolen [1989]). the properties exploited there have in some cases been used to establish conditions on finite horizon versions of the infinite horizon problem that guarantee early decision agreement with optimal decisions of the infinite horizon problem. Such a finite horizon is called a solution horizon. When the agreement does not depend on problem data beyond this solution horizon, it is also called a forecast horizon since only data over this horizon needs to be forecasted to establish infinite horizon optimal early decisions (Bes and Sethi [1988]). Although solution and forecast horizons may fail to exist here, Federgruen and Tzur [1991, 1992] provided a stopping rule that is guaranteed to be met whenever they do exist. Specifically. they exploited monotonicity of optimal cost differences to establish necessary and sufficient conditions for a horizon N to be a forecast horizon. This monotonicity condition implies monotonicity with respect to N in the last period with production. This last property has been extensively exploited to generate forecast horizon existence and discovery results for variations on the dynamic lot size problem (see e.g. Wagner and Whitin [1958]. Zabel [1964]. Eppen et al. [1969], Thomas [1970], Blackburn and Kunreuther [1974], Lundin and Morton [1975], Bensoussan et al [1983], Chand [1982], Chand, Sethi, and Proth [1990], and Chand. Sethi and Sorger [1989]). See also Heyman and Sobel [1984] for a general review of using policy monotonicity in homogeneous MDP problems. In this paper, we consider the infinite horizon version of the general production lot sizing problem under diseconomies of scale in production and inventory holding costs. This convexitv assumption is equivalent to the condition that marginal production and holding costs be nondecreasing. For example, this includes the case where inventory costs are linear and where a firm experiences a higher overtime rate for production exceeding the standard capacity followed by a still higher unit cost for exceeding overtime capacity through outsourcing. The optimization problem to be solved falls within the class of doubly infinite convex programming problems. There is an extensive literature on solution and forecast horizon approaches to solving such general problems in infinite horizon optimization (see e.g. Bean and Smith [1984, 1993], Bes and Sethi [1988], and Schochetman and Smith [1989, 1992]). However a key assumption that guarantees that general purpose algorithms will successfully discover an equivalent finite horizon problem is uniqueness of an infinite horizon optimal 2

solution. Although this condition is believed to be typically met in practice, it is difficult to verify. In this paper, we instead explore a novel algorithmic approach for finding solution and forecast horizons that systematically exploits monotonicity of optimal early decisions in horizon N. This focus on early decision monotonicity, as opposed to late decision monotonicity as in the treatment of the dynamic lot size problem, leads to a closed form expression for a forecast horizon guaranteed to yield optimal early production decisions for the infinite horizon problem. As we will show, the length of the forecast horizon is the longest interval of time over which it can prove profitable to carry inventory. The paper is organized as follows. In Section 2, we formulate the infinite horizon model of the problem. In Section 3, we prove that under very general conditions, solution horizons exist leading to finite horizon versions of the problem that yield optimal solutions to the infinite horizon problem. In section 4, we give a closed-form expression for computing a solution (indeed forecast) horizon and a simple procedure for computing an optimal infinite horizon production schedule. 2 Problem Formulation Consider a single-product firm where a decision for production must be made at the beginning of each period n, n = 1,2,. *. We will adopt the following notation: Constants and functions: Dn = the demand during period n (non-negative integers) a = the discount factor for the time value of money (0 < a < 1) Io = the inventory on hand at the beginning of period 1 (integers) Cn(x) = the cost of producing x units of the product during period n (non-negative) h,(x) = the cost of holding x units of inventory ending period n (non-negative) Decision variables: Pn = the production level during period n In = the inventory on hand at the end of period n We will use the superscript (*) to denote optimality. With the above notation, we can formulate this infinite horizon problem, labeled Q, as (Q) Minimize: E ca'n [cn(P,) + hn(In)] (2.1) n=l Subject to: In-I +Pn,-Dn= In, n= 1,2,.. (2.2) Pn > 0, In > 0, n= 1,2,. - (2.3) Pn, In integer, n = 1,2, -. (2.4) where I is given. As we can see from (2.2), if we know the production levels Pn in all periods. we can determine the inventory levels In. Therefore, it suffices to find an optimal production schedule P* = P/, PI, P;, *. Note however that this is a doubly infinite integer nonlinear programming problem and is therefore a formidable problem to solve. 3

3 Existence of Solution Horizons We now investigate conditions under which a finite horizon version of the problem has an optimal first decision which is in agreement with an infinite horizon optimal first decision. If we can find an optimal infinite horizon first decision P; by solving a finite horizon version of the problem, we can roll forward one period and form a new infinite horizon problem with new initial inventory I1' = Io + P1 - D1 to obtain an optimal infinite horizon seconddecision for the original problem. This rolling horizon procedure can then recursively recover an optimal infinite horizon production schedule. In this section, we formulate the N-horizon truncated version of the problem and show that optimal production levels of the N-horizon problem are increasing in N. We then identify conditions under which an N-horizon optimal nth decision, 1 < n < N, converges as N - oo to an infinite horizon optimal nth decision. Finally, we establish existence of a finite horizon version for solving the infinite horizon problem. 3.1 The N-Horizon Problem We formulate the N-horizon problem, labeled (Q(N)), corresponding to the original infinite horizon problem (Q) as: N (Q(N)) Minimize: E an-[cn(Pn) + hn(In)] (3.5) n=l Subject to: In-1 + Pn - Dn = In, n = 1,2,,, N (3.6) Pn > 0, In 0, n= 1,2,.-,N (3.7) Pn, In integer, n = 1,2,., N (3.8) Let S be the set of all feasible production schedules to (Q), S(N) the set of feasible production schedules to (Q(N)), P(N) any feasible production schedule to (Q(N)), and I(N) the ending on hand inventory resulted from the production schedule P(N), N = 1,2,. The following lemma states that for the finite horizon problem, increasing the demands does not decrease the optimal production levels. Lemma 1 (Veinott [1964]) Let P*(N) = (Pi*(N), P2(N),.., P(N)) be an optimal solution for a vector (D1, D2, * *, DN) of demands and suppose production and inventory holding cost functions are convex. If one of these demands is increased by 1 unit, it is optimal to increase one of these production levels by 1 unit. The proof of this lemma can be found in Denardo [1982]. Consider now the demand profile for an N + 1-horizon problem where DN+1 = 0. Since, without loss of optimality, we never leave positive inventory at the end of a horizon, we conclude Ik = 0 at an optimal solution if DN+1 = 0. By the principle of optimality, P;(N) = P;(N + 1) (3.9) with DN+i = 0. Hence applying the lemma repeatedly, we have P(N)<) P((N + 1), for N =1,2, — (3.10) 4

for any DN+l. Following the same argument, we also have P,(N) < Pn(N+ 1), for all 1 < n <N N = 1,2, ---. (3.11) Hence, we have proved the following Corollary. Corollary 1 Pn(N) is monotonically increasing in N for any fixed n, 1 < n < N. 3.2 Optimal Solution and Value Convergence of the N-Horizon Problems Before we discuss convergence of optimal solutions of the N-horizon problems, we need the following notation and assumptions. Let C(P) be the objective function of (Q) for an? given P E S and C* = C(P*). Also let C(P(N); N) be the objective function of (Q(N)) for any given P(N) E S(N) and C*(N) = C(P'(N); N). Furthermore, we assume, AO: cn(-) and h,(-) are convex functions for all n = 1,2, - -. Al: C(P') < oo for some feasible production schedule P' E S, i.e., there exists a finite cost feasible production schedule to (Q). A2: lim hn(I,) = oo, i.e., the cost of carrying inventories that increase to infinity itself In - 0 increases to infinity. A3: 0 < n < cn(Pn) - cn(Pn - 1) ~ yn < oo for all integers Pn > 0 and all n = 1,2,... i.e., the marginal cost of production is bounded from above and bounded away from zero for all n = 1, 2,. W\e now show P, (N) converges to an infinite horizon optimal nth decision Pn < oo for all n (Theorem 1). That is, lim Pn(N) = Pn under the above conditions. We will achieve this NV —oo first by showing that P7(N) converges to an infinite horizon feasible solution as N - oX (Lemmas 2 and 3) and then that value and solution convergence holds for all n = 1,2,.. (Lemma 4 and Theorem 1). Lemma 2 There exist finite production bounds Pn, n = 1,2, *, so that Pn((N) < Pn < Xo for all N. Proof: Suppose not. then there exists some n and subsequence N, k = 1, 2, -, such that lim Pn (Nk) = oo. (3.12) k —oo, By assumption (A2), lim hn(In(Nk))= oc (3.13) k-coo where In(NIV) is the optimal on hand inventory at the end of period n following the nth production decision P7(Nnk) and hence lim C'(Nk) = oo. (3.14) k-oo However, C*'(A ) < C(P'(N ); NJ) < C(P') (3.15) 5

where P'(Nj) consists of the first Nk decisions in P' and by (Al) C(P') < oo. (3.16) This contradicts equation (3.14). O By Corollary 1, at any decision epoch, n, there exists a monotonically increasing sequence of decisions Pn(N), N = 1,2, -.. By Lemma 2, this sequence of values is bounded from above. Therefore, P,(N) must converge as N goes to infinity, i.e., lim P,(N)= Pn < oo (3.17) N-*oo exists for all n = 1,2,.. It remains to show P is infinite horizon optimal. Lemma 3 P E S, i.e., P is infinite horizon feasible. Proof: Since im Pn(N) = Pn, n = 1,2,..., (3.18) N-oo for any c > 0. there exist integers N,(n) > 0, n = 1, 2, *, such that IP,,(N)- Pl < E, n= 1,2,., (3.19) for N > N,(n), n = 1, 2,.. Recall that production levels are integers. If we let = 1, then there exist integers Nl(n) > 0, n = 1,2, *., such that Pn(N)= Pn, n = 1,2,, (3.20) for NV > N-1(n), n = 1.2, -.. Therefore, at any decision epoch, n, n n A, P= - Y P j (N) > -Io (3.21) (3.21) 2-=1 j=-1 7=1 for all N > max {Ni(j)}. Hence, PJn is feasible for the infinite horizon problem. _<j_<n Lemma 4 lim C*(N) = C*, i.e.. optimal value convergence holds. N-oo Proof: For any feasible infinite horizon schedule P E S, the first N decisions P(N) are feasible to (Q(N)). Therefore, since costs are non-negative, C'(N) < C*. Also, for any feasible N + 1-horizon schedule P(N +1), the first N decisions P( N) are N-horizon feasible. Therefore, C*(N) is increasing in N. This implies that lim C*(N) exists where N —oo lim C*(N) < C' < oo. (3.22) N- oo 6

By (Al), we have F' E S and C* < C(P') < oo. For every N, we construct the followingi feasible infinite horizon production schedule Pby setting Pn n' In- f n= N +l (3.23) { Pn' if n >N+ 1 with corresponding ending inventory In n' if >N+1 where I' is the ending inventory following the production schedule P'. Then C(P) =C*(N) + caN[CN+l(PbN+l) + hN+1(IN+1)] +{fC(P') - C(P'(N); N) - aN[CN+l(P~+l) + hN+I(I~+I)] (3.24) where P'(N) is the first N decisions in P'. Since lim C(P'(N); N) = C(P') K oc and by N ---ooI (A3), we have This implies lirn {C(P') - C(P'(N); N) - aNv [CNl(P'+) + hN+l (I~+I)] +aN [CN+1(.PN+l) + hN+1(!N+l)] lirn a N[CN1(PN) - CN+1(Pk+j) + hN+1(IN+l) - hN+1(I~+J)} lim 0N [CNi(P'+ + Ij~) - ICN+i(PJ~+l) + hN+(I&+i) - h+(~0 N-cc lim 0N [CN~(P'+ + I&) - CN+1(PK+1)] N-cc lim aN 7N+I& IV- or C S lim C*(N)~>C *. N-oo Combining (3.22) and (3.25), we have (3.25) lim C* (N) =C*.N-~oo (3.26) C We can now show our result that finite horizon optima monotonically converge upwards to an infinite horizon optimal solution. T heorem 1 The infinite horiz-on production schedule P* = lim P* (N) where P* (N +l) > N-oo P'(N) is infinite horiz-on optimal. i.e., monotonic optimal solution convergence holds. I.

Proof: Recall that lim P,*(N)= Pn < (3.27) N —oo for all n = 1.2, and note that N f Q~l1[c(Pn) + hn(In)] ~ C(P*(N); N). (3.28) n=1 Therefore, C(P) lim E c n -1 [Cn(Pn) + hn(in)] > lim C(P*(N); N)= C*. (3.29) N-~oo n N- oo Also, for any positive integer M, M Z an'-[Cn(P) + hn(in)] n=1 =llm ~~ a I'[c(P;(N))~ +oC") lim n [Cn(Pn(N)) __hn(I7*(N))] N-c _ =0*. Take the limit as M - oc on both sides of the above inequality to get C(P)= lim [c n-lC(-Pn) ~hn(In)]} ~C*. (3.30) Combining (3.29) and (3.30), we have C(-P)= C. From Lemma 3. P E S. Therefore, P is infinite horizon optimal. Theorem 1 allows us to easily extend Veinott's monotonicity lemma to the infinite horizon case. Theorem 2 Suppose assumptions (AO) through (A3) hold. Let P* be an optimal solution for a vector (D1i D2. ~) of demands and suppose production and inventory holding cost functions are convex. If one of these demands is increased by 1 unit, it is optimal to increase one of these production levels by 1 unit. 8

Proof: Let P* be the optimal infinite horizon schedule for a vector (D1, *, Dj + 1, ) of demands for some j' We know from Theorem 1 that for any integer n > 0, there exists an integer N, such that P,(N) P= and Pn(N) = En for all N > N,. By Lemma 1, Pn(N) > Pn(N). (3.31) Therefore, Pn >_ P:n. (3.32) The result of Theorem 1, (3.17) is called optimal solution convergence and that of Lemma 4, (3.26) is called optimal value convergence. Result (3.26) is analogous to the method of successive approximations applied to homogeneous MDP problems (Denardo [1982]). The latter may be viewed as equivalent to solving successively longer horizon problems as we iterate (the initial guess of value function is seen here as a terminal value at the end of horizon). Optimal value convergence (3.26) says that for N large enough, the corresponding optimal N-horizon plan P*(N) achieves a cost arbitrarily close to that achieved by an optimal infinite horizon solution P*, i.e., P*(N) and P* are close in value. But P*(N) is not an infinite horizon feasible solution. Optimal value convergence is therefore of limited use, approximating infinite horizon optimal cost, but not solutions, while it is the latter we need to implement. Still we may at times be able to extend P*(N) feasibly over the infinite horizon at small cost to achieve an infinite horizon feasible solution with nearly the same cost as P". The solution convergence result of Theorem 1 is however far more powerful since policies and not just costs are arbitrarily well approximated by sufficiently long finite horizon optimal solutions. In fact, the approximation to early decisions is without error in this case as we note in the next subsection. 3.3 Solution Horizons for Solving the Infinite Horizon Problem By Theorem 1, lim Pn(N) = P,n n = 1,2,. (3.33) N- oo where P" is an infinite horizon optimum. This implies that for any e > 0, there exists a horizon. NA(n) such that IP,7(N) - PnI < E, for all N > N,(n). (3.34) Let c = 1. Then lPn,(N)- PIl < 1 (3.35) so that P (N) = Pn (3.36) 9

for all N > N1(n). In particular, P (N) = P, for all N > N~ (3.37) so that NiK = N1(1) is a solution horizon. That is, there exists a finite horizon Nl sufficiently distant that an optimal finite production lot size for any horizon that long or longer yields an infinite horizon optimal first period production lot size. By forward dynamic programming, let fn(i) be the present value of the optimal cost from period 1 to period n with ending inventory level i in period n, where i > IO- Dj. Then fn(i) = min {n-l[cn(Pn) + hn(i)] + fn-l(i + Dn - Pn)} O<Pn.<Dn+i where fo(i) = 0 for i = Io and oo otherwise. If we knew the value of the solution horizon Nj1, we could then solve for fN;(O) to get Pe = Pe'(N*). From optimal solution convergence (3.17), we conclude that large horizon optimal nth period production lot sizes yield nth period optimal infinite horizon production lot sizes. We can then recursively find (Pi*, P2,.) = P* with zero error. We turn to the computation of solution (and forecast) horizons in section 4. 4 Computing Solution and Forecast Horizons W'e have shown in the previous section that there exists a solution horizon N* such that P,(N)= Pn for all N > N at any decision epoch n. In this section, we seek to find a method to compute solution. horizons for all n = 1, 2, 2 and a corresponding simple algorithm to compute the optimal infinite horizon solution P, for all n. To find a solution horizon N, we need to slightly strengthen assumption (A3) to include an upper bound on marginal production costs, i.e. we require that sup { li [Cn(Pn)-Cn(Pn - l)]} =SUp{n} = 7 <. (4.38) n>l Pn — c n>l Now consider Pj(N) as N increases. By Corollary 1, Pl(N + 1) > Pi (N). (4.39) Therefore. the optimal first decision either remains the same or increases as N increases. Suppose PI(N + 1)> P'(N). (4.40) Since moreover Pn(N +1) > Pn(N), for all <n< N (4.41) 10

by Corollary 1, an additional unit of inventory is produced in period 1 and held for N periods to satisfy a unit of demand in period N + 1. Evidently, by (4.40) it is then less costly to satisfy a unit of demand in period N + 1 by production in period 1 then by production in later periods. It follows that if Ni were a bound on the greatest number of periods it were economic to carry inventory, then Pr(N) cannot increase and must remain constant for all N > N'. Hence a solution horizon is provided by the largest period of time it can prove profitable to hold a unit of inventory produced in period 1. For example, if inventory turns over four times a year, N* would correspond to a horizon of 3 months. In this case. solving for optimal first production decisions for a planning horizon of 3 months or beyond would yield an infinite horizon optimal production decision for period 1. We turn now to deriving a formula for the computation of N;. By convexity of the production and inventory costs, the production cost of one more unit in the first period is cl(P (N) + 1) - cl(P;(N)) > c(l1) (4.42) and the inventory cost for carrying one unit to period N + 1 is bounded from below by N E an-lh,(1). Since producing one unit in period 1 and holding it for N periods to satisfy n=l one unit of demand in period N + 1 is by hypothesis optimal (i.e., it is more expensive to produce one more unit in period N + 1) and by (A3) the marginal production cost is bounded from above, we have N ci(l) + E aCn-hn(1) < aNv7N. (4.43) n=l Let N - = Na E a- hn(1) > N-7N - c(l). (4.44) I n=1 Then any N E iA is a solution horizon for the first decision, since it is prohibited to produce in period 1 to satisfy demand in period N or beyond. Let N = min {NIN E A}. (4.45) By (A3), KA is non-empty and therefore N1 -< oo. Note that N1 is also a forecast horizon since its value and hence P;(Nj) = P; is independent of demand Dn for n > N1 (in fact, its value is independent of all demand). That is, we need only forecast demand through period N1 < oc in order to determine P'. Now let us compute a forecast horizon. If we let inf {h( 1)} = a, n>l then it is obvious that a > 0 and N na-l1hn~(1) > - 0. (4.46) n=1 1-a By (4.38), a -cl(1) > a NN - Cl(). (4.47) 11

Hence, if 1 - aN > aN _- C1(1) (4.48) or N> log (1- a)cl(l)~ + (4.49) then N n-lhn(l) > a&yN - C(l). (4.50) n=1 Hence, if we set [log{(1 - a)c(l) + a (4.51) (1- a)c(1) + inf (hn(l)} n>l = log, < ----, --- —^ — l ---- > (4.52) (1- a)sup im [cn(Pn)- cn(Pn - 1)] + inf {h(l)} n>l Pn-"oo n>l where fX] represents the smallest integer strictly greater than X, then P1 = PI(N') (4.53) is an infinite horizon first decision depending only on D1, D2,.,DN;. That is. NA is a forecast horizon for the first production decision. Following the same argument, we can compute the forecast horizon for the second production decision, and so on. The following is an algorithm for computing the first n infinite horizon optimal production levels for any n = 1.2, A Finite Algorithm for Finding an Infinite Horizon Optimal Production Schedule: 1. Compute N{ using formula (4.52); 2. Compute P"(N{) and fN;(i) using the forward recursive dynamic programming procedure in Section 3.3. Let i = 0 to get Pi and P2(N)); I = Io + Pi - D1; 3. j = N' + 1; k = 2; Compute Nk; 4. While k < n do begin Repeat: Compute fj(i) using fj-1(i); Let i = 0 and choose Pk(j) and P+l(j) so that Pj > Pk(j - 1); j = j + 1 until j =.N; 12

U r v 1._ 2 1.4 1.6 1.8 2 0.2 0.2 1 2 3 4 5 0.2 0.1 2 4 6 8 10 0.2 0.05 4 8 12 16 20 0.1 0.2 1 2 3 4 5 0.1 0.1 2 4 6 8 10 0.1 0.05 4 8 12 16 20 0.05 0.2 1 2. 3 4 5 0.05 0.1 2 4 6 8 10 0.05 0.05 4 8 12 16 20 Table 1: The forecast horizon in days for the first infinite horizon optimal production level k = k + 1; Compute No; end; Note that N* is independent of all demands as well as the production and inventory costs. It only depends on the value of bounds on the inventory and marginal production costs. To get a feeling for the magnitude of our forecast horizon, we look at some examples. In the simple case where production costs are stationary and linear over time, sup{ lim [Cn(Pn) - (Pn- )]} = ci(l) n>l Pn - oo and,Vj = 1. In other words, as we would expect, we only need to know the demand in the first period to make the optimal first decision regardless of the inventory costs since no inventory is needed when production cost does not vary over time. Consider now the case where the production costs are piecewise linear or even nonlinear. II this case if we set y = ucl(1), u > 1 (i.e., the marginal production cost will not exceed Ic(l 1)) and a = vc1(1) where v is the inventory charge as the sum of a proportion of production cost, opportunity costs, taxes, insurance costs, the value loss over time (e.g., certain products have to be sold by discount), floor space rental costs, etc., then N- = Floga (1-a)u+v 1 For various inventory charges v per day, discount factor a = 1+/35 per day where r is the interest rate per year, we computed N* for u = 1 to 2. The results are shown in Table 1. W'e chose inventory costs unusually high here to illustrate how short these forecast horizons can be. However, even in the case of moderate inventory costs, forecast horizons can be significantly reduced by a more detailed analysis using ore precise cost information to provide better bounds on the minimal forecast horizon. 13

5 References Aggarwal, A. and J.K. Park. "Improved Algorithms for Economic Lot-Size Problems." 1990. Working Paper, IBM Thomas J. Watson Research Center, Yorktown Heights. NY. Bean, J. and R. L. Smith. 1984. "Conditions for the Existence of Planning Horizons." Mathematics of Operations Research 9 391-401. Bean, J. and R. L. Smith. 1993. "Conditions for the Discovery of Solution Horizons." Mathematical Programming 59 215-229. Bensoussan, A., J. Crouhy and J.M. Proth. 1983. Mathematical Theory of Production Planning, Advanced Series in Management, North-Holland, Amsterdam. Bes, C. and S. Sethi. 1988. "Concepts of Forecast and Decision Horizons: Applications to Dynamic Stochastic Optimization Problems." Mathematics of Operations Research 13 295-310. Blackburn. J.D. and H. Kunruether. 1974. "Planning Horizons for the Dynamic Lot Size Model with Backlogging." Management Science 21 251-255. Chand, S. 1982. "Lot Sizing for Products with Finite Demand Horizon and Periodic Review Policy." European Journal of Operations Research 11 145-148. Chand. S., and T.E. Morton. 1986. "Minimal Forecast Horizon Procedures for Dynamic Lot Size Models." Naval Research Logistics Quarterly 33 111-122. Chand. S.. S. Sethi, and J.M. Proth. 1990. "Existence of Forecast Horizons in Undiscounted Discrete-Time Lot Size Models." Operations Research 38 884-892. Chand, S., S. Sethi, and G. Sorger. 1989. "Forecast Horizons in the Discounted Dynamic Lot Size Model." Working Paper, University of Toronto, Toronto, Canada. Denardo. E. 1982. Dynamic Programming: Models and Applications, Prentice-Hall, Englewood Cliffs, NJ. Eppen. G. D., F.J. Gould, and B. P. Pashigan. 1969. "Extensions of the Planning Horizon Theorem in the Dynamic Lot Size Model." Management Science 15 268-277. Federgruen, A. and Tzur, M. 1991. "A Simple Forward Algorithm to Solve General Dynamic Lot Sizing Models with n Periods." Management Science 37 909-925. Federgruen. A. and Tzur, M. 1992. "Fast Solution and Detection of Minimal Forecast Horizons in Dynamic Programs with a Single Indicator of the Future: Application to Dynamic Lot-Sizing Models." Working Paper, Graduate School of Business. Columbia University, New York. Harris, F. W. 1990. "How Many Parts to Make at Once". Factory: The Magazine of Management 10 135-136. 152. 1913. Reprint, Operations Research 38, 1990: 947-950. 14

Heyman, D. and M. Sobel. 1984. Stochastic Models in Operations Research, Vol. II. McGraw-Hill,'New York. Kunreuther, H. C. and T. E. Morton. 1973. "Planning Horizons for Production Smoothing with Deterministic Demands." Management Science 20 110-125. Kunreuther, H. C. and T. E. Morton. 1974. "General Planning Horizons for Production Smoothing with Deterministic Demands." Management Science 20 1037-1046. Lee, D. R. and D. Orr. 1977. "Further Results on Planning Horizons in the Production Smoothing Problem." Management Science 23 490-498. Lundin, R.A. and T.E. Morton. 1975. "Planning Horizons for the Dynamic Lot Size Model: Zabel vs. Protective Procedures and Computational Results." Operations Research 23 711-734. Modigliani, F. and F. E. Hohn. 1955. "Production Planning over Time and the Nature of the Expectation and Planning Horizon." Econometrica 23 46-66. Morton, T. 1978a. "The Nonstationary Infinite Horizon Inventory Problem." Management Science 24 1474-1482. Morton, T. 1978b. "Universal Planning Horizons for Generalized Convex Production Scheduling." Operations Research 26 1046-1058. Schochetman, I. E. and R. L. Smith. 1989. "Infinite Horizon Optimization." Mathematics of Operations Research 14 559-574. Schochetman, I. E. and R. L. Smith. 1992. "Finite Dimensional Approximation in Infinite Dimensional Mathematical Programming." Mathematical Programming 54 307-333. Thomas. L. J. 1970. "Price-Production Decisions with Deterministic Demand." Mlanagement Science 16 747-750. Thompson, G. L. and S. P. Sethi. 1980. "Turnpike Horizons for Production Planning." Mianagement Science 26 229-241. Veinott, A.F., Jr. 1964. "Production Planning with Convex Costs: A Parametric Study." Management Science 10 441-460. Wagelmans, A., S. Van Hoesel and A. Kolen. 1989. "Economic Lot-Sizing: An O(n log n)Algorithm that Runs in Linear Time in the Wagner-Whitin Case." CORE Discussion Paper No. 8922, Universite Catholique de Louvain, Louvain-la-Neurve, Belgium. Wagner, H. M. and T. M. Whitin. 1958. "Dynamic Version of the Economic Lot Size Model." Management Science 5 89-96. Zabel, E. 1964. "Some Generalizations of the Inventory Planning Horizon Theorem." Management Science 10 465-471. 15