OPTIMAL POLICIES FOR A SERIAL PRODUCTION SYSTEM WITH SETUP COSTS AND VARIABLE YIELDS Candace A. Yano Department of Industrial & Operations Engineering The University of Michigan Ann Arbor, Michigan 48109-2117 Technical Report 86-24 June 1986 Revised March 1987

OPTIMAL POLICIES FOR A SERIAL PRODUCTION SYSTEM WITH SETUP COSTS AND VARIABLE YIELDS Candace Arai Yano Department of Industrial and Operations Engineering University of Michigan Ann Arbor, MI 48109-2117 June 1986 Revised March 1987 This research was partially supported by National Science Foundation Grant DMC 85046444.

OPTIMAL POLICIES FOR A SERIAL PRODUCTION SYSTEM WITH SETUP COSTS AND VARIABLE YIELDS ABSTRACT We investigate the problem of finding optimal policies for facilities-inseries production systems in which process yields are variable and there are positive setup costs at one or more stages of production. In addition to setup costs, costs are incurred for each unit of unsatisfied demand and for work-inprocess and finished goods inventory. For one- and two-stage systems, it is shown that the optimal policy has two critical numbers (s and S) at each stage. If the available input quantity is larger than S, the optimal policy is to input S. If it lies between s and S, it is optimal to input the entire quantity. If the available input quantity is less than s, the optimal policy is not to produce at that stage. We also discuss conditions in which the results might be extended to systems with more than two stages.

OPTIMAL POLICIES FOR A SERIAL PRODUCTION SYSTEM WITH SETUP COSTS AND VARIABLE YIELDS 1. INTRODUCTION Recent concern about quality improvement and international competition in the semiconductor industry has led to increasing interest in production control for systems with high yield losses. The difficulty in controlling systems like this is not high average yield loss. Rather, it is the variability of the yield rate (i.e., the ratio of acceptable output to input) which makes scheduling and inventory control difficult. It is important to note that such situations are not peculiar to the semiconductor industry. Many microelectronic assembly operations and chemical processes experience the same types of yield loss problems. Much of the research to date on variable yield has focused in single-item, single-stage systems. Karlin (1958a, b) gives several results for the singleand multi-period versions of the problem when there are no setup costs. In papers by Klein (1966), and White (1967), the concern is one of finding subbatch sizes for an imperfect production process so as to meet a specified production target. Yano (1986b) shows that the form of the optimal policy for periodic review, single stage systems with known demand but without setup costs has an optimal multiplier in each period. The optimal input quantity is equal to demand multiplied by the optimal multiplier. Mazzola, McCoy, and Wagner (1987) develop dynamic programming-based algorithms and EOQ-based heuristics for the single-stage problem with setup costs and show that the heuristics perform well. Sepehri, Silver, and New (1986) develop and test a heuristic for a single-stage situation in which more than once production run can be used to satisfy a single order and each production run incurs a setup cost. The paper also includes a recent review of the literature on single-stage problems. 1

Recent work by Lee and Yano (1985) has shown that for serial production systems with variable yield rates (but no setup costs), the optimal policy has the single critical number form. That is, the optimal policy is to input the critical quantity, Sn to stage n if the output of the preceding stage equals or exceeds this value. Otherwise, the entire output of the preceding stage is sent to stage n. Yano (1986a) extended these results to incorporate uncertain demand. Many serial production systems with batch processing have been designed so that the capacity at each stage, adjusted for (average) yield losses, is approximately equal. Thus, in order to utilize capacity as fully as possible, managers are inclined to avoid processing batches which are much smaller than usual if a batch of "normal" size can be processed relatively soon instead. These managers are behaving as if there were setup costs associated with processing the batch at each stage, where the setup cost reflects the opportunity cost of capacity utilization. In other situations there are real "out-of-pocket" setup costs, which should be reflected in operating policy decisions. We address the problem of determining the optimal production policy for serial production systems with variable yields, deterministic demand, and positive setup costs. The decisions to be made are how much to input to each stage of production. This deals with the short-term problem of coping with the current situation as economically as possible. From a broader perspective, it is also useful to know how best to operate a system so that one can accurately estimate the system-wide effects of reducing setup costs or improving yields. Our analyses make a step toward that end. In the next section we discuss model assumptions and formulate the problem. In the subsequent section we develop the form of the optimal policy for one-and two-stage systems and suggest a solution procedure. We also briefly discuss conditions in which the results can be extended to systems having three or more 2

more stages. Section 4 establishes conditions for existence of finite optimal finite optimal solutions. The approach is extended to the case of random demand in Section 5. Conclusions appear in section 6. 2. PROBLEM DESCRIPTION AND FORMULATION We consider a serial production system in which the yield rate at each stage of production may be stochastic. We assume that these yield rate distributions are mutually independent, continuous, twice-differentiable, and invariant with input batch size. (Generalization to probability mass functions is straightforward). We also assume, without loss of generality, that the yield rates are bounded above by 1. We assume that there is a single known demand or production target for the finished product, and that there is only one opportunity at each stage of production to satisfy that demand. Production is done in a batch-type process at each stage, where inspection begins after the production run is complete. We assume that 100% inspection occurs at each stage and that the inspection processes are perfect. We also assume that defective units are disposed at no additional cost. This is a standard assumption when defective parts are not reparable or are expensive to repair. Costs to be included in the model are a shortage cost per unit of unsatisfied finished product demand, inventory holding costs charged on excess finished product inventory, and on work-in-process inventory which is not input to the succeeding stage, and variable production and inspection costs at each stage. The shortage cost reflects revenue lost if production of the finished product is inadequate. If the product is produced to stock, then the inventory holding costs can be viewed as the cost of holding the items until the next production run. Since we are examining a single-period problem, the inventory holding cost typically would be negative, reflecting the cash inflow due to 3

salvaging non-defective units. Finally, we assume that there is a setup cost at each stage of production, and that production proceeds on a lot-for-lot basis. In other words, there is at most one setup permitted at each stage before the subsequent stage of production is begun. This is typical in serial production systems since making additional production runs at one stage would tend to delay production at downstream stages. The delay could result from setup time as well as processing time. Let N denote the number of stages, and index the stages so that stage N occurs first and stage 1 is done last. Also, let wn variable production and inspection cost per unit at stage n hn = inventory holding cost per unit of excess output at stage n X - = shortage cost per unit of unsatisfied demand 3p = actual yield rate of stage n f (') = density of the yield rate at stage n D = demand or production target In = on-hand inventory at stage n (having completed stage n) Q = input quantity to stage n 6(Q) = 1 if Q > 0 0 otherwise Kn - setup cost at stage n (.)+ s= positive part E(') = expectation Throughout the paper, we assume that (a) hn+l < wn + hn E(Pn), nl1,...,N; and (b) j [wj/i E(Pi)] < jb) j3 i=1 m~~~~~~~L

The first condition states that it is no more expensive to hold an item at stage n+l than to process it and hold the expected output at stage n. Generally, the wn values are much larger than the absolute values of the hn values, so condition (a) is very mild. In fact, it does not exclude negative inventory holding costs, or negative echelon holding costs (i.e., hn - hn+1 < 0). In section 6 we discuss what might be done if this condition does not hold. The second condition states that the expected total variable cost of producing one unit is less than the shortage penalty. This condition essentially ensures that it is profitable to produce the product. This is also a very mild condition. The problem that we investigate is dynamic in the sense that one does not need to decide what to do at stage n until the outcome of stage n+l is known. The dynamic programming formulation below reflects this fact and incorporates it into the decision process. For any initial inventory vector, I, the problem can be formulated as a stochastic dynamic program with recursion equations: C1(y2) = min {wlQl + K1 6(Q1) + hi E(plQi + I1 - D) + O<Q1<Y2 + h2(Y2 - Q1) + t E(D - PlQ1 - I1)+} (2) Cn(yn) = min {wn Qn + Kn 6(Qn) 0<QnYn + 1 + hn+l (Yn+l Qn) + E[Cn-1 (Pn Qn + In) (3) where Yn = Pn Qn + In, n = 2,...,N and Cn(yn+1) = minimum expected cost for stages 1,...,n given available input to stage n is Yn+. 5

3. FORM OF THE OPTIMAL POLICY Clark and Scarf (1960) showed that the form of the optimal policy for a serial system with stochastic demand for the finished product (only) and positive setup costs, is of the (s,S) type at each stage. We investigate whether the optimal policy for the system under study has a similar form. We initially consider one-stage systems and then extend the results to twostage systems. Finally, we discuss briefly conditions in which the results might be extended to multi-stage systems. 3.1 One-Stage System In this section we prove that the optimal policy for a one-stage system has two critical numbers. We first formulate the problem. We then investigate how C,(y2) varies as a function of Y2. To do so, we must find the optimal value of Q, for each value of Y2. This development permits us to find the breakeven point between producing and not producing for various values of Y2, which leads to a characterization of the optimal policy. For the single-stage system, our objective would be to minimize wl Q1 + K1 6(Q1) + hi E(p1 Q1 + I1 - D)+ 0 < Q1 < Y2 + h2(Y2 - Q1) +, E(D - p, Q1 - I1)+ (4) For notational simplicity, let D' = D - I, (i.e., net demand). Clearly, if D' < 0, Q1 = 0 is optimal since h2 < wI + h1 E(pl). For the special case of Q1 = 0, the cost is - hi min(O, D') + h2y2 + r(D')+ (5) The first term in the expression above simply accounts for inventory holding costs of finished product units in excess of the demand. Note that (5) is a linear function of Y2. 6

In what follows, we will assume that D' > O. We first derive the unconstrained optimal solution for the problem, assuming that Q. > O. We can minimize the one-stage objective function by finding the target input quantity, S1, satisfying D'/S1 r plf,(pl)dpl = [hhE(pl) + w1-h2]/(7+hl) (6) Jo Equation (6) is a simplified form of the first order necessary condition. We note that here, and throughout the paper, we use the fact that Pnfn(Pn)dpn = E(Pn) - I nfn(Pn)dPn anJ~~~~~ JO an where possible to simplify mathematical expressions. It is easily shown that the objective function in (4) is convex in Q1 so satisfaction of the first order condition is sufficient for optimality. Let ac = D'/Si. Then Si = D'/a, is the optimal input quantity provided S. units are available, and provided Q. > 0 is optimal. Observe that it is not necessary to find the optimal value of Q. for each possible D'. One only needs to find the critical ratio al = D'/S1 which satisfies equation (6). To establish the form of the optimal policy, we need to ascertain how the minimum cost of the system changes with Y2 when Q. > O. For Y2 > S., by substituting (6) into (2) we can establish that for Y2 > S. (i.e., when there is enough input material available to input the optimal target amount), C,(y2) = (i + h,)D' f f,(p,)dpl + h2y2 + K1 - hD' (7) Jo 7

To determine whether or not to produce when Y2 > S1, we must compare (5) with (7). If (5) is smaller, it is better not to produce. Otherwise, it is optimal to input a quantity equal to S1. Thus, the optimal policy is S = D'/a, if f f1(pI)dp, > K1 / (O + h,)D' Jal Q1 = T0 otherwise This is derived by comparing equations (5) and (7) to find the breakeven point between ordering and not ordering. The next question to be answered is what should be done if Y2 < S, (i.e, when the unconstrained solution cannot be achieved). Let us assume for the moment it is optimal for Q1 to be greater than zero. We mentioned earlier that the objective function for the single-stage problem is convex in Q1. Thus, if Q, is constrained to be positive but less than or equal to Y2 < S1, the constrained optimal solution is to input Q1 = Y2 (i.e., as much as possible). Therefore, assuming Q1 > 0 is optimal, for Y2 < S, we have Q1 = Y2 and C,(y2) = wlY2 + K1 + hl [Y2 E(p,) - D'] D /Y2 -(r + hi)y2 r PlfI(P1)dpl Jo D'/y2 +(a + hI)D' r fi(p1)dPl (8) Jo This is derived by substituting Q. = Y2 in (2) and combining like terms. [Note that we have represented limits of integrals (i.e., yield rates) in their analytic forms (e.g., D'/y2), realizing that the resulting values may be less than zero'or greater than one. Since f,(pn) = 0 for these values of pn there are no practical or theoretical difficulties associated with this. In all cases, the meaning should be clear from the context, and appropriate 8

modifications to accommodate these situations are straightforward.] By comparing (8) with (5) to find the conditions under which producing (or not producing) is less expensive, we find that if Y2 < Si, the optimal policy is Y2 y if (i + hI)D' > (wl + hi E(pl) - h2)Y2 + K1 D'/y2 + (t + hl)D' ( fI(pj)dpI Q, = \ Jo D'/y2 - (ir + hi)y2 r Plf1(pI)dpi Jo 0 otherwise If y2 < D', the latter policy can be simplified to Y2 if Y2 > KI/[i E(p1) + h2 - wI] 0 otherwise It is important to note that the form of the optimal policy can be determined without knowledge of Y2, although the optimal solution cannot be determined until Y2 is known. For simplicity, let us refer to rl f1(p1)dpl > KI/(i + hl)D' as condition I, (it + hI)D' > (wl + hi E(pl) - h2)y2 + K1 D'/y2 + (ir + hI)D' I f (pi)dpI Jo D'/y, - (ir + hi)Y2 f Plfl(P1)dp1 lo as condition II, and 9

Y2 > K1/[r E(pl) + h2 - wl] as condition III. Each of these is a condition for Q1 > 0 to be optimal. More specifically, if y2 > Si and condition I holds, it is optimal to input S1 units. If D' < Y2 < Si and condition II holds, it is optimal to input Y2 units. If Y2 < D' and condition III holds, it is also optimal to input Y2 units. If none of the above holds, it is optimal not to produce. Before continuing to a two-stage system, it would be useful to establish a more general form of the optimal policy. In particular, for fixed D', we might expect the form of the optimal policy to be 0 if Y2 < si (for some s1) (9a) Q = - Y2 if sI < Y2 < S1 (9b) S if Y2 > S1 (9c) where sI = inf {Y2 | Y2 satisfies condition II}. In fact, if the optimal policy is more complex than this, it could be difficult to extend the approach to multiple stages. Clearly, if Y2 < D' and condition III holds, the form of the optimal policy satisfies (9a). To show that it is also true for D' < Y2 < si we need to establish that the right hand side of condition II is monotonically nonincreasing in y2. If this is true, then either (i) for Y2 sufficiently small, condition II will not be satisfied, or (ii) condition II is satisfied for all Y2 > 0 (in which case sI - 0 and it is always optimal to produce). It can be shown that the partial derivative with respect to Y2 of the right hand side of condition II is D'/y2 [w, + h1 E(pl) - h2] - (ir + hl) f Plfl(p1)dpl (10) Jo 10

Using equation (6) and the fact that Y2 < SI, the partial derivative can be shown to be strictly negative. Thus, the optimal policy has the form of (9a). We next need to show that the policy has the form of (9b). Observe that if condition III is satisfied for Y2 = D', then condition II (which is equivalent to condition III at Y2 = D') is also satisfied. Since the right hand side of condition II is monotonically decreasing in Y2, the condition will be satisfied for D' < y2 < SI. If condition III is not satisfied by Y2 = D', but condition II is satisfied by some sI > D', monotonicity of the right hand side of condition II guarantees that the policy has the form of (9b). The optimal policy clearly has the form of (9c) by the convexity of (4). The only thing remaining to be shown is that sI < S1. This follows directly from the fact that conditions I and II are equivalent when Y2 = Si and the fact that the right hand side of condition II is monotonically decreasing in y2. We have thus proved the following theorem: Theorem 1: For a one-stage system with variable yields and positive setup cost, the form of the optimal policy is ~ if Y2 < sI Ql = Y2 if sI < Y2 < S1 S, if Y2 > S1 where s, = inf { y2 | Y2 satisfies condition II}, and SI satisfies (6). The same result can be shown diagrammatically. Recall that the expected cost function for Q1 = 0 is linear in Y2, while the expected cost function for Q1 > 0 is convex in Q1. Note also that for Y2 > S,, the expected cost function (see equation (7)) is linear in y2. Thus, the relevant expected cost functions are like those in Figures 1 and 2 for the cases of h2 > 0 and h2 < 0, respectively. 11

Expected Costs CostforQ1 =0 Cost for Qi =>0 I\ ~~~~~~~~~Cost for Q 1 > I I sI 51 y2 Figure 1 Expected Costs at Stage 1 when h2 > (shown by solid line) 12

Expected Costs K1 \\..Cost for Q1 =0 Cost for Q1 )0 Si Y2 Figure 2 Expected Costs at Stage 1 when h2<0 (shown by solid line) 13

3.2 Two-Stage System In this section we prove that under certain conditions on costs and the yield rate distributions, the optimal policy at stage 2 has the (s,S) form. We show that (i) the two-stage cost for Q2 = 0 is linearly increasing in y3, and (ii) the two-stage cost function is convex in Q2 for Q2 > O. Then, by examining breakeven points between producing and not producing, we show that for n = 1, 2 the optimal policy has the stated form. If Si = 0 then Q2 = 0 is optimal provided hn+1 < wn +hn E(Pn), n = 1, 2. Suppose Si > O. We have C2(y3) = min {w2 Q2 + K2 6(Q2) + h3(y3 - Q2) 3<Q,2Y3 - EECC(P2Q2+I2)]} Note that the expression in braces is linearly increasing in y3. This demonstrates (i) above. Since we will need to consider C1(y2) over various ranges of Y2 values, for notational simplicity, let us define f C1(y) for Y2 < si 0 otherwise *1(Y2) Cit(Y2)for s1 < Y2 < Sl 0O otherwise Also, for simplicity, let Y2(y3) denote the two-stage cost function assuming that Q2 > O. That is, Y2(y3) = w2 Q2 + K2 + h3(y3 - Q2) + E[C(P2Q2+I2)]} (11) 14

We first need to understand characteristics of the expectation term in (11) before we can proceed further. In the Appendix we show that E[C1(p2Q2+I2)] is convex in Q2 under certain conditions on costs and the yield rate distribution at stage 1. This permits us to establish that Y2(y3) is convex in Q2 for Q2 > 0, since the remaining terms in C2(y3) are either linear in Q2 or constant. If Q2 > 0 is optimal then the target input quantity to stage n is the value of S2 satisfying the first order necessary condition. We now have established the convexity of Y2(Y3) in Q2 for Q2 > 0 and the linearity (in Y2) of the two-stage objective function when Q2 = O. We now need to investigate the breakpoints between ordering and not ordering. We will consider y3 > S2, S2 < y3 < S2, and y3 > S2 in turn. Consider the case of y3 > S2. Q2 = S2 is optimal if h3 y3 + C1(I2) > w2S2 + K2 + h3(y3-S2) + E[Cl(p2S2+I2)] or Cl(I2) > (w2-h3)S2 + K2 + E[Ci(p2S2+I2)]. This simply compares the expected cost if Q2 = 0 with the expected cost if Q2 = S2. Observe that satisfaction of this condition depends only upon 12 and S2 and not on y3 (except to the extent that y3 > S2). If the condition is not satisfied, Q2 = 0 is optimal. On the other hand, if y3 < S2, then Q2 = Y3 is optimal if h3y3 + C1(I2) > w2y3 + K2 + E[CI(p2y3+I2)] (12a) or C1(I2) > (w2-h3)y3 + K2 + E [C1(p2y3+I2)] (12b) Otherwise, it is optimal not to produce. We have already shown that the last term on the right hand side of (12a) is convex with a minimum at S2; thus, it is convex decreasing for y3 < S2. Note that h3y3 is linearly decreasing in y3 if h3 > 0 and increasing in y3 if h3 < O. Thus, the entire right hand side of (12b) is a convex function of y3, and s2 is the breakeven point between 15

producing and not producing. The proof of the form of the optimal policy is similar to that given for the one-stage problem. The optimal policy has two critical numbers at each stage, s2 and Sz. A solution procedure follows directly from the dynamic programming formulation. One solves successively for Sn and sn, n = 1, 2. The results above simply limit the search for the critical numbers. 3.3 Extension to Three or More Stages It may be possible to extend these results to systems with more than two stages. The main difficulty in proving that the result holds in general is that for three or more stages, the cost function when Qn > 0 may not be convex. Indeed, it is possible to show (details are omitted here) that as Qn increases, the n-stage cost function is linearly increasing (decreasing) over [0, snl-In] if hn is positive (negative). It is also strictly concave for [sn_ —InSn1In] if hn > 0 or monotonically decreasing over the same domain if hn < 0. Finally, it can be shown that the function is convex increasing for Qn sufficiently large. The shape of the function in the interval from Snl-In to the "sufficiently large" Qn is difficult to specify. Thus, the n-stage cost function might be convex, or concave-convex (i.e, concave for small values of Qn and becoming convex for sufficiently large values, with one inflection point between the concave and convex portions of the function), or it may have multiple local optima in [Snl-In, a). If the n-stage cost function is convex or concave-convex, and if the cost function for Qn = 0 intersects this function in such a way that E{Cn(pnQn+In)} remains convex or concave-convex, then it is possible that the (s,S) type of policy is optimal at all stages. It appears, however, that strong conditions on inventory holding costs and on the yield rate distributions may be required for 16

this. Further research is needed-to accomplish this extension. Next we discuss conditions in which the critical numbers are finite. 4. CONDITIONS FOR FINITENESS OF THE CRITICAL NUMBERS To ensure that Sn is finite, certain conditions on costs are needed. We need (sn-l-In)/Sn n(Yn+l) =wn hn+1 + n Pn nn-l(PnSn+In) fn(Pn) dPn i+ Pn Wn-l(PnSn+In) fn(Pn) dPn (SnlIn)/Sn to be greater than or equal to zero for Sn sufficiently large (but finite). We show that the condition hn+1 < wn + hnE(Pn) is sufficient to guarantee finite Sn. Observe that the sum of the last three terms is the partial derivative of E[Cn_1(PnQn + In)] with respect to Qn and evaluated at Sn. It is thus nondecreasing with Sn. We next show that it eventually becomes larger than - wn + hn+1 It can be shown that t-1 (PnSn+In) = hn' (Recall that *(') represents the portion of the cost function where there is more than enough to satisfy the target input quantity. Thus, the marginal cost of a unit of available input is h.) Therefore, as Sn increases, the last term asymptotically approaches hnE(Pn) from below and the third and fourth terms decline in value (eventually to zero). Since - wn + hn+1 < hnE(Pn) by assumption, Y(yn+1) asymptotically approaches a non-negative value from below. Thus, the first order condition is satisfied by some finite value of Sn. 17

There are two situations that we need to consider with regard to sn. The first occurs where the cost of producing and the cost of not producing have a point of intersection at sn < Sn. In this case sn < X since Sn < A. The second case occurs when it is always cheaper to produce than not to produce. In this case, we can set sn=0, and identify this case by the fact that lim Cn(Qn) < Cn(0). Qn —>O 5. SYSTEMS WITH RANDOM DEMAND We would like to establish that the form of the optimal policy for systems with random demand is the same as for systems with deterministic demand. To do so, we only need to show that the respective cost functions at stage 1 have the same fundamental properties. The formulation of the single-stage problem is the same as given in (4). Let fD(') denote the density of net demand and FD(') denote the corresponding cumulative distribution. If D - I, < 0 with probability 1, then there is no need to produce. Assume that FD(O) < 1. Suppose we were to choose Q, = 0. The expected cost would be h2y2 + I E(D)' - hi E[min(0, D)] (13) If Q, > 0, we can minimize costs by finding Si satisfying the first order necessary condition co 1 w1 - h2 + hi f f pIf1(p,)fD(D)dpdD JD —= Jpi-D/S1 D/SI - x r f Pif (Pi)fD(D)dpIdD = 0 JD=O Jp,1= The second derivative with respect to Q1 is 18

Qi [(r + h,)/Q ] f D2fl(D/Ql)fD(D)dD > 0 JD=O so the one-stage cost function is convex in Q1. Thus, if Y2 < S1, one would like to input as much as possible, provided the expected cost evaluated at Y2, i.e., 1 w1Y2 + hi f [ (PrY2 - D)fi(pi)fD(D)dpldD JD=-OO JpD/S, X= D/S1 + [ [f (D - py2)fl(pl)fD(D)dpdD + K1 (14) JD=O JP1i= is less than (13). Let sl denote the value which equates the two expressions. The optimal policy is 0 if y, < s, Q, 2= Y2 if s1 < Y2 < Si Si if Y2 > S1 The proof again parallels that given in section 3.1. This has the same form as the case of deterministic demand. As in the case of deterministic demand, certain conditions on costs and the yield rate distributions (given in the Appendix) are needed to ensure that the two-stage cost function is convex for Q2 > O. Under these conditions, we have the following theorem: Theorem 2: The optimal policy for a one- or two-stage serial system with variable yields, positive setup costs, and either deterministic or random demand, has the form 0 if Yn+l < Sn Qn Yn+l if s < Yn+1 < Sn Sn if Yn+l > Sn 19

6. CONCLUSIONS We have developed a model of a serial production system with variable yields and positive setup costs. Variable production costs and inventory holding costs are also considered in the model. We have shown that for one- and two-stage systems, under certain conditions on the cost structure and the yield rate distributions, the form of the optimal policy is 0 for Yn+l < Sn Qn Yn+1 for sn < Yn+l < Sn Sn for Sn < Yn+1 where Qn is the optimal input quantity, Yn+l is the available input for stage n, and sn and Sn are two critical numbers with sn < Sn. A solution procedure is proposed in which one successively solves for Sn and sn for n = 1, 2. One area for future research is to determine whether the results generalize to more general conditions on costs. There are two specific conditions which might be relaxed. We required that it be less expensive to hold a unit in inventory at a stage rather than to process it and to hold the expected output at the following stage. If this condition is not satisfied, it is relatively expensive to hold inventory at stage n+1, and it may be desirable to collapse stages n and n+l into one stage if the setup cost at stage n is sufficiently small. Thus, even if the condition is not satisfied, it may be possible to construct an equivalent system in which the condition is satisfied by all remaining stages. The various cost functions are not as well behaved as when then condition is satisfied, however, so procedures to find optimal values must be modified to accommodate these situations. The existence of setup costs may make such a collapsed policy suboptimal in some instances, so further research is needed to find conditions in which collapsing is either optimal or near optimal. 20

One other sufficient condition on costs and the yield rate distribution for stage 1 was given in the Appendix for the (s,S) policy to apply to stage 2. It is likely that less stringent conditions are required for optimality of an (s,S) policy and future research may bear out this conjecture. We also described briefly how the results might be extended to multiple stages if further research can prove out certain characteristics of the n-stage cost functions. Further research is also needed to analyze and develop solution procedures for multi-period versions of this problem, and to incorporate other properties of real production systems, such as multiple batches at each stage of production, rework, and yield rate distributions which vary with the batch size. 21

REFERENCES Clark, A.J. and H. Scarf (1960), "Optimal Policies for a Multi-Echelon Inventory Problem," Management Science 6(4), 475-490. Karlin, S. (1958a), "One Stage Models with Uncertainty," in Studies in the Mathematical Theory of Inventory and Production, K.J. Arrow, S. Karlin, and H.E. Scarf, Eds.,Stanford University Press, Stanford, California. Karlin, S. (1958b), "Steady-State Solutions," in Studies in the Mathematical Theory of Inventory and Production, K.J. Arrow, S. Karlin, and H.E. Scarf, Eds.,Stanford University Press, Stanford, California. Klein, M. (1966), "Markovian Decision Models for Reject Allowance Problems," Management Science 12(5), 349-358. Lee, L. and C.A. Yano (1985), "Production Control in Multi-Stage Systems with Variable Yield Losses," Operations Research (to appear). Mazzola, J.B., W.F. McCoy, and H.M. Wagner (1987), "Algorithms and Heuristics for Variable-Yield Lot Sizing," Naval Research Logistics 34(1), 67-86. 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. White, L.S. (1967), "Bayes Markovian Decision Models for a Multi-Period Reject Allowance Problem," Operations Research 15(5), 857-865. Yano, C.A. (1986), "Controlling Production in Serial Systems with Uncertain Demand and Variable Yields," Technical Report 86-5, Department of Industrial and Operations Engineering, University of Michigan. Yano, C.A. (1986), "Optimal Finite and Infinte Horizon Policies for Single-Stage Production Systems with Variable Yields," Technical Report 86-32, Department of Industrial and Operations Engineering, University of Michigan. 22

APPENDIX In this appendix, we show that the objective function for the two-stage problem is convex in Q2 under certain conditions on costs and yield rate distributions. To do so, we first show that E[CC(p2Q2+I2)] is convex in Q2. E[CC(p2Q2+I2)] = (s1-I2)/Q2 f n (p2Q2+I2) f2(P2) dP2 Jo (Sl-I2)/Q2 + f 1(P2Q2+I2) f2(P2) dP2 J (s1-I2)/Q2 (Sl-l2)/Q2 + I 91(P2Q2+I2) f2(P2)dP2 (A-l) J(S-I,2)/Q2 where li(Y2) = h2y2 + irD' = h2(P2Q2 + 12) + rD'. -4(Y2) = wl (P2Q2+I2) + hl[(P2Q2+I2)E(Pl)-D'] D'/(p2Q2+I2) - (rh+hl) (p2Q2+I2) I PlfI(Pi)dP1 Jo D'/(P2Q2+I2) + (wr+hi) D' f fl(pl)dpl + KI fl(p1)dp1 + K1 Jo *1(Y2) = (ir+h,)D' f fl(pl)dp1 + h2 (P2Q2+I2) + K1 (A-2) Jo The last three expressions were obtained by replacing Q1 in the cost function by its optimal value. 23

We also have 3 E[C1(P2Q2+I2)]} /d Q2 (sl-I2)/Q2 r P2 nl(P2Q2+I2) f2(P2)dP2 Jo - n1(s1)f2 ((s1-2)/Q2) * ((s1-2)/Q2 2) (SI-I2)/Q2 I + P2 I1(P2Q2+I2) f2(P2)dP2 J (sl-I2)/Q2 -,(sl)f2 ((S1-I2)/Q2) * ((S1-I2)/Q22) + <1(sl1)f2 ((S1-l2)/Q2) * ((S -I2)/Q22) 1 + f P2W1'(p2Q2+I2) f2(P2)dP2 J (S1-I2)/Q2 + ll(Sl)f2 ((Si-l2)/Q2) * ((S-I2)/Q22) But O(S,) = I(S1), and n(s1) = p(s() by definition, so only the terms with integrals remain. We also have (s l-2)/Q2'{E[C(p2Q2+I2]} /dQ22 = r P2 n'l(P2Q2+I2) f2(P2)dP2 Jo - (s2-I2)2 nl(s,) f2 ((s1-I2)/Q2)/Q! (Si-I2)/Q2, + f P2 1)(P2Q2+I2) f2(P2)dP2 JI J(s1-I,2)/Q2 - (S1-I,)2 * (l(Si) f2 ((S1-I2)/Q2)/Q2 + (s,-I2)2 * <'(s1) f2 ((s,-I2)/Q2)/Q~ + 1 p2 P'(P2Q2+I2) f2 (P2)dP2 J(S1-I2)/Q2 + (S1-I2)2 pI(S1) f2 ((S1-I2)/Q2)/Q2 (A-3) The first term vanishes for n = 2 since n1 is a linear function of Q2. Since Ci is minimized at S.,'i(Sl) = 4'(Sl) = 0. Hence, the fourth and seventh terms 24

cancel. Also if ln'(s,) >'((s'), the sum of the first and fourth terms is nonnegative. We next derive conditions in which this is true. Now s, is defined as the value which satisfies (t + hl) D' = [wI + hlE(p1)] Si + K1 D'/sl + (i + hi) D' f f1(p1)dpI Jo D'/sl - (t + hi) Si r P1 fI(pI)dpI Jo Rearranging terms, we have 1 D'/sl (i + hi) D' I fI(pI)dpI = si [w1 + hlE(pl) - (iT + hi) r pI f,(p,)dp], JD'/s, Jo + KI But the term in brackets is j(s,), so we have 1 cl(si) = {(t + hi) D' I fl(pl)dp1 -K1i/S1 JD'/s, Now nl(s,) = h2, so 4'(Sl) is greater if 1 (r + hi) f f,(pI)dpi - KI > h2 sI (A-4) JD'/s, In addition to the condition above, for (A-3) to be positive, we also require that'1 > 0 and i, > O. It can be shown (using (8) evaluated at Y2 = P2Q2 + I2) that )'(Y2) = (T+hl)P2D'2 fl(D'/(P2Q2+I2))/(p2Q2+I2)2 > 0 It is obvious from equation (A-2) that 4'~ = O. Since w2 Q2 and h3(y3-Q2) are both linear in Q2, Y2(Y3) is convex in Q2. 25

For the case of random demand, the condition in (A-3) should be replaced by 0o 1 (r + hl) f I D fi(pi)fD(D)dpdD - K, > h2 sI JD=O Jp1=D/s, It is also easy to show that (f and ~' are non-negative. 26

UNIVERSITY OF MICHIGAN 3 9015 03994 8156