PRODUCTION CONTROL IN MULTI-STAGE SYSTEMS WITH VARIABLE YIELD LOSSES Hau L. Lee Department of IndjRfaal Engineering and Engineering Management Stanford University Candace Arai Yano Department of Industrial & Operations University of Michigan Engineering Technical Report 85-32 October 1985 Revised August 1986 and May 1987

PRODUCTIOK CONTROL IIB ULTI-STAG STSTEg S WITH VARIABL YIELD WLOS8e Hau L. Lee Department of Industrial Engineering and Engineering Management Stanford University Stanford, CA 94305 and Candace Aral Yano Department of Industrial and Operations Engineering University of Michigan Ann Arbor, MI 48109-2117 October 1985 Revised August 1986 and May 1987 Supported in part by National Science Foundation Grant DMC-8504644, and the Stanford Institute for Manufacturing and Automation.

PRODUCTION CONTROL IN MULTI-STAGE SYSTEMS WITH VARIABLE YIELD LOSSES ABSTRACT Many manufacturing processes involved in the fabrication and assembly of "high tech" components have highly variable yields, complicating the planning and control of production. We develop a procedure which determines optimal input quantities at each stage of a serial production system in which process yields at each stage of production may be stochastic. The procedure is applied to an example in the manufacture of a light-emitting diode (LED) display using actual yield data. We also provide a brief analysis of quantifiable savings obtained by reducing the variability of the yield at one production stage.

PRODUCTION CONTROL IN MULTI-STAGE SYSTEMS WITH VARIABLE YIELD LOSSES 1.0 INTRODUCTION Many manufacturing processes involved in the fabrication of "high-tech" components have highly variable yields, complicating the planning and control of production. Specific examples include wafer fabrication and microelectronic assembly. Similar problems also arise in chemical and other process industries. In many instances, the processes are intrinsically variable and the short term objective is simply to deal with the variability as well as possible. Over the longer horizon, management may be interested in assessing the economic benefits of improved equipment or process controls to improve the yield rate distribution. A few early papers addressing the problem of controlling production systems with uncertain yields focus on systems in which the yield is observed only after production of the entire order is completed. In these models (e.g., Giffler (1960) and Levitan (1960)), the entire production process is viewed as a single stage and the objective is to find a reject allowance which optimizes the tradeoff between shortages and overages. Klein (1966) and White (1967) investigate other single-stage situations in which inspection may be done for sub-batches. They demonstrate that optimal sub-batch sizes can be found for single stage production systems using linear programming. In simulation studies of single-stage systems, Whybark and Williams (1976) found that safety stock is a more effective and"efficient buffer against quantity uncertainties (including stochastic yields) than safety time. Other recent work on production control in systems with uncertain yields (e.g., Porteus (1986), Sepehri, Silver, and New (1986), and Lee and Rosenblatt (1986)) is also limited to single-stage systems. Wagner (1980) points out a need for methods to handle stochastic aspects of multi-stage systems, including yields, 1

and suggests that they be developed with a view toward "more realistic approaches, better approximations, and clearer insights about design and decision tradeoffs." We describe and formulate a single-period production control problem in general serial systems with stochastic yields in the next section. It bears some resemblance to a problem addressed by Beebe, et al. (1968) in the manufacture of transistors. There, the critical decisions were the amounts of impurities to add to pure crystal in order to achieve a desired resistivity. The resistivity actually achieved was random due to a variety of factors. We then develop a relatively simple procedure to determine optimal input quantities for each process stage. The procedure is applied to a light-emitting diode (LED) fabrication facility using scaled actual data. We then provide results of a brief analysis of the economic impact of changes in the yield variability at one production stage. Finally, we discuss directions for future research. 2.0 PROBLEM DEFINITION AND FORMULATION The system under study is an N-stage serial production environment in which the yield at each process stage may be stochastic. We assume that the yield rate probability distribution functions at the various stages are mutually independent and that each has a range whose endpoints are greater than zero and less than or equal to 1. Throughout the paper, we use the term yield rate to refer to the fraction of acceptable parts. We assume that the yield rate distributions are invariant with the size of the input batch (i.e., no economies or diseconomies of scale). The p.d.f. of the yield rate at stage n is denoted as fn('). 2

We assume that there is a single product and that the product has a fixed or predetermined routing through the production facility which can be represented conceptually as a serial system. There is a single known requirement or demand for the finished product, D, to be satisfied, and the problem is one of determining the optimal input quantity at each process stage so as to minimize total cost. We assume that the finished product requirements have been specified so that the capacity limitations of any batch processes are likely to be satisfied by the optimal input quantities. (Our approach can be generalized to capacity constrained situations with little difficulty, however). We further assume that setup costs, if any, are either sunk costs by virtue of the fixed routing, or are considered outside this framework, perhaps to specify the requirement (or lot size), D, if a "make to plan" policy is followed. The flow of items in the system can be represented diagrammatically as shown in Figure 1. The stages are numbered so that the stage of production to be performed first is denoted as stage N, while the final stage of production is referred to as stage 1. The decision at stage n, n-1 to N, is the input quantity at stage n, which we denote as un. The input to stage n is obviously constrained by the output of stage n+1, which, in turn, depends upon the input at stage n+2, etc. The output of stage n is yn - PnU' where pn denotes the actual (random) yield fraction at stage n. There is a yield loss of (1-pn)un and an overage quantity of (Yn-unl)+, where (')+ indicates the positive part. At the final stage of production, the shortage quantity is (D-Y1)+. We assume that initial inventory of all semi-finished items is zero. Later in the paper we explain how the approach can be generalized to accommodate positive initial inventory. FIGURE 1 3

Costs to be included are (1) wn = marginal production cost per unit of input at stage n (material, labor, and inspection), (2) hn - net cost of disposing a unit produced at stage n but not used at stage n-1 (overages), where stage n - 0 corresponds to finished product demand, and (3) r - shortage cost for each unit of unsatisfied demand. All of these costs reflect cash flows. Therefore, the net cost of disposing an unused unit is typically the cost of removing each unit of overage from the production facility, less the salvage value if it can be sold. Hence, hn can be negative, reflecting the cash inflow arising from the net salvage value. Similarly, the shortage cost reflects lost revenue, plus any additional shortage penalties. We assume that all defective units are disposed at no additional cost. It is also assumed that ir > Ih1. If h1 is positive, this condition implies that one would prefer to hold a unit of the finished product in inventory rather than to incur a shortage. If h1 is negative, this condition simply requires that the shortage cost (lost revenue) be at least as large as the net salvage value. All other parameters and costs are assumed to be non-negative, and the integrals of fn(') are assumed to exist and to be continuous and twice differentiable. 3.0 SOLUTION APPROACH Let YN+1 denote the available input (raw material) for production stage N. We might formulate the problem as: N minimize E{ I [wnun + hn+l(Yn+l-Un)+] + hl(Y1-D)+ + r(D-y1)+}, (1) ul,...,uN n-1 subject to 0 < un < Yn+ n 1,...,N, -n " PnUn' n 1,*...N, where n has density where Pn has density fn(')~ 4

This formulation of the problem requires that the decision variables, un, be selected before the Ynl values are known. It therefore does not take advantage of the dynamic nature of the problem. In reality, one does not need to specify un until Yn+l is known. The dynamic programming formulation given below reflects the dynamic nature of the problem. Let Cn(yn+l) - expected cost of operating the system optimally from stage n through stage 1, given that the output from stage n+l is Yn+1l n - 1 to N. Then CN(yN+1) represents the minimum total cost of operating the system. Clearly at each stage we must have un Y n+ (i.e., input cannot exceed output of the preceding stage). Therefore, we can write the dynamic programming recursion relationships as: Cn(yn+1) min {wnun+hn+l(yn+l-un)+E[Cn-l(Pnun)]} n - 2 to N, (2) 0 < Un i Yn+l and C1(Y2) - min {Wlul+hl E(y1-D) + h2(y2-ul) + w E(D-y1)+}. (3) 0 u1 < Y2 To simplify the presentation, let gn (nlYn+1) WnUn + hn+l(Yn+1 - un) + E [Cn-l(Pnun)], n-2,...,N, (4) gl(U1lY2) - Wl1 + h2(y2-u1) + hlE(p1u1-D)+ + iE(D-plUl)+, (5) and un* - optimal value of un. We note that g1(u1ly2) is a function only of u1. Also gn(unlyn+1) is a function of un which affects only downstream stages n-1,...1. Therefore, we can determine ul* from equation (3), and successively determine un* given Yn+1 for n - 2,..., N in sequence from equation (2). We next demonstrate that the form of the optimal policy does, in fact, have a "single critical number" at 5

each stage, and that these values exist. 3.1 STRUCTURE OF THE OPTIMAL POLICY We shall show that there exist S1,...,SN such that the optimal production decisions satisfy * f Yn+ if Yn+l <Sn u ' a n-1,..., N. Sn otherwise, In words, this states that the optimal policy has a single critical number for each stage (Sn), which is independent of the output of the preceding stages. Two conditions on costs are required for the theorem which follows to hold. For notational simplicity, let pn denote E(Pn). The conditions are: Condition I: For all n = 1,..., N, Wn + hnPn > hn+l Condition II: For all n - 1,..., N, n-1 j n hn+1 + [Wn- j H n P hn+l ~Cwn-j " Pn-i+l < Pi J=O i-i i-i The first condition ensures that it is less expensive to dispose an item at one stage than to process it at the next stage and to dispose the expected output of the item at that stage. Stating this in terms of the net salvage-values (when the hn values are negative), we could rewrite condition I as: hn+1 > -hnPn - wn This states that the cash inflow from salvaging at stage n+1 exceeds the expected cash inflow from salvaging at stage n, less the cost of processing at stage n. If this condition is not satisfied, it would be optimal to set un = 6

Yn+1' i.e, to input all available units. Condition II essentially ensures that it is profitable to produce the product. We next present the main result of the paper: Theorem 1: If conditions I and II hold, then there exists a unique set of finite values S1, S2,...,SN such that SN > SN-1... S1, and such that the optimal production decisions satisfy r Yn+1 if Yn+1 < Sn Sn otherwise Proof: The proof consists of two parts. In the first part we establish (for all cases) the optimality of the critical number policy and the relationship among the Sn values. We also prove uniqueness and existence of Sn assuming that Sn-1 is positive. In part two, we show that the uniqueness and existence results are valid even when Sn-1 is zero. Part 1: First, we establish that the critical number policy given by the S s is optimal, and that Sn is unique if Sn_1 > 0. We then show that conditions I and II are sufficient for the existence of a finite value of Sn if Sn_1 > O. We also demonstrate that the values of Sn, if they exist, have the property that SN > SN_1... > S1. Details of several lemmas needed for the proof appear in the Appendix. We will prove optimality of the critical number policy by induction. Consider n-4. Then we have C1(y2) - Min g1(uIY2) 0<u1 <Y2 Consider gl(ulIY2) as defined in (5). 7

Clearly, the first derivative with respect to u1 is D/u1 1 w1 - h2 - I r Plfl(P )dp1 + hl f P1fl(pl)dpl (6) P1 -0 P1 D/u1 Moreover, the second derivative with respect to u1 is (i + h1)(D2/u3)f1(D/u1) > 0 Hence, the uI that minimizes g1(ullY2) is the value of ul which equates the expression in (6) to zero. Let S1 be the value of u1 which satisfies this first order condition. By the convexity of gl(ully2), if Y2 < S1, then u1 - y2, whereas if y2 > S1, then ul - S1. The expected cost of using ul - Y2 is simply g1(Y21Y2), and the expected cost of using u1 - S1 is gl(S1ly2). Now suppose that the theorem is true for some stage n-1. The expected cost of using the optimal decision rules for stages n-1, n-2,..., 1 is gn-l(YnlYn) if Yn < Sn-1 Cn-1(yn),, gn-1(Sn-llYn) if Yn > Sn-l. Let us now consider stage n, given output Yn+l from stage n+l. Cn(yn+ ) - Min (Wnun + hn+l (Yn+l - u) + E[Cn-.(PnUn)]} O<Uniyn+l The expression in braces on the right hand side of the expression above can be written as Sn-1/Un Yn(un) 'WnUn + hn+l(n+l - n) + I gn- l (nun pnn) n (p ) d Pn-O 1 + F gn-1(Sn-1 IPnUn)fn(Pn)dPn Pn'Sn- 1/Un 8

Let gn(xlx) - gn(x x)/ax, gn(Snlx) - gn(Snlx)/d x, g(xlx) - a)2gn(xlx)/ x2 gn(Snx) - d 2n(S lX)/x2 The first derivative of Yn with respect to un is S /u Yn(un) - wn hn+1 + gnpn U n-pn n)Pn(n(Pn)dpn 1 + gn-1 (sn- 1PnUn)Pnfn(Pn)dPn7) PnSn- 1/un All other terms cancel. The last term can be simplified by using Lemma 1, so Y'(u) becomes Sn_1/un, n - hn+1 + gn l(pnun un)Pnfn(Pn)dPn Pn =0 1 + hnPnfn(Pn)dPn (8) Pn=Snl t /Un The second partial derivative of Yn is Sn- /un n(un) - (Pn n l PnUnl )pnfn(Pn)dPn (9) Yn(un) -PJ''l( 9) Pn=O since all other terms cancel by Lemma 2. Using the result of Lemma 3, it can be shown that Yn(un) > 0 if Sn_1 > 0. Hence, Yn(un) is strictly convex in un for n - 1,...,N. Let Sn be the value of un which equates Y'(u ) to 0. By the convexity of Yn(un), the optimal policy has the critical number form, and by its 9

strict convexity, the values of Sn, n - 1,...,N are unique. We next show that Sn exists and is finite when Sn_1 > 0. Let &n(Sn) - Yn(Sn). Now n-1 J n Sn(0) I [w n- 11 Pn-i+1l hn+1 - 1 I Pi, by Lemma 4. j-0 i-1 i-1 Therefore, if condition II holds, in(0) < O. Also, from equation (8) limr sn(Sn) - wn w hn+1 + hn Pn Sn —>> Therefore, if condition I holds, then Slm n(Sn) > 0. By the strictly increasing property of rn(Sn) when Sn_1 > O, there must exist a finite Sn that satisfies &n(Sn) ' O. To establish that SN ~ S1 >... > S1, we make the observation that, for any n, if Sn < Sn-1, then &n(Sn) has the same value as &n(Sn'Sn-1). Therefore, if Sn < Sn_1, we simply set Sn_1 - Sn. This proves the first part of the theorem for all n. Part 2: We shall show that a finite, unique Sn exists even when Sn-_l 0. If S -1 ', then from (9) Y"(un) 0 for all positive values of un, so Yn(u) is linear over this domain. By condition I, we have from (8) that Yn(un) > 0 for all positive un. Now consider what happens at un - O. We have from (9) and Lemma 3 that Yn(O) > O. Thus, Yn is strictly convex at un - 0, and is linearly increasing for all positive un. It is therefore optimal to set Sn - 0. By induction, it is also optimal to set Sn+1,...SN to zero. Observe that the optimal values exist and are unique and finite. This proves the second part of the theorem for all n. o 10

We next examine solution characteristics when either of the two conditions is not satisfied. If condition I is not satisfied at some stage n, then for that stage, lim ~n(Sn) < O. This implies that 5n(Sn) < 0 for all Sn > 0 since &n(Sn) is increasing for all value of Sn. Hence, for this stage, from equation (8), we have Yn(un) - Sn(un) < 0, for all un > O, so that we can always reduce Yn(un) by increasing un. As a result, the optimal value of un is Yn+1, which is the largest available quantity. In other words, the entire output of stage n+1 should be input to stage n. This implies that we must redefine Yn(yn+l) accordingly. We can then proceed as before to solve for Sn+1 using Yn+1 - 0. Thus, whenever condition I is not satisfied, we set Sn - -, and proceed as before. If condition II is not satisfied at some stage n, then for this stage we have lim oi (S ) > 0, which implies that n(Sn) > 0 for all S > 0. n Therefore, for this stage, from (8) we have Yn(u ) - Sn(u) > 0, for all un > O. As a result, the optimal value of un is 0, irrespective of the value of Yn+'1 In other words, it is not profitable to process any unit from stage n onward. In this case, the solution to the original problem should be not to produce the product at all. It is now evident that conditions I and II are conditions which ensure that the Sns are positive and finite. However, the methodology can be applied (with appropriate modifications) even when the conditions do not apply. To find the critical numbers, we simply solve d g1(S1 Y2)/d S1 - 0 for S1 and S(S ) - 0, n = 2,...,N, recursively for S2,..*,SN, by equating the expression in (8) to zero. 3.2 CASE OF POSITIVE INITIAL INVENTORY If the initial inventory of any semi-finished part or the finished product is positive, the procedure still can be applied with minor modifications. Let 11

In denote the inventory of items which have completed stage n but not stage n-1. Then we can rewrite the dynamic programming recursion relations as: Cn(Yn+1 + In+) - min {wnun + hn+l (Yn+l + In+1 - Un) + E[Cn-1 (PnUn + In)]} OUnYn+ +n+1 n n - 2,...N and C1(Y2 + 12) - min {w1u1 + h2 (Y2 + I2 - u1) + h1 E(Y1 + I1 -D) + Oul SY2+I2 + i E(D - I1 - Y1)+} Let Yn - Yn + In for all n. By substituting Yn for Yn throughout the analysis, it can be shown that relationships and results established earlier hold even when In > 0 for some or all n. To solve for the optimal values of Sn, n - 1,..,N, the following equations should be used instead of g(S1 IY2) - 0 and &n(Sn) ' 0: (D-I1) /S1 w i Pjf (P1)dP l + hl r JPi-o J p1-(D-I )/S Plfl(Pl)dpl - 0 and Wn - h+1 (Sn-1 ' In)+/Sn + ( 8 n-1 (PnSnlPnSn)Pnfn(Pn)dPn JPn'O + r n J Pn-=(Sn,.l-I,,) +/Sn, gn- 1 (Sn- 1 Pnn)Pnfn(Pn)dpn = 0 Observe that these equations use D-I1 rather than D and Sn_1 - In rather than Sn_1 to find S1 and Sn-1 respectively. Thus, the net "requirement" (for either finished product demand or the target input quantity for the appropriate successor stage) is used instead of the gross requirement. The optimal critical number for stage n, Sn, is defined in the same way as before. However, it may be supplied frrom two sources: existing inventory at stage n+1 (In+1) and the 12

output of stage n+l which is Yn+1 ' Pn+1 Un+.l The sequential procedure described above can still be used. The only special cases that need to be considered are: (i) I1 > D and (ii) In > Sn-1 In the former case, nothing needs to be produced, and S1 - 0, which implies Sn - 0 for n - 2,...,N by part 2 of Theorem 1. In the latter case, there is sufficient input to stage n-1, so Sn - 0 is optimal, and Sj - 0 for j - n+l,..,N as well (also by Theorem 1). Thus, there are minor computational differences between the case with positive initial inventories and the case without initial inventories and only minor modifications to the procedure are required. 4.0 COMPUTATIONAL RESULTS For most commonly observed yield rate distributions, it is not possible to obtain a closed form solution for any of the Sns. The solution procedure requires a search in conjunction with numerical integration. However, in many real-world applications historical yield data are available and empirical distributions can be used rather than fitted distributions. Moreover, since the relevant cost functions are convex, the first derivatives are non-decreasing, making bisection or Fibonacci search effective search procedures. Actual yield rate data were obtained for the three major stages of production for a light-emitting diode (LED) fabrication facility. The fabrication process is depicted in Figure 2. The die attach process involves placement of LED chips into appropriate locations within a frame or base. These LED chips are then electrically connected in the wire bond process. Finally, a reflecting cavity is cast around each LED display to enclose it and to provide appropriate diffusion and reflection. There are several other steps in the production process but they have been omitted because their yield rates are 13

essentially 100%. The scaled yield rates are reflected in histograms in Figure 3. Variable production costs (scaled to preserve confidentiality) are $0.82, $0.63, and $1.45, at stages 1, 2, and 3, respectively. The shortage cost is $5.29, which is the selling price per unit less other variable production expenses. The variable production costs include inspection costs as indicated in Table 1. The plant produces three shifts per day, seven days a week, so the actual problem involves multiple periods. In order to reflect this as accurately as possible within the context of a one-period problem, we let the wn values represent the opportunity cost of producing a unit in this period rather than next period (due to discounting effects). We assumed that other inventory holding costs were negligible. Similarly, we let Ir be the opportunity cost of selling a unit in the next period rather than this period. We used a discount rate of 30%. per year. The production requirement for one shift is 7000 units; we therefore let D = 7000. FIGURES 2 AND 3 AND TABLE 1 To find S1 we need to solve: D/S1 1 wi - h2 - 4r P1If(pl)dp1 + h1 r P1fl(pl)dpl - 0 1 O P1 D/S1 which is the first order necessary condition for the one-stage cost function. Observe that we only need to find the ratio D/S1, or the appropriate fractile of the yield-distribution. For the given data, we obtain S1 - 7857. Now, given S1, we solve for S2 using the first order condition for the twostage cost function: S1/S2 2 h3 + wi f P2f2(P2)dP2 P2-0 14

S1/S2 1 +h1 f r J J P1O0 P1-D/P2S2 S1/S2 D/P2S2 -. f t P11 JP20 P1O0 Plf1 (P1)P2f2(P2)ddldP 2 f1 (P1 )P2f2(P2)dPldP2 1 + h + 2 P2f2(P2)dP 2 = 0 P2'S1 /S2 which was obtained from equation (7) by substituting for g1'. We obtain a solution S2* - 9481. Finally, we solve for S3 in the first order condition for the three-stage cost function: S2/S3 1 w3 + w2 r p3f3(p3)dp3 + h3 I P3f3(P3)dP3 p3mo p3-S2/S3 s2/s3 + h2 r P3-0 r P2'SI/P3S3 P2f2(p2)p3f3(p3)dP2dP3 + 2/s3 + f3 ^30 rSi /P3 3 -Iw +h f pht'1 (p1)dpl S/3S3pp3S3 r - [ Wl + hl [P(P1)dP1 J J P2=0 Pl=D/P2P3S3 D1i/P2P3S3 R r P1 -0 Pffl(pl)dP1 ] P2f2(P2)P3f3(P3)dP2dP3O0 which was derived by recursively substituting for g2' and then g1l' The solution for S3* is 10,000. Substituting for S* in the (true) total cost function, we obtain a cost of $27,970, given D-7000. 15

We next examine the effect of "improved" yield rate distributions on the total cost of producing the batch. This may be of concern when there are opportunities to purchase new equipment or to make the investments to improve the yield (e.g., process controls) and the justification for the purchase depends, in part, on a reduction of the variable cost per unit. Suppose the LED fabrication facility under consideration has opportunity to purchase die attach equipment which provides an improved yield distribution as depicted in Figure 4. The average yield is the same as for the current equipment, but the variance is reduced. For the new yield distribution, the optimal policy is S1 - 7857, S2 - 9481, S3 - 10054, with a total cost of $27849. With a three-shift, five day per week operation, the annual savings would be over $90,000. If the yield rate in die attach were perfectly deterministic with the same averages as before, we would obtain S1* - 7857, S2* - 9481, S3* - 10116, with a total cost of $27,712. Of the total cost, $20,300 represents the minimum variable production costs necessary to satisfy demand (i.e., in wn - $2.90 multiplied by 7000 units). The remaining $7400 or more is attributable to yield losses and yield variability, i.e., more than $1 per unit on an item whose gross margin before yield-related costs is only $2.39. It is evident that a reduction of the yield variance may make an important contribution to the economic viability of new equipment. FIGURE 4 Observe that finding Sn involves solving a first order condition with n-tuple integrals (n+1 in the case of uncertain demand). The computational complexity of the solution procedure thus increases exponentially with the number of stages. However, for most systems with empirical yield rate probability mass functions with a moderate number of (less than ten) support points, up to 10 stages can conceivably be handled. The solution procedure is also affected by the magnitude of D, and we found this to be much more critical 16

in our test problems with only three stages. If, however, one is willing to sacrifice a little with regard to optimality by considering a limited number of input batch sizes at each stage (e.g., multiples of a dozen or a hundred) rather than all possible integers, computation time can be reduced dramatically. Nevertheless, the test problems in our study were solved very quickly even on a micro-computer. 5.0 SUMMARY AND CONCLUSIONS We have developed an approach for production control in serial production systems in which the yield at each stage may be stochastic. A procedure is developed and is shown to provide optimal solutions for any N-stage system. We also illustrate how the procedure can be used by way of an example using scaled actual data from an LED fabrication facility. The viability of this type of procedure for fairly general yield distributions and the sequential nature of the decision-making procedure indicate that extensions to more complex production environments may be possible. In addition, further research needs to be done to incorporate other realistic factors, such as setup costs, demand uncertainty, possible rework, multiple production batches at a stage, and multiple periods, into the current model. 6.0 ACKNOWLEDGEMENT This work was partially supported by National Science Foundation Grant DMC8504644 to the IUniversity of Michigan and the Stanford Institute for Manufacturing and Automation. The authors are also grateful for the helpful comments of two anonymous referees and an Associate Editor. 17

TABLE 1 COST DATA Variable Production Cost/Unit Inspection Cost/ Unit Total Production and Inspection Cost Per Unit Die Attach Wire Bond Cast and Post Cast 1.40 0.55 0.72 0.05 0.08 0.10 $1.45 $0.63 $0.82 18

SYSTEM: DETAIL: Gc Un 7 Pa 3 2 1 Defective Parts (1-pn)un - - - - - - Figure 1 Serial Production System with Yield Losses 19

< Inspection -Scrap | Passed Inspection Wire Bond Failed Inspection Scrap | Passed Cast, Post Cast Failed Final Scrap Inspection Scrap Passed Mark and Finish Figure 2: LED Display Production Flowchart 20

n L p r o 0.3 b a b 0.2 i! 0.1 i t Y 0 0.4 P r o 0.3 b a b 0.2 i I 0.1 t y 0.- —:.-_..-.:.':';:::'-;'.-:;:.:..::.....:...:..76.80.83.86.90 Yield Rate (a) Die Attach Yield Rate Distribution.93.96 i.-:.....76.78.79.81.83 Yield Rate (b) Wire Bond Yield Rate Distribution.84.86 P r 0 b a b i I i t y 0.4 0.3 0.2 0.1 0 B _:%-.%%-A;.-:0.:-M. i.ss %,, 126.938.867 r.879.891.902.914.9 Yield Rate (c) Casting/Final Test Yield Rate Distribution Figure 3 Yield Rate Distributions 21

0.40 0.35 p 0.30 r o 0.25 b a b 0.20 i 0.15 t Y 0.10 0.05 0 - I.86.90.93 Yield Rate Figure 4 "Improved" Yield Rate Distribution for Die Attach 22

REFERENCES Beebe, J.H., C.S. Beightler, and J.P. Stark (1968), "Stochastic Optimization of Production Planning," Operations Research 16(4), 799-818. Giffler, B. (1960), "Determining an Optimal Reject Allowance," Naval Res. Log. Quarterly 7(2), 201-206. Klein, M. (1966), "Markovian Decision Models for Reject Allowance Problems," Management Science 12(5), 349-358.1 Lee, H.L, and M.J Rosenblatt (1986), "Economic Production Cycles with Imperfect Production Processes," IIE Transactions 18(1), 48-55. Levitan, R.E. (1960), "The Optimum Reject Allowance Problem," Management Science 6(2), 172-186. Porteus, E.L (1986), "Optimal Lot Sizing, Process Quality Improvement, and Setup Cost Reduction," Operations Research 34(1), 137-144. Sepehri, M., E.A. Silver, and C. New (1986), "A Heuristic for Multiple Lot Sizing for an Order Under Variable Yield," IIE Transactions 18(1), 63-69. Wagner, H.M. (1980), "Research Portfolio for Inventory Management and Production Planning Systems," Operations Research 28(3), 445-475. White, L.S. (1967), "Bayes Markovian Decision Models for a Multi-period Reject Allowance Problem," Operations Research 15(5), 857-865. Whybark, D.C. and J.G. Williams (1976), "Material Requirements Planning Systems under Uncertainty," Decision Science 7(4), 595-606. 23

APPENDIX The proofs in the a ndix derive largely from the first order necessary conditions for the one- and n-stage problems: D/u1 1 Wl - h2 - r [ P1fl(Pl)dP l + h1 f Plfl(pl)dp1l 0, 1 = ~P1-D/U (A-1) and Wn - hn+1 + Sn- 1/Un, gn- 1 ( PnUn I PnUn')Pnfn (Pn)dPn Pn 0 1 + f )dn~nnPn - 0; n-(Sn1 nn) Pnfn(Pn- Pn'Sn- 1/un n-2,...,N. (A-2) where n- 1 /Yn+ gn(PnYn+ll PnYn+l) Wn Yn+1 + Pn=O gn-1PnYn+ llPnYn+ ) fn(Pn)dPn 1 + f gn-1 (Sn-1 PnYn+) fn(Pn)dPn' PnSn- /Yn gn(SnlYn+l) = (Wn - hn+l)Sn + hn+lYn+1 Sn- 1/Sn + r-1 (n(PnSnlPnSn)fn(Pn)dPn + I PnOJ Pn=O 1 gn- (Sn- IPnSn)fn(Pn)dPn, Pn=Sn-1/Sn n = 2,...N. 24

Lea 1: Proof: gn(Snlyn+l) - hn+l n-1,..., N. We first note that gn(Snlyn+) - (wn - hn+1)Sn + hn+lYn+ s /s Sn-1/Sn + g n-1 (Pnsn IPnSn)fn(Pn)dPn Pn-O 1 + g n-1 (Sn-I PnSn)f n(Pn)dPn PnSn- 1/Sn It is clear that gn(n+l ) - +1 n - 2,..., N. Moreover, g1 (S1 IY2) - 1 (S1 lY2)/d Y2 = h2 (from equation (5)). Hence, we have, in general, gn(SnaYn+l) ' hn+l LeaFo 2: For all n -_1,...., N, n-l,..., N. a n(SnlSn)/) Sn - hn+1 25

Proof: We have gn(Yn+l n+ l ) WnYn+l Sn- 1/yn+ 1 + gn- (PnYn+l lPnyn+l )fn(Pn)dPn Pn-O Pn'Sn-1 /Yn+1 Differentiating this with respect to Yn+ ' we get, w~ Sn- 1/ + I, gn(Yn+llYn+l) ' Wn + f gn-1(Pnyn+l IPnyn+1 )nfn(Pn)dPn Pn-O 1 + hn ( Pnfn(Pn)dn (A-3) PnSn-1/Yn+l Hence, from equations (7) and (A-3), we have gn (SnlSn) ' hn+1 a We can now use Lemma 2 to establish: Lema 3: For all n - 1,...,N, gn(YnrllYn+1) > O, for Yn+1 > 0. Proof: Differentiating equation (A-3) with respect to Yn+1' we get it, S n-l1/Yn+l. gn(Yn+llYn+l) ' n gn-l(PnYn+llPnYn+l1)Pfn(Pn)dPn Pn=O gn-1 (Sn-1JSn-1) (Sn_1/yn+1 )n(n /Yn+l) 26

+ hn(S 1/Yn3+ )n(Sn /Yn+ ) Sn- /Yn+1 ' r gn-1 (PnYn+1 lPnYn+l)Pnfn(Pn)dPn Pn-O The last equality results from Lemma 2. Now Pn > 0 and fn(Pn) > O, so we need only to establish that g1 (y21y2) > 0 to prove that gn (Yn+1 Yn+1) > O for all n. From equation (5) we have g1(Y21Y2) ' wlY2 + h1 1 r - Pl =D/Y2 D/Y2 (PLY2 - D)fl(Pl)dpl + r F (D - P1Y2)ff(P1)dp1 P1 -O0 1 D/Y2 g;(Y21Y2) - w1 + h1 PIr (P1)dpl - D y P1-D/Y2 P1-O Plfl(P1)dpl (A-4) g(Y2Y2) h1(D2/y23)f1(D/y2) + r(D2/y3)f1(D/y2) > 0 since I > j|hl by assumption. o Finally, we first state and prove a lemma regarding the form of g (O) which is useful in proving the second part of Theorem 1. Lea 4I: For all nl1,..., N, n-1 J n gn(010) - Z [Wn-j n Pn-i+1] - w r i -, - ity i where, for simplicity of presentation, we define the expectation of Pn as Pn ' t Pn-O Pnfn(Pn)dPn and we use the convention b nII 1 if a > b. i-a 27

Proof: We will prove the Lemma by induction. From equation (A-4), for n-1 we have, g;(010) - w - rp, so the Lemma is true for n-1. Suppose the Lemma is true up to n. From equation (A-3), we have 1 n-1 3 n n+1 (Yn+21yn+2=0) Wn1 + [wn-j I Pn-i+l ] I Pi Pn+l n+(Pn+l )dPn+l J j-o i-1 i-1 0 n J n+l - I Wn+l-j i Pn+2-i iw Pi so the Lemma is true for n + 1, and therefore for all n. o 28