OPTIMUM SELECTION OF DISCRETE TOLERANCES Woo-Jong L.e Tony C. Woo Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, MI 48109-2117 Technical Report No. 87-34 December, 1987

OPTIMUM SELECTION OF DISCRETE TOLERANCES WOO-JONG LEE TONY C. WOO Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, Michigan 48109-2117 December, 1987

ABSTRACT Tolerance determination involves considerations from manufacturing, design, and assembly. Along with minimum cost and maximum functionality and interchangeability, the practice of tolerancing urges a process engineer to choose an appropriate manufacturing process as well. This situation is formalized by using a discrete model. For an optimum selection of tolerances from given tolerances of various manufacturing processes, minimization of manufacturing cost is achieved under the constraints of tolerance stack-ups. A random variable and its standard deviation are assigned to a dimension and its tolerance. This probabilistic approach enables trade-off between performance and tolerance but it also suggests stochastic optimization. With the aid of a notion called the reliability index [8], tolerance selection is formulated as an integer programming problem. A branch and bound algorithm for ensuring an optimum selection is developed by exploiting the special structure of the constraints. To make the enumeration tree small, monotonic relations among the reliability index, cost, and tolerance are examined. The algorithm is tested with examples. Keywords: Tolerancing, Combinatorial Optimization, Branch-and-Bound

1. INTRODUCTION Tolerance is the total amount by which a specific dimension in an engineering drawing is permitted to vary [1]. It is specified by the difference between the upper and the lower limits of a dimension. Once assigned, tolerance reflects the cost of manufacturing. Reduction of cost can be achieved by increasing tolerance but such an increase must be constrained by performance (functionality and interchangeability). A great deal of research [3-7,10,18,21,23] on tolerancing have been devoted to the resolution of this trade-off between cost and performance. However, they are concerned with tolerance analysis - that is, for a given set of tolerances, find the effect on cost or performance. It may be noted that tolerance is an input. If the particular combination of tolerances does not meet the criteria, some or all of the input have to be changed. And, the analysis procedure iterates. This potentially combinatorially complex situation of tolerance selection raises the concern for convergence. In an interactive mode [4-6,10,21], convergence depends on the "experience" of the user. However, because of the nature of input selection, there is no assurance of optimality. In a more resource abundant environment, Monte Carlo simulation [7,21] can be adopted. While, with simulation, the solution can be made arbitrarily close to the optimum, the amount of resource demanded can be arbitrarily large. The synthesis of tolerance, an alternative to manual data preparation and random number generation, remained as an intellectual and practical challenge. Recently, tolerance synthesis by non-linear optimization have been reported [11,14,15]. In them, tolerance is treated as a continuous variable such that the relationship between tolerance and cost takes the form of a continuous function as illustrated in Figure 1 -(a). <Insert Figure 1> Tolerance can be thought of as a discrete variable. The eight classes of fit in the ANSI standard [1] is an example. For each class of fit, there is an associated 1

2 manufacturing process. While a process p1 capable of producing a tight tolerance t1 may be used to produce a less stringent tolerance t2, its cost c1, however, may be higher than c2, that of another process P2 capable of producing t2. In this paper, a discrete tolerance model such as the one illustrated in Figure 1-(b) is adopted. That each process Pi is the most efficient in tolerance and in cost is also understood. Because of the discrete nature of the tolerance-cost model, the problem of synthesizing tolerances becomes one of tolerance selection. This paper presents the development of a procedure that optimizes the selection. Suppose n tolerances are to be selected for the n dimensions and each tolerance is to be selected from a set of si manufacturing processes, l1ion. For each dimension xi, the s. available manufacturing processes will be referred to as the PSMPi (Predetermined Set of Manufacturing Processes for the i-th dimension). Tolerance selection starts with the given PSMP. for 1li<n. Only one manufacturing process is to be selected from each PSMP. and this condition will be referred to as the selection condition. In other words, the selection condition for dimension x. is described by using the 0-1 variables, Yik, for 1 k-s. such that yi, + - + Yis = 1, where Yik= 1 signifies that the k-th manufacturing process (tolerance) is chosen from PSMP.. As a criterion for selection, cost minimization is used. The cost minimization selection, however, -is constrained by stack-up conditions for functionality and interchangeability. Consider Figure 2. Suppose the clearance between the two components in Figure 2-(a) is to be within limits -0.1 and 0.2. Figure 2-(b) illustrates the area Rs for satisfying the following stack-up conditions: F1(X)= x1 - x2 - 0.1 0 (1) F2(X) = - x1 + x2 + 0.2 > 0. Suppose the nominal dimensions for the dimensions x1 and x2 are 5.00 and 4.85, respectively. If two manufacturing processes are available for x1 and four for x2 as shown

3 in Figure 2-(c), the number of feasible solutions that satisfy the selection condition is eight and their relations with the stack-up conditions are shown in Figure 2-(d). Notice the overlap between Rs and the rectangle specified by the tolerances. For example, the rectangle specified by (t12, t24) is entirely covered by Rs, whereas a smaller fraction of the rectangle specified by (t12, t21) is covered by Rs. The fraction of coverage determines the level that the dimension within tolerance limits satisfies the stack-up conditions. Now, cost minimization leads to the selection of (tl1, t2l), but this selection gives the worst result - with the least fraction of coverage in the in-tolerance area. If a higher level of satisfaction of the stack-up conditions is deemed desirable, some of the manufacturing processes would have to be replaced by those with having smaller tolerances and the feasibility test for the stack-up conditions is iterated. <Insert Figure 2> Tolerance selection is formulated here as a combinatorial optimization problem by treating cost minimization as the objective function and stack-up conditions and selection conditions as the constraints. The overall procedure for tolerance selection is outlined in Figure 3. <Insert Figure 3> Concept in probability is used. Since tolerance implies randomness, a random variable and its standard deviation are respectively associated with a dimension and its tolerance. The probabilistic approach enables the partial satisfaction of the stack-up conditions. By permitting a fraction of the assemblies to be "out-of-spec," a reduction in cost may be achieved by selectively increasing some of the tolerances. This approach is considered to be advantageous over the deterministic approach [3,5,14] for the 100% "inspec" case only. Suppose an inequality F(X)>0 represents a certain stack-up condition, where X is a random vector composed of dimensions. The level of satisfaction of the stackup condition can be described by the following multiple integral:

4 fF(X) f(X) dX (2) where f(X) is the multivariate probability density function (p.d.f.) of X. F(X), the function for stack-up condition, is nonlinear if non-rectilinear shapes and/or dimensions are in an engineering drawing. See, for example, F3(X) and F4(X) in Figure 4. (Those two conditions specify that the angular difference between 81 and 62 is to be within ~(7r/180) radians.)1 Now, suppose the stack-up conditions are linear. Tolerance selection then can be formulated as a pure 0-1 linear integer programming problem because of the following property: under the assumption of independence, the variance of a linear function can be expressed as the linear sum of the variances of the constituting dimensions. Hence, binary tree enumeration such as Balas' 0-1 algorithm [2] can be used for tolerance selection [9,16,23]. Unfortunately, such is not the case in general as engineering drawings are not always rectilinear. Furthermore, there is no rule for expressing the variance of a nonlinear function, such as F3(X), in terms of variances of its constituting dimensions. <Insert Figure 4> To compute the multiple integral of equation (2), simulation or numerical methods may be considered. But, since it is an inner loop in the overall algorithm for tolerance selection (as illustrated in Figure 3), a fast approximation is sought. In this paper, the nonlinear function F(X) is approximated by a hyperplane. To retain accuracy, the area that is probabilistically the densest is preserved by computing the distance from the hyperplane to the origin of standardized coordinate system. A notion called the "reliability The two conditions F3(X)> 0 and F4(X) 0 are derived by taking the following steps: - (7r/180) c 6 - 02 _ 7r/180 tan(- (7r/180)) 5 tan(61 - 2 ) < tan(7r/180) tan01 - tanG2 - tan (7r/180) < - tan(Tr/180) 1 + tan9ltan92 (X8 - X7)(X2 - x3) - (X6 - X5)(Xo - X9) - tan (7r/180) <. S tan(7r/180) (x10 - X9)(X2 - 3) + (8 - x7)(x6 - 5)

5 index" introduced by Hasofer and Lind [8] is used for computing this distance. With the aid of the reliability index for computing (2), the tolerance selection problem can be formulated as the following nonlinear 0-1 integer programming problem: n si Min E E ciy1ik i=l k=l (3) subject to 3j 2- qj, forj=l,-,m (3-1) Si E Yik = 1, for i= l,.-,n (3-2) k=l 1 where yik = 0 or 1 for k=l,-, si and i=l,-.,n where cik is the cost incurred when using the k-th manufacturing process for dimension xi. The constraint (3-1) states that the j-th stack-up condition, whose satisfaction level is approximated through the reliability index P3., should be satisfied with at least the given probability qj. The constraint (3-2) describes the selection rule such that only one manufacturing process is selected from the given PSMP.. The notation is summarized in Table 1. <Insert Table 1> An algorithm for (3) that comes to mind first is the binary tree enumeration since the formulation takes the form of a pure 0-1 integer programming problem. The number of solutions, however, is of 0(2N ), where N is the total number of manufacturing processes. If each PSMP. for 1 _i n has s. elements (manufacturing processes), then n N= si. For example, if two and four different manufacturing processes are considered i= 1 for the dimensions x1 and x2, then s1=2, s2=4 and N=6. Tolerances (tll, t12) and (t21 t22, t23, t24) are associated with the dimensions xl and x2, respectively. The number of solutions for the binary tree enumeration becomes 0(26) though only eight solutions, i.e., (t't21) (tlt22 ) (tit) (tt) ) (t123t22) (tlt, (t t23) a-and ( anrd a ctually feasible to constraint (3-2). A branch-and-bound algorithm is developed in this paper by

6 exploiting the special structure of the constraint (3-2), the so called "multiple choice constraint." It is noted that the computation time for the branch-and-bound algorithm can be n 0(ITsi). Hence, making the enumeration tree smaller is essential. The monotonic i=l relations among cost, performance and tolerance - as tolerance decreases, cost and performance increase - enable efficient pruning and fathoming operations in the algorithm. Monotonicity is also used to simplify the lower bound computation and the feasibility test in each iteration. Furthermore, to facilitate fathoming by cost, a heuristic procedure requiring O(N) 'feasibility tests is given to provide an initial incumbent value. Finally, the practical run time of the algorithm (about 3 CPU seconds) is illustrated by one of examples (for 12 dimension variables, each with up to 5 manufacturing processes). 2. FORMULATION A random vector X =(x,-,xn)t is used to represent the n dimensions in an engineering drawing to capture the randomness of manufacturing processes. Mean and standard deviation vectors for X, denoted by X and E, are associated with nominal dimensions and tolerances, respectively. Dimension variables x.,s are assumed to be independent with each other and to follow the normal distribution [13]. Stack-up conditions are assumed to be given and are represented by the functional form F.(X) for l<sjm, that are inequalities. Each inequality divides the dimensional space into a safe region RS = { X | Fj(X)O0} and a fail region RF ={ X F.(X)<0}. The 3j J J J safe region Rs of satisfying all the stack-up conditions is the intersection of Rs, 1 <jm. That is, RS = njlRs. Figure 2-(b) illustrates the safe region specified by the two stack-up conditions of (1). The probability of satisfying a stack-up condition F.(X) >0 is then described as:

7 +(X; V) dX (4) JFj(X)_> 0 The objective of tolerance selection.. is to select tolerances (standard deviations) by minimizing the manufacturing cost. The selected tolerances are constrained to satisfy the stack-up condition F.(X) 0 at a desired probability level 1-6.. These constraints are J J referred to as reliability constraints. Also, by the nature of tolerance selection, only one tolerance should be selected from a given PSMP. These selection constraints are referred to as selection constraints. Then, the problem can be formulated as: n Si Min E E cikyik i=1 k=l subject to (5) I/ +<^ (X; V) dX 2 1-6., for j = l,,m (reliability constraints) Fj(X)a0 J Si E Yik = 1, for i= 1,- -,n (selection constraints) k = 1 where ik = 0 or 1 fk=l, —,si and i=l,-,n As an example, consider Figure-2 for which s1=2 and s2=4. Tolerance selection is then formulated as follows: Min c 11ll + c12Y12 + c21Y21 + c22y22 + c23Y23 + c24Y24 subject to I1(X) x1-x2- 01>O (X; V)dX > 1-61 1F=(X)= X- X2 -0.1O0 O/ (X; V) dX > 1-62 JF(X)=-x1+x2+0.2>O (X Y11 + Y12 = 1 Y21 + Y22 + Y23 + Y24 1 where yll, Y12' Y21, Y22' Y23' Y24 are 0-1 variables and

8 61' 62 are permissible dissatisfaction levels for F,(X)>0, F2(X):0. When solving problem (5), two difficulties arise. First, the reliability constraints of (5) involve a multiple integral bounded by nonlinear functions. Evaluating it numerically is time consuming. Second, the selection constraints of (5) involve a large number of n solutions, i.e., IHsi. The first problem is dealt with in the remainder of this section while i=l the second problem is treated in the next section. Observe that the integral of the reliability constraints of (5) is to be taken in the safe region Rs. Since Rs is to be integrated under the multivariate normal p.d.f., the j j accuracy of an approximation for (4) depends on the preservation of the probabilistically densest area. Suppose the dimension variables are standardized (to be described in Appendix A) such that they, denoted by z.'s, follow the standard normal distribution. Then, the vicinity of the origin in the standardized coordinate system (standard system, for short) is probabilistically the densest and the density decreases exponentially from the origin. Linearization is performed by taking the tangent hyperplane at a point on the stackup function having the minimum distance from the origin in the standard system. This minimum distance is called as reliability index [8] and is denoted by /3. (The solution scheme for computing 3 is also explained in Appendix A). Then, the probability of covering one side of the tangent hyperplane, P(Rs), can be computed based on the univariate normal distribution, because rotational symmetry is preserved in the standard system as illustrated in Figure 5. This is summarized in Lemma 1. <Insert Figure 5> Lemma 1. If the stack-up function F.(X) has a reliability index 3., then P(Rsj) -4 (). (6 Si The accuracy of (6) depends on the curvature of the stack-up function. As long as the

9 radius of the curvature at the expansion point is large compared to the reliability index as in most practical cases, this approximation is quite accurate [12]. For a linear stack-up function, P(Rs) = )(3.). j J Based on Lemma 1, formulation (5) can be converted into the following deterministic optimization problem: n Si Min E E CikYik i=1 k=l subject to ' 2 3.- (1-6.), for j = 1,-.,m (reliability constraints) Si E Yik = 1, for i= 1,-.. n (selection constraints) k = 1 k=l where Yik = 0 or 1 for k= l,.-,si and i=l, —.,n The value - 1(1- 6.) in the reliability constraints can be looked up in the standard normal distribution table. 3. ALGORITHM A branch-and-bound algorithm for efficient tree enumeration is developed in this section. To make the enumeration tree small, monotonic relations among the reliability index, cost and tolerance are exploited. 3-1. Monotonicity A function g(X) is said to be monotone nonincreasing in every element xi s if X1 > X2 results in g(X1) < g(X2). The monotonicity between tolerance and cost is generally understood as: the more tolerance the less cost. That is, 6C.(oi)/9ai < 0 where Ci.(a.) is the cost function in terms of the standard deviation (i.e., tolerance). Indeed, most tolerance-cost models [19,20,22]

10 exhibit this relationship. Without loss of generality, this strict nonincreasing monotonicity is described by taking the following ordering: ci < ci2 < ci3 < cis for i= 1,...,n i i 1is ail > aci2 > ai3 > is fori= l,-,n The monotonicity between tolerance and the reliability index is less obvious. But it can be established based on the following observation: If a certain standard deviation is reduced, the distance from the origin of the standard system to a point on the stack-up function becomes greater than or equal to the distance before the reduction. This observation can be generalized as follows: Lemma 2. Suppose dj. is the distance in the standard system from a point Zo on the j-th stack-up function to the origin. Then, 9d. o /. < 0 for 1 i n and 1sj m. jO 1 Proof. The proof is given in Appendix B. ~ From this lemma, it follows immediately that the minimum distance j3. also decreases with the decrease of the standard deviations. That is, 9j3. / Oa. 0 (7) Inequality (7) reconfirms the trade-off between tolerance and performance: tolerance represented by standard deviation has an inverse relationship with performance implied by the reliability index. 3-2. Branch-and-Bound The enumeration tree used in this paper is depicted in Figure 6. To denote a partial solution, a Ixn row vector Y is used. For example, Y=(2,s2,0,0, -,0) means that for dimension x1 the second manufacturing process is selected from PSMP1 and for dimension 2 the s2-th manufacturing process from PSMP2. The value 0 in Y shows that the decision for the corresponding dimension has not been made yet. Notice that, by using the vector Y, the selection constraints can be handled implicitly. That is, if it is decided that a

11 dimension is to be produced by a certain manufacturing process, the remaining manufacturing processes in the same selection constraint (i.e., the same PSMP) are set to 0. < Insert Figure 6> The following branch-and-bound procedure TOL-B&B provides a way of tracing the enumeration tree. Here, the terminology of branch-and-bound [17] is assumed. A flowchart is given in Figure 7. < Insert Figure 7 > Procedure TOL-B&B Begin Step 1. Initialize the candidate list to consist of partial solution vectors (1,0,.*-,0),.-.,(sl,0,*.,0), and set the incumbent value C* to an arbitrary large number. Set the incumbent solution, denoted by a 1xn row vector C, to (0,0,-..,0), where (0,0,..,0) signifies that no decision has been made for any dimension. Step 2. Go to Step 3 if the candidate list is not empty. Otherwise, stop and the current incumbent solution is then optimum except the case in which the incumbent value is an initial value set in Step 1. (The exceptional case happens only when there is no feasible solution.) Step 3. Select a candidate problem from the candidate list. The selection rule is LIFO (last-in-first-out). The candidate list is maintained in a stack. Step 4. Calculate the lower bound CL for the candidate problem. Suppose the current partial solution for the candidate problem is Y=(i,i2, *,i,0, O,0). n Then, the lower bound CL for Y is c i ++ri + c. fi r j-r+ 1 Step 5. (Fathoming Criterion 1) If CL>C*, go to Step 2. Step 6. (Fathoming Criterion 2) Modify Y=(i,i2,..., ir,0,0,-,0) with Y-=(il,i2,, irsr+ 1,..,sn). Check if this Y* is feasible. If it is not feasible, go to Step 9. Step 7. (Fathoming Criterion 3) If r=n (terminal node), go to Step 8. Otherwise, go to Step 10. Step 8. Update the incumbent solution C with Y and the incumbent value C* with n Sc... Go to Step 2. j=1 JJ

12 Step 9. Prune the left siblings of the current partial solution from the candidate list. For example, if ir=3, the candidates (ili2.. ir-,1,0,,0) and (il,i2,-,ir_ 1,2,0, -',0) can be deleted. Go to Step 2. Step 10. Separate the candidate problem and add its offsprings to the candidate list. The offsprings of Y are (il,i2,.,ir, 1'0'...0), (il,i2,.,ir,2,0,...,0),.-, (il,i2,'-,irsr+,0,'-,0). Go to Step 2. end; Steps 4 and 6 are based on the monotonic relations among the reliability index, cost and tolerance. In Step 4, the cost ordering and its strict nonincreasing monotonicity is used to compute the lower bound such that CL for the partial solution Y=(i1,-,ir,0, —,0) is equivalent to the cost for the selection (il,,',ir,1, -:,1). Similarly, in Step 6, to check for the feasibility of Y, Y*=(i, ir,s +1,,sn ) is tested based on the nonincreasing monotonicity of the reliability index of (7). Now, to save computation time, the following observations are made. Observation 1. If the current node is the right-most sibling, its partial solution for feasibility test is the same as that of its parent. From this observation, the feasibility test in Step 6 can be omitted if the candidate problem is the right-most offspring. In a similar manner, the computation for the lower bound in Step 4 can be expedited with the following observation. Observation 2. If the current node is the left-most sibling, its lower bound in cost is the same as that of its parent. Hence, the computation in Step 4 can be omitted also if the candidate problem is the leftmost offspring. More generally, this computation can be done in the following way: Observation 3. Provided that the partial solution is (il,.,i,0,'",0), the j-th left offspring of the current partial solution has the following lower bound in cost:

13 CL of the j-th offspring = CL of the parent + c r+. - cr+ 1,1 Note that Observation 2 is a special case of Observation 3, since Cr+ j + 1,1. The pruning operation of Step 9, which contributes to making the enumeration tree smaller, is based on the following observation: Observation 4. For siblings having the same parent, the lower bound in cost and the feasibility of the sibling to the right are greater than those of the sibling to the left. Lastly, to facilitate fathoming by cost in Step 5, the following heuristic procedure TOL-INITIAL is used for generating a reasonable initial incumbent value C*. Procedure TOL-INITIAL Begin Step 1. Start with Y =(sl,,sn) where i=0. Set the integer variables "stop-check" and "current-flag" to 1. The variable stop-check is used to check the stop of the circular search of feasible solution. And, the current-flag indicates the dimension being considered. Step 2. If the manufacturing process index for the dimension indicated by the current-flag is the first one, go to Step 6. Step 3. Change the manufacturing process index of the dimension indicated by the current-flag to the manufacturing process index one lower than the current one. Let this changed solution be Y Step 4. Test if Yi+ is feasible. If feasible, stop-check: =0 and go to Step 7. Otherwise, go to Step 5. Step 5. If Y'+ =(1,1,..,1,1), then stop since there is no feasible solution. Otherwise, Yi =yi Step 6. stop-check:= stop-check + 1. Step 7. If current-flag = n, then current-flag:= 1. Otherwise, current-flag: = current-flag + 1. Step 8. If stop-check = n + 1, then C: = Y +1 and stop. Otherwise, go to Step 2. end;

14 Procedure TOL-INITIAL starts with the manufacturing process having the highest cost. It reduces the cost through circular search until cost reduction is impossible because of infeasibility. TOL-INITIAL involves O(N) feasibility tests in the worst case. In the example to follow, it is assumed that in Step 1 of TOL-B&B, the initial solution C is now obtained from TOL-INITIAL. Since TOL-INITIAL checks for the existence of feasible solutions in Step 5, the use of TOL-INITIAL simplifies Step 2 of TOL-B&B as follows: if candidate list is empty, stop and the incumbent solution is optimum. 4. EXAMPLES Algorithm TOL-B&B has been programmed in PASCAL and run on the University of Michigan IBM 3090-400/VM under the MTS operating system. Two examples are given. Example 1, based on the simple assembly of Figure 2-(a) with two dimension variables and two linear stack-up conditions, traces the flow of the algorithm. In particular, effective pruning by TOL-B&B is illustrated. Example 2 is based on the assembly in Figure 4, with twelve dimension variables, each with three to five selections for a total of 1,574,640 possible solutions. Example 1. Consider the assembly in Figure 2-(a) in which stack-up conditions are specified by the two inequalities of (1). These two conditions define the safe region Rs in the relevant positive dimension space as shown in Figure 2-(b). Suppose each stack-up condition of (1) is to be satisfied with a 97.468% (=v/095) confidence level. Then, 61=62=1-/.95. Here, two and four different manufacturing processes are respectively considered for the dimensions x1 and x2, i.e., s =2, s2=4, and N=6. The corresponding tolerance-cost model is illustrated in Figure 2-(c). The discrete tolerances tik as shown in Figure 2-(c) are assumed to signify 99.73% two-sided confidence intervals. That is, tik is the same as +3aik such that aik tik/6. Note that these standard deviations aik are used to compute

15 /j's in the reliability constraints of (3-1). The dimensions x and x are assumed to have the nominal dimension values 5.00 and 4.85 respectively, i.e., (x1,x2)= (5.00,4.85). The relationship between tolerances and the nominal dimensions is illustrated in Figure 2-(d). To obtain an initial solution for procedure TOL-B&B, procedure TOL-INITIAL is used. It finds an initial solution (2,3): the second manufacturing process with tolerance t12 is selected for dimension xl and the third manufacturing process with tolerance t23 is selected for dimension x2. This initial solution incurring a cost of 47.0 is obtained in four iterations of TOL-INITIAL. These four iterations start respectively with solutions (2,4), (2,4), (2,3) and (2,3), and perform the feasibility test in Step 4 with solutions (1,4), (2,3), (1,3) and (2,2). The solution (2,3) and its cost of 47.0 are used as the initial incumbent solution and its incumbent value in Step 1 of procedure TOL-B&B. TOL-B&B traverses the enumeration tree as illustrated in Figure 8. In that figure, the nodes indicated by solid circles are the nodes traversed by TOL-B&B while the dashed nodes are the non-traversed ones. The number in a traversed node represent the traversal sequence. This numbering shows that TOL-B&B is based on the depth-first search. When the procedure first visits node 1, the lower bound in cost for the partial solution (2,0) becomes 32.0. Since this lower bound is less than the incumbent value 47.0, the feasibility test is done with solution (2,4). It turns out to be feasible so that the next traversal node is node 2 having the solution (2,4). 'Nodes 2 and 3 are fathomed since their lower bounds in cost are not less than the incumbent value 47.0. Nodes 4 and 5 are fathomed because they are infeasible. It is noted here that TOL-B&B obtains the optimum solution with five iterations whereas the possible solutions for binary tree enumeration is 64 (=26). Figure 8 also shows how the monotonicity among tolerance, cost, and the reliability index works for partial enumeration. The pruning of node A is due to the monotonicity between tolerance and the reliability index: the reliability indices of the left-siblings are less than or equal to those of the current node. That is, node A is infeasible because of the infeasibility of node 4. In the case of node B, the solution for feasibility test is the same as

16 the solution of its parent, i.e., node 5, by Observation 1. Since node 5 turns out to be infeasible, node B is also infeasible and this infeasibility makes possible the pruning of node C as in the case of node A. In this example, the initial incumbent solution obtained by TOL-INITIAL is the optimum. <Insert Figure 8> Example 2. The assembly is shown in Figure 4. The first and second stack-up functions are for specifying the vertical and the horizontal clearances between two parts, respectively. The third and fourth stack-up conditions show the angular difference condition between angles 01 and 62 as mentioned in the footnote in Section 1. The last two functions show that the size difference of the horizontal lengths of two parts should be within 0.01. F3(X) and F4(X) are nonlinear and the others are linear. The nominal dimensions for the 12 dimensions are given as X = (50.0, 40.00125, 20.05, 9.9985, 9.9985, 30.00, 10.00, 30.00, 10.05, 30.00, 40.00, 50.00)t. The other input data for cost and standard deviations are listed in Table 2. < Insert Table 2 > Suppose each of the six stack-up conditions is to be satisfied at 99.1488% (=(0.95)16) level, i.e., =..=4 = 1- (0.95) 16. The output produced by TOL-B&B and its statistics are given in Table 3. The initial incumbent solution by TOL-INITIAL is (2, 2, 2, 2, 2, 2, 1, 1, 1, 3, 4, 3) and its corresponding incumbent value is 275. Starting with this initial incumbent solution, the optimum solution of (3,2,1,3,2,2,2,1,1,2,2,1) is obtained in 2554 iterations which is 0.16% of the total number of possible selections 1,574,640. This result (in 3.076 CPU seconds) is tabulated and compared to the one obtained without using TOL-INITIAL (in 3.884 CPU seconds) in Table 3. <Insert Table 3 > Under optimum selection, the reliability indices of the given stack-up functions F (X,

17 for 1 <j6 are shown in the second column of Table 4. This column shows that the reliability index obtained for each stack-up function is almost the same as the reliability index 2.38617 for the desired satisfaction level 99.1488%. By the definition of the reliability index, it corresponds to the minimum distance from each stack-up function to the origin in the standard system. This distance is used here to measure the satisfaction level covering the half-space safe region obtained by the hyperplane approximation of a stack-up function. By Lemma 1, these satisfaction levels are approximately equal to (j3.) for 1 <j 6. Those are listed in the third column of Table 4 and their differences from the desired level of 99.1488% are shown in the fourth column of Table 4. The reason that the obtained reliability indices are not exactly the same as the desired reliability index is due to the discrete nature of tolerance selection. By Lemma 2 and inequality (7), the reliability index higher than the desired level needs a smaller tolerance because of the negative monotonicity of the reliability index to tolerance. The smaller tolerance, however, in turn incurs a high cost because of the negative monotonicity of cost to tolerance. Hence, the selection is optimized so as to reduce the gap between both sides of the reliability constraint of (3-1) to as small a value as possible. <Insert Table 4> 5. SUMMARY It is recognized that the arena of CAD, CAM and robotics is populated with "islands of technology." While tolerancing may be construed as another island, it has the integrative element that bridge design, manufacturing, assembly and testing. The intent of this work is to fold the traditionally "down-stream" considerations such as functionality, interchangeability and cost to the design stage. Formulated probabilistically, the problem of automatic tolerancing permits trade-offs between these considerations. The contribution of this work is in practice. As born by the practical considerations such as the association of tolerance to discrete manufacturing processes and the

18 observations on monotonicity hence the fathoming criteria, the branch-and-bound algorithm as implemented is suitable for near real-time tolerancing. In addition, the algorithm guarantees an optimum selection from given PSMPs under linear as well as nonlinear stack-up conditions.

19 REFERENCES [1] ISO System of Limits and Fits, General Tolerances and Deviations, R286-1962, American National Standards Institute, New York (1962). [2] Balas, E., "Additive Algorithm for Solving Linear Programs with Zero-One Variables," Operations Research, 13, 517-546 (1965). [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, 108, 438-441 (Dec. 1986). [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] Greenwood, W.H. and Chase, K.H., "A New Tolerance Analysis Method for Designers and Manufacturers," Trans. of ASME, Journal of Engineering for Industry, 109, 112-116 (May 1987) [7] Grossman, D.D., "Monte-Carlo Simulation of Tolerancing in Discrete Parts Manufacturing and Assembly," Report No. STAN-CS-76-555, Computer Science Department, Stanford Univ. (May 1976) [8] Hasofer, A.M. and Lind, N.C., "Exact and Invariant Second-Moment Code Format," ASCE J.Eng.Mech.Div., 100, EM1, 111-121 (1974). [9] Huang, J. and Ostwald, P.F., "A Method for Optimal Tolerance Selection," ASME Paper No. 76-WA/DE-23 (1976). [10] Kirkpatrick, E.G., Quality Control for Managers and Engineers, John Wiley and Sons, Inc., New York (1970). [11] Lee, W.J. and Woo, T.C., "Tolerancing: Its Distribution, Analysis, and Synthesis," Technical Report 86-30, Dept. of Industrial and Operations Eng., Univ. of Michigan, Submitted to Trans. of ASME, J. of Eng. for Industry (1986) [12] Madsen, H.O., Krenk, S. and Lind, N.C., Methods of Structural Safety, Prentice-Hall, Inc., Englewood Cliffs, New Jersey (1986). [13] Mansoor, E.M., "The Application of Probability to Tolerances Used in Engineering Designs," Proc.Inst.Mech.Eng., 178, 1, 29-51 (1963). [14] Michael, W. and Siddall, J.N., "The Optimization Problem with Optimal Tolerance Assignment and Full Acceptance," Trans. of ASME, Journal of Mechanical Design. 103, 842-848 (Oct. 1981) [15] Michael, W. and Siddall, J.N., "The Optimal Tolerance Assignment with Less Than Full Acceptance," Trans. of ASME, Journal of Mechanical Design, 104, 855-86( (Oct. 1982) [16] Monte, M.E. and Datseris, P., "Optimum Tolerance Selection for Minimum Manufacturing Cost and Other Design Criterion," ASME Paper No. 82-DET-35

20 (1982). [17] Murty, K.G., "Linear and Combinatorial Programming," John Wiley and Sons, Inc., New York, 437-480 (1976). [18] Parkinson, D.B., "The Application of Reliability Methods to Tolerancing," Trans. of ASME, Journal of Mechanical Design, 104, 612-618 (July 1982) [19] Peat, A.P., Cost Reduction Charts for Designers and Production Engineers, The Machining Publishing Co. Ltd., Brighton (1968). [20] Spotts, M.F., "Allocation of Tolerances to Minimize Cost of Assembly," Trans. of ASME, Journal of Engineering for Industry, 762-764 (August 1973). [21] Turner, J.U., "Tolerances in Computer-Aided Geometric Design," Ph.D. dissertation, Rensselaer Polytechnic Institute, Troy, New York (1987). [22] Wilde, D. and Prentice, E., "Minimum Exponential Cost Allocation of Sure-Fit Tolerances," ASME Paper No. 75-DET-93 (1975). [23] Wilde, D., "Simplifying Discrete Tolerance Assignment," ASME Paper No. 75-DET106 (1975).

21 APPENDICES Appendix A. Reliability Index The Euclidean distance of a point Z in the standard system to the origin is (ZtZ)1/2 X. - X. 1 1 The standardized vector Z is obtained by the transformation z =- for l<i<n. i. Hence, (ZtZ)/2 = {(X_-X)tV-'(X-X)}112 The reliability index can be obtained by solving the following problem: Min,32=(X-X)tV- (X-X) subject to (8) F(X) ' 0 Here, the objective function is expressed as 32 instead of i3 since the positive definiteness of the covariance matrix V always guarantees the same solution. As a solution scheme for (8), the iterative method based on the Newton-Raphson method [12] is as follows: (k+) (k(X (k)_X)t VF(X(k)) - F(X (k)) X(k+) = X + V VF(X(k)) VF(X(k))t V VF(X(k) where X(k) denotes the solution after the k-th iteration and VF(X) is the nxl gradient vector of F(X) at X. It is noted that this iterative method starts from the nominal dimension point X.

22 Appendix B. Monotonicity of the Reliability Index As shown in Appendix A, the Euclidean distance d. from the origin of the standard system to a point Z0 can be expressed in terms of the original vector X by {(X -)tV (X -X) 1/2, where X is for the point Z0 before standardization. Note that this distance expression corresponds to the equation of an ellipsoid with center X, the semiaxes of which are expressed as the product of d. and the standard deviations. Then, j,0 n (Xoi- i)2 2 d. i=l 2 1 As a standard deviation c. decreases, the distance d. increases. 1 J,O

23 Table 1. Notation Notation Description i= l,...,n j=l,.-.,m k=l,..,si C C Cik CL Fj(X) N qj Rs, RF tk V X X Y Yik Z 6. a. rik 4(X;V) 4,-1) 4)-1(.) dimension index stack-up function index manufacturing process index incumbent solution in TOL-B&B incumbent value in TOL-B&B cost for dimension i and manufacturing process k lower bound in cost for the partial solution Y in TOL-B&B the j-th stack-up function where F.(X) > 0 is the desired condition total number of manufacturing processes, i.e., s1 + -.+s desired reliability of the j-th stack-up condition, i.e., -1(1- j) safe and fail regions formed by F.(X) tolerance of dimension i due to the use of manufacturing process k 2 nxn diagonal variance matrix whose i-th diagonal element is a2 random dimension vector mean vector of X partial solution in TOL-B&B 0-1 decision variable for dimension i and manufacturing process k standardized dimension vector reliability index for the j-th stack-up function permissible dissatisfaction of the j-th stack-up condition standard deviation for dimension i and manufacturing process k multivariate normal p.d.f. having mean X and variance V cumulative standardized normal distribution function inverse cumulative standardized normal distribution function

24 Table 2. Cost and Standard Deviations for Example 2 Process Dimen- 1 2 3 4 5 sion Cost SD* Cost SD* Cost SD* Cost SD* Cost SD* 1 20.0 35.0 23.0 30.0 29.0 25.0 - - - - 2 2.0 2200.0 5.0 2000.0 11.0 1800.0 - - - - 3 13.0 97.0 16.0 96.0 22.0 95.0 - - - - 4 13.0 110.0 16.0 105.0 22.0 100.0 - - - - 5 35.0 3.3 45.0 3.2 65.0 3.1 - - - - 6 35.0 4.1 41.0 4.0 53.0 3.0 - - - - 7 32.0 3.0 39.0 2.9 53.0 2.8 - - - - 8 32.0 2.2 38.0 2.1 50.0 2.0 - - - - 9 2.0 2100.0 5.0 2050.0 11.0 2000.0 - - - - 10 4.0 136.0 6.0 134.0 10.0 132.0 18.0 130.00 - - 11 10.0 97.0 12.0 96.0 16.0 95.0 24.0 94.00 - - 12 16.0 31.0 18.0 30.0 22.0 29.0 30.0 28.00 46.0 27.0 * standard deviation (unit: 10 4)

25 Table 3. Results for Example 2 Data see Table 2 Input n Size (s )s 40 i=l n No. of Selections (I si) (a) 1,574,640 i=1 Run Statistics iterations in TOL-B&B (b) =2553 (3267f') fathoming by cost (C) = 1271 (1719() feasibility checks (d) = 1282 (1548()) fathoming by feasibility = 460 (490(0) incumbent changes = 9 (73(f) Efficiency of TOL-B&B (e) 616.8 (482.0(f)) Run Time 3.076 (3.884(f)) CPU seconds Optimum Selection (3,2,1,3,2,2,2,1,1,2,2,1) Optimum Cost 262.00 Note: (b) = (c) + (d) (e) = (a) / (b) (f): result obtained without TOL-INITIAL

26 Table 4. Satisfaction Level at Optimum in Example 2 Stack-Up Reliability Index Satisfaction Level in % Over-Satisfaction Level in % Condition (i3.) ($(B(j)) ()(3.)-0.991488) 1 2.38697 99.151 0.002 2 2.38618 99.149 0.000 3 2.39801 99.176 0.027 4 2.39556 99.170 0.022 5 2.51101 99.398 0.249 6 2.51101 99.398 0.249 Note: The desired reliability index corresponding to 99.1488% is 2.38617 since $ 1(1-0.991488) = 2.38617

- 27 - Cost Tolerance (a) Continuous Model Cost C 1 C 2 C 3 C 4 L P1 P -1-p I ' P 2.... -.. -- - manufacturing p1 p2 p3 P4 process tolerance t t2 t t4 cost c c c c CIt 2 3 4 9 I p 0.......... - 4 9 — - + - ~ ~ ~ - ~ - - ~-; 9 9 9 9 9I9 9I tl t2 t3 t4 Tolerance (b) Discrete Model F 91ure 1'. Tolerance-Cost Relationship

0o S a ON O _ ___ 0 _ (II '=lh, ~~~~G,!,??", o,,, v — *^~* ',, C- ----- -- gI P I " II I II0...-..-.,,~,,8 \ ~~ -~ r, (t or 3 g~~~~~~~~~~~~~~~~t ) r P H w

- 29 - Tolerance Selection Figure 3. Basic Scheme of Tolerance Selection

suo!ilunI Jeau!luoN pue Jeau!l jo aldwuex3 *' ajn!ij TX = (X) 9 10'0 + ZIX ZI I 10'0 + + + x - =(X) - {( S - 9x)*( LX - 8X)+( x - ZX)*(6x -Ox) } * (0o8 /)u + (E -Z x) (Lx - 8 X) - ( 6x -OIx)*( - 9X) =(X) J {( S - ) * ( - 8 )+( x - (6x - ox) x )*(6x -_ x)} * (081 ) II/ + (SX -9 X) - (x -Z X) *(LX - 8X) ( - 11X)- ( x - x) (LX - 8X) - (gx - 9X) =(x) A 7',, '01. II v 01 v q 1w I - v ~~~~~~~A. ~~~~~~' fil.- 4 l I ------ A —, 8 x 9 x X I r I -da h- i k k I I q i -qw 4 I I X

- 31 - 2 Z Z2 P(RS1 )= P(R 2) = 1 (B) Rs2 i i I i I (B 0) Figure 5. Rotational Symmetry of Standard System

- 32 - (19 0, ot... 9 0) 1, O,..., 0), 2,s 3,0,..., 0) Figure 6. Enumeration Tree

- 33 - Figure 7. Flow-Chart of Procedure TOL-B&B

- 34 - C = (2,3) C* = 47.0 h-4 = (1,0) ( 5C = 14.0., FATHOMED BY, FEASIBILITY 0 > ~~~~~~~~~~~1 Y = (2,0) C = 32.0 L A)Q 0 Y =(2,2) Y = (2,3) Y = (2,4) C =37.0 C =47.0 C =67.0 L L L FATHOMED BY FATHOMED FATHOMED FEASIBILITY BY COST BY COST Figure 8. Tree Traversal in Example 1