See discussions, stats, and author profiles for this publication at: https://www.researchgate.

net/publication/261622147

Tolerance analysis for setup planning: A graph theoretical

approach

Article in International Journal of Production Research · November 2010

DOI: 10.1080/002075497195579

CITATIONS READS

39 276

3 authors, including:

Samuel Huang Hong-Chao Zhang

University of Cincinnati Texas Tech University
120 PUBLICATIONS 9,059 CITATIONS 237 PUBLICATIONS 7,166 CITATIONS

SEE PROFILE SEE PROFILE

All content following this page was uploaded by Hong-Chao Zhang on 27 October 2015.

The user has requested enhancement of the downloaded file.

INT. J. PROD. RES., 1997, VOL. 35, NO. 4, 1107-1124

Tolerance analysis for setup planning: a graph theoretical approach

S. H. HUANG*, H-C. ZHANGf and W. J. B. OLDHAMJ

Setup planning is the act of preparing detailed work instructions for setting up a
part. The purpose of setting up a part is to ensure its stability during machining
and, more importantly, the precision of the machining processes. Therefore,
tolerance control can be achieved proactively via setup planning. This fact was
somewhat overlooked in the computer-aided process planning (CAPP) research
community. While many researchers focused their attention on tolerance chart
analysis, the issue of tolerance analysis for setup planning was relatively unex-
plored. To systematically solve the setup planning problem, a graph theoretical
approach is proposed. The design specification of a part is represented as a graph.
The problem of identifying the optimal setup plan is transformed into a graph
search problem. A setup planning algorithm for rotational parts was then
developed. The algorithm was evaluated and found to be both efficient and
effective.

1. Introduction
Tolerance control plays a crucial role in precision manufacturing. It ensures that
the resultant part dimensions do not exceed the specified design values. It is desirable
to apply tolerance control techniques at the early stage of process planning since no
great time or dollar loss will occur if a process, setup, or datum change Is required
(Wade 1983). Traditionally, tolerance control in process planning is achieved via
tolerance chart analvsis (Gadzala 1959, Eary and Johnson 1962, Johnson 1963, Wade
1967, 1983).
A tolerance chart analysis shows how individual machining cuts combine to
produce each blueprint dimension. It yields a set of hnear algebraic expressions
showing the relationship between each desired blueprint dimension and the individual
cuts that contribute to it. Since the dimension produced by a specific cut is a stochastic
variable dependent on factors such as machine tool capability, raw material, cutting
tool and so on, production is then faced with the task of distributing tolerances
among individual cuts so that when these cuts combine, blueprint tolerance specifica-
tions are not exceeded. With the help of a tolerance chart, a process planner will be
able to determine mean values and tolerances of the operational dimensions in a
systematic way.
However, tolerance chart analysis has a limitation. A tolerance chart can be built
only after all the initial engineering decisions have been made concerning the process
plan, namely, the selection of setups, datums, operation sequences, etc. (Wade 1983).
When these decisions are not made properly, a tolerance chart analysis may require
the use of machine tools with higher accuracy than necessary. As a result, the
manufacturing cost will be higher than necessary, which is undesirable. Tolerance

Received January 1996.

EDS/Unigraphics, 10824 Hope Street, Cypress, California 90630, USA.
tDepartment of Industrial Engineering, Texas Tech University, Lubbock, Texas 79409, USA.
tDepartment of Computer Science, Texas Tech University, Lubbock, Texas 79409, USA.
*To whom correspondence should be addressed.
0020-7543/97 SI200 f 1997 Taylor & Francis Lid.
1108 .S, H. Huang et al.

chart analysis can only reactively check existing tolerance stackup problems rather
than proactively minimizing tolerance stackup by selecting an appropriate setup plan.
However, this fact was somewhat overlooked in the computer-aided process planning
(CAPP) research community. While many researchers focused their attention on
tolerance chart analysis, the issue of tolerance analysis for setup planning was
relatively unexplored.
In this paper, a graph theoretical approach is proposed to systematically solve the
problem of setup planning based on tolerance analysis. The design specification of a
part is represented as a graph. The problem of identifying the optimal setup plan is
transformed into a graph search problem. A setup planning algorithm for rotational
parts was then developed. The algorithm was evaluated and found to be both efficient
and effective,

2. Setup planning
Setup planning is the act of preparing detailed work instructions for setting up a
part. The purpose of setting up a part is to ensure its stability during machining and,
more importantly, the precision of the machining processes. Therefore, tolerance
control can be achieved proactively via setup planning (Zhang et al. 1996),
Boerma and Kals (1988) reported on a system called FIXES which can perform
the task of setup selection. Two main objectives of the setup selection procedure are
(Boerma and Kals 1988):
(1) to reduce the number of critical tolerances in the geometrical relations
between features belonging to different setups, and
(2) to keep the number of setups as low as possible,
Huang and Gu (1994) also provided two rules for setup selection:
Rule 1: A setup should be selected such that maximum number of features can be
synchronously machined.
Rule 2: A setup should be selected such that minimum locating errors can be achieved.
The above mentioned researches provide some guidelines for setup planning
based on tolerance analysis. However, no systematic approach for setup planning is
available in the literature. There is a need to develop a systematic approach for setup
planning based on tolerance analysis,
A major purpose of setup planning is to determine an optimal setup so that the
influence of tolerance stackup is kept to the minimum. To develop a theoretically
sound foundation for setup planning, the problem of tolerance stackup must be
analysed. In NC machining, three setup methods are used to obtain the dimension
between two features within a part. These methods are (1) machining the two features
in the same setup; (2) using one feature as the locating datum and machine the other;
and (3) using an intermediate locating datum to machine the two features in diiferent
setups. The three methods are denoted as setup method I, setup method II, and setup
method III, respectively.
When locating and clamping (setting up) a workpiece on the fixture, a setup error
occurs, A setup error includes workpiece-locating error, workpiece-clamping distor-
tion, geometrical and dimensional inaccuracy of the fixture, etc. After a workpiece has
been located and clamped, the setup error remains as a constant until the workpiece is
removed from the fixture. In addition to setup errors, there exist machine motion
errors, A machine motion error is the deviation of a machine movement from its ideal
 Tolerance analysis for setup planning 1109

position due to the inaccuracy of the machine tool, thermal deformation of the
machine tool, etc.
When using setup method L the setup error is not included in the dimension
obtained. The geometric relationship of the features machined in the same setup
mainly depends on the geometry built into the machine tool. The dimensional
relationship, such as the distance between two parallel surfaces, is determined
mainly by the accuracy of the machine control unit (MCU), which is a built-in
capability of the machine tool. Dimensions obtained using setup method I consist of
the least manufacturing errors. Whenever possible, this setup method should be used
to facilitate tolerance control.
When setup method II is used, the setup error is included in the dimension
obtained. To control the tolerance of the dimension, the accuracy of setting up the
part has be a concern, which becomes a major part of the tolerance. Dimensions
obtained using setup method II are usually less accurate than those obtained using
setup method I. However, it is regarded as a good method when two features cannot
be machined in the same setup.
Setup method III is the least desired setup method. A dimension (tolerance) chain
is formed for every dimension obtained using setup method III. As a result, the
tolerances will stack up. When the tolerance of a dimension is tight, setup method III
should be avoided. If this setup method is used to obtain a dimension with tight
tolerance, although tolerance chart analysis can be used to calculate the operational
dimensions and tolerances, the undesired stackup of tolerances might make the
manufacturing impossible even with the best machine tool.
The above discussion showed that tolerance control can be achieved proactively
via setup planning. Features with tight tolerance relationship should be arranged into
the same setup whenever possible. When two features with tight tolerance relation-
ship cannot be machined in the same setup, they should be mutually datumed. Only
when the tolerance relationship between two features is not tight can an intermediate
datum be used. Please refer to Huang and Zhang (1996) for more details.

3. A graph theoretical approach to setup planning

Setup planning is a complex problem. To solve the setup planning problem
effectively, a mathematical tool is preferred. In the past two decades, graph theory has
developed as a powerful mathematical tool in the understanding and solution of large
complex problems that arise in the study of engineering, computer, and communica-
tion systems (Thulasiraman and Swamy 1993). The language of graphs makes it
possible to represent the structure of a complex problem in a simple manner. Graph
representation has a twofold advantage: (1) it allows one to express the deep structure
of the given situation, and (2) it presents an overall view of the problem, which is a
valuable guide to intuition and reasoning (Gondran and Minoux 1984). Graph theory
has been successfully applied in many engineering domains (Foulds 1992, Henley and
Williams 1973, Johnson and Johnson 1972). The success of graph theory in various
engineering domains implies that it can be a useful tool for setup planning.

3.1. Graph theory

A finite graph G -- {V,E) consists of two sets: a finite set V of elements called
vertices and a finite set E of elements called edges. Each edge is identified with a pair of
vertices. If the edges of a graph G are identified with ordered pairs of vertices, then G
is called a directed graph. Otherwise G is called an undirected graph. A graph G with
1110 S.H. Huang etal

weights associated with its edges is called a weighted graph (Thulasiraman and Swamy
1993).
In a graph, the symbols vi, vj, v^, ... are used to represent the vertices and ei, ei,
e3, ... are used to represent the edges. Hence V = {vi,V2,v-x,,...} and E =
{ei,e2,e^,...}. The vertices u, and Vj associated with an edge e/ are called the end
vertices of e/. The edge e, is then denoted as e/ = (u,, Vj). While the elements of E are
distinct, more than one edge in E may have the same pair of end vertices. All edges
having the same pair of end vertices are called parallel edges. Further, the end vertices
of an edge need not be distinct. If e/ = (i),, t;,), then the edge e/ is called a self-loop at
vertex ?;,. A graph is called a simple graph if it has no parallel edges or self-loops.
Consider a graph G = ( F , ^ ) . G' = ( F ' , £ ' ) is a subgraph of G if V' and E' are, res-
pectively, subsets of V and E such that an edge (i>,, Vj) is in E' only if ii, and Vj are in V'.
An edge is said to be incident on its end vertices. Two vertices are adjacent if they
are the end vertices of some edge. The number of edges incident on a vertex w, is called
the degree of the vertex, and is denoted by d{vi). A complete graph G is a simple graph
in which every pair of vertices is adjacent.
A graph is completely determined by specifying either its adjacency structure or its
incidence structure. These specifications provide far more efficient ways of represent-
ing a large or comphcated graph than a pictorial representation. Because computers
are more adept at manipulating numbers than are recognizing pictures, it is standard
practice to communicate the specification of a graph to a computer in matrix form
(Foulds 1992). Let G = {V,E) be a graph with no parallel edges. Let V =
{fi, ?;2, • • •! ^n}- The adjacency matrix M = [wy] of G is an « x n matrix with /Wy
defined as follows:
J 1, if {Vi, Vj) g E.
"'" \ o , otherwise.
In addition to the adjacency matrix, a graph can be represented using an incidence
matrix, a circuit matrix, a cut matrix, etc. For more about graph theory, readers may
refer to Mayeda (1972), Biggs et al. (1976), McHugh (1990), Thulasiraman and
Swamy (1993).

3.2. Graph representation of the setup planning problem

The purpose of setup is to locate and fix a part in a definite manner on a machine
tool so that machining can take place. Usually a part needs to be manufactured in more
than one setup. Therefore, the task of setup planning includes (1) grouping features
into setups, (2) selecting setup datums for the setups, and (3) sequencing the setups.
The first step in setup planning is to group features of a part into setups, namely,
setup formation. Tool approach direction is an important factor in determining
setups. The tool approach direction of a feature is an unobstructed path that a tool
can take to access the feature (Chang 1990). Features with the same tool approach
direction can be grouped into one setup. A feature may have more than one tool
approach direction and hence can be grouped into different setups. The feature might
have tolerance relationships with another feature which has only one tool approach
direction. If these two features share a common tool approach direction, then they
should be grouped into the same setup so that setup method I is appUed to assure the
tolerance. This is the purpose of setup formation.
The problem of setup formation can be represented using the language of graphs
as follows. The features within a part and their relationships (in terms of tool
approach direction) can be represented as a graph GQ = (K, E) called a feature
 Tolerance analysis for setup planning nil
relationship graph. Here, the term feature refers to a surface that can be dimensioned
and toleranced. The features are represented as the vertices V — {v\,V2,...,Vn},
where n is the number of features. Their relationships (in terms of tool approach
direction) are represented as the edges E = {e\,e2,.. •, e^}, where m is the number of
edges. If two features f, and Vj (i ^j) can be machined within a setup (i,e, they have
the same tool approach direction), then {vi,Vj) G E; if i = j then (i;,, Vj) e £; otherwise
{Vi, Vj) ^ E. Let Mo = [wy] be Go's adjacency matrix. Let #•, and c, (/ = 1,2,,,,, n) be
Mo's row vector and column vector, respectively. Since Go is an undirected graph. Mo
is symmetric, Henee r, =; c]{i = \,2,....n).
An example is used for the purpose of illustration. Figure 1 shows the example
part. The parts consists of 8 features, denoted as A, B, C, D, E, F, G, and H, Feature
B has a circular runout tolerance (001) when rotated about the datum axis (feature
F), Feature D and feature F have a concentricity tolerance (0 02), The size between
features A and F, G and E, and C and E are denoted as d^E, d^g, and dc^,
respectively. The tolerances for dimensions dAE, '^GE- and dcE are ±0 05, ±0-03, and
±0 02, respectively. This part is to be machined using an NC lathe. The fixture to be
used is a three-jaw chuck.
The feature relationship graph Go for the example part is shown in Fig, 2, MQ, the
adjacency matrix of Go, is shown as follows:
A B C D E F G H
A "1 1 0 0 0 1 1 1
B 1 1 1 1 1 1 1 1
C 0 1 1 1 1 1 0 0
D 0 1 1 1 1 1 0 0
E 0 1 1 1 1 1 0 0
F 1 1 1 1 1 1 1 1
G 1 1 0 0 0 1 1 1
H 1 1 0 0 0 1 1 1

unit: mm

Figure 1, An example part (only relevant dimensions are shown).

1112 S. H. Huang et al.

Figure 2, The feature relationship graph GQ of the example part (self-loops are omitted).
The feature relationship graph consists of a number of complete subgraphs. Each
complete subgraph represents a setup. The vertices within a complete subgraph
represent the features to be machined in the setup. The purpose of setup formation is
to find these subgraph G'l = {V\,E\), Gj = {V2,E'2), ,,,, Gj = {V'i,E',), such that
K/n F ; = 0 , for r = 1,2, , , , , / , ; = 1,2,,,,,/, / V J and Fj U K2 U .,, U F,'= K,
Examining the matrix MQ, one finds that it consists of three distinct row (column)
vectors ([1 1 0 0 0 1 1 1], [0 1 1 1 1 1 0 0], and [1 1 1 1 1 1 1 1]), This
means that the features can be categorized into three sets. The physical meaning of
the sets is explained as follows, Eor rotational parts, there are two tool approach
directions, namely, the left and the right, A feature can thus be machined (1) only
from the left, (2) only from the right, or (3) from either the left or the right. Therefore,
the features in a rotational part can be categorized into three sets defined as follows:

{
SL, if feature u, can be machined only from the left
SR, if feature W, can be machined only from the right (1)

SB, if feature v, can be machined from either the left or the right
in which / = 1,2,,,,,«,
In this example, one can see that SL = {A, G, H}, SR = { C , D , E}, and
SB = {B,F}, Rearranging the matrix MQ according to the sets, one has a new
matrix Mj shown as follows:
A G H B E C D E
A • 1 1 1 1 1 0 0 0
G 1 1 1 1 1 0 0 0
H 1 1 1 1 1 0 0 0
B 1 1 1 1 1 1 1 1
E 1 1 1 1 1 1 1 1
C 0 0 0 1 1 1 1 1
D 0 0 0 1 1 1 1 1
E 0 0 0 1 1 1 1 1
Erom the matrix M\, one can see that the feature relationship graph Go consists of
 Tolerance analysis for setup planning 1113

at least two complete subgraphs. Since it is desirable to reduce the number of setups in
machining (Chang 1990), the graph Go should be partitioned into exactly two
complete graphs, denoted G\ = {V\,E\) and Gj = (F^,^^), respectively. It is easy
to see the vertices in the set SL belong to a complete graph while the vertices in the set
SR belong to the other one. Without loss of generality, let S L C F ( and SR C Fj.
Since a vertex in the set Sg, denoted v*, is adjacent to all the other vertices of the graph
Go, G'l will still be a complete graph if u* is assigned to V[. Similarly, G'2 will still be a
complete graph if w* is assigned to Fj. Therefore, the problem of setup formation is
transformed to assign vertices in the set Sg to either V[ or Fj. The requirement for
such an assignment is that the resultant complete subgraphs (setups) should be
optimal in terms of tolerance control.
In order to find the optimal complete subgraphs, a tolerance graph is constructed
based on the feature relationship graph and the design tolerance information. The
procedure for constructing the tolerance graph is as follows. First, vertices in the
feature relationship graph Go are partitioned into three sets as defined in (1). The edge
connections of GQ are then removed. In the mean time, the design tolerance
information is added as new, weighted edges with the size of the tolerance zone
being the weights. The feature relationship graph GQ evolves to a tolerance graph G].
The tolerance graph G, for the example part is shown in Fig. 3.
The assignment of vertices in the set Sg is based on the tolerance graph. The
primary concern is that features with tight tolerance relationships should be machined
in the same setup (corresponding vertices belong to the same subgraph). The result of
this assignment is a setup graph G2. The setup graph G2 consists of two subgraphs (not
complete subgraphs because the setup graph is difierent from the feature relationship
graph) representing the two setups, denoted Gi_^{Vi,Ei_) and GR = {VR,ER),
respectively.
In this example (Fig. 3), one can see that features B and F need to be assigned
to either SL or SR. Since feature F has a tolerance relationship with feature D (the size
of the tolerance zone is 0 02) and D € SR, feature F should be assigned to SR. After
feature F has been assigned to SR, feature B should also be assigned to SR since it has
a tolerance relationship with feature F (the size of the tolerance zone is 0 01). As a
result, the features within the example part are grouped into two sets, SL = {A, G. H}
and SR = {B, C, D, E, F}. Let F^ = SL and V^ = SR, the two subgraphs G^ and GR
are obtained. The setup graph G2 for the example part is shown in Fig. 4.

SB

Figure 3, The tolerance graph G, of the example part.

1114 S. H. Huang et al.

Figure 4, The tolerance graph G] of the example part.

After setups have been formed, setup datums need to be selected and the sequence
of the setups needs to be decided. The concerns at this stage are those dimensions
that cannot be obtained using setup method I, The primary purpose is to make
sure that the dimension with the tightest tolerance is obtained using setup method II,
The secondary purpose is to sequence the setups so that setup method II is applied to
obtain as many dimensions with specified tolerances as possible.
Dimensions obtained using setup method I are mainly determined by the built-in
machine/process capabilities and have nothing to do with the selection of setup
datums and setup sequence. Therefore, their tolerance information is not necessary
for datum selection and setup sequencing and can be screened out. To fix a rotational
part on a machine tool, one (and only one) vertical feature and one (and only one)
cylindrical feature are needed. Therefore, vertical features and cylindrical features
need to be distinguished. The vertices in the setup graph are partitioned into four
subgraphs denoted as G'l^y = {V'i^y,E'iy) {V'ly consists of vertices representing
vertical features that need to be machined from the left), G'lc = {VLC^E'IC) {V'LC
consists of vertices representing cylindrical features that need to be machined from the
left), G'nY = {V'HY,E', consists of vertices representing vertical features that
need to be machined from the right), and G'jic = (F^ci E'^c) ( ^'RC consists of vertices
representing cylindrical features that need to be machined from the right), respec-
tively. As a result, the setup graph G2 evolves to a datum graph G^. The datum graph
G3 for the example part is shown in Eig, 5,
Datum selection and setup sequencing are both based on the datum graph. The
purpose of datum selection is to find one and only one vertex from each of V'ly, V'LC^
V'^Y^ and V'nc- The vertices found are to be used as the setup datums. The purpose of
setup sequencing is to sequence G^ and G^ so that the sequence of the corresponding
setups can be determined. Again, the decisions made should facilitate tolerance control.
In this example (Eig. 5), one can see that the tolerance between features A and E
(0-10) and the tolerance between features G and E (0 06) are to be assured. The tighter
tolerance is the one between features G and E, Therefore, features G and E are to be
used as setup datums. Since the degree of E (d(E) = 2) is greater than the degree of G
{d(G) = 1), feature E needs to be machined in the first setup. In this way, both feature
A and feature G are machined using feature E as a setup datum in the finishing
process (setup method II is applied). Since there is no tolerance requirement among
 Tolerance analysis for setup planning 1115

Figure 5, The datum graph Gj of the example part,

the cylindrical features, the selection of cylindrical setup datums does not influence
the tolerance control. In this case, features H and D are selected as the cylindrical
setup datums for the ease of fixturing,

4. A setup planning algorithm for rotational parts

4,1, The algorithm
Section 3,2 provides a graph representation of the setup planning problem. It
shows that a graph theoretical approach can be used to advantage in generating
appropriate setup plans. In this section, a setup planning algorithm for rotational
parts is developed. The following assumptions are made:
(1) The part is to be machined on an NC lathe,
(2) The part is to be set up on the lathe using a three-jaw chuck,
(3) Only primary features such as cylindrical surfaces and vertical surfaces are
considered. Secondary features such as keyways, chamfers, grooves, and
threads are not considered because they do not infiuence setup planning,
(4) All the features of the part are to be machined,
(5) Different types of tolerances are of equal importance,
(6) The tool approach direction of each feature is given,
(7) Each setup requires one (and only one) vertical feature and one (and only one)
cyhndrical feature as the setup datums.
The task of setup planning is divided into three steps: (1) setup formation, (2)
datum selection, and (3) setup sequencing. The procedure for the graph theoretical
approach to setup planning is shown in Fig, 6, The input to the algorithm for setup
formation is the tolerance graph G| whose vertices are categorized into three sets
denoted SL, SR, and SB, Let e/ = (t',, Vj) denote the weight of the edge incident on
vertices ?>, and v,. Let r be the number of edges in G[ that are incident on at least one
vertex in the set Sg, The algorithm is given as follows:
If SB = 0 then exit
Else
Find e/ = (i.i^, u,,) = min[e,], in which ; = 1,2,.,,, r, D^ e SB, V^ ^ SB,
If v,i G SL then assign Vp to SL, otherwise assign v^ to SR,
B ~~ B 1 D I

Repeat
1116 S. H. Huang et al.

Feature Relationship Graph Go

Group features into different

Initialization sets (SL, SR, and SB) based on
their tool approach direction
as defined in (4.1)

Tolerance Graph

Assign features in Se to
Setup Formation either SL or SR based on the
design tolerance information

Setup Graph G2 (consists of

two subgraphs GL and Go)

Datum Graph G3 (consists of

four subgraphs G^ = (\{,,.£^

Find one and only one

Datum Selection vertex in each of VLV, VU:, Sequence Gi.and Gn Setup Sequencing
Vm, and VFC

Figure 6. A graph theoretical approach to setup planning.

The output of the algorithm is a setup graph G2. The setup graph G2 is then
transformed into a datum graph G3 (see § 3.2 for the procedure) which consists of four
subgraphs G'ly = {V'iy,E'j^y), G'/^^-= (F^c,££<;), G'i{y = {V'^y,E'j^y), and G'^c =
(V'j^c: E'RC)- The datum graph G3 is the input for the algorithms for datum selection
and setup sequencing.
Let t be the number of edges in G3 = (Fji?). Let D denote the set of features
selected to be the setup datums. Initially, D = 0. The algorithm for datum selection
is given as follows:
If the number of elements in D equals 4 then exit
Else
Find ei = [vp, v^) = min[e,], in which / = 1,2,...,?.
Let D = D U {vp} if no element in D and Vp belongs to the same subgraph
Let D = D U {v^} if no element in D and v^ belongs to the same subgraph
Let E = E - {e,,, = {Va,Vf,)}, in which v^ and Vp belong to the same subgraph
while Vf, and v^ belong to the same subgraph
Repeat
Let Vi denote the element in D, in which / = 1,2,3,4. Let c/(w,) denote the
degree of vertex Vj in the datum graph G3. The algorithm for setup sequencing
 Tolerance analysis for setup planning 1117

is given as follows:
Eind d{vp) = max[d{vi)], in which / = 1,2,3,4
If u^ e Vl then machine the features in V^ in the first setup; otherwise machine the
features in F^ in the first setup,

4,2, Analysis of the algorithm

The setup planning algorithm developed is a greedy type algorithm. Its efficiency
and effectiveness will be evaluated in this section,

4,2,1, Efficiency of the algorithm

The setup planning algorithm for rotational parts consists of 3 parts. In the first
part, namely, setup formation, the analysis of the algorithm is given as follows. Let s
denote the number of vertices in the set SB and r denote the number of edges incident
on at least one vertex in the set SB, Let a be the time taken to execute the statement
[If SB = 0 then , , , ] , Let b be the time taken to examine the weight of an edge. Thus, it
takes a time br to find the edge with the minimum weight. Let c be the time taken to
execute the statement [If v^ e SL then ,,,] and d be the time taken to execute the
statement [Let SB = SB - {vp]]. Therefore, the time taken for one trip through the
statements, except [Repeat], \sa + br + c + d. Since there are s vertices in the set SB,
the algorithm will repeat s times before it exits. Therefore, the total time taken is
(a + ftr + c + d)s. Since a, b, c, and d are constants, the algorithm takes a time in
O{s + sr) = O{va2ix{s,sr)). Since r > 1, one can conclude that the setup formation
algorithm takes a time in 0{sr).
The setup formation algorithm is compared with an exhaustive search algorithm
to show its efficiency. To perform an exhaustive search, the vertices in the set SB need
to be assigned to either the set SL or the set SR first and then the effect of the
assignment is examined so that the best assignment can be selected. There are 2* ways
for the assignment, Eor each assignment, the weights of the r edges need to be
examined. Therefore, it takes a time in 0(2V) for an exhaustive search algorithm.
Apparently, the developed setup formation algorithm is much more efficient than an
exhaustive search algorithm.
The analysis of the algorithm for datum selection is given as follows. Let a be the
time taken to execute the statement [If the number of elements in D equals 4 then , , , ] ,
Let b be the time taken to examine the weight of an edge. Thus, it takes a time bt to
find the edge with the minimum weight. Let c be the time taken to execute the
statements [Let D = Dl^ {v^} if ,,,] and [Let /) = /) u {wj if , , , ] . Let d be the time
taken to execute the statement [Let E^E~ {e,,, = {v,, v^)} in which , , , ] . Therefore,
the time taken for one trip through the statements, except [Repeat], isa + bt + c + d.
These statements will repeat at most 3 times, which is a constant. Since a, b, c, and d
are also constants, the algorithm takes a time in 0{t).
The datum selection algorithm is compared with an exhaustive search algorithm.
Let «|, «2, rtj, and ri^ be the number of vertices in F^^., V'i_c, V'KV, and V'/^^
respectively. There are «|«2«3«4 ways of selecting the setup datums,' Eor these
selections, the weights of the t edges need to be examined to find the best selection.
Therefore, it takes a time in Oin^n.n^n^t) for an exhaustive search. Again, the
developed datum selection algorithm is more efficient than the exhaustive search
algorithm.
The time needed for the setup sequencing algorithm is a constant independent of
1118 S. H. Huang et al.

the problem size. On the other hand, to perform an exhaustive search, the weights of
the t edges need to be examined and the time taken is in 0{t). Based on the above
analysis, one can see that the developed setup planning algorithm is efficient
compared with an exhaustive search algorithm.

4.2.2. Effectiveness of the algorithm

Manufacturing of parts with exactly equal dimensions is impossible. The machin-
ing processes used in industry exhibit typical peculiarites. The peculiarities impose
typical distributions of the dimensions produced by the processes. Although these
distributions may be identified, they are not always known. It is known from experi-
ence, however, that most processes give distributions varying between a normal
distribution and a rectangular distribution (Bjorke 1989).
Since the objective of setup planning is to reduce the infiuence of tolerance stackup
and thus achieve tolerance control, one can say that a setup plan is better than
another one only if the variation of the resultant part dimension is smaller. Therefore,
to evaluate the eifectiveness of a setup plan, the variances of the resultant part
dimensions should be examined.
The Monte Carlo simulation method is used to evaluate the effectiveness of the
setup planning algorithm. Monte Carlo simulation is a popular device for studying an
artificial stochastic model of a physical or mathematical process (Rubinstein 1981).
Under the Monte Carlo simulation, a system is examined through repeated evalua-
tions of the mathematical model as its parameters are randomly varied according to
their true behaviour.
The block diagram of the simulation model is shown in Fig. 7. Given a part
design, the alternate setup plans can be determined. Given the design tolerance
requirement, one of the setup plans is the most appropriate in terms of tolerance
control and should be selected. If the design tolerance information (including
dimensioning patterns) changes, the most appropriate setup plan might change.
Based on the selected setup plan, an NC program can be made. The machining of the

Part Design

Setup Plan

NC Program

NC Machining
(Simulation)

Resultent Part
Dimensions

Figure 7. The block diagram of the simulation model.

 Tolerance analysis for setup planning 1119

. 50±0.02

unit: mm

B
D

Machined features: A, B, C, D, and E

Possible setup plans: 2(i)(i)= 12

Figure 8. An example of a typical rotational part.

part based on the NC program is then simulated. The output of the simulation is
the resultant part dimensions. Based on the simulation, the sample variances for the
resultant part dimensions can be calculated.
The part shown in Fig. 8 is used as an example part. The part is a typical rotational
part. Features A, B, C, D, and E are to be machined. Since the part consists of five
surfaces that need to be machined, four dimensions (and their tolerance requirements)
are needed. Usually the part is machined in two setups with features A and B in one
setup and features C, D, and E in the other setup. Either setup can be machined first.
When machining features C, D, and E, either feature A or feature B can be used as a
setup datum. Similarly, any one of features C, D, and E can be used as a setup datum
when machining features A and B. Therefore, there are 2(,)(,) = 12 alternate setup
plans (Table 1). Based on the setup plans, NC programs were made and the
machining processes simulated. It is assumed that the setup error follows a nonnal
distribution with a mean of 0mm and a standard deviation of 0006mm (// = 0mm
and (T = 0-006 mm), while the machine motion error follows a nonnal distribution
with a mean of 0mm and a standard deviation of 0003mm {ii = Omm and
cr = 0-003 mm). The four resultant dimensions are normally distributed random
variables denoted Xx, X2, XT,, and X4., respectively. Let a\ he an indicator to the
quahty of the part, in which Y = Xi + X2 + X^ + X4. Therefore, (T| = ^f^, aj, in
which aj is the variance of A', (;' = 1,2,3,4). The smaller a\ is, the better the quality of
the part.
Let (Ty, denote the a'y resulted from the ith setup plan, in which / = 1,2,..., 12.
Let e he the setup plan selected by the setup planning algorithm. To show the
effectiveness of the setup planning algorithm, one needs to test the equality of a]-,
{i = 1,2,.... 12) and show that o-^y is small.
1120 S. H. Huang etsd.

Setup plan Method

(1) Machine features C, D and E using feature A as a setup datum and then
machine features A and B using feature C as a setup datum
(2) Machine features A and B using feature C as a setup datum and then
machine features C, D and E using feature A as a setup datum
(3) Machine features C, D and E using feature A as a setup datum and then
machine features A and B using feature D as a setup datum
(4) Machine features A and B using feature D as a setup datum and then
machine features C, D and E using feature A as a setup datum
(5) Machine features C, D and E using feature A as a setup datum and then
machine features A and B using feature E as a setup datum
(6) Machine features A and B using feature E as a setup datum and then
machine features C, D and E using feature A as a setup datum
(7) Machine features C, D and E using feature B as a setup datum and then
machine features A and B using feature C as a setup datum
(8) Machine features A and B using feature C as a setup datum and then
machine features C, D and E using feature B as a setup datum
(9) Machine features C, D and E using feature B as a setup datum and then
machine features A and B using feature D as a setup datum
(10) Machine features A and B using feature D as a setup datum and then
machine features C, D and E using feature B as a setup datum
(11) Machine features C, D and E using feature B as a setup datum and then
machine features A B using feature E as a setup datum
(12) Machine features A and B using feature E as a setup datum and then
machine features C, D and E using feature B as a setup datum

Table 1, Setup methods for the part shown in Figure 8,

Setup method ;5f^ydO-^mm^)

1 215-41
2 180-12
3 219-67
4 179-01
5 217-53
6 179-57
7 216-72
8 236-30
9 210-55
10 233-11
11 217-07
12 227-74

Table 2, Results of the simulation for the part shown in Fig, 8,

To perfortn the test, 5000 samples were taketi. The sample variance (5^, a point
estimator ofthe population variance ay) resulted from each setup plan was calculated
(Table 2). Let

Sy^ = mid[5y.] (the middle, or the sixth smallest among the 5y's except s]rj
S]-^ = maxiSy]
in which i = 1,2,... ,12, i ^ e.
 Tolerance analysis for setup planning 1121

In other words, the ath, blh., and cth setup plans are the best, the middle, and the
worst setup plans, respectively, among those setup plans that were not selected by the
setup planning algorithm. The a\ resulted from the eth setup plan is compared,
respectively, with the one resulted from the ath, the Mh, and the cth setup plans. The
hypotheses are shown as follows:
(1) Comparing a\^ = a\^
2
cry, =

(2) Comparing a\^ with a'y^

Ho: o'y^ = CTY^,

H,: (TY,>a\^
(3) Comparing o\ with o\^
Ho: o-y,, = o-y^
Hj: (7y^ > a]-^
In this example, setup plan 2 is selected by the setup planning algorithm.
Therefore, e = 2. From Table 2, one can see that a = 4, b = 1, and c = 8. The
comparison of the setup plans is shown in Table 3. From Table 3, one can conclude
that (7y, is not significantly different from cxy^, a — 0-01, BOE (based on evidence).
However, a\^ is significantly different from both a\.^ and a\^,a = 0-01, BOE. In other
words, the setup plan selected by the setup planning algorithm is not significantly
different from the best setup plan; however, it is significantly better than both the
middle setup plan and the worst setup plan, a = 0 0 1 , BOE. Therefore, in this case,
the setup planning algorithm is effective.
To further examine the effectiveness of the setup planning algorithm, four
more examples are used. The design requirement (dimensioning pattern and toler-
ances) of the example part (Fig. 8) is randomly generated as shown in Fig. 9. For
different design requirement, the most appropriate setup plan may vary. For the
parts shown in Fig. 9a, 9b, 9c and 9d, setup plans 1, 11, 7, and 5 are selected,
respectively, by the setup planning algorithm. For each part, the same procedure used
previously is used to examine the effectiveness of the setup planning algorithm. The
simulation results for the four parts shown in Fig. 9 are shown in Table 4, Table 5,
Table 6 and Table 7, respectively. The results of the comparisons are shown in Table
8.
From Table 8, one can see that for each of the 4 examples, the setup plan selected
by the setup planning algorithm is not significantly different from the best setup plan;
however, it is significantly better than both the middle setup plan and the worst setup
plan, a = 0 01, BOE. Therefore, the setup planning algorithm is effective.

2
VS ay

F-value S\jS\^ = \m6 S\jS\ = \-2QS 5 1 / 5 ^ = 1-312

P-value " 0-414 2-2 x 10~" 0

Table 3. Comparison of the setup plans for the part shown in Fig. 8.
1122 S. H. Huang et al.

50±0.02 »
« - 26±0.02 » unit: mm unit: mm
8±0.0J
|« 26±0.01 >
<—1810.02—»
C C
B B
D D

(a) (b)

(c) (d)
Figure 9. Randomly generated design requirements for the example part.

Setup method ify{\O-'mm')

1 107-84
2 109-18
3 127-11
4 107-79
5 125-11
6 107-99
7 108-69
8 125-72
9 123-83
10 124-41
11 126-33
12 124-95

Table 4. Results of the simulation for the part shown in Fig. 9a.

5. Conclusion
Tolerance control is absolutely crucial to achieving production of high-precision
parts at low cost. It is desirable to apply tolerance analysis at the early stage of process
planning since no great time or dollar loss will occur if a process, setup, or datum
change is required. Tolerance chart analysis has been the major tool used for
tolerance analysis in process planning. However, a tolerance chart can be built only
when a setup plan of a part has been generated. Tolerance chart analysis can only
 Tolerance analysis for setup planning 1123

Setup method S\ (10"" m m ^ )

1 179-41
2 163-64
3 182-52
4 162-77
5 143-08
6 161-40
7 183-68
8 162-64
9 176-05
10 160-59
11 144-36
12 159-85

Table 5, Results of the simulation for the part shown in Fig, 9b,

Setup method 5^(10

1 143-82
2 164-97
3 180-67
4 163-55
5 179-82
6 162-42
7 145-60
8 162-50
9 178-07
10 160-39
11 181-89
12 161-81

Table 6, Results of the simulation for the part shown in Fig, 9c,

Setup method S\ (10"" m m ^ )

1 126-18
2 108-75
3 128-12
4 107-22
5 106-93
6 107-61
7 127-36
8 126-82
9 123-33
10 124-75
11 108-20
12 123-17

Table 7, Results of the simulation for the part shown in Fig, 9d,

passively calculate the operational dimensions and tolerances for an existing process
plan. On the other hand, setup planning can proactively select an appropriate plan so
that the influence of tolerance stackup is kept to the minimum.
The major contribution of this research is the development of the graph
1124 Tolerance analysis for setup planning

part ff'y VS ay 0 'y, , VS cry_ a\^ vs ffy^^

Figure 4.10a F-value SljSl = 1-000 IS:2, ^ i . , 5 4 5-1/5'y = 1 - 1 7 9

P-value 0-5 2 -1 X 1 0 " ^ 3x'lO-'
Figure 4.10b F-value ;Sy^JSl^ = 1-009 S'Y 1
s y,, = 1-128 S\jS\^^ = 1-272
P-value 0-376 1-0 X 1 0 ^ 0
Figure 4.10c F-value S]-JS\^ = 1-012 s\j si, = 1-123 S\^ /S\ = 1-249
P-value 0-337 2 -1 X 1 0 " ^ 2-0 X 1 0 " ' '
Figure 4.10d F-value S], /s\ = 0-994 "Sy-,, / s y = 1-153 S\,JS\ = 1198
P-value 0-584 2 -4 X 1 0 " ^ 8-8 X 1 0 " "

Table 8. Comparisons of the setup plans for the parts shown in Fig. 9.

theoretical approach to the solution of the setup planning problem in CAPP. It has
been recognized that current approaches to CAPP are knowledge-based in nature and
thus hinder the progress of CAPP development. The graph theoretical approach is a
mathematical approach and is the first step towards building a scientifically rigorous
base for CAPP research.

References
BIGGS, N . L., LLOYD, E . K . , and WILSON, R . J., 1976, Graph Theory: 1736-1936 (London:
Oxford University Press).
BJ0RKE, 0., 1989, Computer-Aided Tolerancing, 2nd edn (New York: ASME Press).
BoERMA, J. R., and KALS, H . J. J., 1988, FIXES, A system for automatic selection of set-ups and
design of fixtures. Annals of the CIRP, 37(1), 443-446.
CHANG, T . - C , 1990, Expert Process Planning for Manufacturing (Reading, MA: Addison-
Wesiey).
EARY, D . F . , and JOHNSON, J. E., 1962, Process Engineering for Manufacturing (Englewood
Cliffs, NJ: Prentice-Hall).
FOULDS, L. R., 1992, Graph Theory Applications (New York: Springer).
GADZALA, J. L., 1959, Dimensional Control in Precision Manufacturing (New York: McGraw-
Hill).
GoNDRAN, M., and MINOUX, M . , 1984, Graphs and Algorithms (New York: Wiley).
HENLEY, E. J., and WILLIAMS, R . A., 1973, Graph Theory in Modern Engineering: Computer
Aided Design, Control, Optimization, Reliability Analysis (New York: Academic Press).
HUANG, S. H . , and ZHANG, H . - C , 1996, On the use of the tolerance chart for NC machining.
Journal of Engineering Design and Automation, in press.
HUANG, X., and Gu, P., 1994, Tolerance analysis in setup and fixture planning for precision
machining. Proceedings of the Fourth International Conference on Computer Integrated
Manufacturing and Automation Technology, Rensselaer Polytechnic Institute, Troy, New
York^ October 10-12, pp. 298-305.
JOHNSON, A. M., 1963, Tolerance charts. In Manufacturing Planning and Estimating Handbook
(New York: McGraw-Hill), pp. 1-14.
JOHNSON, D . F . , and JOHNSON, J. R., 1972, Graph Theory With Engineering Applications (New
York: Ronald Press).
MAYEDA, W., 1972, Graph Theory (New York: Wiley).
MCHUGH, J. A., 1990, Algorithmic Graph Theory (Englewood Cliffs, NJ: Prentice-Hall).
RUBINSTEIN, R . Y . , 1981, Simulation and The Monte Carlo Method (New York: Wiley).
TuLAsiRAMAN, K., and SWAMY, M . N . S., 1993, Graphs: Theory and Algorithms (New York:
Wiley).
WADE, O. R., 1967, Tolerance Control in Design and Manufacturing (New York: Industrial Press).
WADE, O . R . , 1983, Tolerance Control. In Tool and Manufacturing Engineers handbook: 1,
Machining (Dearborn, MI: SME), pp. 2-1 to 2-60.
ZHANG, H . - C , HUANG, S. H . , and MEI, J., 1996, Operational dimensioning and tolerancing in
process planning: setup planning. International Journal of Production Research, 34(7).
1841-1858.
View publication stats