OPTIMAL PRODUCTION POLICIES FOR MULTISTAGE SYSTEMS WITH SETUP COSTS AND UNCERTAIN CAPACITIES Juhwen Hwang and Medini R. Singh Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, MI 48109-2117 Technical Report 93-11 March 1993

Optimal Production Policies for Multistage Systems with Setup Costs and Uncertain Capacities Juhwen Hwang Medini R. Singh Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, MI 48109 March 4, 1993 Abstract In this paper we consider a serial production process which contains several stages. At each stage, not only the production capacity is uncertain but also the setup cost may be non-zero, essentially complicating the planning and control of the production. We have shown that the form of the optimal production planning decision at each stage has either one or two critical numbers depending on the setup costs at the downstream stages. Furthermore, we demonstrate how the behavior of the critical numbers is affected by production capacity expansion, demand increase and the change of the cost parameters. 1 Introduction In many production systems, the manufacturing process for a certain type of product contains a sequence of operating stages. In view of increasingly complicated products today, the production output is not always perfect; in other words, the production output uncertainty can not be neglected. The production uncertainty is influenced by many factors, such as defective items, machine breakdowns, insufficiency of labor, etc. Furthermore, setup costs are unavoidable for some 1

manufacturing stages, such as heating, painting and coating. Both production uncertainty and setup costs essentially complicate the production planning and control in a serial process. In attempting to analyze the production uncertainty, two different methods have been developed: random yield and uncertain capacity. The random yield model focuses on unreliable production processes resulting in defective items. On the other hand, the uncertain capacity model is concerned with insufficient capacities due to machine breakdowns and shortages of resources. A random yield model of a serial production process without setup cost has been studied in Lee and Yano (1988) to deal with a single-period problem with a deterministic demand. They show that if it is beneficial to produce, the optimal strategy is a sequence of single-critical-number policies. Yano (1986a) extends their results to uncertain demand cases. Moreover, in considering the model with setup costs, Yano (1986b) shows that the optimal policy has two critical numbers in single-stage cases. For two or more stages in this system, it is still unclear whether or not there is an optimal policy with a simple form, such as an (s, S) policy. The uncertain capacity model has not been discussed very much in any production and inventory systems. Recent work by Ciarallo et. al. (1991) has shown that in a single-stage production planning system with no setup cost, the optimal policy is of an order-up-to form in both finite and infinite horizon cases, although the cost function is not convex but unimodal in every period. In this paper, we analyze a serial production system considering uncertain capacities. We have shown that the optimal strategy in our model with setup costs has a sequence of two critical numbers. In the next section we describe and formulate a single-period multi-stage production control problem with a random demand, uncertain capacities and setup costs. In Section 3 and Section 4, we show that for single- and multi-stage problems respectively, the optimal policies have one or two critical numbers at each stage. In Section 5 we discuss the behavior of the critical numbers as influenced by demand, production capacities and cost parameters, such as the cost(s) of setup, production, shortage and holding. Then, in Section 6 we extend the model to deal with initial inventories or with raw material ordering capability. Finally, in Section 7 several numerical examples will be demonstrated. 2

2 Problem Description and Formulation An N-stage serial production facility is dedicated to meeting an uncertain demand for a given type of commodity during a period of time. Let 0 be the demand random variable with c.d.f. Q(() and p.d.f. q(Q). At each stage of this serial production facility, the production capacity is uncertain and the production setup cost may not be negligible, i.e., non-zero. The production capacity at stage n is assumed to be a random variable, tY, with c.d.f. Fn(yn) and p.d.f. f,,(yn). These c.d.f.'s and p.d.f.'s are assume to be continuous and to be twice differentiable. Moreover, all the random variables are assumed to be mutually independent. In this serial production facility (see Figure 1), stage N is the first stage (the raw material input) and stage 1 is the final stage (the finished goods output). At stage n, a planned production System: /.. 1 Demands System: (N. —................. Iand A u,(<xn+n) i mintu,n} A Stage n: ---- Kn Figure 1: A Serial Production System quantity, un, has to be decided. Clearly, the production quantity can not exceed the available input quantity and the maximum capacity at that stage. Because u, is limited by the uncertain capacity at stage n, the actual production output, x,, is equal to min{un, y,}. Several costs are imposed on the facility which influence the production decisions. For the whole facility, a shortage cost, 7r, is charged for each unit of any unsatisfied demand. At stage n, there are several costs: a) a holding cost, hn+l, is associated with each unit of the unused available input material, for instance, hN+l is relative to the raw material for the system and h1 is relative to the finished goods, b) a setup cost, Kn, is charged for any production decision, i.e., Un > 0, and c) a marginal production cost, wn, is charged per unit of actual production output. All cost parameters are assumed to be non-negative. Before formulating the cost functions of this system, we presume that the initial inventories 3

of all intermediate materials are zero. Later in Section 6.1, we will address how to approach the system without this assumption. Now, we are in a position to define recursively the cost functions which form the basis of the analysis. Let Cn(x,,+l) be the expected cost of operating the system optimally from stage n through stage 1, where the available input quantity is x,,+l. Then, CN(XN+1) represents the minimum expected cost to operate the system, where the available raw material at stage N is XN+1. As mentioned earlier, we should have u,, <~ xn+ at each stage 71. Therefore, the cost expectation function C,(x,,n+) satisfies the functional relationships: For n = 1 to N, Cn(Xn+l) = min {7n(un) + KnS(Un) + -hn+lXn+l}, (1) Oun xn+where 1 if un > O 6(Un) = 0 otherwise, 71(ul) = F1(u1)[wlul + J ( - u) dQ() + hj (u -.) dQ() - h2U1] + / [wily + r v ( - yi) dQ(g) + hi (yi - ) dQ() - h2Yl] dFi(yi), (2) and for n = 2 to N, Yn(un) = Fn(u,)[wnU, - hn+lun + Cn-1((71)] Un + / [Wnyn - hn+lyn + Cn-l(yn)] dFn(yn). (3) There are two necessary cost conditions throughout this paper: CONDITION I w1 - h2 < r. CONDITION II For all n, wn + hn > hn+l. The first condition implies that the penalty for unsatisfied demand is so high that it is profitable to produce. The second one ensures that it is possible to dispose of the material at any intermediate stage instead of producing. The following lemma indicates that if there is no input material available at stage n, the cost expectation is the expected shortage penalty, i.e., since there is no chance to produce, then pay the penalty. 4

LEMMA 1 7y(O) = Cn(O) = 7rE[O] for all n. Proof: We know that 71(0) = irE[O] from (2). Furthermore, y,,(O) = C?,-1(0) = C,,(0) from (3) and (1). Therefore, 71(0) =... = 7,(0) = Cl(0) =... = C,(0). QED. When the planned production quantity has been raised from un to u' at stage n, 7( lU,))-Y1L(UL) represents the marginal cost in view of (1), (2) and (3). Consequently, the following two lemmas are readily perceived: LEMMA 2 For all n, suppose that the first derivative of'7y,(U), 7y (un), exists and is greater than zero in interval (a, b). Then, it is not a benefit to increase the planned production quantity Un in the interval. Clearly, -y(un) has a local minimum at un = a. LEMMA 3 If 7yn(un) + Kn > 7n(0) for all un, it is not worthwhile to produce at stage n. Thus, <* = 0. It is not an interesting case if it is not profitable to produce at all stages. Hence, from now on, we presuppose that it is beneficial to produce at any stage. Furthermore, we relax the maximum capacity constraint in the analysis for convenience. Later in Theorem 10, we will show that the analysis is still valid with the capacity constraint. 3 The One-Stage Problem In this section we shall discuss the one-stage problem for the model introduced in Section 2. Our objective shall be to show the following: At the first stage, decreasing and convex in (0, S1) 1. 71(ul) is increasing in (S1, oo), 2. 0 <si < Si < oo, 3. The form of the optimal policy is 0 if x2 E (0, s) ut(x2) = ( x2 if x2 E (si,S1) (4) S1 if x2 E (1,00 oo), 5

where sl and S1 represent two critical numbers in this stage. To do this, we start with property 1: the behavior of 71(ul). Now, taking the first and the second derivatives of (2), we have 7 (ul) = F1(ul)gi(ui), (5) 7(Ul ) = Fl(Ul)(7r + hl)q(ul) - fi(ul)g1(Ui), (6) where gl(ul) = (r + hl)Q(ul) + w1 - h2 -'r. (7) Clearly, gl(ul) is increasing. Then, define S1 such that gS(Si) = 0, i.e., 1 = Q -( h2r+/w ) From Condition I and Condition II, we have 7(O0) < 0 and lim>u, BOO/(ul) ~ 0, respectively. These ensure that S1 E (O, oo). Then, g(ul) is negative in (0, Si) and is positive in (Si,oc). Hence, we should discuss these two intervals separately in order to characterize the behavior of y1(ul). We have 1. u1 E (0,S1): From (5) and (6), 7'(ul) < 0 and?7'(ul) > 0, respectively. As a result, 71(ul) is decreasing and convex. 2. u1 E (S1, oo): From (5), Xy'(ul) > 0, i.e., 71(ul) is increasing. However, from (6), 71(u1) mIay change sign, i.e., 7l(ul) may be neither convex nor concave. Consequently, the behavior of y1 (u1) is shown in Table 1 (also see Figure 2 which is from a numerical example in Section 7). Hence, the minimum at ul = S1 is the global minimum. 71(Ui) 1l U1 E Convex Concave Increasing Decreasing (0, S) V/ ___ IV (Si, oo) May vary! V/ Table 1: The behavior of 71(ul) Now that we have characterized the behavior of l1(u1), we go on to property 2. From Lemma 3, there exists at least one ui such that 71(0) = K1 +Y1(i). (8) 6

200000 100000 L 2973 9000 Planned Production Quantity, ul Figure 2:-' y(ul) of Example 2.1 Since 71y(u) is decreasing in (0, Si), let sl be the ii E (0, Si). Now that we have proved that properties 1 and 2 hold, we go on to property 3. From properties 1 and 2, we still can conclude that the optimal policy is a two-critical-number policy with the form of (4), although yl(ul) is neither convex nor concave. The optimal policy says that a) if the quantity of the available intermediate material x2 is less than the lower critical number sl, then no item should be produced, b) x2 is between sl and the upper critical number Si, then the planned production quantity uc should be equal to the quantity of the available material, and c) x2 is more than Si, then u* should be equal to the upper critical number. Clearly, the lower critical number of the optimal policy represents the effect of the setup cost K1. 4 The n-Stage Problem In this section we shall discuss a general problem which consists of n stages. Our objective is to determine that the form of the optimal policy for the n-stage problem is 0 if xn+1 E (0, s,) Un(Xn+l) = Xn+ if Xn+1 e (Sn, Sn) (9) Sn if,n+1 E (Sn,,o), where Sn and Sn represent two critical numbers in stage n (also see Figure 3). Before proving (9), let us characterize a very important property as given in Theorem 4. This property is also illustrated in Figure 4. 7

x n+ 1 n y n I. @ u* n 0 s y S n n Figure 3: The Optimal Policy at Stage n THEOREM 4 At stage n, suppose that an (s,, Sn) policy of form (9) is optimal, and ln(un) is conveX and decreasing in (s,, Sn). Then, convex in (Is,, Sn) Cn(Xn+l) is linear with slope hn+l otherwise. 409756 (N r-) 200000 214 3000 Available Input Quantity, x2 Figure 4: Cl(x2) of Example 2.1 Proof: From (1) and (9), we have 7 n(O) + hn+l Xn+l if x.+l E (0, Sn] Cn(Zn+l) = < 7n(xn+1) + Kn + h,+17x,+ if xn+l E [S7L, S,] (10) Yn(Sn) + Kn + h,+l xn+l if xn+l E [Sn, ~o). 8

Then, differentiating (10), we get hn+l if x2+l1 E (0, s,) C/L(xL+l) = 7(xl+l) + hn+l if x,7+l E (sn, S] (11) hn+1 if x7,+1 c [Sa, o). Hence, C',(x,,+l) is linear with slope hn+1 if xn+1 t (s, S,n). If.+l1 c (s,, Sn), then Cn(zX,+l) is convex since 7((xn+l) > 0 by assumption. Now, we are ready to introduce the following theorem showing the optimal policy and its properties: THEOREM 5 At stage n, increasing and concave in (0, sn-1) decreasing and convex in (sn,- Sn) I. 77, (un) is (see Figure 5) increasing in (Sn, Sn-1 ) increasing and concave in (Sn-, oo), 2. _n-1 < Sn <~ Sn < Snl, 3. The form of the optimal policy is (9), where so = 0 and So oo. 409756 250000 231 2176 9000 Planned Production Quantity, u3 Figure 5: Y3(U3) of Example 2.1 Proof: We have shown already that all the properties are true at stage 1. Suppose that at stage n - 1, all the properties are still true. By induction, let us validate the properties at stage 7n. First 9

of all, we should characterize the behavior of 7y,(un). Therefore, we shall consider',N(u?7) in the following two intervals: 1. u,n E (0,n-l): 7L(Un) = Fln(Un)[wLun - hn+1Un + Cn-1 (u,1)] 2. Un E (Sn-1, I): 7n(Un) = Fn(un)[Wnn - h+lUn, + Cn-l(Un)] Sn-1 + / [WnYn - hn+lYn + Cn-l(Yn1)] dF,,(yn).o + j [Wnyn - hn+lYn + Cn-l(Yn)] dFn(yTn). (12) JSn-1 For convenience, we divide the interval (sn_l,oo) into (s-,_lS,_1l] and [S,,-l, o), although u, = sn-1 is the only break point of Cn-l(un). Then, taking the first and the second derivatives of 7n(un), and substituting expressions from Theorem 4 and (11), we get Fn(un)[Wn + h, - h,-+1] if Un < Sn-l %Yn(Un) = ( Fn(n)gn(un) if Sn-1 < Un < S,-1 (13) Fn(un)[Wn + hn - hl+l] if u, > Sn-_, and -fn(un)[Wn + hn - hn+l] if un < Sn-1 n(Un) = Fn(un)gn(un) - fn(un)gn(un) if Sn-1 < Un < Sn-1 (14) -fn(un)[Wn + h, - hn+l] if u, > Sn-1, where gn(un) =' g9n(un) = Cn-l(Un) + W1 - hn+l Fn-1(Un)gn-1(Un) + wT + hn - hn+l (15) n-1 = I Fn(u)[(r + hl)Q(u,) + wl - h2 - w] j=l n-1 n-1 + I J Fj(un)[wk + h - hk+l] +n + hn - hn+l. (16) k=2 j=k 10

Differentiating gn(u,) and using Theorem 4, we get g'n(u,) = Cl(Un) > 0, (17) i.e., gn(u,) is increasing in (s,ni, Sn-1). Now, let us discuss 7,,(u,,) in the intervals (0,sni) and (Sn-l,oo). Because of Condition II, 77,'(un) > 0 and 7(u,,) < 0, i.e., y(u,,) is increasing and concave. Knowing that 7,,(u,^) is increasing in (0, s,_l) and (Sn_, oo), we are in a position to determine the behavior of y,(u,) in (snl,S,-l]. Since y7(S,_l) > 0, gn(Sn-1) > 0. By Lemmas 2 and 3, g^(S+_l) must be less than zero, i.e., y7(s+_) < 0. (Otherwise, it is not worthwhile to produce.) Therefore, define Sn E (sn-l Sn-1] such that g7L(St) = 0. (18) Hence, we divide (s,-l, Sn-] into two intervals: (s,-l, Sn] and [S,, S,-_1]. 1. u E (Sn-i, Sn]: From (18), g.(u,,) < 0, i.e., 7y(un) < 0. Therefore, y7(u,,) > 0 from (14). 2. un ~ [Sn,Sn-]: From (18), gn(un) > 0, i.e., 7y'(un) > 0. However, from (14), /y(un) may change sign. _ 7n(un) un E Convex Concave Increasing Decreasing (O,n-) A-V V __ (Sn- 1,Sn) VJ (Sn, Sn-) May vary! v (Sn1, 0o) / V Table 2: The behavior of 7yn(un) Consequently, the behavior of 7n(un) is shown in Table 2. Again from Lemma 3, the minimum at ul = Sn is the global minimum. Now that we have characterized the behavior of yn(un), we go on to property 2. From Lemma 3, there exists at least one ut, such that 7n(0) = Kn +Yn(i2). (19) 11

Since y,,(O) < 7y-(s_) and y,(u,,) is decreasing in (_l, Sn), let sn be the L,, E (s-_l, Sin]. Now that we have proved that properties 1 and 2 hold, we go on to property 3. From properties 1 and 2, we still can conclude that the optimal policy is a two-critical-number policy with the form of (9), although y,,(u,,) is neither convex nor concave. The optimal policy says that a) if the quantity of the available intermediate material x,,+n is less than the lower critical number sn, then no item should be produced, b) if x,n+ is between s,, and the upper critical number S,,, then the planned production quantity u* should be equal to the quantity of the available material, and c) if Xn+ is more than S,,, then un should be equal to the upper critical number. Clearly, the lower critical number of the optimal policy represents the effect of the setup cost Kn (a detailed discussion of this effect will be shown in Section 5.2). K 5 The Properties of Critical Numbers In this section, we shall characterize the behavior of the critical numbers. We discuss the effects of demand increase and production capacity expansion in Section 5.1 and the effects of the costs of setup, production, holding and penalty in Section 5.2. The general properties of the system are illustrated by the following two corollaries. Corollary 6 comes from the structure of the optimal policy and Lemma 3. Corollary 7 comes from Theorem 5. COROLLARY 6 If it is not worthwhile to produce at stage n, S,, = s,- = 0. COROLLARY 7 A sequence of (sn,, Sn) policies is optimal for this serial production process. Furthermore, s1 < S2 _... < SN < SN <... S2 < S1. Corollary 7 indicates several characteristics of the system: a) If it is not worthwhile to produce at stage n, i.e., Sn = 0, it is also not worthwhile to produce at any of the upstream stages, i.e., Si = 0, V i > n, b) the monotonic sequence {s,} implies that the effective setup cost at an upstream stage is always higher than at any downstream stage, i.e., an upstream production decision may trigger downstream production decisions, and c) the monotonic sequence {Sn} shows that it is not economical to produce more items than the optimal intermediate material needs from the immediate downstream stage. (In a random yield approach of this model with no setup cost, Lee and Yano (1988) have shown SN >... > S2 > S1.) 12

5.1 The Impacts of Demand and Production Capacities Here, we shall discuss the impacts on the critical numbers of changing demands and production capacities. Let l and 1 represent two different distributions with densities / and A, respectively. We say that the density 4 is stochastically smaller than the density <b (written V <~st () if T(x) > F(x) for all x > 0. THEOREM 8 If we are given two demand distributions Q and Q, and if q <st q, then Sn < Sn and sn > Sn at all stages. Proof: By assumption, we have Q(x) > Q(x). Therefore, gl(ul) > gl(ul) referring to (7). Since 41(ul) is increasing, Si < S1. Then, 7'(u1) > 7y(u1) from (5). Hence, from (8), we have K1 71()- 1(1) 1(- 1) i.e.-, K1 < ((0) - l(sl) > 1i Ki ~'51(0) - )1(s1). -Si -81 -iS1 Because of Theorem 5, -7l(ul) is decreasing in (0, S1). This implies that sl > s1. By induction, we have gn(Un) > 9n(Un) from (15) for all n. Since gn(un) is increasing from (17), Sn < Sn. From (13), 7y)(Un) > j(un) in (sn-l,oo). By Theorem 5, 7y,(un) and n(un7) are increasing in (0,Sni) and (O,sn-1), respectively. Since sn- > _n-1, from (13) 7y(u,L) = 7^(u,,) in (O,.n-1). Let us define Zn E (sn-iSn) such that 7n(Zn) = yn() and Zn E (n-_1i,Sn) such that 7n(Zn) = Tn(O). Notice that 7f(Un) > " (Un) in (On-,lSn-i). Therefore, Zn > zn. Then, Kn _ 7n(Zn) - Yn(Sn) > 7n(Zn) - n(Sn) Zn - Sn Zn Z- n Zn - Sn i.e., Kn < n(zn) - ^n(sn) < n(zn) - ^n(Sn)Again from Theorem 5, 7n(un) is decreasing in (,_n-1, 5). As a result, Sn ~> n- Theorem 8 is reasonable since if we have more demand than before, then not only the effective setup cost will become less, i.e., Sn > S', but also the shortage penalty will drive the system to produce more, i.e., Sn < SnTHEOREM 9 If we are given two capacity distributions Fj and Fj at stage j, and if fj <st fj, then Sj = Sj and Si < S for all i > j. 13

Proof: Following the assumption, we have 1 - Fj(uj) < 1 - Fj(uj) for all uj. Then, gj(uj) = 4g(u1) from (15), i.e., Sj = Sj. By induction and (15), we get gj(ui) > gi(ui) in (s;-,Si-l), i.e., Si < S for all i > j. Theorem 9 illustrates that if we enlarge the production capacity at stage j, we are willing to produce more (Si < oo) at all the upstream stage i > j. However, the upper critical number at the current stage will remains the same (Sj = Sj). Unlike the stochastically smaller demand condition in Theorem 8, the condition in Theorem 9 is not sufficient to show the behavior of the lower critical numbers since the stochastically larger production capacity can not guarantee that the effective setup cost will become less. For example, let us "move" the probability of the production capacity from just below the original lower critical number to far above the original upper critical number. Then, if the quantity of the available intermediate material is equal to the original lower critical number, then we may have a greater probability of producing less than before. Now, we shall indicate a way to solve the problem dealing with the capacity constraint. Let sup y, denote the minimum upper bound of the capacity at stage n. THEOREM 10 If S, > sup,n > Sn,, then set S,, = sup y,,. If sup y,n < s,n, then set S,, = O. Then, Theorem 5 still holds. Proof: From Theorem 5, y,(un) is decreasing in (sn,,S,). Thus, if S, > sup y, > s,, then set Sn, = supy,. It is clear that u, = supyn is still the global minimum. On the other hand, if sup yn < sn, then set Sn = 0. 5.2 The Impacts of Cost Parameters Now, we shall examine how the critical numbers are affected by the costs of setup, production, shortage and holding. In Theorem 5, we discussed the problem with the setup cost at each stage. However, there is no indication whether or not the optimal policy would be affected by the setup costs at the other stages. In the following theorem, we will determine how the setup cost at a stage influences the critical numbers of the other stages. 14

THEOREM 11 Ki = 0, for all i < n if and only if the optimal policy at stage n is of a produce-up-to fo T7.t: 71+1 if Xn+1 < Snt form: un(x+1) = i.e., sn = 0. St if X7l+l > S5l, Proof: From (8), we have sl = 0 if and only if K1 = 0. From (19), we have s, = 0 if and only if K1, = 0 and s,_l = 0. The proof is done by induction. N In other words, the optimal policy is a single- instead of a two-critical-number policy if the setup costs at all the downstream stages (including the current stage) are zero. Theorem 11 ensures that the setup cost at a stage would have an influence on the optimal policy of all the upstream stages. The upper critical number is independent of all the setup costs since gn(u,,) (refer to (16)) is not a function of any setup cost. Thus, Corollary 12 follows. COROLLARY 12 As the setup cost increases at a stage, the upper critical numbers at all stages remain the same. The following theorem shows that any increase of the setup cost at a stage would also increase the effective setup costs at all the upstream stages. THEOREM 13 As the setup cost increases at a stage, the lower critical numbers also increase at all upstream stages as well as the current stage. Proof: Assume that the setup cost Ki increases to Ki at stage i. Now, we know that'yi(ui) is decreasing in (si1, Si) by Theorem 5. Since Ki < Ki, we have si < Si by the definition of the lower critical number (refer to (19)). Clearly, 7i(ui) = 7i(ui). From Corollary 12, we know that Sj = Sj for all j. At stage i+ 1, i'+ (Ui+i) = 7+1(ui+i) in (si, Si+1) because of (13). When ui+l E (i, Si+1), we have from (12) and (10): 7i+i(Ui+l) —,i+(Ui+i) = Fi+(ui+l)[C( ) - i (ui) C(i+i)] + [Ci((ui+) - Ci(ui+l)] dFi+l(yi+,) Jo + [Ci(ui+l) - Ci(ui+,)] dFi+(yi+l) + j[Ci(ui+i) - Ci(ui+i)] dFi+l(yi+l) Jsi Js = Fi+(uii+l)[ - Ki] + ^[IKi - Ki] dFi+l(yi+l) (20) si l + [V'i(0) - i(Ui+l) - Ki] dFi+l(Yi+l). Jsi 15

Clearly, the first two terms of (20) are greater than zero. Since 7(y(ui+l) is decreasing, the third term of (20) is also greater than zero from (19). Therefore, i+l(ui+i) > 7i+i(ui+i) in (i, Si+i). By induction, assume that sj-l < sj_i and 7-i (uj-i) < j-1l(uj-1) for j > i + 2. Because of (13), y(uj) = j(uj) when u; E (j_1,jS5j). When uj E (j-_i, Sj), we have from (12) and (10): 7j(^u) - 7j(u3) = Fj(uj)[7j_~l(u) - 7j-l(uj)] + d [7jFl() - 7j-l(j)] drj(y,) Sj-i + fr [-l(O)- -7-l(u)- Kjl] dFj(yj). (21),Sj 1 Since j_-l(uj-i) < j_l(uji-), the first two terms of (21) are greater than zero. Since 7yj-(uj) is decreasing, the third term of (21) is also greater than zero from (19). Therefore,'(u;) > yj(uj) in (j_-l,Sj). Recall the definition of zj in the proof of Theorem 8: zj E (sji,Sj) such that yj(zj) = 7j(0). We have that zj < zj since 7j(zj) = jj(zj) < 0. Therefore, s; < sj from (19). * THEOREM 14 As the shortage penalty increases, the upper critical numbers also increase but the lower critical numbers decrease at all stages. Proof: Assume that the shortage penalty increases from 7r to fr. Therefore, gl(ul) > li(ul) for all ul from (7), i.e., [(ul) ~> 7(ul) from (5). Then, follow the same procedure as in the proof of Theorem 8. QED. 1 Theorem 14 ensures that an increase of the shortage penalty will force the system to produce more and reduce the effective setup costs at all stages. The following theorem shows that any decrease of the marginal production cost at a stage will reduce the effective setup costs and also force the system to produce more at all the upstream stages as well as the current stage. THEOREM 15 If the marginal production cost wi decreases to wij, then Sj < Sj and sj > ij for all j>. Proof: Since wi > wij, gj(uj) > gj(uj) in (sj_l, Sj_-) from (7) and (16), i.e., yj(uj) > fi(uj) from (5) and (13). Then, follow the same procedure as in the proof of Theorem 8. 3 THEOREM 16 If the holding cost hi decreases to hzi, 16

1. For all j > i, Sj < Sj and sj > ~j. 2. For stage i - 1, Si-1 > Si-1 and si_1 <._1. Proof: 1) Since hi > hi, for j > i, gj(uj) > 9j(uj) in (sj_,Sj-i) from (7) and (16), i.e., yg((uj) > t(u5j) from (5) and (13). 2) On the other hand, we have gi-(ui-j) < 9i-1(u1i-) and 7_ 1(ui-l) < 7L 1(i-m) in (si-2, Si-2). Then, follow the same procedure as in the proof of Theorem 8. QED. I Theorem 16 tells us that any decrease of the holding cost at a stage influences the critical numbers not only at the current stage and all the upstream stages but also at the immediate downstream stage. The influence at the current stage and all the upstream stages decreases the effective setup costs and drives the system to produce more than before. On the other hand, the influence at the immediate downstream stage increases the effective setup costs and forces the system to produce less than before. 6 Two Extensions of the Model In this section we shall discuss two extensions of this model. First, we consider the problem with initial inventory at each intermediate stage. Second, we expand the system with raw material purchasing ability. 6.1 The Extension of Positive Intermediate Inventory Suppose that the initial inventory level of any intermediate stage is non-negative. Through the same analysis as before, let I,+l denote the initial inventory of available input material at stage n. Accordingly, Cn(xn+l + In+1) satisfies the functional relationships: For n = 1 to N, Cn(xn+l + In+l) = min vn(u,n) + K,6(Un) + h,n+l(xn,+l + In+l)}, O<un <,n+ l+In+ where roo VI(u1) = F(u1)[wluI + 7r ( - U1 - I1) dQ(E) Ll +I+ 1 +h1] (ul + I - O) dQ(0)- h2um] 17

+'[wil + T ( - y - I,) dQ() 1+I2 +h1io +J (Y1 + I1 - ) dQ(') - h2Y1] dFi(yl), and for n = 2 to N, Vln(Un) = Fn(U)[wU - hn+lUn, + C,-_l(Un + -n)] rUn + [WYn hn+lYn + Cn-l(yn + In)] dFn(yn) Similar to the analysis without any intermediate inventory, we have Vl(ui) = Fl(u)pi(ui) Fn(un)[wn + hn - hn+l] if u, + In < sn_-1 V(Un,) = ( Fn(U)Pn(U) if Sn-1 < Un + In < Sn-1 Fn(Un)[Wn + hn - hn+l] if Un + In > Sn-_1, where pi(ul) = (7r + h)Q(ul + I1)+ wi - h2 -7 pn(un) = Fn-l(Un + In)pn-l(un + In) + Wn + hn - hn+l n-1 n n -= Fj(Un + Z Il)[(r + hl)Q(un + II)+ Wl -h2 - r] j=l l=j+l 1=1 n-1 n-1 n + Z 1J j(Un + Z II)[Wk + hk - hk+l] + Wn+ hn- hn+l. k=2 j=k l=j+l Then, for all n we can get Sn such that Pn(Sn) = 0, and Sn E (sn-,Sn) such that Vn (O) = (Sn) + Kn Hence, the form of the optimal policy at stage n is 0 if Xn+l + In+l < Sn (Xn,+l + I+n+) = x +l + In+1 if Sn < xn+l + In+l < Sn Sn if Xn+1 + In+1 > Sn. 18

6.2 The Extension of Raw Material Ordering Here, assume that a dummy stage N + 1 represents the raw material purchasing stage in the series. In this stage, the purchasing capacity is unlimited and certain. Let WYN+1 represent the marginal cost for each unit of raw material purchased. Notice that XN+2 = hN+2 = 0, because there is no physical inventory at this stage. Then, we have CN+1(XN+) = min {CN(UN+1) + WN+1(UN+1 - XN+1)} XN+1<UN+1 Consider YN+1(UN+1) = CN(UN+1) + WN+UN+I, 7N+1(UN+l) = CN(UN+1)W N+1 hN+1 + WN+1 if UN+1 E (0, SN) = V(UN+1) + hN+1 + WN+1 if UN+1 E (SN, SN] (22) hN+l + WN+1 if UN+1 E [SN, oc), and N+1(UN+l) = C(r(UN+1). (23) We know that 4N+1(UN+l) is convex in (SN, SN) from (23) and Theorem 4. In case that UN+1 E (0, SN) or (SN, oo), YN+1(UN+1) is linear from (22) and is increasing from Condition II. Now, if it is beneficial to order any raw material, then from Lemma 2, 7y+l(uiN) < 0 for some UN E (SN, SN). By convexity, 7v(+ (s+) < 0. Now, define SN+1 E (SN, SN] such that 7N+1(SN+l) = 0. (24) If it is not beneficial to order or 7YN+1(SN+I) > 7YN+1(XN+1), then uN+1 = XN+1 is the global minimum. Hence, let SN+1 = XN+1. Then, the optimal ordering policy is an order-up-to policy with a critical number SN+1Unlike production stages, the purchasing stage does not suffer the problem of limited input material available. For this reason, the optimal policy at the purchasing stage has only a single critical number. 19

7 Computational Results Here, we shall give several numerical examples of the system in this paper. In the examples, there are three production stages in each series. All the probability distributions are assumed to be LogNormal. The definition of the LogNormal probability density function is given below: 1 -(ln x - )2 f(xyI,, ) = exp[ -(n, x > 0, N/;2-7a x 2a2 where f(.) is determined by fy and a. In order to find the critical numbers in these examples, from Sections 3 and 4 we should solve Sn and s,, which satisfy (18) and (19), respectively. Furthermore, the property snl < sn < Sn < S,_1 of Theorem 5 essentially reduces the computation effort. EXAMPLE 1 The demand distribution is described by,Ad and ad chosen as;ld = 7.5 and crd =.5. At stage i,,ii and voi represent the two parameters of the capacity distribution and are selected as,3 = 8.5 /U2 = 8.3,u1 = 8.5 a3 =.2 a2 =.5 c'1 =.3. The cost parameters are chosen as W3 =30 w2 = 10 Wl = 15 h4 = 10 h3 = 20 h2 = 25 hi =50 or = 200 K3 = 25,000 K2 = K = 45,000. Then, by solving (18) and (19), we find the critical numbers of the example to be S3 = 424.40 s2 = 230.77 sl = 214.29 S3 = 2,176.25 S2 = 2,654.55 S1 = 2,972.70. Clearly, these critical numbers have the monotonic property described by Corollary 7. Controlling the system optimally, the planned production quantity at the first stage, S3, is always less than the quantity at the second or the third stage. Therefore, S2 and Sm are useful only in calculating S3 but are meaningless in controlling the system. However, all s's are very helpful to prevent any non-economical production due to high production setup costs. Notice that the setup cost at stage 2 is zero. From Theorem 11, s2 is greater than zero due to the nonzero setup cost at stage 1. 20

We portray the behavior of functions 7i(ui) and CFi(x) of Example 1 in Figure 2 and Figures 4 through 8. Evidently, yi(ui) is not a K-convex function. We know that 7i(O) = C-'(O) = rE[O] = $409, 756 for i = 1,2,3. This also demonstrates the intuitive result of Lemma 1. Let us now consider ordering capability, which we mentioned early in Section 6.2. Let the purchasing cost, W4, be twenty dollars for each unit of raw material. Then, we get S4 = 1, 863.30 from (24). Suppose that the system dose not hold any raw material. Then, 74(S4) = C4(S4) = $305,247. In other words, we can save 7rE[Q] - C4(S4) = $104,509 by using this critical number strategy against doing nothing. When demand or production capacity changes in Example 1, the behavior of the critical numbers also changes as shown numerically in Examples 2 through 4. EXAMPLE 2 Set Ad = 7.3 in Example 1. Then, the critical numbers in this example are (2)= 452.55 s2)= 230.77 s2)= 214.29 S(2) = 1,468.69 S(2) 1,708.20 S(2) 2,177.12 S(2) 2,433.84. Clearly, s < s(2) and Si > S(2) for all i. This is because the demand distribution here is stochastically smaller than in Example 1 (see Theorem 8). EXAMPLE 3 Set u2 = 7.6 in Example 1. Then, the critical numbers in this example are (3) = 424.46 3) = 230.77 (3) = 214.29 S3) = 1,626.43 S(3) = 1,930.66 S(3) 2,654.55 S(3) 2,972.70. Clearly, Si > S(3) for all i. This is because the capacity distribution at stage 2 here is stochastically smaller than in Example 1 (see Theorem 9). EXAMPLE 4 Assuming the capacity at stage 2 is perfect in Example 1. Then, the critical numbers in this example are,(4) (4) (4) 4) = 424.40 24) = 230.77 s 214.29 S4 = 1,900.61 (4) - 2,219.85 S(4) - 2,654.55 S4) - 2,972.70. Clearly, Si > S(4) for all i. Because the production output at stage 2 is perfect, we may consider that F2(u2) is equal to one for any finite u2. 21

8 Summary We have studied the uncertain capacity approach for planning and control in serial production processes with setup costs in which the output at each stage may be stochastic. The optimal control strategy for any N-stage system is shown to have a sequence of two critical numbers. We also show the sensitivity of the critical numbers to changes in demand and system parameters. Four numerical examples are offered to scale the behavior of the critical numbers and cost functions. However, further research needs to incorporate multiple periods into the current model since the demands for some products may occur more than once. 409756j 200000 2655 9000 Planned Production Quantity, u2 Figure 6: 72(u2) of Example 2.1 409756 250000 231 3000 Available Input Quantity, x3 Figure 7: C2(x3) of Example 2.1 22

409756 C) 300000 424 3000 Available Input Quantity, x4 Figure 8:-C3(x4) of Example 2.1 Reference CIARALLO, F. W., R. AKELLA AND T. E. MORTON 1991. A Periodic Review, Production Planning Model with Uncertain Capacity and Uncertain Demand - Optimality of Extended Myopic Policies. Submitted to Mgmt. Sci. LEE, H. L., AND C. A. YANO 1988. Production Control in Multistage Systems with Variable Yield Losses. Opns. Res. 36, 269-278. YANO, C. A. 1986a. Controlling Production in Serial Systems with Uncertain Demand and Random Yield. Technical Report 86-5, Dept. of Industrial and Operations Engineering, University of Michigan, Ann Arbor. YANO, C. A. 1986b. Optimal Policies for a Serial System with Setup Costs and Variable Yields. Technical Report 86-24, Dept. of Industrial and Operations Engineering, University of Michigan, Ann Arbor. 23

UNIVERSITY OF MICHIGAN 3 9015 04735 0213