Generalized Tolerance Synthesis for Recti-Linear Systems Woo-Jong Lee Tony C. Woo Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, Michigan 48109-2117 August 1988 Technical Report 88-11

Abstract Minimum cost tolerance allocation is considered for recti-linear systems, in which the dimensions are recti-linear, such as VLSI circuits and peg-hole assemblies. Tolerance synthesis is achieved by nonlinear optimization in which the objective is cost minimization and the constraints are design functions, both of which are non-linear. Globally optimal solution for tolerances is obtained by a key development: a proof that those non-linear functions are convex. This enables the utilization of known algorithms for convex programming. The non-linear constraints are carefully derived through the point of view of tolerance stack-up analysis. The derivation yields a technique that unifies the deterministic approach and the probabilistic approaches by considering asymmetric probability density functions. A model for representing the geometric uncertainty of a dimension is also proposed.

1. INTRODUCTION Tolerance is the total amount by which a specific dimension in an engineering drawing is permitted to vary [1]. The specification of a tolerance involves opposing considerations in cost and in performance (functionality and interchangeability): the more tolerance, the less cost and performance and vice versa. The resolution of this conflict in tolerancing for recti-linear systems is considered in this paper. As a global criterion for resolving the conflict, cost is minimized. Minimum cost tolerance allocation, however, is constrained by design functions for performance. A design function specifies the scope of permissible variations in the aggregation of component tolerances, or what is commonly referred to as "stack-up". Consider Figure 1. The clearance Y between the two components is represented by the equation Y=X1-X2, where the variables X1 and X2 represent the dimensions of the hole and the shaft, respectively. Suppose the variation of the clearance is to be less than or equal to 0.05 for successful assembly. That is, Ty < 0.05, where Ty is the tolerance for the aggregate Y. Under this constraint, minimum cost tolerance allocation can be formulated as follows: Min C(T1,T2) subject to Ty = f(T1, T2) < 0.05 where C(-) is the cost function, T1 and T2 are, respectively, tolerances for X1 and X2, and Ty is a function of T1 and T2. For situations where many design functions are involved, minimum cost tolerance allocation generalizes to: Min C(T1, T2,, T) subject to (1) TYi = fi(T1, T2, Tn) T fori=1..,m -- "' - ~Yi" 1

Figure 1. Clearance between Mating Parts IA_^^W^^^^ >^> V7 ~'7777zX77777777Y77777A,,, - -, i iii",, o, A, - f, Z.... _ { - ffo///////Awfo//////7aM~~~~~~...... ~/77777777777777/z> Legend: 0: diffused A: polysilic l: contact e: ion impl region region:on line 88 lantation (a) An NMOS VLSI A 8s L 7:.....,...-.,:....................-:...................,.................,...................................................................................................................................................................-............................................................... - -.. *......................... _......................................... 6.40 y 0 0 I i I 0 0 0 0 0 1 0 1 0................................. I I I I I d I _. 1 -0 l XI'I.. ~A _ ~XI A i d (b) A Design Rule Figure 2. An Example of a Recti-Linear System 2

where C(): Tj n Tr. TYi TU Yi xj Yi cost function in terms of component tolerances, tolerance of the j-th component dimension Xj, total number of component tolerances to be decided, the i-th assembly tolerance, design function relating Tyi to T1,..., Tn, upper limit of TYi for desired performance in an assembly, the j-th component dimension, the i-th assembly dimension, and m: number of assembly tolerances (stack-up tolerances) to be considered. A recti-linear system is one in which an assembly dimension Yi is defined by a linear function of component dimensions X1,...,Xn: n Yi = 2. aij Xj j=l for i=l,...,m (2) where aij is an integer. Recti-linear systems are found not only with mechanical applications, such as peghole assemblies illustrated by Figure 1, but also in the design of VLSI (Very Large Scale Integrated) circuits. A mask used in the fabrication of VLSI circuits is composed of a collection of rectangles. Each rectangle is either a portion of a diffused region, a polysilicon line, an ion implantation region, or a "via" contact, as illustrated in Figure 2-(a). These rectangles are laid out according to certain design rules, which specify allowances for certain widths, clearances, extensions, or overlaps. These inter-component relations such as widths, clearances, etc., can be thought of as assembly dimensions Yi. Consider Figure 2-(b) in which a polysilicon gate crosses a diffused region, thereby forming a transistor. In order to make certain that the diffused region does not short-circuit the drain-to-source path of the transistor, it is necessary for the polysilicon gate to extend a distance Y of at least 2X beyond the nominal boundary of the diffused area, where X denotes a unit length in process resolution [2,10,13]. This distance Y can be represented by the difference of the two values X1 and X2, i.e., Y = X2- X1. In general, by associating all the geometric 3

dimensions Xj in Figure 2-(b), design rules can be described as linear functions of the component dimensions Xj. Because of the "randomness" of the fabrication process, resulting dimensions follow a distribution. In this paper, asymmetric distribution for dimension Xj is considered. The consideration of asymmetric distribution is motivated by a practice called "maximum material condition" (MMC) [1] (or, LMC for "least material condition" as the case may be). The practice, in effect, encourages the least amount of manufacturing time and produces skewed distributions. MMC tells the machining process to remove as little material as possible to meet the specification, hence leaving the "maximum material". (Alternatively, LMC tells the vapor deposition process to deposit as little material as possible so as to create the "least material condition.") Either way the resulting dimension is far from being distributed normally as illustrated in Figure 3. TI. t T * Tj /1 TJ 2 T J + Tj / 2 (a) Least Material Condition for Shaft (b) Maximum Material Condition for Shaft (Maximum Material Condition for Hole) (Least Material Condition for Hole) Figure 3. Asymmetric Distribution due to MMC or LMC In solving formulation (1), the tolerances Tj in the objective function are computed, hence synthesized. But they must obey the constraint which specifies the functional relation fi(T1, T2, **, Tn) between assembly tolerance Tyi and component tolerances T1, T2, *.., Tn. The study of the aggregate behavior of given individual tolerance T1, T2, *., Tn is referred to as tolerance analysis or, more commonly, as stack-up analysis. Hence, synthesis is performed through analysis. Tolerance analysis is 4

typically conducted in one of two ways: deterministic or probabilistic. Neither approach is considered as appropriate for dealing with asymmetric tolerances. The deterministic approach (worst-case analysis) evaluates an assembly tolerance to a value larger than necessary. In the wQrk by Balling, et al. 3 and Michael and Siddall 14, the i-th assembly tolerance Tyi is represented by n Tyi E la ijl Tj for i=l,...,m. (3) J=1 While (3) is very simple to compute, the resulting assembly tolerance is often pessimistic. For example, five components each with 0.001 inch tolerance will stack up to 0.005 inches assembly tolerance according to (3). If the sum exceeds the specified upper bound for assembly tolerance (of, say, 0.0017 inches), what typically happens next is that the component tolerances Tj are reduced. To continue the example, suppose the component tolerances are reduced uniformly from 0.001 inch to 0.0003 inches by the designer. As common sense dictates - higher cost for lower tolerance - worst case analysis incurs a component cost higher than otherwise possible. With the probabilistic approach, partial satisfaction of the design function, e.g., 99% yield, is possible. The probabilistic approach is well-defined under the assumption of normality for the random variable Xj by the following property: when the constituting dimensions follow the normal distributions, the linear sum for an assembly dimension also follows a normal distribution. However, distributions are assumed to be asymmetric in this paper. While an asymmetric p.d.f. (probability density function) may be modeled by the beta distribution,4'5 there is no general rule for representing the distribution of the linear sum for an assembly dimension Y. The challenge of the optimization problem formulated as (1) may be now summarized. Because of the problem domain, the assembly dimension Y, in a rect-linear system is a linear function of the component dimensions as described by (2). But because of process considerations, asymmetric distributions for component dimensions are assumed as shown in Figure 3. However, there is no known technique for computing the linear sum of asymmetric distributions. 5

To overcome the difficulty, a new model for a dimension is proposed. The basic idea is to decompose the manufacturing uncertainty into two parts: uncertainty due to mean shift and uncertainty due to other noises. Then, tolerance is represented by the sum of these two parts. The concept of decomposition has been used in market forecasting [16] to explain the variation of market demand influenced by predictable factors such as seasonal effects and less predictable factors due to the introduction of competitions or the discovery of new materials and processes. The first application of decomposition to tolerancing was due to Greenwood and Chase [8]. This paper, in addition to providing statistical justification, proves fi(T1, T2, *, Tn) to be a convex function in terms of the component tolerances. Because of this proof of convexity, the tolerance synthesis problem of formulation (1) becomes a convex programming (CP) problem. This observation leads to a pleasant result: that the globally minimum cost tolerances for a recti-linear system can always be obtained. There exist several algorithms to guarantee an optimum for a CP problem, such as the homotopy procedure of Eaves and Saigal for finding a fixed point [20] and the Lagrangean method [23]. The cost function adopts existing models [21,22]. The paper is organized as follows. Section 2 presents a new approach and its justification. Section 3 investigates the convexity of fi(T1, T2,.*., Tn) for recti-linear systems. The result of convexity is then applied to the solution procedure of problem (1) and the whole procedure is illustrated with an example. 6

2. HYBRID TOLERANCE ANALYSIS In the probabilistic approach, a random variable and its confidence interval are associated with a dimension and its tolerance. The confidence interval (tolerance T.) for the j-th dimension X. is determined by two attributes; the confidence coefficient k. and the standard deviation aj such that T. = k. oa for j= 1,...,n. Then, T. a0 1= for j=1,...,n (4) J k. J Since the variance of the linear sum Yi of (2) is the sum of the squares of the variances of the constituting 2 n 2 2 variables, i.e., (cyi)2 = A (aij)2(aj)2, the i-th assembly tolerance can be represented by j=1 Tyi = kyi (aij) 2()2 for i=l,....,m (5) j=l kj where kyi is a confidence coefficient for the i-th assembly dimension Yi. Since tolerance is the amount by which a dimension is permitted to vary, as in 1.000 +~ 0.002, it is an unsigned magnitude. The square root in equation (5) is always positive. To illustrate the approach, the example from Figure 1 is again considered. Suppose the tolerances for X1 and X2 are 0.001 with confidence coefficients kl=k2=6 and they follow (for the time being) the normal distribution. The worst-case tolerance for Y by the deterministic approach is 0.002. Assume that in the probabilistic approach a 1% defect is allowed in the linear sum. Then 5.15 oy = 0.002, since Pr(Z < 515 = 1 -.01 where Z denotes a random variable following the standard normal distribution. This leads 0.002 to ay = 5.1' If equal distribution of this linear sum tolerance into components is assumed, then al = a2 = 0.000275 since (ay) = (a<) + (a2). As a result, the tolerances for X1 and X2 can be increased by 65% from 0.001 to 0.001647 (= 6 x 0.000275) by allowing a 1% defect in the linear sum (i.e., stack-up). 7

However, the above procedure can not be applied since the distribution of the dimension Xj, hence that of the linear sum Y1, are not symmetric. To resolve the difficulty from asymmetry, a hybrid approach, which combines the deterministic and probabilistic approaches, is proposed. The concept of a hybrid approach is based on the decomposition of a tolerance into a known quantity (deterministic) and other uncertain quantities (probabilistic). The decomposition of a tolerance is explained by the following additive model for a dimension: Xj=Cj+Mj+Ej forj =l,...,n. (6) Cj is a constant representing the center of the j-th tolerance interval. M. and Ej are, respectively, independent random variables for representing the mean shift from Cj and the remaining error term. To capture the general asymmetric case, the distribution form of Mj is assumed to be unknown. However, the error term Ej is assumed to follow the normal distribution around the shifted mean Cj + M. (i.e., E(Ej)=O) based on the central limit theorem since it is due to many independent sources. The relationship among Cj, * * M., and E. is illustrated in Figure 4. If MJ=M., the p.d.f. of E is symmetric around C.+M., but the p.d.f. for Xj could be asymmetric because of the unknown distribution of Mj. p.d.f. ofE vhenMj= N J 3 p.d.f Cj Figure 4. Additive Model for Dimension Xj 8

3.1 Representation of the First and Second Moments of a Dimension To compensate for the lack of information about M., its first and second moments and those of Ej are determined in terms of tolerance Tj. Suppose the mean of Mj is rewritten as a convex combination of the two limits of the tolerance interval: T. T. E(Mj)='P j- (1-pj)= Tj (pj- 0.5) where pj is a positive scalar such that 0 < pj < 1. The scalar pj reflects the skewness of the tolerance interval: if 0 < pj < 0.5, the mean value of Xj is to the left of C, if pj= 0.5, the mean value of Xj coincides with Cj, and if 0.5 < pj < 1, the mean value of Xj is to the right of Cj. Hence, the measure of skewness of E(Mj) can be obtained from the two variables Tj and pj. The variability of Mj and Ej also can be represented in terms of T. and p. by taking the following two steps: (i) represent the standard deviations of Mj and Ej in terms of T. and a new scalar wj, and (ii) relate wj topj. For the first step, denote the standard deviations of Mj and Ej by aMj and aEj, respectively, and definme the proportion of'Mj to aj as the weighting factor wj, i.e., Mfor j = Wj= 1 forj=l,...,n (7) 9

Since aMj and aEj are usually very smallt, the standard deviation aj can be approximated by the sum of aM. and Ejtt. That is, aj I'Mj + aEj forj=l,...,n (8) By combining (8) with equations (4) and (7), aMj and aEj can be represented in terms of Tj: T. J aMj = j k (9) T. J Ej = (l-wj) kj Now, the second step is to relate wj to pj. The relation is based on the observation that the variability by random noise is proportional to the minimum distance to the tolerance limit. The essence of this observation is illustrated in Figure 5: the further the shifted mean is from the center, the smaller the variability becomes (in order to keep the manufacturing process in control). This observation can be expressed as follows: aEj = 2pj aj if 0.0<pj<0.5 (10) = (2 - 2pj) aj if 0.5<pj<1.0 Since aEj is approximated by (l-wj)aj in (9), equation (10) leads to the following relation: wj =11-2pjl (11) These two steps combined are summarized in the following lemma. t For instance, the tolerance for a hole or shaft of diameter 1.00 is recommended by ANSI to be 0.0025 (or 0.0006) in case of loose fit (or tight fit). tt Since j2=aM2+Ej 2, ^ (Mj+ Ej)2 -2MjEj. When Mj<<l.O and TEj<< 1., MjEj becomes almost zero and hence j _ Mj+iEjj J almost zero and hence ali aM+aE. ~ 10

(a) when pj - 0.6 Cj Xj (b) when p - 0.75 Cj Xj (c) when p - 0.9 j - Tj 2) /I c+rj/2) Tj Figure 5. Variability due to Random Noise after Mean Shift 11

Lemma: In the additive model of (6), the first two moments of a dimension can be represented in terms of four parameters Cj, Tj, pj, and kj as follows: E(Xj)=Cj +E(Mj)= Cj + Tj -0.5) T. (Mj =11 - 2pj I Tj T. Ej =(1- 11 - 2pj 1) j J kj 3.2 Representation of Assembly Tolerance Based on Lemma 1, the tolerance of an assembly dimension Tyi can be expressed in terms of aMs and aEj.. By combining equations (2) and (6), an assembly dimension has three parts: sum of constant centers CSi, sum of mean shifts MSi, and sum of error terms ESj. That is, n n n Yi = X aij Cj + 1 aji Mj + l aij Ej = CS + MSi + ESi = CS. + MS. + ES. for i=l,...n, Since the first term CSi is a constant, it does not influence the assembly tolerance Tyi. Hence, the assembly tolerance Tyi can be determined by tolerances due to MSi and ESi. Denote those two tolerances by TMSi and TES., respectively. Then, the assembly tolerance Tyi can be represented by Ti = TMSi+ TESi for i=,...,m (12) Recall that the distribution of MS is unknown hence the distribution of Yi is also unknown. The derivation for Tyi is as follows. 12

To compute Tyi, first consider TESi. Note that TESi is the tolerance for the linear sum of error n terms, i.e., A aijEj. Since each error term Ej follows the normal distribution, the tolerance of the linear sum can be described by using (5)' That is, ttt TESi=kESi / (aij)(1-11-2pjl) (-) for i=l,...m (13) j=1 j where kESi is a confidence coefficient for TESi. Note that (13) is probabilistic. n Next, consider TMSi. It is the tolerance for the linear sum of the mean shift Mj's. i.e., aijMj. j=1 Since the distribution of each component Mj is unknown, the tolerance of the linear sum is taken to be the worst case. That is, n Tj TMSi= a lajl 11- 2pjl k for i=l,...,m (14) where kMj is a confidence coefficient for the j-th tolerance due to Mj. Note that (14) is deterministic. By substituting (13) and (14) into (12), an assembly tolerance is obtained. Lemma 2: In the additive model of (6), the tolerance of the linear sum of dimensions can be computed by n T.. 2j2 Tyi=' a1 k M-2 + kEs i ai) (111 - 2pjl)2( 2 for i=l,...,m (15) J=1 j kj=1 n n T. ttt ESi= aijEj. Hence, (aESi2 = (aij)2 Ej)2. Since = (1- 1 2pj byLemma )2 j=11 J n T = (aij)2(1- 11- 2pj)2( )2. This leads to (13) since TESi is defined as kESi ESi.p )2 1J 1 kn. ES " 13

In (15), the natural choice of kMj is to make it equal to kj since both distributions of Mj and Xj are unknown. In addition, kESi can be set to 6 such that a 99.73% confidence level is covered under the normal distribution. Then, equation (15) is simplified to TYi- la.l.l 11- 2pjl Tj +6 (aij) (1- l11- 2pjl) for i=l,...m (16) j=1.J=. This hybrid approach unifies the existing approaches [4,5,6,9,11,12,14,15] to tolerance analysis. That is, both the deterministic and the probabilistic approaches can be explained by equation (16): if pj = 0 or 1 (i.e., w.=l) for j=l,...,n, the equation is the same as that for the worst-case analysis; if pj = 0.5 (i.e., if wj=O) for j=l,...,n, the equation is the same as that for the probabilistic analysis. 14

3. TOLERANCE SYNTHESIS This section presents the solution to tolerance synthesis. Based on the derivations in the previous section, formulation (1) for tolerance synthesis can be written as a non-linear programming (NLP) problem: Min C(T1, T2,, Tn) subject to (17) j=l j=l.)= In this formulation, the decision variables are T's for 1 < j < n. The constraint is derived through tolerance analysis. The scalars ai and kj are given, and wj is computed from the given pj using equation (11). Now, consider the solution scheme for this NLP problem. To determine the existence of an algorithm that guarantees global convergence to the optimum, the objective function C(T1, T2,', Tn) and the constraint functions must be examined. If these functions turn out to be convex, the corresponding NLP then becomes a convex programming (CP) problem. Then, existing algorithms for CP can be used to solve problem (17). Convexity of the cost function C(T1, T2, —, Tn) is generally understood in tolerancing [4,17,21,22]; the more tolerance the less cost Hence, this section is devoted to showing the convexity of the constraint. n The first part of the constraint, i.e.,, wj lajl Tj, is a linear function in terms of Tj's. So it is a j=l convex function. Since the linear sum of two convex functions is also convex, the remaining work is to n i. show the convexity of the second part, i.e., (-W)2 (aj) (k For its proof, the following j=l J theorem is used. 15

Theorem (Cauchv-Schwartz Inequality): Let x and y be two column vectors in R. Then, Ixtyl < II x 11y l where 11I11 denotes the Euclidean norm. (Proof) The proof can be found in page 130 of [19]. Lemma 3: rn ~ 2 ( j2 X/ (1-wj)2 (aij) (k is a convex function in terms of Tj's. j=1' j (Proof) For notational convenience, denote the function 2 (-wj)2(ai.)2(1)2 byG(T) and j=l J 2... 2 (1-wj.) ( by hij Notice that hi > 0. Then, n G(T)= hij Tj2 j=1lJJ The function G(T) is convex if a G(T1) + (l-a) G(T2) > G(aT1 + (1-a)T2) (18) for two arbitrarily chosen tolerance vectors T=(T11, T21..., Tnl), T2=(T12 T22..., T2)t and a scalar a such that 0~al1. To see if inequality (18) holds, the difference of the squares of both sides, i.e., (aG(Tl) + (1-a)G(T2))2 - G(aT1 + (1-a)T2)2, is checked. (Squaring both sides of inequality (18) is permissible since they are nonnegative. Refer to equation (5).) Invoking the Cauchy-Schwartz inequality proves the convexity of G(T) as follows: 16

(aG(T1) + (1-a)G(T2))2- G(aT1 + (-a)T2)2 = 2a(1 —a) { ( h/ij Tjl)2 ( hij Tj2)2 - (hij Tjl)( j Tj2)} = 2a(1-a) { I T II T2 II - I T T I } >0 where T; = (hij Ti, 4T2,...hij Tn1) for 1=1,2. Q.E.D. Since both the objective function and the constraints are convex, the tolerance synthesis problem of (17) is a CP problem. This leads to a desirable result: that the minimum cost tolerances can be always found by using the existing algorithms for a CP problem [23]. Example Consider the assembly in Figure 6 in which three assembly dimensions Y1 - Y3 are described as linear functions of component dimensions X1 - X7. (In this example, the component dimensions are specified with respect to datums A and B, which are the surfaces labelled in the drawing.) The three assembly dimensions are for clearances between the two parts. To synthesize the tolerances of component dimensions, three kinds of input are needed: (i) bounds on the assembly dimensions Tyi, (ii) probabilistic data on component dimension Xj, and (iii) cost function C(T1,T2,..., T,). The maximum allowable tolerances of the assembly dimensions specify the performance of the system. In this example, the three assembly tolerances have the following upper bounds: Ty< 0.005, Ty < 0.003, and Ty3< 0.005. As each dimension is represented by the additive model of (6), the center Cj of tolerance limit and scalar pj for mean shift are read in for each dimension X.. Table 1 gives the data. In it, the scalar wj is J J 17

computed from pj using (11). Although Cj does not influence the determination of Tj, it is used to compute EC. T. Tthe resultant tolerance limits [Cj - 2 C + 2. The coefficient pj is used not only for the determination of Tj, but also for the computation of the mean value of X. since E(Xj)=Cj+T.(p.-O.5) according to Lemma 1. B i = X2 - X'-7 + X6 ~= X- X5 - + X2 Y3 = X - X3 - X5 Figure 6. Assembly of Two Mating Parts Dimension Index 1 2 3 4 5 6 7 Cj 1.0 2.0 3.0 4.0 0.998 2.0 2.998 pj 0.6 0.1 0.9 0.4 0.6 0.4 0.5 wj 0.2 0.8 0.8 0.2 0.2 0.2 0.0 Table 1. Data for the Component Dimensions 18

Cost functions typically fall into two groups: inverse-square model [21] and exponential model [22]. Both models describe a convex relationship between cost and tolerance: a. C(Tj) = 7 + Tj. C(Tj) = aj exp(- -) + fj pj (inverse-square model) (exponential model) where C(Tj) denotes the manufacturing cost for tolerance Tj, while aj and p. are the coefficients for variable cost, and f. indicates the fixed cost. For this example, the inverse-square model is adopted and the coresponding coefficients are given in Table 2: Dimension Index 1 2 3 4 5 6 7 aj 1.0 1.0 1.5 1.5 1.4 1.4 0.6 _ J 0.1 0.1 0.1 0.1 0.1 0.1 0.1 Table 2. Coefficients of Tolerance-Cost Model Then, the total manufacturing cost is: nn a n C(T,,T2....Tn)= C(Tj) x Tole e j=e j=b j 1 Tolerance synthesis by cost minimization (17) instantiates to: 19

7 a. 7 Min ( x 10-6) +, f. j~=l r Pij= J subject to W1Tl+w2 T2+w6T6+w7T7+ (l-w22 + (1-w2)2T22 + (1-w6)2T62 + (1-w7)2T72 < 0.005 w2 T2+ w3 T3+ W5 T5 + w6T6+ (1-w2)2T22 + (1-w3)2T32 + (1-w5)2T52 + (1-w6)2T62 < 0.003 W3 T3 + W4 T4 + w5 T5+'(1-w3)2T32 + (1-w4)2T42 + (1w)2T52 < 0.005 To solve this CP problem, the software package MP5-FIXPT, which implements the homotopy procedure of Eaves and Saigal for finding a fixed point [20], is used. It runs on the IBM AT personal computer. The result of executing the algorithm is given in Table 3. And, this result is compared in Table 4 with results from two other methods, worst-case [3,14] and probabilistic [4,11,15], which were also implemented by adjusting wj. The hybrid approach generates tolerances looser than the worst-case analysis but tighter than the probabilistic approach, for a total cost 6.849. For instance, the tolerance T7 is 25.095 x 10-4 units when the hybrid approach is used. If the worst-case analysis (or the probabilistic approach) is used for tolerance analysis, then T7 decreases (or increases) by 35.1% (by 19.9%). This decrease (or increase) in turn incurs an increase (or decrease) in manufacturing cost The difference in cost among the approaches is due to the difference in the available information about the distribution of the dimensions: if the distribution is fully known, then the probabilistic approach should be used to reduce the manufacturing cost; if the distribution is totally unknown as in the worst-case analysis, then a higher manufacturing cost is incurred to insure against uncertainty. The hybrid approach deals with partial information. 20

dimension index Tj(*) Mean E(Xj) ( Tolerance Limits ( J Lower Upper 1 29.4381 10002.9400 9985.2810 10014.7200 2 8.4896 19996.6000 19995.7600 20004.2400 3 9.7463 30003.9000 29995.1300 30004.8700 4 39.1872 39996.0800 39980.4100 40019.5900 5 9.8801 9980.9880 9975.0600 9984.9400 6 9.8617 19999.0100 19995.0700 20004.9300 7 25.0950 29980.0000 29967.4500 29992.5500 Note: (*) unit: 104 Table 3. Result of the Example Ti Worst-Case) Probabilistic (**) Hybrid(***) T1 19.299 34.183 29.438 (65.6%) (116.1%) (100.0%) T2 6.807 13.975 8.490 (80.2%) (164.6%) (100.0%) T3 7.878 15.521 9.746 (80.8%) (159.3%) (100.0%) T4 34.423 45.015 39.187 (87.8%) (114.9%) (100.0%) T5 7.699 15.255 9.880 (77.9%) (154.4%) (100.0%) T6 7.615 15.202 9.862 (77.2%) (154.1%) (100.0%) T7 16.278 30.085 25.095 (64.9%) (119.9%) (100.0%) Total Cost 10.672 3.268 6.849 (155.8%) (47.7%) (100.0%) Note: - The values in parenthesis are normalized ones based on the values of the hybrid approach - (*) when all w=-1.0, unit: 104 - (**) when all wj=0.0, unit: 104 - (***) unit: 104 Table 4. Comparison with Other Methods 21

4. SUMMARY AND DISCUSSION The contribution of this paper is two-fold. In theory, the hybrid technique in section 2 unifies the deterministic and the probabilistic approaches to tolerance analysis. This is made possible by the additive model (6) that handles both the symmetric and the asymmetric distributions, the properties of which have been rigorously derived. In practice, globally optimum tolerances for recti-linear systems that are prevalent in simple assembly tasks and in VLSI design are synthesized by cost minimization. The globally optimum solution is enabled by the formulation of an NLP (17) which is proven to be convex in section 3. In the early days of computer aided design, development of finite element analysis and computer graphics proceeded in parallel. It was not until both areas were sufficiently mature did automatic meshing emerge. Here, a technique for synthesizing tolerances in recti-linear electro-mechanical systems is reported. It requires "non-geometric" data such as tolerance-cost models and probabilistic parameters. If tolerance synthesis turns out to be useful, this and other recent efforts [11,12] merely underscore the need to incorporate manufacturing related data in product models. Perhaps more fundamental is the issue of representing geometric uncertainties. While developments in computer hardware and application software have advanced, the representation of a non-ideal world, in which noise abounds and in particular dimensions are not nominal, has not been fully embraced by CAD/CAM researchers. Work in geometric modeling such as [7,18] and probabilistic models in section 3.1 and 3.2 are but the first steps from different directions. It is hoped that this work will generate a critical mass of researchers not only in the modeling but also in the computation of geometric uncertainties. In turn, such an effort will enable designers to fold some of the "downstream" considerations such as manufacturability and cost into the design stage. 22

ACKNOWLEDGMENT This work was supported in part by Center for Research in Integrated Manufacturing at the University of Michigan, Ann Arbor as well as a grant from the Ford Foundation. We are thankful to Dr. R. Saigal of the Department of Industrial and Operations Engineering at the University of Michigan, Ann Arbor for supplying MP5-FIXPT, the code for computing a fixed point. 23

REFERENCES [1] Dimensioning and Tolerancing, ANSI Standard Y14.5M-1982, American Society of Mechanical Engineering, New York, 1982. [2] Baird, H.S., "Fast Algorithms for LSI Artwork Analysis," J. of Design Automation and Fault Tolerant Computing, Vol. 2, 1978, pp. 179-209. [3] Balling, R.J., Free, J.C., and Parkinson, A.R., "Consideration of Worst-Case Manufacturing Tolerances in Design Optimization," Trans. of ASME, Journal of Mechanisms, Transmissions, and Automation in Design, Vol. 108, Dec. 1986, pp. 438-441. [4] Bjorke, O., Computer Aided Tolerancing, Tapir Press, Norway, 1978. [5] Dong, Z. and Soom, A., "Automatic Tolerance Analysis from a CAD Database," ASME Paper No. 86-DET-36, 1986. [6] Evans, D.H., "Statistical Tolerancing: The State of the Art, Part II, Methods for Estimating Methods," Journal of Quality Technology, Vol. 7, No. 1, pp. 1-12, January 1975. [7] Gossard, D.C., Zuffante, R.P., and Sakurai, H., "Representing Dimensions, Tolerances, and Features in MCAE Systems," IEEE CG&A, March 1988, pp. 51-59. [8] Greenwood, W.H. and Chase, K.H., "A New Tolerance Analysis Method for Designers and Manufacturers," Trans. of ASME, Journal of Engineeringfor Industry, Vol. 109, pp. 112-116, May 1987. [9] Kirkpatrick, E.G., Quality Control for Managers and Engineers, John Wiley and Sons, Inc., New York, 1970. [10] Lauther, U., "4-dimensional Binary Search Trees as a Means to Speed Up Associative Searches in the Design Verification of Integrated Circuits," J. of Design Automation and Fault Tolerant Computing, Vol. 2, No. 3, July 1978, pp. 241-247. [11] Lee, W-J. and Woo, T.C., "Tolerances: Their Analysis and Synthesis," Technical Report 86-30, Depr. of Industrial and Operations Eng., Univ. of Michigan, Ann Arbor, Michigan; to appear in Trans. of ASME, J. of Eng. for Industry. [12] Lee, W-J. and Woo, T.C., "Optimum Selection of Discrete Tolerances," Technical Report 87-34, Depr. of Industrial and Operations Eng., Univ. of Michigan, Ann Arbor, Michigan; to appear in Trans. of ASME, J. of Mechanisms, Transmissions and Automation in Design. [13] Mead, C. and Conway, L., Introduction to VLSI Systems, Addison-Wesley Publishing Company, 1980. [14] Michael, W. and Siddall, J.N., "The Optimization Problem with Optimal Tolerance Assignment and Full Acceptance," Trans. of ASME, J. of Mechanical Design, Vol. 103, Oct. 1981, pp. 842848. 24

[15] Michael, W. and Siddall, J.N., "The Optimal Tolerance Assignment with Less Than Full Acceptance," Trans. ofASME, J. of Mechanical Design, Vol. 104, Oct. 1982, pp. 855-860. [16] Montgomery, D.C. and Johnson, L.A., Forecasting and Time Series Analysis, McGraw-Hill Book Co., pp. 99-126, 1976. [17] Peat, A.P., Cost Reduction Charts for Designers and Production Engineers, The Machining Publishing Co. Ltd., Brighton, 1968. [18] Requicha, A.A.G. and Chen, S.C., "Representation of Geometric Features, Tolerances, and Attributes in Solid Modelers Based on Constructive Geometry," IEEE Journal of Robotics and Automation, Vol. RA-2, No. 3, Sep. 1986, pp. 156-166. [19] Rockafellar, R.T., Convex Analysis, Princeton University Press, 1970. [20] Saigal, R, "Fixed Point Computing Method," in Operations Research Support Methodology, (Ed. Albert G. Holzman), Marcel Dekker, Inc., pp. 545-566, 1979. [21] Spotts, M.F., "Allocation of Tolerances to Minimize Cost of Assembly," Trans. of ASME, Journal of Engineering for Industry, Aug. 1973, pp. 762-764. [22] Wilde, D. and Prentice, E., "Minimum Exponential Cost Allocation of Sure-Fit Tolerances," ASME Paper No. 75-DET-93. [23] Zangwill, W.I., Nonlinear Programming - A Unified Approach, Prentice-Hall Inc., Englewood Cliffs, New Jersey, 1969. 25