PRODUCTION AND PROCUREMENT POLICIES FOR AN ASSEMBLY SYSTEM WITH RANDOM-YIELD COMPONENTS Candace Arai Yano Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, MI 48109-2117 Thomas J. Chan Department of Computer Science Southern Methodist University Dallas, TX Technical Report 86-6 Revised June 1989

PRODUCTION AND PROCUREMENT POLICIES FOR AN ASSEMBLY SYSTEM WITH RANDOM-YIELD COMPONENTS ABSTRACT We address the problem of determining production or procurement quantities for assembly components with random yields. Some properties of the optimal solution are derived, and these properties are used to develop a parametric heuristic procedure. The parameter to be varied is an adjusted shortage cost, and is used in a newboy-type model. Computational results show that a limited search using this procedure provides a solution that is very close to optimal. Key words: Inventory/Production —Reject Allowances

PRODUCTION AND PROCUREMENT POLICIES FOR AN ASSEMBLY SYSTEM WITH RANDOM-YIELD COMPONENTS 1. INTRODUCTION Concern about managing production systems with random (or variable) yields has increased because of competitive pressures and the "just-in-time" and "zero-inventory" crusades. Random procurement yields arise when some delivered parts do not meet specifications. Random production yields arise when the production process is intrinsically variable and the output cannot be predicted accurately from the input. Prime examples of this phenomenon are semiconductor fabrication and various chemical processes. Random yields are a particular problem in assembly systems because the number of units that can be assembled is constrained by the inventory level of the component with the fewest good units. Yield variability may also exist in the assembly process itself, even if the components are not defective or out of tolerance. This variability arises when the assembled unit doesn't work because of incompatibility of components. A classic example involves a nut and bolt, both of which are in tolerance. The tolerances have been set so that the parts will fit nearly all, but not 100% of the time. In this case, a human and some "robot" assemblers will simply select another nut or bolt and resolve the problem. In other cases, such as electronic assembly, a defective component may be impossible to detect until a module or an entire unit is assembled. Thus, the only alternative is to assemble the unit and wait to see what happens. High "infant mortality" of components also contributes to the yield variability problem in these industries. The problem here is not exclusively one of better quality control or of "doing it right the first time." Two important questions are: How should we operate under current conditions to minimize cost? What are the benefits of reducing yield variability? Reduction of yield variability might be achieved through the selection of a different supplier, redesign 1

of a part, recalibration of a process, or a different specification of tolerances for parts to be assembled. In most cases, such decisions result in real costs (since not all "quality" is free), and quantification of benefits is extremely important in such decision making. Most of the research on uncertain production yields in the 1960's focused on single stage systems (e.g., Giffler 1960, Levitan 1960, Klein 1966, and White 1967). In simulation studies, Whybark and Williams (1976) found that safety stock is more efficient and effective than safety time when quantities are uncertain. Recently, Mazzola, et al. (1987) developed very good heuristic procedures for single-stage systems with deterministic demand. Gerchak et al. (1988) have derived characteristics of optimal policies for single-stage systems with random demands and yields. Yano (1987a) addressed a problem with a single stage and multiple products. The reader is referred to Mazzola, et al. for an excellent review of related papers on single-stage systems. Wagner (1980) pointed out a need for methods to handle stochastic aspects of multi-stage systems. Relatively little research has been done on multi-stage systems with stochastic yields. Some recent work has been done on serial systems (e.g., Lee and Yano 1988) and on multi-location systems (Karmarkar and Lin 1986). For a review of lot-sizing in the presence of random yields, see Yano and Lee (1989). We investigate the problem of simultaneously determining procurement or production quantities for assembly parts with variable yield rates in a make-to-plan environment. Lee (1987) addresses a problem similar to ours, but permits production or procurement decisions to be made sequentially rather than simultaneously. Singh et al. (1988) and Yao (1988) consider assembly scenarios, but use simpler objective functions that are not cost-based. Before describing the model and its underlying assumptions, we first provide a brief sketch of the motivation for the research. 2

2. MOTIVATION FOR THE RESEARCH The system that motivated this research produces a limited product line, but the products are similar enough for the system to be modeled as having one finished product. The electronic parts are substantially the same, but some of the mechanical parts and housing differ from model to model. Assembly proceeds in several stages, with one to several components added at each stage. There is a total of n different components. However, because the unit is not operational (and therefore critical functional tests cannot be performed) until nearly all of the components are assembled, it is practical to model the system as if it involved a single assembly operation with n components. Such a system is diagrammed in Figure 1 for the case of zero initial inventory, where n+1 is the index of the finished product. FIGURE 1 Components are procured from external suppliers and are 100% inspected upon arrival. The company has made the decision to do this because of the cost of testing, assembling, and reassembling a unit with a defective part. Upon completion of assembly, the assembled unit is tested, and if operational, is "burned in" to eliminate infant mortality problems prior to shipment. If a unit is not operational initially or does not pass "burn in," it is reworked to repair assembly connections or to replace defective parts. The firm produces to plan and a production target is specified for each time period. The production target is based upon the assembly capacity of the company. The primary problem is one of coordinating purchase quantities of the components so that an appropriate number of "kits" of parts is available for assembly. A kit is a non-defective set of all components required for a unit of the finished product. 3

3. MODEL ASSUMPTIONS AND FORMULATION The actual problem described in the previous section is quite complex. It involves multiple decision points, components with different procurement leadtimes, and random assembly yields due to a combination of assembly errors, defective parts not identified during inspection, yield losses during burn-in, and rework. We take a first step toward solving this problem by considering a simplified version with only one decision point (one period), zero procurement leadtimes, no initial inventory, and deterministic assembly yields. Our goal is to develop an understanding of how the production or procurement quantities should be coordinated to achieve relatively balanced inventories of the components. If we can find a simple way to achieve this coordination, it will be easier to work toward solving the real problem. For our simplified problem, let us define a period to be one production or procurement cycle. The decisions are the purchase or production input quantity for component i, i = 1,...,N. The objective is to minimize the sum of expected inventory holding costs associated with unassembled (or unkitted) components, excess kit inventory, and expected shortage costs due to shortfalls from the production target. By unkitted parts, we mean units of components for which a full set of mates is not available. Procurement or production costs per unit are not included because, on the average, one must eventually incur the expected variable costs to satisfy the production targets. Costs incurred because of timing differences (i.e., discounting of costs) are incorporated into the inventory holding and shortage costs. The inventory holding cost represents the cost of holding a unit for one period, which includes the opportunity cost of ordering a unit earlier than necessary plus variable costs of storage, etc. We assume that all shortfalls from the production target can be satisfied by the subsequent batch (which is true in most situations), so that per unit and per unit per period shortage costs are equivalent. In the case of the company described earlier, the shortage 4

cost might represent the opportunity loss of shipping the unit in the next period (i.e., from the next batch) rather than from the current one. We assume that the distributions of the yield rates (fraction good) are independent of the batch size, mutually independent, continuous, and differentiable, with endpoints between zero and one. The analyses can be extended easily to discrete yield distributions and to those having finite upper limits greater than one. Yield losses have been modeled principally in two different ways in the literature. In one approach the production of good parts (or acceptance of parts) is viewed as a Bernoulli process and the yield quantity from any batch is therefore a binomial random variable. Our experience suggests that the production yield quantity is often not represented very accurately by the binomial distribution. In many situations the yields have much smaller domains of support (i.e., smaller ranges of yield rates) than would be suggested by the binomial, and the distributions are relatively stable over wide ranges of batch sizes. In these instances, it might be more appropriate to model the yield rate distribution as being independent of the batch size. This is the approach that we use here. For simplicity, we assume that the finished product requires one unit of each component. If a larger quantity is required, for practical purposes, variables can be redefined and costs can be rescaled to treat each "package" of components as a unit, although this is clearly an approximation. The following notation is used throughout the paper: ui = units of component i procured or processed, i = 1 to n; u = vector of uis; Pi = yield rate for component i (random variable); Pi = actual yield rate for component i, where 0 < pi < 1; fi (~) = density of the yield rate for component i Fi (e) = cumulative distribution of the yield rate for component i; hi = holding cost per unit of component i; xt = shortage cost per unit of finished product; 5

Yi = Piui = number of acceptable units of component i (random variable); i = Piui = actual number of acceptable units of component i; Q = min {Yi} = quantity of kits available for assembly (random variable); and i i We first establish some identities and define some functions which simplify modeling of the problem. Suppose there is a target value, S, of kits to be available for assembly. The probability that at least S units of component i will be available given ui, is: 1 - Fi [ S /ui] and we have P[Q>S]= 1 - Fj [ S /uj]}. Thus, the distribution of kits available for assembly given u is G(qlu)=1-n- { 1-Fj[q/uj] }. Since the Fis are assumed to be continous and twice differentiable, G is also. For notational simplicity, in the following discussion, we also define: Gi(qlu)=l- { 1 - Fj[q-/uj]} jfi G'(qlu)=aG(qlu)/aq Gi'(q I u )=Gi(q I u)/ a q Observe that Gi is simply G with the ith term of the product removed. 6

We can now formulate the problem as: Ui 1 minimize hi J J (piui-q) fi(Pi) Gi'(ql u ) d dq i q=O Pi = q/ui 00 +1 hi I (q-S) G'(ql u ) dq i q=S S + 7t (S-q) G'(qlu )dq (1) q=0 The first sum represents the expected inventory holding costs of unkitted components. The second term represents the expected inventory holding costs of kitted but unassembled components. The third term represents expected shortage costs given a production requirement of S units. 4. PROPERTIES OF THE OPTIMAL SOLUTION To develop some insight into properties of optimal solutions, we first examine the twocomponent problem. For this case, the problem can be formulated as 1 P u1/U2 min z= hI If (plU - P2u2) f2(P2) fl(P1) dP2 dP Pl= 0 P2= 0 1 P2U2/U1 + h2 J f (P2U2- p1u1) fl(P1) f2(P2) dp1 dP2 P2=0 Pi= 1 P 1U /U2 + (hl + h2) [ (P2U2 - S) f2(P2) fl(P1) dP2 Pl=S/ui p2=S/u2 dpl 1 P2U2/UI + I J (PlUl - S) fl(Pl) f2(p2) dpl dp2] P2=S/u2 Pl=S/ul 7

S/u2 P2U2/U1 + t { I (S- Pul)fl(Pl)f2(p2)dPl dP2 P2=0 Pl=0 S/u1 PlU1/U2 + I I (S- P2u2)f2(P2)fl(Pl)dP2 dp1 P1= 0 P2= 0 S/u2 + [1- F1 (S/Ul)] f (S- P2u2)f2(p2)dp2 0 S/u1 + [1-F2 (S/u2)] (S- PUl)fl(Pl)dpi} 0 Note that we have not included variable production costs in the formulation. The reason for this is that both the his and x represent penalty costs, analogous to overage and shortage costs in the newsboy model. More specifically, define it' = loss of revenue plus goodwill for a unit of unsatisfied demand, Ci = unit production cost, and hi' = cash outflow for each unit of component i remaining. Then x = tn' - Ci and hi = Ci + hi'. Our primary reason for using x and hi rather than nI', ci, and hi was to simplify computations. After a considerable amount of algebra and a change of variable, we obtain S/ui z/aui =- (r + hl + h2){ [1 - F2 (S/u2)] f P fl(pl) dp 0 S/u2 p2u2/ul + I I Plfl(Pl)f2(P2)dpldp2} P2=0 pi= 0 + hlE(P1) 1 + 2[(h1 + h2)ul/u2] f p1 (P1 - S/ui) f2 (plul/U2)fl(p1) dpl. S/ul 8

The expression for az/au2 can be obtained by reversing the subscripts. Unfortunately, it is not possible to show in general that the objective function is jointly convex in the two decision variables because the Hessian is a function of the derivatives of the yield rate densities. However, it can be shown (proof omitted), that the objective function is convex in each decision variable separately when the other decision variable is held constant. Thus, the objective function is somewhat well behaved. It is also useful to point out that the objective function is jointly convex in the two decision variables if the holding cost for unassembled kits is not included. The proof is straightforward but tedious and is not shown here. It is interesting to note that aTC/aul and aTC/9u2 can be written as functions of S/u, and S/u2, so that finding the "optimal" solution involves finding these ratios. As such, we might expect the optimal solution (expressed in terms of these ratios) to be relatively insensitive to the value of S. The first-order condition also suggests that the cumulative yield rate distributions, Fi(S/ui), and the inventory holding costs are important factors. The first-order conditions for the N-component problem are quite complicated, so it is quite difficult to show that the objective function for the n-component case is jointly convex in all decision variables, even in special cases. Nevertheless, the objective function in our problem is convex in each decision variable separately. Because of the complexity of the problem, we chose to investigate heuristic procedures. In particular, we analyze policies that are designed to achieve "balanced" inventory levels. Based upon the results above, we decided to develop a systematic method to simultaneously increase or decrease the S/ui values (to try to achieve balance) within a search procedure. We describe such a method in the next section. 5. HEURISTIC PROCEDURE We propose a parametric heuristic policy in which the uis are set so that 1 - Fi(S/ui) = (i + )/(it + X + hi) (2) 9

where X is the parameter to be varied and may be negative (but greater than -n). Using this policy, items with higher holding costs will have lower probability of meeting the target than those with lower holding costs, which is logical from an economic perspective. As X increases, the differential among the fractiles decreases. This also is logical since when implicit shortage costs are high, there is less concern about the high inventory holding costs of a few items which might otherwise limit assembly quantities. The role of X in this procedure is to create an adjusted shortage cost, i + X. The main idea here is that each component may not be fully responsible for a shortage. As such, we may want to use a negative value of X to account for this. On the other hand, since the assembly quantity is constrained by the minimum of the output quantities, it may be necessary to provide increased incentive to produce or purchase by way of a higher adjusted shortage cost. We comment briefly that we considered and tested other parametric policies, including 1 - Fi(S/ui) = 3 for all i and 0< 3 < 1. We found that the proposed policy outperformed the others in initial experiments, so we eliminated the others from further consideration. In the next section we describe an experimental study to evaluate the proposed heuristic procedure. 6. EXPERIMENTAL STUDY To evaluate the performance of our parametric heuristic policy, we applied it to forty 5-component problems. We first explain how the characteristics of the problems were selected. Later in the section, we compare the best solution obtained by the heuristic with the optimal solution obtained by an extensive grid search. In practice, the yield rate density functions are difficult to specify exactly. Our experience suggests that most, however, tend to be unimodal and have finite supports. In our study, we assume that the yield rate of each component has a triangular distribution. A 10

production manager can usually provide an optimistic, a most likely, and a pessimistic value for the yield rates fairly accurately. Although these values can provide the basis for fitting a variety of distributions, we chose the triangular distribution for (relative) ease of computation. Since triangular distributions can take on a wide variety of "shapes," we decided to consider several alternatives. A triangular distribution is described by three parameters: the minimum (a), the mode (c), and the maximum (b). The mean is (a + b + c) /3, and the variance is (a2 + b2 + c2 - ab - ac - bc) / 18. The four "shapes" considered in this study are specified as follows: NS: c=m, a = c - 0.1, b = c + 0.1 =0.04 SL: c = m + 0.033, a = c - 0.2, b=c+0.1 o=0.06 SR: c = m - 0.033, a = c - 0.1, b = c + 0.2 =0.06 WS: c = m, a = c - 0.2, b=c+0.2 a=0.08 where m is the mean and a is the standard deviation. The shape NS represents narrow (low variance) symmetric, SL represents skewed to the left, SR represents skewed to the right, and WS represents wide (high variance) symmetric. Characteristics of the forty test problems are displayed in Table 1. The problems are separated into 9 groups. Ci, mi, and si denote the unit cost, the mean yield rate, and the shape of the density for component i, respectively. (Note that Ci is used as a reference value only since it does not appear explicitly in the objective function.) For each problem, the target assembly quantity is 40, and the holding costs and shortage cost are defined as follows: hi=O.5Ci and 7C=1.5,Ci /mi. i The shortage cost is set sufficiently high to ensure that the product is profitable to produce. The given value of n roughly gives a gross margin of 60%, which is not unusual in the electronics industry. 11

TABLE 1 The components have yield rate densities with identical shapes in the problems in groups 1 through 8. Groups 1 to 4 are designed to reveal the effects of varying the yield rate means for a given density shape. Groups 5 to 8 are designed to reveal the effects of varying both the unit costs and the mean yield rate for each density shape. Group 9 is a set of random problems. Each problem parameter in group 9 is generated randomly, with each of several alternatives being equally likely. Each Ci can take on one of the values 1, 2, 3, 4, and 16; each mi can take on one of the values 0.4, 0.5, 0.6, 0.7 and 0.8; and each si can take on one of the four possible shapes with equal probability. To apply the parametric heuristic, we need to examine different values of X. However, it is not clear what range of X values should be considered and evaluated. To overcome this difficulty, we utilize the following relationship: 1i [ -Fi(S/ui)] = In + + h a i i K + X + hi \ where a is the probability of meeting the target S. Since a must lie in the interval (0,1), it is easier to vary a rather than X. Given a, we can determine X by solving a polynomial of order N, where N is the number of components. For computational simplicity, we use the following approximation to determine X for a given a: 2 + DN= a (t + k + H where H is the average holding cost over all components. In our experimental study, we varied a from 0.02 to 0.99 in steps of 0.01 for each problem. For each a, we used the value of X obtained from the above approximation to determine the uis according to (2), and then evaluated the objective function in (1). (To evaluate the objective function, we assumed that the number of good parts could take on only integer values and discretized the triangular distributions consistently with this 12

assumption. Note that this requires a different discretization for each ui.) We then compared the objective values for the different a values, and selected the set of uis corresponding to the lowest objective value as the final heuristic solution. Hereafter, we refer to this as the a-search procedure and denote its final solution as u. Although it is not necessary to vary a over such wide range and in such fine steps, we chose to do so to observe characteristics of the objective function. Next, we used u as the starting point for a neighborhood search procedure. The purpose of the neighborhood search is to determine how close the solution obtained from the a-search is to the optimal solution. At each iteration, the neighborhood search compares the incumbent objective value with that of all us in the immediate neighborhood of the incumbent. The immediate neighborhood is defined as all us such that each component of the vector differs by at most one unit from the incumbent. (Only combinations that have not been considered at previous iterations are evaluated.) The u with the lowest objective value among the combinations is chosen as the new incumbent. The search terminates when no improvement in the objective value is obtained. Since this neighborhood search cannot guarantee an optimal solution, for four of the more "difficult" problems, we also evaluated the objective function over an extensive area of the solution space. The results showed that although the objective function may be slightly "bumpy" aroundh the minimum, the objective function is generally well-behaved, and the solutions obtained from the neighborhood search procedure were verified to be optimal. Because of the number of decision variables in these problems, it was not possible to perform grid searches for all problem since the necessary CPU time would be prohibitive. We focused our effort on the four problems for which the percentage error for the heuristic was largest because we considered it important to confirm optimality of the solution from the neighborhood search for these problems. We discuss this point in more detail later. Throughout the remainder of this paper, we will refer to the solutions from the neighborhood search procedure as the "optimal" solutions. 13

7. COMPUTATIONAL RESULTS The results from the a-search are shown in Table 2. Columns 2 and 3 list the a and X values corresponding to u. Also shown are the costs for u, the optimal solution, and the error percentage for the heuristic. The last column indicates the number of iterations required for the grid search to reach the optimal solution, using ui as the starting solution. (Except for the a values, all real numbers in Table 2 are rounded to the nearest decimal.) TABLE 2 Table 2 shows that although the a values vary only from 0.76 to 0.95, the corresponding values for X vary over the much wider range from -55.8 to 242.3. Without the a-search, it would be very difficult to determine the range of X values that must be examined. A more efficient implementation of the a-search would be to apply binary search for a over some interval (e.g., 0.6 to 0.99). We also observed that for problems with high mi values, the solutions tended to remain unchanged over a wide interval of a and X values. For example, in problem 2 the solution remained constant as a varied from 0.83 to 0.95. The corresponding interval for X is from 37.9 to 391.1. Thus, for these problems, it may be more efficient to search for "break points" where the solution changes, rather than to perform a more detailed search. For each problem in Table 2, only the smallest values of a and X corresponding to ui are listed. Overall, the a-search performed extremely well. The procedure found the optimal solution for 10 of the 40 test problems. For the remaining problems, the cost penalty ranged from 0.03% to 6.2% (for problem 26), with an average of 2.0%. Our results show that a-search performs best when all the components in the problem have identical distributions. When unit costs for the components are also identical, the problem is equivalent to a single component problem. In this case, the a14

search is guaranteed to find the optimal solution since we have shown that the objective function is convex for one variable. However, even when the unit costs differ among the components (as in groups 5 to 8), the performance of a-search is still very good. Detailed results (not shown here) also indicate that ui tends to be less than the optimal value when the corresponding mi is low (i.e., 0.4 or 0.5), and greater than the optimal value when the corresponding mi is high (i.e., 0.8). This may be due to the fact that yield rates are not considered at all in computing the X values. The worst cases occur when components whose yield rates have low means and high variances also have high unit costs (e.g., problem 26). Here, one component tends to dominate the cost function, and approximate procedures that do not consider this component heavily enough can lead to significant cost penalties. For problems of this type, more sophisticated procedures may be needed. An interesting observation from our study is that the objective function is very flat near the optimal solution when all components have low mean yield rates, and rather steep when all components have high mean yield rates. When the mean yield rates differ among the components, the objective function is also rather flat near the optimal solution. This observation applies for all four distribution shapes. This suggests that heuristic procedures may perform well in precisely those situations where yields tend to be problematic —when some of the mean yield rates are low. In our study, we also considered other cost structures. We applied the a-search to the same set of forty problems under the following three scenarios: 1) hi = 0.2 Ci; 2) hi = 0.9 Ci; and 3) n = 3.0 Ci / mi i For all three cases, the performance of the a-search is similar to that reported here. We also considered different target values and found that the S/ui ratio corresponding to the optimal solutions remains approximately the same for each problem. The slight differences are due to the integrality restrictions on the uis (rounding). 15

8. CONCLUSIONS Our study has shown that a heuristic unidimensional search procedure performs well as a procurement and production control procedure for an assembly system with random component yields. The procedure not only executes quickly, even on a personal computer, but also provides near-optimal, if not optimal, solutions for all of our test problems. Since the yield rate distribution functions are only approximate in practice, it is not crucial to obtain the optimal solution in most cases. However, if the optimal solution is desired, then a local grid search can be applied after the heuristic search is completed. Note that the unidimensional search procedure can be applied to problems with any yield rate distributions. Equally important, we have shown that the optimal ratio of the demand to the optimal input quantity for each individual component is robust with respect to the magnitude of the target value. This means that we can use a small target value, apply the heuristic search procedure, and then scale the solution. By doing so, the computation time can be reduced tremendously (especially when the target value is large) without affecting the accuracy of the solution. The heuristic can be used as a sensitivity analysis tool. Production managers can ask "what-if' questions such as which components have the most impact on the solution, or what is the effect on the expected cost of improving the mean or variance of the yield rate for certain components. In this way, management effort can be focused on areas with the largest potential for improvement for the system as a whole. Possible changes include finding alternative suppliers or working with the current supplier to improve the yield rate distribution. Although the heuristic procedure can be implemented quickly, even on a personal computer, for problems with up to 20 components, for applications with a large number of components, other approaches may be necessary. Futher research is needed to develop 16

methods to identify the "most important" components to be included in a heuristic or optimal procedure, approaches to adjust solutions to account for the impact of excluded components, and methods to determine appropriate production or procurement quantities for components not included in the procedure. In addition, research is needed to develop solution procedures for assembly systems with multiple time periods, with lead time differences among the components, and with yield considerations in the assembly process. ACKNOWLEDGEMENTS We would like to thank the three referees for their valuable comments and suggestions on an earlier version of this paper, and Farin Mohammadi for assisting in the the computational study. The work of Candace A. Yano was supported in part by National Science Foundation Grant DMC-8504644. 17

REFERENCES Gerchak, Y., R.G. Vickson, and M. Parlar (1988), "Periodic Review Production Models with Variable Yield and Uncertain Demand," HIE Transactions 20 (2), 144-150.. Giffler, B. (1960), "Determining an Optimal Reject Allowance," Naval Res. Log. Quarterly 7(2), 201-206. Karmarkar, U. and S. Lin (1986), "Production Planning with Uncertain Yields and Demands," Working Paper, William E. Simon Graduate School of Business Administration, University of Rochester. Klein, M. (1966), "Markovian Decision Models for Reject Allowance Problems," Management Science 12(5), 349-358. Lee, H.L. (1987), "Lot-Sizing for Assembly Systems with Variable Yields," Paper presented at the 1987 Multi-Echelon Inventory Conference, Wharton School, University of Pennsylvania. Lee, H.L. and C.A. Yano (1988), "Production Control for Multi-Stage Systems with Variable Yield Losses," Operations Research 36(2), 269-278. Levitan, R.E. (1960), "The Optimum Reject Allowance Problem," Management Science 6(2), 172-186. 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. Singh, M.R., C.T. Abraham, and R.Akella (1988), "Planning for Production of a Set of Components when Yield is Random," Proceedings of the IEEE International Electronics Symposium. 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 Under Uncertainty," Decision Sciences 7(4), 595-606. Yano, C.A. (1987), "The Product Cycling Problem in Systems with Random Production Yields," Technical Report 87-32, Department of Industrial and Operations Engineering, University of Michigan. Yano, C.A. and H.L. Lee (1989), "Lot Sizing with Random Yields: A Review," Technical Report 89-16, Department of Industrial and Operations Engineering, University of Michigan. Yao, D.D., (1988), "Optimal Run Quantities for an Assembly System with Random Yields," lIE Transactions 20(4), 399-403. 18

Appendix Extended Form of the First Derivative The first partial derivative with respect to ui is 1 aTC/ul = hi j Pifl(P1) F2(PlUl/U2)dP 1 p2U2/U1 -h2 J I Pi f2(P2)fl(Pl)dPl dP2 P2 0 Pi= 0 1 P2U2/U1 + (hl + h2) f f Pi fl(Pl)f2(p2)dPl dp2 p2=S/U2 Pi= 0 1 + [(hl + h2)ul/u2] f Pi (P1 - S/ul) f2(P1u1/U2)fl(pi) dp1 S/ui 1 - [(hi + h2)u22lu12] f P2 (S/u2 - P2) fl(p2u2/ul)f2(p2) dP2 S/u2 S/u2 P2U2/U1 + 7 i f I Pl fl(Pl)f2(P2)dPl dp2 P2= 0 i= 0 S/u2 -(u22/u12) f P2 (S/u2 - P2) fl(p2u2/ul)f2(p2) dP2 0 S/u1 + (ul/u2) f Pi (S/ul - Pi) f2(plul/u2)fl(pl) dpl 0 S/u1 [1 -F2 (S/u2)] Pi f(Pl)dP1 } 0 and the derivative with respect to u2 has the same form, but with subscripts 1 and 2 reversed. 19

n+1 2)."" 0. 0 0 n-i* n Figure 1 Assembly System

Table 1. Problem Characteristics Group Prob. # # C1 C2 C3 C4 C5 ml m2 m3 m4 m5 s1 s2 s3 s4 S5 1 1 1010101010 0.4 0.5 0.6 0.7 0.8 NS NS NS NS NS 2 1010101010 0.8 0.8 0.8 0.8 0.8 NS NS NS NS NS 3 1010101010 0.4 0.4 0.4 0.4 0.4 NS NS NS NS NS 2 4 1010101010 0.4 0.5 0.6 0.7 0.8 SL SL SL SL SL 5 1010101010 0.8 0.8 0.8 0.8 0.8 SL SL SL SL SL 6 10 10 0 10 1 0 0 0.4 0.4 0.4 0.40.4 SL SL SL SL SL 3 7 10 10 10 10 10 0.4 0.5 0.6 0.7 0.8 SR SR SR SR SR 8 1101010 10 0.8 0.8 0.8 0.8 0.8 SR SR SR SR SR 9 1010101010 0.4 0.4 0.4 0.4 0.4 SR SR SR SR SR 4 10 1010101010 0.4 0.5 0.6 0.7 0.8 WS WS WSWSWS 11 10 10 10 10 10 0.8 0.8 0.8 0.8 0.8 WS WS WS WS WS 12 10 10 10 10 10 0.4 0.4 0.4 0.4 0.4 WS WS WS WS WS 5 13 1 2 4 816 0.4 0.5 0.6 0.7 0.8 NS NS NS NS NS 14 1 2 4 8 16 0.8 0.7 0.6 0.5 0.4 NS NS NS NS NS 15 1 2 4 8 16 0.8 0.8 0.8 0.8 0.8 NS NS NS NS NS 16 1 2 4 8 16 0.4 0.4 0.4 0.4 0.4 NS NS NS NS NS 6 17 1 2 4 816 0.4 0.5 0.6 0.7 0.8 SL SL SL SL SL 18 1 2 4 8 16 0.8 0.7 0.6 0.5 0.4 SL SL SL SL SL 19 1 2 4 8 16 0.8 0.8 0.8 0.80.8 SL SL SL SL SL 20 1 2 4 816 0.4 0.4 4 0.4 0.4 SL SL SL SL SL 7 21 1 2 4 816 0.4 0.5 0.6 0.7 0.8 SR SR SR SR SR 22 1 2 4 816 0.8 00.70.6 0.5 0.4 SR SR SR SR SR 23 1 2 4 816 0.8 0.8 0.8 0.80.8 SR SR SR SR SR 24 1 2 4 816 0.4 00.4 0.4 0.4 SR SR SR SR SR 8 25 1 2 4 816 0.4 0.5 0.6 0.7 0.8 WS WS WS WSWS 26 1 2 4 816 0.8 0.7 0.6 0.5 0.4 WS WS WS WS WS 27 1 2 4 8 16 0.8 0.8 0.8 0.8 0.8 WS WS WS WSWS 28 1 2 4 8 16 0.4 0.4 0.4 0.4 0.4 WS WS WS WS WS 9 29 1 1610 2 8 0.8.7 0.5 0.5 0.6 NS NS SL WS SR 30 16 8 10 1 4 0.7 0.5 0.4 0.4 0.8 SR SL WS WS NS 31 1016 4 2 1 0.6 0.6 0.5 0.4 0.8 SR SR NS WSNS 32 1 4 81010 0.7 0.7 0.4 0.5 0.6 SL SL NS WS WS 33 1016 8 1 2 0.6 0.4 0.5 0.4 0.8 WS SL WS NS NS 34 1616 410 1 0.7 0.7 0.5 0.4 0.5 SL NS WS SL WS 35 1 1 16 4 2 0.8 0.4 8 0 0.8 0.8WS NS SR WS SR 36 16 4 2 1 4 0.4 0.7 0.5 0.7 0.5 NS WS SL SL NS 37 4 4 1 810 0.7 0.5 0.8 0.5 0.7 SL SR WS NS SR 38 8 210 2 1 0.7 0.5 0. 8 0.5 0.7 SL SR WS NS SL 39 10 1 4 8 2 0.8 0.6 0.44 0 0.5 WS SR SR SL SL 40 8 8 10 4 1 0.5 0.7 0.6 0.5 0.6 SL WS SR NS NS

Table 2. Computational Results Prob. Heuristic Optimal Percent Number of # ca X. ^ __ Cost Cost Error Iterations 1.91 129.9 193.1 193.1 0.0 0 2.83 37.9 132.2 132.2 0.0 0 3.91 75.1 290.0 290.0 0.0 0 4.84 8.2 323.9 317.5 2.0 12 5.77 -0.6 217.1 217.1 0.0 0 6.86 -24.2 543.1 543.1 0.0 0 7.90 102.1 257.4 257.2 0.1 1 8.82 29.7 178.4 178.4 0.0 0 9.89 24.5 418.5 418.5 0.0 0 10.87 44.4 389.4 373.4 4.3 20 11.76 -5.1 267.4 267.4 0.0 0 12.83 -55.8 714.6 714.6 0.0 0 13.92 117.5 89.4 89.3 0.1 2 14.88 19.6 139.3 138.8 0.4 1 15.87 51.6 76.6 76.4 0.3 1 i6.91 46.6 169.0 168.4 0.4 2 17.85 26.9 144.7 143.3 1.0 10 18.89 31.3 240.4 237.1 1.4 5 19.81 13.9 123.2 123.2 0.0 1 20.86 -15.0 310.3 310.2 <0.1 2 21.85 26.9 120.0 119.4 0.5 4 22.87 9.6 189.2 187.7 0.8 2 23.85 35.7 103.5 102.8 0.7 1 24.89 15.2 243.3 242.9 0.2 2 25.80 1.0 175.3 171.5 2.2 19 26.89 31.3 292.8 275.7 6.2 14 27.80 9.8 151.1 150.8 0.2 1 28.84 -28.9 406.0 406.0 0.0 1 29.92 127.9 170.1 168.9 0.7 5 30.90 76.1 217.9 210.5 3.5 21 31.89 53.6 155.7 154.4 0.8 16 32.85 17.0 211.9 211.8 <0.1 1 33.95 242.3 264.3 251.0 5.3 3 34.88 60.4 266.8 266.4 0.2 3 35.86 31.5 86.2 85.5 0.8 3 36.89 25.8 146.0 145.6 0.3 1 37.87 27.7 124.5 124.5 0.0 0 38.83 10.5 112.2 111.7 0.4 2 39.86 9.4 172.1 167.2 2.9 10 40.85 13.2 179.6 179.2 0.2 2