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-2117 Technical Report 94-4 March 1994

Optimal Production Policies for Multistage Systems with Setup Costs and Uncertain Capacities Juhwen Hwang Department of Industrial and Operations Engineering The University of Michigan, Ann Arbor, Michigan 48109-2117 Medini R. Singh The Amos Tuck School of Business Administration Dartmouth College, Hanover, New Hampshire 03755-1798 Abstract The increased complexity of modern manufacturing has lead to uncertainties in production processes. Factors, such as unplanned machine maintenance, tool unavailability and complex process adjustments, make it difficult to maintain a predictable level of output. To be effective, an appropriate production model must incorporate these uncertainties into the representation of the production process. This paper considers a one-time production of an application-specific product which must follow a fixed routing through the manufacturing system. The flow of items can be modeled as a multi-stage serial production line. The productive capacity is uncertain at each stage and the decision to produce at any stage incurs a significant setup cost. Semifinished products have little value and inability to satisfy the demand incurs a penalty for each unit of unmet demand. We show that the optimal production policy for this system can be characterized by two critical numbers, which can be computed apriori based on the cost parameters and distributional information for all downstream stages. Sensitivity of the critical numbers is also explored. 1 Introduction The increased sophistication of modem manufacturing processes in many high-tech industries has lead to an increase in internal uncertainties in these manufacturing systems. The use of state-of-the-art technology, intricate equipment, complex tooling requirements, involved process control, reliance on specialized operator skills and greater adherence to performance specifications, are all factors that make it difficult to maintain a predictable level of output. Often, the newer, more profitable products face even greater uncertainty because the organization has not yet accumulated enough learning experience with the equipment and processes to reduce the variance. Nevertheless, production needs to be carried out in an economic manner, despite the inherent variabilities in the system. 1

We present a model for planning production in a multi-stage serial production system where the aggregate productive capacity at each stage is uncertain. That is, the output quantity at any stage is the minimum of input quantity and the realized productive capacity, which is random. Production is carried out to satisfy an uncertain one-time demand for the final product. Each unit of unsatisfied demand incurs a penalty, so does the the disposal of any unused material. A decision to produce at any stage incurs a setup cost plus a processing cost for each unit produced. Due to limited time until shipment, there is only one opportunity to produce at any stage, i.e., a production shortfall can not be compensated by another production run. Production control must decide, for each stage, how much to produce after the output from the immediately preceding stage becomes available. One must take into account capacity uncertainties at all downstream stages, together with the demand uncertainties and costs, to arrive at an economic production decision. Our analysis shows that the optimal production policy for each stage can be characterized simply by two critical numbers. If the available input exceeds the lower critical number, one tries to produce as much as possible, but no more than the upper critical number. If, on the other hand, available input is less than the lower critical number, one chooses not to produce. The interrelationship among critical numbers and their sensitivity to various cost parameters as well as capacities and demand distributions are also explored. There are two fundamentally different models in the literature to represent internal uncertainties. Yield models focus on output loss due to process imperfections while capacity models deal with production loss due to resource unavailability. In random yield models, one identifies the defective units after processing the entire input quantity and incurring the production cost. In uncertain capacity models, one may not be able to process the entire input material due to resource constraints; unused input incurs no production cost. To further illustrate the differences between the two models, note that increasing the input batch size always increases the expected output in an uncertain yield model. This is not necessarily true for the uncertain capacity model where, no matter how large the input batch size, the expected output can not exceed the average productive capacity. Henig and Gerchak (1990) propose a general representation of production output which can be used to model yield as well as capacity uncertainty. Yield models have been studied rather extensively in recent years. Interested readers are referred to Yano and Lee (1991) for an excellent survey. We discuss here only those works which are closely related to the present paper. Lee and Yano (1988) analyze a single-period, single-product, serial production system, similar to the one considered here, but without set-up cost. The demand is known and the yield at each stage is a random multiple of input batch size (referred as stochastically proportional yield by Henig and Gerchak, 1990). Lee 2

and Yano (1988) show that the optimal production policy for each stage can be characterized by a single critical number representing the target input quantity. The policy stipulates that one should input the target quantity, if enough is available; otherwise one should input whatever is available. An identical result for the random capacity case can be obtained from our model by setting the setup costs at all stages to zero. A number of generalizations have been attempted for the Lee and Yano (1988) model. Yano (1986a) shows that structural results similar to those in Lee and Yano (1988) are valid even when the demand is random. Wein (1992) allows for the rework of defective items at a cost. She shows that the optimal production/rework policy can be characterized by two critical numbers. Barad and Braha (1991) allow for the procurement of semifinished items in a multi-stage binomial yield model. They establish the optimality of a two-critical-number policy where the second critical number specifies a procurement target for semifinished items. Yano (1986b) presents an extension of the Lee and Yano (1988) model by incorporating a setup cost at each stage of production. For a single-stage problem, she demonstrates that a two-critical-number policy, similar to that proposed in this paper, is optimal. She also demonstrates the optimality of a similar policy for a two-stage system, but only under certain restrictive conditions. The form of the optimal policy for general serial production systems with random yield and setup costs remains an open research problem worthy of investigation. This paper addresses the same problem for the case where production stages are subjected to, not yield, but capacity uncertainties. The analysis of Lee and Yano (1988) model for the multi-period scenario is quite involved and is unlikely to yield a structurally simple policy. In fact, the dynamic problem is quite complex even for a single-stage problem, as shown by Gerchak, Vickson and Parlar (1988). As a result, recent research efforts have focussed on the study of such systems under suboptimal but tractable operating policies. Tang (1990) develops operating characteristics for Lee and Yano (1988) model under partial restoration rule and provides interesting insights about the impact of uncertainty. Denardo and Lee (1991) extend Tang's approach to allow rework and unreliable machines. Gong and Matsuo (1990) formulate a linear control problem that tries to stabilize work-in-process and to smooth production. The development of models for systems with setup costs is still lacking in the literature. The aggregate capacity model used in this paper captures parsimoniously the cumulative impact of varying availabilities of numerous productive resources. Hopp, Spearman and Duenyas (1993) have used this representation to model the total amount of regular-time capacity available in any period. They demonstrate that the distribution of aggregate capacity plays a central role in setting production quotas for a pull manufacturing system. Ciarallo, Akella and Morton (1994) consider finite and infinite-horizon models for a single3

stage production system with uncertain capacity and uncertain demand. They show that a single critical number, which represents the order-up-to point, is sufficient to characterize the optimal policy in a multi-period setting. This is in contrast to stochastically proportional yield models where, under similar circumstances, the optimal policy is known to have no structurally simple form (see Gerchak et al. 1988). The mathematical instrument used to model the uncertainty in aggregate capacity here is identical to those in Ciarallo, Akella and Morton (1994). In contrast to their single-stage, multi-period model, we analyze a multi-stage, single-period model with setup cost at each stage of production. In Ciarallo et al., order-up-to policies are derived from the analysis of a cost function which is quasi-convex. In spite of this non-convexity, the cost-to-go is shown to be convex. The presence of setup cost in our model destroys the quasi-convex unimodal structure of the cost function so effectively utilized by Ciarallo et al. in their analysis. We derive the two-critical-number policy from the analysis of a cost function which is neither unimodal nor quasi-convex. In fact, the nature of this cost function changes from concave-increasing, to convex-decreasing, convex-increasing, simply increasing, and finally to concave-increasing. The contribution of this paper is threefold. First, the optimality of a simple two-criticalnumber policy is established for an important class of manufacturing problems. Considering the unusual behavior of the cost function involved, our proof of optimality is somewhat novel. Second, the sensitivity of the critical numbers to cost parameters is explored, which reveal many interesting structural properties of the system. Finally, the impact of uncertainties on the production line is studied by changing the distributions of demand and capacities. The interaction between internal uncertainties and demand uncertainty is also revealed by the recursie equation used for the computation of crition cal numbers. This paper is organized as follows. Section 2 presents a mathematical description of the problem and its formulation as a dynamic optimization model. Section 3 analyzes a single-stage problem and shows that a two-critical-number policy is optimal. This result is extended in Section 4 to a multi-stage problem. The sensitivity of the critical numbers to cost parameters, as well as to capacity and demand uncertainties, is explored in Sections 5 and 6, respectively. A numerical example is presented in Section 7. The paper concludes with some final remarks in Section 8. 2 Problem Description and Formulation Consider an N-stage serial production system shown in Figure 1. Let the stages be numbered such that the final stage of production is denoted as stage 1 while the stage of 4

production to be performed first is denoted as stage N. The production is aimed towards satisfying a single uncertain requirement or demand for a product at the final stage. Let Z be the demand random variable with c.d.f. Q(z) and p.d.f. q(z). Q^ _ ^ Demand System: y -- j — - - - Q(.) Utn / min (u,y) Stage n: Mn+l Y F() Xn Yn - ~) Figure 1: A Serial Production System At any stage, the productive capacity may be uncertain due to a number of factors such as machine failures, tool unavailability, time spent in process, parameter readjustments, etc. Let the random variable Y, represent the available productive capacity at stage n with c.d.f. Fn(yn) and p.d.f. f,(yn). We assume that all the random variables are mutually independent and their c.d.f.'s are continuous and twice differentiable. The problem is to determine a planned production quantity, Un, at each stage of production such that the expected total cost is minimized. The actual production output from a stage may be less than the planned production quantity. This will occur whenever the capacity realization, yn, falls below the production target, un. Otherwise, the complete production target is accomplished successfully. In general, the production output of stage n, xn, is given by min{un,yn}. We assume that the initial inventory of all semi-finished items is zero; the analysis can be extended to accommodate positive initial inventories. The planned production quantity at stage n is obviously constrained by the actual production output from stage n + 1, which, in turn, depends upon the planned production quantity at stage n + 1, etc. That is, un < Xn+l = min{un+lYn+l}. We solve this problem dynamically by delaying the specification of the planned input quantity at a stage until the production output from the stage before becomes kfown. In other words, UN,lUN-1,..., Ul must be determined sequentially after receiving the output from the stage before. The following costs are considered in this model. The decision to produce at stage n incurs an "out-of-pocket" setup cost Kn independent of the production quantity. In addition, each unit of item actually produced at stage n incurs a cost wn,. Each unit of unsatisfied demand incurs a penalty nr. There is a cost hn for disposing a unit of item processed at stage n 5

but not used by stage n - 1. The cost of disposing leftover raw material is represented by hN+1- Since this model is especially applicable to one-time production of unique products, it is assumed that semi-finished items have little salvage value. Disposal of raw material and finished product, on the other hand, may bring a net cash inflow; this is modeled by allowing h1 and hN+1 to be negative. All other parameters and costs are assumed to be non-negative. The following two cost conditions are necessary to ensure that it is profitable to produce and that production is motivated only by the desire to satisfy the demand. CONDITION 1 h2 + 7r > Wl. If Condition 1 did not hold, one would simply dispose the input material at cost h2 and incur a penalty ir for not meeting the demand, rather than process an item at a higher cost wl. Clearly, this makes it unprofitable to produce anything at the final stage. CONDITION 2 Wn + hn > hn+l for n = 1,..., N. This states that it is less expensive to dispose an item at one stage than to process it and then dispose it at the next stage. Let Cn(xn+l) be the expected cost of operating an n-stage system with available input Xn+1, assuming that the best input decision is used at stage n through stage 1. Then, CN(XN+l) represents the minimum expected cost to operate the whole system, where the available raw material is XN+1 at stage N. A dynamic programming formulation for the problem can now be given as Co(xl) Ez{hl max{O,xz -Z} + 7rmax{O,Z- x}}, (1) and Cn(xn+l) = min Eyn{hn+l((n+ - min{un,Yn}) + Kn(un) +Wnmin{un, Yn} +Cni_(min{un,Yn})}, n=1,...,N (2) 1 if Un > 0 where 6(n) = otherwise. Let u4 be the optimal value of un. In our analysis we will often utilize the following representation for Cn(xn+l) Cn(Xn+l) = n {hn+lzXn+ + Kn6(u)+ ( n))} n = 1,... N, (3) 0<Un:5xn+l l where yn(un) is a function only of un and is given by rUn'n(Un) = / [(Wn - hn+l))n + Cn-l((yn)] dFn(yn) +Fn(ln)[(Wn - hn+l)un + Cn-(i(un)], (4) where Fn(un) = 1-Fn(un). 6

The function 7n(Un) plays a central role in defining the structure of the optimal policy for this problem. The following observation follows directly from (3). LEMMA 1 If nY(O) < Yn(un) +Kn for all un, then it is not worthwhile to produce at stage n. Thus, un = 0. The following lemma points to another intuitive result. If no input material is available at stage n, then the minimum expected cost for stage n through stage 1 is simply the expected penalty for not meeting the demand. LEMMA 2 Cn(O) = y7n(0) = 7rE[Z] for all n. Proof: From (3), Cn(O) = yn(0) and from (4), 7n(O) = Cn_(O). The result follows by induction, since Co(O) = 7rE[Z] from (1). These observations will be utilized during the analysis in coming sections. 3 The Single-Stage Problem In this section we analyze the single-stage problem for the model introduced in Section 2. This analysis will provide important insights in understanding the multi-stage problem. We begin by rewriting (3) as Cl(X2) = min {h22 + K16(ul) + l71(U )}, (5) where -yl(ll) is obtained by substituting (1) into (4), Y (ul) = [(wi - h2)Y1 + hi I (Iy - z) dQ(z) + 7r (z - yi) dQ(z)] dFi(y1) +Fl(u) [(w, - h2)u1 + hl (ul - z) dQ(z) + 7r (z - ul) dQ(z)]. We first investigate the nature of 7 l() since it plays a central role in the minimization in (5). The first two derivatives of 71(ul) are given by (u,) = d F1(ui)gl(ui), (6) d2 )(h + 7r)q(ul - ()g() ('1 ) \ F= = i)(, + 7r)q(ul) - fi(uj)gj(uj), (7) where gl(ul) = (hi + r)Q(ul) + wl - h2 - 7r. (8) gl(ui) is non-decreasing since Conditions 1 and 2 together imply that (hl + 7r) > 0. Define S1 such that gl(S1) = 0, i.e., S = Q-l(h2 + - ) (9) 7

S1 is non-negative and finite because (h2 + ir - il) > 0 and (h2 + 7r - w) < (hi + 7r) from Conditions 1 and 2. Then, g91(ul) is negative in (0, Si) and positive in (Si, oo). The nature of 7Y1(') can now be characterized using (6) and (7): 1. For u1 E (O, Si), i(ul1) < 0 and Yi'(u1) > 0, hence yl(ul) is decreasing and convex in this region. 2. For ul e (Sl, oo), i(ul1) > 0 and hence ly(ul) is increasing in this region. Nothing further can be concluded about the nature of 1l(ul) since Y'(ul) may alternate its sign in different sub-intervals. From these observations, it is clear that 71(uI) attains its global minimum at ul = S1. The behavior of yl(ul) is shown graphically in Figure 2. Y)(U1 )+K1 Yz (O) +K( / Y1/ (1+KU1 r,(o) c - W Y, (0) U1 0 sl S, Figure 2: The form of yl(u1l) Whenever S1 = 0, the problem is trivial since it is optimal not to produce. Note that from (9), S > 0 iff h2 + - W > (hi +r)Q(0), or wl +hi -h2 < (hi +7r)Pr{Z > 0}. That is, if the effective cost of processing a unit, (wi + h1 - h2), exceeds the marginal saving derived from making a unit available, one is better off not processing anything. Now consider the minimization in (5), in particular the term (K16(ui) + 1l(ul)). The nature of (K1 + y1(i1)) is identical to that of y1(u1) and it attains its global minimum at S1 with value K1 + 71y(S1). If 71(0) < K1 + yl1(S1), it is not worthwhile to produce, as 8

per Lemma 1. An excessively high setup cost makes the problem trivial, since one always chooses not to produce. If, on the other hand, 71(0) > K1 +7I(S1), since y1 (ui) is decreasing in region (0, Si), there exists a unique sl E (0, S1) such that 71(0) = K1i+i(si). (10) It follows (see Figure 2) from the definition of sl and the decreasing nature of 71(u1) over (0, S1) that 71(0) < K1 +7l(ul) for ul < sl, (11) and 71(0) > K1 + 71(U1) for si < ul < S1. (12) Based upon the available input material x2, the optimal policy can now be characterized in terms of the two critical numbers si and Si. For 22 s i, it is not worthwhile to produce because the setup cost, K1, will offset the expected savings, (71(0) - yi(u1)), derived from production. This follows from (11), since u1 < x2 < sl. For sl < 2 < Si, the advantage gained by producing, (y1(O) - yi(ui)), can offset the setup cost, K1, provided one plans to produce more than sl. This follows from (12). In fact, since 7y1(u1) is decreasing in range (si, Si), it pays to set the production target as high as possible; the optimal policy simply inputs all the available material. Finally, for X2 > Si, one sets the production target at Si, the point where (K1 +7Y1(u1)) attains its global minimum. The optimal policy for stage 1 and the nature of 71(ui) are now summarized in the following theorem. THEOREM 1 For the model stated in Section 2, if it is worthwhile to produce, then 1. the optimal policy for stage 1 is 0 ifx2 E(0,si) U;(X2) -= X2 if X2 E (s,S1) (13) Si if 2 (Sl, oo), where critical numbers Si and sl are solutions to equations (9) and (10) respectively and satisfy the relationship, 0 < sl < S1 < oo; 2. 7(u) i { decreasing'and convex in range (0,S1) increasing in range (Si,oo). The upper critical number, Si is the production target, i.e., the largest quantity one would ever process at stage 1. The lower critical number, sl, represents the smallest input quantity one is willing to process at stage 1. Note that Si, given by (9), is the same newsboy solution one would expect if the problem were formulated without any capacity constraint. 9

This observation is consistent with that in Ciarallo et al. regarding the order-up-to point in a single-stage single-period model with capacity uncertainty. The lower critical number, sl, however, does depend on the capacity distribution. In effect, given an input quantity, the decision as to whether one should produce is intrinsically linked to capacity uncertainty. However, the production target is independent of capacity. Once a decision is made to produce, one simply hopes that enough capacity will be available The cost-to-go, C1(x2), is obtained by substituting u* from (13) into (5) h2X2 + 7Y1(0) if X2 E (0, s1) C1(z2) = h2X2 + K1 + 711(X2) if X2 E (li, S1) h2X2 + K1 + 7i(Si) if X2 E (S1, oo). One can easily show that, unlike Co(-), C1(-) is not convex. As a result, the mathematical structure of the multi-stage problem presented in the next section is quite different than that for a single stage problem. 4 The Multi-Stage Problem The analysis of the single-stage problem, presented in the last section, was considerably simplified because the terminal cost-to-go, Co(lx), is convex. This is no longer true for the multi-stage problem that we analyze in this section. The key results of this paper are contained in THEoREM 2 For the model stated in Section 2, if it is worthwhile to produce, then 1. the optimal policy for stage n is 0 if Xn+l e (0, n) U((Xn+l) = n+ if Xn+l E (sn, Sn) Sn if zn+1 E (Sn, o), where critical numbers Sn and Sn are solutions to equations Yn(sn)+Kn = 7n(0), (14) and /Yn(Sn) = 0, respectively and satisfy the relationship 0 _< Sn- < Sn < Sn < Sn-1 < c0; increasing and concave in range (O, sn-l) 2 ) is decreasing and convex in range (snl,Sn) increasing in range (Sn, Sn-l) increasing and concave in range (Sn-1, oo). 10

Proof: The proof will be by induction on n. Define so = 0 and So 0 oo. Then, for stage 1 all the properties are true from Theorem 1. To prove that these properties hold for the general case, suppose that Theorem 2 is true for stage n -1. Then, the following properties must hold: 0 if xn E (0, sn-1) ul(xn) = Xn if n E (sn-l, Sn-l) (15) Sn-1 if Xn ~ (Sn-1,00), where critical numbers Sn,_ and Sn_ satisfy n- 1(Sn-1) + Kn-1 = Yn-1(0), (16) n-l(Sn-l) = 0, (17) Sn-2 < Sn-1 < Sn-l < Sn-2, (18) increasing and concave in range (0, sn-2) and a-l.)is, decreasing and convex in range (sn-2, Sn-)) increasing in range (Sn-1,Sn-2) increasing and concave in range (Sn-2, oo). Figure 3(a) illustrates the nature of n -l(u1n-l) and the relationship among critical numbers as indicated in the induction hypotheses (16)-(19). Since the nature of 7n(-) plays a fundamental role in determining the form of the optimal policy, we first explore its behavior. To this end, we first differentiate 7n(un) in (4) to get 7n(Un) = Fn(Un)[Wn - hn+l + C_-l(Un)]. (20) The term Cn_1(-) can be obtained by first substituting u*_l from (15) into (3) to get hnxn + 7n-1(0) if xn E (0, sn- ) Cn-l(Xn) hnXn + Kn-i + ^n-l(Xn) if Xn E (n-1, Sn-l) (21) hnxn + Kn-l + 7n-l(Sn-1) if Xn E (Sn-1,00), which can then be differentiated to yield Cr'- ( _> \ - n-l(xn)+hn if Xn (Sn-l, Sn-l) n 1(in) - h otherwise. n(u1n) can now be written as t(,), _ | Fn(Un)gn(Un) if un E (sn-1, Sn-1) / Fn(un)[wn + hn - hn+l] otherwise,(22) where gn(un) = wn+hn -hn+l + n-1(Un). (23) Differentiating'n(un), one readily obtains Y',(,) = _ Fn(Un)/n-_l(un)- fn(un)gn(un) if n E (Sn-1, Sn-l) 24) /n(Un); - -fn(un)[Wn + hn - hn+l] otherwise. (24) 11

(a) Yn,(n-1) + K yl(Un1) Yn,, (o)+ K,,_/ y(1(O) 0 S S2 S.0 - - s,-2 /,, S-i S2 Figure 3: (a) The form of Yn-ti(n-l) and (b) its derivative We first investigate the behavior of yn(un) for Un 0 (sn-l, Sn-). From Condition 2, the term (wn, + hn - hn+l) is always positive. Equations (22) and (24) then imply that Yn(un) > 0 and <Y(un) < 0, and hence 7n(un) is increasing and concave outside the interval (Sn-l,Sn-l). To explore the behavior of yn (uz) in the interval (sn-_, Sn-1), we need to first understand the behavior of n_l-(un) since it controls the behavior of gn(un). From the properties of 7n-i(-) indicated in (19), it'can be inferred that (i) for un E (Sn-2 Sn-l), n-1 (un) < 0, _n'-(un) > 0, and (ii) for un > Sn-1, -_(un) > 0. These imply that In_-l(un) is negative and increasing in range (sn-2, Sn-l), crosses zero from below at Sn-_ and remains positive for un > Sn_1, as illustrated in Figure 3(b). Now consider the behavior of gn(un) over the interval of interest, (sn-l,Sn-1). From (23), gn(un) = positive constant+_l(un). But i4_l(un) is increasing in range (sn-2, Sn-l). 12

From (18), (sn-i,Snl) C (sn-2,Sn-1l), i.e., the interval (sn-i,Sn-i) is a sub-interval of (Sn-2, Sn-_). Hence, gn(un) is increasing over (sn-l, Sn-_). The zero-crossing property of gn(un) is of fundamental interest. But before we explore that, we propose the following lemma which rules out the circumstances under which the problem is trivial. The proof and further economic interpretation can be found in the Appendix. LEMMA 3 If (wn + hn - hn+l) > -Yn-l(s+_ 1), then it is not worthwhile to produce at stage n. That is, u, = 0. Consider gn(un) now. It is increasing over interval (sn-i, Sn-i). From Lemma 3 and (23), gn(s+_l1) < 0. Also, gn(Sn-l) > 0 by substituting (17) in (23) and using Condition 2. Hence, there exists an Sn, Sn-i < Sn < Sn-1, such that gn(Sn) = 0. (25) Clearly, gn(un) < 0 for un E (Sn-i,Sn) and gn(un) > 0 for un E (Sn, Sn-). Also, from (19), n'_l(Un) > 0 for Un E (Sn-2,Sn-1) D (Sn-l,Sn-l). It follows from (22) and (24) that (i) Yn(Sn) = 0, (ii) for Un E (Sn-i,Sn), Yn(Un) < 0 and Yn'(un) > 0, and (iii) for Un E (Sn, Sn-i), 7/n(un) > 0, but Yn'(Un) may be positive or negative. Together, these properties imply that Yn(') (i) has a local minimum at Sn, (ii) is decreasing and concave over interval (sn-, Sn), and (iii) is increasing over interval (Sn, Sn-i). Recall that yn(-) is increasing and concave for 2un < Sn-1 and un > Sn-i. This completes the characterization of 7n('). We now characterize the form of the optimal policy. Note that Yn(Un) for un E (0, Sn-i) achieves its minimum at yn(0) while 7yn(ln), Un E (sn-, oo), achieves its minimum at 7n(Sn). If 7yn(0) < yn(Sn), it is optimal not to produce at stage n. If, on the other hand, 7n(Sn) < Yn(0), i.e., Sn is the global minimum of n(.), then it may be worthwhile to produce. The answer depends on the setup cost, Kn. If Kn > 7yn(0) -7n(Sn), i.e., the setup is more expensive than the maximum benefit achievable from production, then one chooses simply not to produce, irrespective of the available input material Xn+i. If, on the other hand, Kn < yn(0) - n(Sn), there exists a unique Sn E (sn-i, Sn) such that Yn(0) = Kn +Yn(sn). (26) Note that a point Sn satisfying (26) can not lie in interval (0, Sn-i) since yn(*) is increasing over this interval and Yn(sn) < Yn(0). It follows from the definition of sn and the decreasing nature of yn(un) over (sn-l, Sn) that Yn(0) < Kn~ + n(un) for all un < sn, (27) and 7n(0) > Kn +7n(un) for all sn < un < ~Sn. (28) 13

Based upon the available input material xn+l, the optimal policy can now be characterized in terms of the two critical numbers Sn and Sn. For Xn+i < Sn, it is not worthwhile to produce because the setup cost, Kn, will offset the expected savings, (7n(O) - yn(un)), derived from production. This follows from (27), since Un < xn+l < Sn. For Sn < Xn+l < Sn, the advantage gained by producing, ('yn(0) -'n(Un)), can offset Kn provided one plans to produce more than Sn. This follows from (28). In fact, since yn(un) is decreasing in range (sn, Sn), it pays to set the production target as high as possible; the optimal policy simply inputs all the available material. Finally, for xn+l > Sn, one sets the production target at Sn, the point where (Kn + Yn(Un)) attains its global minimum. Q.E.D. I The lower critical number, sn, represents the smallest input quantity one is willing to process at stage n. In this sense, Sn is a measure of the effective setup cost at stage n. The upper critical number, Sn, is the maximum desired output from stage n. The interrelationship among critical numbers is of significance for their efficient computation and for understanding how system operates. An immediate corollary of Theorem 2 is COROLLARY 1 For the model stated in Section 2, the optimal operating policy is characterized by a sequence of critical numbers, (Sn, Sn}, such that 0 < s1 < S2 <... < SN < SN <... < S2 < So < 00. This relationship has many intuitive implications for the operation of the serial system under study: 1. The lower critical number is zero at a stage only if it is zero at all downstream stages. 2. The lower critical number increases as one moves upstream. 3. The upper critical number decreases as one moves upstream. As a result, for n = N - 1,..., 2, 1, one has a binary choice: (i) input everything if Xn,+ > Sn, or (ii) input nothing if Xn+1 < sn. In effect, the system has a single-critical-number policy for all stages except stage N, which must follow a two-critical-number policy. 4. The upper critical number at any stage is greater than the lower critical number for all stages. That is, the~largest lower critical number is smaller than the smallest upper critical number. 5. The sequence of intervals (sn, Sn)} is imbedded, i.e., (SN,SN) C (SN-l, SN-) C... C (S2,52) C (Sl,Sl) C (0, oo). (29) 14

5 Sensitivity Analysis This section explores how the critical numbers, Sn and S,, change as the cost parameters are varied. Whenever possible, we have tried to characterize the sensitivity quantitatively, but in many instances, we could only give a qualitative characterization. 5.1 Sensitivity Analysis for the Upper Critical Number, Sn The upper critical number, S, was defined in Section 4 as the zero of the recursive function -n(.) in interval (sn-i,Sn-i). For the purpose of sensitivity analysis, it will be helpful to express -yn(.) explicitly in terms of the other model parameters. Consider /n(un) for un E (Sn-, Sn- ). Substituting (23) into (22), ~n(Un) = Fn (un) (Wn + hn - hn+l) + Fn (Un) /n-L (Un), for un E (sn-l, Sn-l). (30) Similarly, for un E (sn-2, Sn-2), 7n-i(Un) is given by n —l(Un) = Fn-l (n) ( W)n-1 + hn-1 - hn) + Pn-l (Un) Yn-2 (n) which can be substituted in (30) to yield Yn(Un) = Pn(Un)(Wn + hn - hn+l) + Pn(Un)Pn-i(n)(Wn- + hn-1 - hn) +Fn(Un),Fn~- (Un)'n-_2(Un), for Un E (sn-l, Sn-l) Note that this substitution is valid because intervals (sn-i,Sn-i) C (Sn-2,Sn-2) as indicated in (29). By recursive substitution, we can obtain Yn(un) in terms of the model parameters alone. The result is n n n Yn(Un)= E 1 Fj(Un)(Wk + hk-hk+l)- F j(un)Q(un)(r + hl) k=1 j=k j= for un E (sn-i, Sn-1), (31) where Q(un) = 1 -Q(un) and we have used the definition of g1(ul) given in (8). Recall that the upper critical number, Sn, is the solution to equation ^n(Un) = 0, Un E (Sn-1, Sn-i). That is, Sn satisfies n n'n n(sSn) = E F FJ(Sn)(k + h~k-hk+l)- 1 Fj(Sn)Q(Sn)(r + h) = 0. (32) k=l j=k j=l Equation (32) defines Sn in terms of model parameters; other critical numbers are not present in this equation. The upper critical number for any stage can be computed using (32) in a non-recursive fashion. Note that Sn is independent of the capacity distribution for stage n, but it does depend on the capacity distributions for all the downstream stages. 15

Also, the absence of the setup cost parameters, Ki's, in (32) implies that the upper critical numbers do not depend on setup cost. Using the implicit-function theorem, the sensitivity of Sn with respect to any parameter p can be expressed by aoP 9Yn(Sn)/OSn ap ~on(sn) /sn From (24), for,n E (sn-, Sn-. ), Y(Sn = - n(Sn) = Fn(Sn.)"_l(Sn) - fn(Sn)gn(Sn). OSn But gn(Sn) = 0 from definition of Sn, which makes the last term of the above equation vanish. Hence oSn _ rn (Sn)/ (33) ap - F(Sn)yn_(Sn )' The sensitivity of Sn to changes in cost parameters can now be obtained by taking partial derivative of (32) with respect to hi, wi, ir and Ki respectively and then substituting the results into (33). We get THEOREM 3 The sensitivity of the upper critical number, Sn, with respect to 1. disposal cost, hi, is n-1 -Q(Sn) r Fj(Sn)/~n'-_(Sn) if i = 1 j=1 n-1 aSn -Fi-_ (Sn)/ iFj(Sn) (Sn) if li<n j=i -Fn 1(Sn )//- 1 (Sn) if i = 1l/Yin _ (Sn) if i=n+ 0 otherwise; 2. unit production cost, wi, is n-I sn -:l Fj(Sn)/Yin-(Sn) ifi <n 9wi: - -l/in ll(Sn) if i = n 0 otherwise; 3. penalty for not satisfying the demand, 7r, is 97 = Q(Sn) n Fj(sn)/ (Sn); j=1 4. setup cost, Ki, is aSn aKi 16

Note that /t1_(Sn) > 0 since yn-_(un) is convex in (sn-l,Sn-1) and Sn E (sn-,,Sn-1) by Theorem 2. We make the following observations based on Theorem 3: 1. The upper critical number at a stage (i) decreases with an increase in disposal cost at a downstream inventory location, (ii) increases with an increase in disposal cost at the inventory location immediately upstream and (iii) remains unaffected by changes in disposal cost at all other upstream inventory locations. 2. The sensitivity of the upper critical number at stage n, with respect to changes in disposal cost at a downstream inventory location i, aSn/9hi, is directly proportional to the probability that the entire input Sn gets through all the production stages following stage n, up to and including stage i, and is stopped at location i (due to insufficient capacity at stage i - 1, or insufficient demand, if i = 1). That is, aSn oc Pr {Yn-1 > Sn; Yn-2 > Sn;...;Yi > Sn; Yi-i < Sn} for 1 < i < n, Ohi and n oc Pr{Ynl > Sn; Yn-2 > Sn;...; Y1 > Sn; Z < Sn}. aOh Clearly, the farther the inventory location i from stage n, the smaller the likelihood that the entire input Sn reaches location i, and hence the weaker the dependence of Sn on hi. 3. The upper critical number at a stage decreases with an increase in production cost at that stage or at any other downstream stages, but it remains unaffected by the changes in production costs at all upstream stages. Moreover, 9Sn/9/wi is proportional to the probability that input Sn is successfully processed at all stages following stage n, up to and including stage i. Based on observation 2, OSn _ Pr { 1 < S,} OSn/wi if 1 < i < n Ohi = Pr{Z < Sn} Sn/Owl if i = 1, also, for i < j < n, S = Pr {I > Sn; Y+lI > S;...; Yj- > Sn} < OS i.e., the upper critical number at a stage is far more sensitive to the changes in production cost at a nearby downstream stage than those at a stage farther downstream. 4. The upper critical number at a stage increases as the penalty for not satisfying the demand increases. Moreover, the sensitivity 9Sn/97r is proportional to the probability that input Sn is successfully processed at all downstream stages, and still falls short of satisfying the demand. Based on observation 2, we have OSn - Pr (Z > S)Sn 17

i.e., the upper critical number is less sensitive to changes in production cost than to changes in stockout penalty; the negative sign signifies that their effects are in opposite direction. 5. The upper critical number is equally sensitive to changes in disposal cost at the immediately preceding inventory location and to the production cost at the stage under consideration. In fact the changes in either of these parameters affects the upper critical number the most, as can be seen from, as, as, 1 awu =-hn+ =- (S7) = Constant of proportionality. 5.2 Sensitivity Analysis for Lower Critical Number, Sn The proofs of the following sensitivity results for the lower critical number are somewhat involved and are relegated to the Appendix. THEOREM 4 The lower critical number at a stage is zero if and only if the production at that stage incurs no setup cost and the same is true for all downstream stages. That is, s, = 0 if and only if Ki = 0, for all i < n. Whenever the lower critical number, s,, is zero, the optimal policy at stage n is of produceup-to form given by a single critical number, S,, U (=n+l) Xn+ if Xn+1 Sn {Sn if Xn+i > Sn. According to Theorem 4, a nonzero setup cost at a stage makes the lower critical number positive not only for that stage, but for all upstream stages. If the optimal policy for a stage is of produce-up-to form, the optimal policy for all downstream stages must also be of produce-up-to form. The following theorem shows that any increase in the setup cost at a stage will also increase the effective setup costs at all the earlier stages. THEoREM 5 An increase in setup cost at a stage leads to an increase in lower critical number at that stage as well as at all preceding stages. The lower critical number at a stage (i) increases with an increase in setup cost at that stage or at any other succeeding stages, and (ii) remains unaffected by setup cost changes at preceding stages. THEOREM 6 An increase in stockout penalty leads to a decrease in lower critical numbers for all stages. 18

As the shortage penalty increases, one is more likely to carry out production (due to a decrease in lower critical number) and one tends to produce in a larger quantity (due to an increase in upper critical number) at all stages, to avoid the higher shortage penalty. A reduction in unit production cost has an analogous affect on all upstream stages as indicated in the theorem below. THEOREM 7 A decrease in the unit production cost at a stage leads to a decrease in the lower critical number at that stage as well at all preceding stages. The lower critical number at a stage (i) decreases with a decrease in unit production cost at that stage or at any other succeeding stages, and (ii) remains unaffected by the changes in unit production costs at preceding stages. THEOREM 8 A decrease in disposal cost at an inventory location leads to an increase in lower critical number for the stage next to the inventory location. Any decrease in disposal cost at the inventory location before a stage increases the lower critical number and decreases the upper critical number at the stage. However, the decrease in the disposal cost will increase the critical numbers at all the upstream stages. 6 The Impact of Uncertainties We now turn our attention to examine the effect of demand and capacity uncertainties on the optimal policy. We explore this by examining changes in critical numbers as the demand or capacity distribution is changed stochastically. Our results are summarized in the following two theorems; their proofs can be found in the Appendix. THEOREM 9 As the demand increases stochastically, the upper critical number increases but the lower critical number decreases at every stage of the system. An increase in demand tends to increase the expected shortage penalty. To avoid this extra penalty, one is less reluctant to start production and is willing to produce more. THEOREM 10 A stochastic increase in capacity at any stage leads to an increase in the upper critical numbers for all upstream stages, but the upper critical numbers for all downstream stages, including that for the current stage, remain unchanged. As capacity decreases stochastically at a stage, there is larger probability that capacity will take on smaller values. Since it is more likely that only a smaller input quantity can be processed at this stage, the maximum desired output from upstream stages are curtailed. 19

The capacity changes at a stage, however, does not affect the maximum desired output from that stage. To explain this, suppose that the maximum desired output for a stage was determined assuming an infinite capacity at that stage. In case of capacity uncertainty, one simply hopes to produce this desired amount. Reducing the maximum desired output in anticipation of a low capacity realization guarantees lower output for all capacity realizations. This can be no better than letting the realized capacity limit the output. 7 A Numerical Example The purpose of this example is (i) to demonstrate that the two critical nun.Jers can be computed efficiently, (ii) to validate that the sequence of critical numbers, {sn,S,}, is imbedded, and (iii) to illustrate the nature of 7n(*) numerically. Consider a three-stage serial production system with the following costs, W3 =30 W2 = 10 wi = 15 h4 = 10 h3 = 20 h2 = 25 h = 50 r = 200 K3 = 25000 K2 = 0 K1 = 45000. Demand as well as capacities are assumed to follow a lognormal density function 1 -(lna- _)2 0(al|,a) = ---- expt[ 2a2 ] for all a > 0, V/27r7a 2a2 where Ap and a are parameters of the lognormal distribution. That is, q(z) = q(z\pd, ad) and fn(yn) = k(ynl tn), ), n = 1, 2, 3. The parameters of these distributions are I3 = 8.5 /12 = 8.3 gi = 8.5 /d = 7.3 a3 =.2 a2 =.5 al =.3 ad =.5. The upper critical numbers, Sn's, can be computed using (32). Note that this computation need not be carried out in a recursive fashion, i.e., the upper critical numbe r can be obtained independent of each other. In fact, since the implementation of the optinal policy requires only S3 (see Observation 3 for Corollary 1), there is no need to compute any other upper critical numbers. For the purpose of comparison, we report below all the Sfp's S3 = 1708, S2 = 2177, S1 = 2434. The lower critical numbers are calculated recursively using (14) to obtain S3 = 453, s2 = 231, s1 = 214. Note that S2 is greater than zero despite the fact that K2 is zero. This is because the effective setup cost at stage 2 is greater than zero due to a positive setup cost at stage 1. Observe also that the critical numbers satisfy the monotonicity property indicated in Corollary 1. To illustrate the nature of 7n, a plot of y3(u13) is shown in Figure 4. 20

'3 (U3) YY3( )(O) 73(0) \ tU3 s2=231 S3=1708 Figure 4: A plot of 73(u3) for the numerical example 8 Concluding Remarks A major goal of this investigation was to explore how capacity uncertainties affect production decisions in a multi-stage system with setup costs. Despite the unwieldy nature of the cost functions involved, we were able to establish the optimality of a simple two-criticalnumber policy. The critical numbers for successive stages were shown to be monotonic. This fact was exploited for efficient computation of critical numbers. The monotonicity of critical numbers also lead us to the interesting conclusion that production for all but the very first stage, can effectively be controlled using only the lower critical numbers. In our effort to understand how production decisions are affected by cost parameters, we explored the sensitivity of critical numbers to these parameters. The impact of demand and capacity uncertainties were also studied by letting their distributions change stochastically. These results provided us with further insights on the interrelationship among various stages of the system. 21

Appendix Proof of Lemma 3: Suppose (wn+hn-hn+l) > — in_(s+l) then, from (23), gn(sl) > 0. Since gn(un) is increasing over interval (sn-i, Sn-i), it remains positive over this entire interval. As a result, from (22), Yn(Un) is always positive. That is,'7n(O) < Yn(Un) for all un, and it is not worthwhile to produce at stage n. Q.E.D. X Fiarther Explanation for Lemma 3: Recall that for the single-stage problem, an equivalent condition is (wi + hi - h2) > (7r + hl)Pr{Z > O} or g1(0) > 0, which implies that S1 = 0. Condition 2 and Lemma 3 together specify lower and upper bounds on quantity (wn + hn - hn+l) which can be explained as follows. If (wn + hn - hn+l) < 0, one has an unnecessary incentive to process the input at stage n, just for the sake of disposing the output at the next stage. On the other hand, as (Wn + hn - hn+l) increases, it provides an increasing disincentive for production, and beyond a point, it may well become totally uneconomical to carry out production at stage n. In general, if the effective cost of processing a unit, (wn + hn - hn+l), exceeds the maximum marginal benefit derived from making the unit available at the next stage, -n-l(s+-1), one simply chooses not to produce. Proof of Theorem 4: From (10), we know that sl = 0 if and only if K1 = 0 since si E (0,S1) and 71i() is decreasing in (0, Si) by Theorem 1. Assume K1 = 0. From Theorem 2, 72(') is decreasing in (sl = 0, S2). Then, from (26), s2 = 0 if and only if K2 = 0 since s2 E (0, S2) by definition. If K1 # 0, then s1 > 0. By Theorem 2, s2 > sl > 0. Therefore K1 must be zero to have S2 = 0. To proceed by induction, assume sn- =... = S2 = si = 0 if and only if Kn-_ =...= K2 = K1 = 0. By Theorem 2, 7yn(.) is decreasing in (sn-i = 0, Sn). By the definition of the lower critical number, Sn = 0 if and only if Kn = Sn-i = 0 since Sn-l E (0, Sn) by definition. Suppose Ki # 0 for some i < n. Then, Sn-, > 0 by assumption. By Theorem 2, Sn > sn-I > 0. Therefore, Ki for all i < n must be zero to have Sn = 0. QED. U Proof of Theorem 5: Suppose the setup cost at stage i increases from Ki to Ki. Let the corresponding functionsryn(.), Cn( ), etc., be represented by n( ), Cn( ), etc. Similarly, let the new critical numbers be represented by Sn and Sn, for all n. Recall that the upper critical numbers are not affected by changes in setup costs (Property 4 of Theorem 3), i.e., Sn = Sn for all n. Since the change at stage i does not affect decision for any of the downstream stage, hence sj = sj for all j < i. From (26), for stage i 7j(Si) = 7i(0)-iK, 22

i(s) =?i(0)-Ki. Since yi(0) = yi(0) by Lemma 2 and Ki < Ki, hence yi(si) > 71i(5i). Observe from (3) and (4) that yi(*) is not a function of Ki, i.e., yi(ui) = t1i(ui) for all ui. Then, 7yi(i) = %i(si) < yi(si). By Theorem 2, yi(') is decreasing in range (si-l = si-_,Si), and both si and Si belong to interval (sil, Si). Hence, si > si since 7Yi(si) < 7i(si). For stage i + 1, from (4), fui+1 1i+l((Ui+) = ] [(wi+l - hi+2)yi+l + Ci(yti+)l dFi+(y4i+l) do +Fi+l(ui+l)[(wi+l - hi+2)ui+i + Ci(ui+i)]. Then, we can derive rUi+ i+li(ui+-) - +(i+1(u+) = J [i(yi+l) - Ci(yi+l)] dFi+l(yi+l) +Fi+1(Ui+)[Ci(ui+1) - Ci(ui+i)], VUi+1. (A.1) Consider (A.1) for ui+l E (si, Si). Since si > si and Si = Si, the first term can be divided into three sub-intervals (0,si), (si,.i) and (si, ui+l), and then by substituting (21) into (A.1), we have 7i+-l(ui+l) -7 ^i+1()i+l-) {si fsi -= J[7i(0) - Yi(0)] dFi+i(yi+r) + J ^r(0) - 7i(yi+i) - Ki] dFi+l(yi+l) JO Usi + tli+l _ _ + [Ki - Ki] dFi+l(yi+l) + Fi+l(ui+)[Ki - Ki]. (A.2) The last two terms of (A.2) are positive since Ki > Ki. Observing that -i(0) = 7i(0) from Lemma 2, the first term becomes zero and the integrand of the second term can be rewritten as yi(si) - 7i(Yi+l) by the definition of si. By Theorem 2, yi(') is decreasing in (SiSi) C (i-, Si). Therefore, 7yi(si) > 7i(yi+i) for Yi+l E (si, i). Hence, the second term of (A.2) is also positive. As a result, i+41(ui+l) > -i+l(u1i+i) in (si, Si+1). By Lemma 2 and from the definition of the lower critical number, we have i+l(si+l) = yi+(0)- Ki+l = i+(O(KiKi+ =' i+l(Si+l). Hence, i+li(si+i) = 4i+1(s4i+l) > 4i+1(s4i+1) since 1i+l E (1i, Si+) by Theorem 2. Notice that 7Yi+l(*) is decreasing in (si, Si+l) C (si, Si+1) by Theorem 2. Therefore, si+1 < si+l1. In order to proceed by induction, we need 1il1(ui+1) > 7yi+1(ui+l) in (1i+l, Si+2) C (5i, Si+l) from (29). The rest of the proof for stage n > i + 1 is analogous to the proof at stage i + 1. However, instead of the term (Ki - Ki) in (A.2), it will become $n-l(un) - Yn-l(Un) for stage n > i + 1. 23

By induction, assume Sn-I < sn-1 and yn-l(un-1) < 7n-l(un-1) in range (sn-_,Sn) for n > i. For stage n, from (4) we can write rUn ^ 7n(u -n(n) -= J(u) [Cn-l(yn) - Cn-l(yn)] dFn(yn) +Fn(un)[Cn(_,(n) - Cn-_l(Un)]. (A.3) Consider (A.3) for un E (n —1, Sn-1). Since sn-i ^ sn-, and Sn-1 = Sn-1, the first term can be divided into three sub-intervals (0,sn-1), (sn-,s n-1) and (Sn-u,), and then by substituting (21) into (A.3), we have nn(un) - 7Yn(un) /Sn-1 ISn-1 = [^n- 1(0 - yn-(0)] dn(yn) + [^n-l(0) - yn-l(yn) - Kn-l] dFn(yn) JO JSn-1+ Un [7n-l(Yn) - 7n-1(Yn)] dFn(yn) + Fn(un)[^'n- (un) - 7n-l(n)]. (A.4) Sn — The last two terms of (A.4) are positive since %-l(un) > yn-(un). Observing that 7Yn-1(0) = - 1i(0) by Lemma 2, the first term becomes zero and the integrand of the second term can be rewritten as yn_-(sn-1) - 7n-l(Yn) by the definition of Sn-.l By Theorem 2, yn-l(') is decreasing in (sn-1,,sn-) C (sn-2,Sn-l). Therefore, Yn-l(Sn-i) > Yn-l(Yn) for yn E (Sn-l, nl-1). Hence, the second term of (A.4) is also positive. As a result, un(un) > 7Yn(un) in (On-i, Sn). By Lemma 2 and from the definition of the lower critical number, we have Yn(Sn) = ( = nn(0)- K = (0)-K = n(Sn). Hence, yn(sn) = 7n(Sn) >'Yn('n) since Sn E (n-i,Sn) by Theorem 2. Notice that yn(.) is decreasing in (sn-lS,n) C (sn-1, S) by Theorem 2. Therefore, sn < n. In order to complete the proof by induction, 7^n(un) > 7n(un) in (On, Sn+i) C (n-1, Sn) from (29). QED. Proof of Theorem 6: Suppose the penalty cost 7r increases to *t, and the associated yn(.), Sn and Sn become yn(*), Sn and Sn, respectively. The following lemma must hold for all stages LEMMA A.1 For all stage n, IJ/n Fn(un)[Wn + hn - hn+l dun + - n (un) dun = -Kn. (A.5) JO JSn — Proof: By the definition of sn, consider -Kn = Yn(sn) - n(O) = j vIn(Un) dun, 24

by definition of integration. From (22), 7Y(un) can be decomposed into two sub-intervals (0, sn-l) and (sn-l, sn) instead of (0, sn). Hence, equation (26) can be rewritten as (A.5). QED. o By Condition 2, the integrand in the first term of (A.5) is positive, and since an(-) is decreasing in (sn-i, Sn) by Theorem 2, the integrand in the second term is negative. Hence, equation (A.5) can be interpreted as follows: the increment of yn(*) from 0 to sn-l minus the decrement from Sn,- to s,, is always equal to -Kn. Consider (A.5) for the case when the penalty is 7r j"-1 Fn(un)[w + hn -hn+l] dun + Yn n(un) dun = -K. (A.6) JO sn-1 Since -Kn is a constant, the difference between the left-hand-sides of (A.5) and of (A.6) is zero. We will prove the theorem by induction. For each stage n, we will show if Sn > Sn is not true, then the difference between (A.5) and (A.6) will turn out to be negative. By contradiction, s, > Sn,. For stage 1, the first terms of both (A.5) and (A.6) vanish since so = so = 0. Then, by subtracting (A.6) from (A.5), we have jS1(ul)dj )d = 0. (A.7) Jo Jo In order to prove by contradiction, suppose sl < sl. Then, equation (A.7) can be rewritten as [Y (ul) - A (ul)] dul + Jl(ul) dul = 0. (A.8) Since,r > 7r, thereby i(1(u1) > %(u l) in range (O, si) C (0, oo) from (31). Then, the first term of (A.8) is negative. The second term is also negative since the integrand, i(ul), is negative in range (sl,s} ) C (0,sl) by Theorem 1. Hence, the left-hand-side of (A.8) becomes negative. This breaks the equality in (A.8). Therefore, sl > S~1. By induction, assume sn-i > Sn-1. For stage n, in order to prove by contradiction, suppose Sn < 3n. Hence, Sn-i < sn-i < Sn < Sn since Sn-i < sn by Theorem 2. Subtract (A.6) from (A.5) - n —1 n —1 J 9n-l bSn S-n + [Yn( un) - /n(un)] dun + Yn(un) dUn = 0. (A.9) JSn-l Jsn The first term of (A.9) is negative since Wn + hn - hn+i > 0 by Condition 2. By Theorem 2, 7n(.) is negative in range (sn-l,Sn), which contains intervals (sn-l,sn-i) and (sn,,n). 25

Therefore, the second and fourth terms of (A.9) are both negative. From (31), consider yn(un) in (sn-1,Sn-1) and Zn(un) in (n-i,Sn-1). Since i _> ir, hence j(un) < n(un) in range (Sn,-i, Sn- l) = (Sn- i,Sn-_) n (nl-1,S- 1) since Sn-i < Sn-_1 by Property 3 of Theorem 3. By Theorem 2, (sn-_, Sn- ) contains interval (Sn-i, Sn). Therefore, the third term of (A.9) is also negative. Hence, the left-hand-side of (A.9) is negative. This breaks the equality in (A.9). As a result, sn < sn. QED. * Proof of Theorem 7: Suppose the unit production cost Wi at stage i decreases to Wi, and the associated yn(.), Sn and Sn become $n(.), Sn and Sn, respectively. By Lemma A.1, rewrite (A.5) for stage i, Fi(ui)[wi + hi - hi+l] dui + i(ui) dui = -K. (A.10) For the change from wi to wi, equation (A.10) becomes j llFi(ui)[zwi + hi - h+i+l] dui + (ui) dui = -K. (A.11) O0 J 5/-1l Since -K, is a constant, the difference between the left-hand-sides of (A.10) and of (A.11) is zero. We will prove the theorem by induction. For each stage n, we will show that if Sn >'n is not true, then the difference between (A.10) and (A.11) will turn out to be negative. By contradiction, sn > sn. By subtracting (A.11) from (A.10) and observing sil = si-i(since si,- is not a function of wi), we have /0 Fi(ui)[,i - Wi] dui + [+(ui) - Yi(ui)] du + I'(ui) dui = 0. (A.12) JoQ ~ si —1 JSi The first term is negative since wi < wi, and the third term is also negative since Y(.) is negative in range (si, i) C (si-,,Si) by Theorem 2. From (31), consider -i(ui) in (si-,S,-l) and /(ui) in (i_-1,Si-1). Since wii < wi, hence Y/(uj) < Yi(ui) in range (si-, Si-I) = (Si-1, Si-l) n (Si-i, Si-l) since Si-i < Si-i by Property 2 of Theorem 3. By Theorem 2, (si-1,Si-i) D (si-l,si). Therefore, the second term of (A.12) is also negative. Hence, the left-hand-side of (A.12) is negative. This breaks the equality in (A.12). As a result, ~i < si. By induction, assume sn-_ > Sn-1. For stage n > i, consider (A.5) and (A.6), which is the version of (A.5) after wi shifts to Wi. Suppose Sn <.n. Hence, sn-1 < Sn-i < Sn < Sn since sn_ < Sn by Theorem 2. Notice that both integrands in the first term of (A.5) and (A.6) are the same. Subtract (A.6) from (A.5). Then, we get (A.9). The first term of (A.9) is negative since Wn + hn - hn+l by Condition 2. By Theorem 2, n(') is negative in range (n-l, Sn), which contains intervals (sn-l,s5n-) and (Sn, n). Therefore, the second 26

and fourth terms of (A.9) are both negative. From (31), consider 7,n(Un) in (sn-i, Sn-) and gn(un) in (On-1,Sn-l). Since Wti < wi, hence Yn(Un) < Y/n(n) in range (n-i, Sn-i) = (Sn-i, Sn-l) n ('n-1, Sn-i) since Sn-1 < Sn-i by Property 2 of Theorem 3. By Theorem 2, (Sn-i, Sn-i) contains interval (n-i, Sn). Therefore, the third term of (A.9) is also negative. Hence, the left-hand-side of (A.9) is negative. This breaks the equality in (A.9). As a result, Sn < Sn. QED. Proof of Theorem 8: Suppose the disposal cost hn+l at inventory location n +1 increases to hn+l, and the associated,n(.), Sn and Sn become,n(.), Sn and Sn, respectively. By Lemma A.1, consider (A.5) for stage n when the disposal cost at inventory location n + 1 is hn+l, Sn-1 n l Fn(un)[Wn + hn - hn+l] dun + in(Un) dun = -Kn. (A.13) JO Sn-1 Since -Kn is a constant, the difference between the left-hand-sides of (A.5) and of (A.13) is zero. In order to prove sn ~ sn by contradiction, we will suppose that Sn < ~n for stage n, and then show that the difference becomes negative. Suppose sn < sn. Notice that sn-i is not a function of hn+i, i.e., Sn-l = sn-i. By subtracting (A.13) from (A.5), we have fSn-1 Sn S FFn(un)[hn+l-lhn,+] dun+ [/n(Un)-7n(un)] dun+ J n(Un) dUn = 0. (A.14) ~JO~~~ ^~S~n-1 n The first term is negative since hn+l > hn+i, and the third term is also negative since 7n(-) is negative in range (Sn, sn) C (sn-i, n) by Theorem 2. From (31), consider /n(un) in (s,-1,Sn-l) and in(un) in (,n-_,Sn-_). Since hn+l > hn+l, hence Yn(un) < Yn(un) in range (sn-i,Sn-i) = (Sn-i,Sn-i) n (sn-i,Sn-i) since Sn-1 < Sn_1 by Property 1 of Theorem 3. By Theorem 2, (sn-i, Sn-i) contains interval (n-i, Sn). Therefore, the second term of (A.14) is.also negative. Hence, the left-hand-side of (A.14) is negative. This breaks the equality in (A.14). As a result, Sn < Sn,. Proof of Theorem 9: Suppose that the demand distribution changes from Q(z) to Q(z) such that Q(z) < Q(z) for all z, and the associated gn(-), yn(-), Sn and Sn become 9n(~), (.n('), Sn and Sn, respectively. We first show inductively that Sn < Sn for all stages. By substituting (22) into (31) for n, E (Sn-l, Sn-1), one obtains n-ln-1 gn(Un) = (Wn + hn-hn+l) + E I j(Un)(Wk + hk - hk+1) k=l j=k n-i - n Fj(un)Q(un)(7r + hl) (A.15) j=l 27

Since So = so = 0 and So = So oo, both gl(ul) and gi(ui) are defined in (0, oo) in (A.15). Since Q(un) < Q(un) hence gi(ul) > 1(ul) in range (0, oo). Then, gl(Si) < gi(Si) = 0 by definition of Si. Hence, Si < Si since function gl(ul) is increasing and i(5Si) = 0. By induction, assume Sn-1 < Sn-1. For stage n, 1. in case that Sn < Sn-i: By Theorem 2, Sn < Sn since Sn-i < Sn. 2. in case that Sn > Sn-i: From (A.15), consider gn(un) in (Sn-l,Sn-1) and 9n(un) in range (5n-i,Sn-1). Since Q(un) < Q(un), hence gn(un) >.n(un) in range (max{Sn-i, n-i}, Sn-l) = (Sn-i, Sn-i) n (5n-i, Sn-i). By Theorem 2, both Sn and Sn belong to the interval (max{(sn-.i, n-i}, Sn-i). Hence, 3n(5n) < g9n(Sn) = 0 from (23). Therefore, Sn > Sn since gn(-) is increasing in (Sn, Sn-i) C (Sn-i, Sn-i). Now, we need to prove that sn > Sn for all stages. From (31), while the demand density shifts from Q(z) to Q(z), we have Pn(un) < yn(un) in range {(Sn-i, Sn-i) n (Sn-_, Sn-l)} since ^n(Un) < gn(Un) in the same range. This result is analogous to the one in the proof of Theorem 6, where the penalty cost increases from 7r to *'. Following the proof of Theorem 6 by using (A.5)-(A.9), one can show that sn > Sn. QED. U Proof of Theorem 10: Assume the capacity density at stage i change from Fi(yi) to Fi(yi) such that Fi(yi) < Fi(yi) for all yi, and the associated gn(-), Sn and Sn become gn('), Sn and Sn, respectively. From (A.15), gi(ui) is not a function of Fi(-). Hence, from (25) Si = Si. From (22), iy(ui) = Fi(ui)gi(ui) if ui e (si-i, Si-1), (Uli) = Fi(u)gi(u) if ui E (siSi-i). ThenY, (uj) > 7(u1) in range {(si-_,Si-_) n (Si-l, S-i)}. From (23), gi+i(ui+l) = Wi+n + hi+l - hi+2 + i(ui+l), 9i+1(ui+l) = Wi+l + hi+, - hi+2 + Y(ui+l)Hence, gi+l(u1i+l) > 9i+l(ui+l) in range {(si-,Si-l) n (Si-i,Si-i)}. By recursive substitution and (29), we obtain -f,(un) > n(un) and gn(un) > gn(Un) in range {(sn-i, Sn-,) n (Sn-1,Sn-i)} for n > i. By induction, assume Sn-i < Sn-i for n - 1 > i. Then, gn(un) > 9n(un) in range {(Sn-, Sn-i) n (Sn-_, Sn- ) }. For stage n, if Sn < Sn- i, then Sn < 5n since sn-1 < Sn by Theorem 2. If, on the other hand, Sn > Sn-i, then Sn E {(Sn-i, Sn-i) n (sn-i, Sn- )} by Theorem 2. Hence, 4n(Sn) < gn(Sn) = O from (23). Therefore, Sn > Sn since 9n(') is increasing in (Sn, Sn-1) C (sn_ 1, Sn-1). 28

Reference Barad, M. and D. Braha, "Optimal Policies for Coping with Stochastic Yield in MultiStage Discrete Processing Systems: Part I," Working Paper, Department of Industrial Engineering, Tel-Aviv University, Tel-Aviv, Israel, 1991. Ciarallo, F. W., R. Akella and T. E. Morton, "A Periodic Review, Production Planning Model with Uncertain Capacity and Uncertain Demand - Optimality of Extended Myopic Policies," Management Sci., 40 (1994), 320-332. Denardo, E. V. and Y. S. Lee, "Managing Uncertainty in a Serial Production Line," Working Paper, Department of Operations Research, Yale University, New Haven, CT, 1991. Gerchak, Y., R. G. Vickson and M. Parlar, "Periodic Review Production Models with Variable Yield and Uncertain Demand," IIE Transactions, 20 (1988), 144-150. Gong, L. and H. Matsuo, "Stabilizing Work-in-Process and Smoothing Production in a Production System with Random Yield," Working Paper, Graduate School of Business, University of Texas, Austin, TX, 1990. Heing, M. and Y. Gerchak, "The Structure of Periodic Review Policies in the Presence of Random Yield," Operations Res., 38 (1990), 634-643. Hopp, W. J., M. L. Sperman and Y. Duenyas, "Economic Production Quotas for Pull Manufacturing Systems," IIE Transactions, 25 (1993), 71-78. Lee, H. L. and C. A. Yano, "Production Control in Multistage Systems with Variable Yield Losses," Operations Res., 36 (1988), 269-278. Tang, C. S.,'The Impact of Uncertainty of a Production Line," Management Sci., 36 (1990), 1518-1531. Wein, A. S., "Random Yield, Rework and Scrap in a Multistage Batch Manufacturing Environment," Operations Res., 40 (1992), 551-563. Yano, C. A., "Controlling Production in Serial Systems with Uncertain Demand and Variable Yields," Technical Report 86-5, Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, 1986a. Yano, C. A., "Optimal Polidies for a Serial System with Setup Costs and Variable Yields," Technical Report 86-24, Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, 1986b. Yano, C. A. and H. L. LEE, "Lot-Sizing with Random Yields: A Review," Technical Report 89-16, Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, 1991. 29

UNIVERSITY OF MICHIGAN 3 9015 04735 3621