Zhang , Y. F. et al "Application of Genetic Algorithms and Simulated Annealing in Process ..."
Computational Intelligence in Manufacturing Handbook
Edited by Jun Wang et al
Boca Raton: CRC Press LLC,2001

©2001 CRC Press LLC

9

Application of Genetic
Algorithms and
Simulated Annealing
in Process Planning

Optimization

9.1 Introduction

9.2 Modeling Process Planning Problems
in an Optimization Perspective

9.3 Applying a Genetic Algorithm
to the Process Planning Problem

9.4 Applying Simulated Annealing
to the Process Planning Problem

9.5 Comparison between the GA and the SA Algorithm

9.6 Conclusions


in the shop floor. The term “best” refers to a plan that satisfies a predetermined criterion.
3. Capable of generating alternative process plans to suit production scheduling needs and/or changes
in the shop floor status.
Over the last 20 years, there have been numerous attempts to develop CAPP systems for various parts
manufacturing domains, such as rotational and prismatic parts. The levels of automation among the
reported systems range from interactive, variant, to generative [Alting and Zhang, 1989]. The discussion
in this chapter focuses on the generative type as it is the most advanced and preferred. In general, the
main characteristics of those reported generative CAPP systems, in terms of various decision-making
activities in process planning, can be summarised as follows:
1.

Machining features recognition

— The workpiece, both the raw material and finished part, is
generally given in a solid model representation. The difference between the finished part and the
raw materials represents the volumes that need to be removed. The total removal volumes are
extracted and decomposed into individual volumes, called machining features (e.g., holes and
slots), which can be removed by a certain type of machining process (e.g., drilling and milling).
2.

Operations selection

— For each machining feature, an operation or a set of operations (e.g.,
roughing and finishing operations) is selected.
3.

Machines and cutters selection

— For each operation, a machine and a cutter are assigned to it
for execution, based on shop floor resources.

optimal or near-optimal solution.
In this chapter, a novel algorithm that models process planning in an optimisation perspective is
presented. The application of genetic algorithms and simulated annealing to solve the process planning
model are discussed together with a case study.

©2001 CRC Press LLC

9.2 Modeling Process Planning Problems in an Optimization

Perspective

9.2.1 The Process Planning Domain

The process planning domain for a CAPP system is defined by the types of parts, machining features, and
machining environment it deals with. The discussion focuses on prismatic parts. The geometry of a part
is represented as a solid model created using a CAD software. The raw material is assumed to be a pre-
machined prismatic block that just encloses the part (a convex hull). The basic machining features, which
can be used to construct the most commonly encountered prismatic parts, are shown in Figure 9.2. Some
of these simple features can be merged together to form complex intersecting machining features. As for
the machining environment domain, a CAPP system should be flexible enough to handle common parts
in traditional job shops. In this discussion, the job shop information in terms of its machining capability
and current status is treated as user input through an open architecture, to update the currently available
machining resources (machines, tools) along with their technological attributes such as the dimensions

FIGURE 9.1

Two typical CAPP approaches.
Operations? Machines?
Cutters?
Fixtures?

2.

Operations sequencing

— Determine the sequence of executing all the OPMs required for the
part so that the precedence relationships among all the operations are maintained. Set-ups can
then be generated by clustering the neighboring OPMs that share the same machine and fixture
arrangement.
It is obvious that decisions made in steps 1 and 2 may contradict each other. Therefore, the decision-
making tasks in 1 and 2 must be carried out simultaneously in order to achieve an optimal plan. For

FIGURE 9.2

Basic machining features.
Step
Simple hole
Throughslot
Notch C-bore hole
Blind slot
Chamfer
Sink-bore hole
T-slot
Boss
Pad
Dovetail slot
U-slot
Ball-end-slot
Blend
Round pocket
Rectangle pocket

machined. Similarly, feasible TADs for an OPT(M/T) can be multiple. For a prismatic part, six possible
TADs, i.e., the six normal directions of a prismatic block (

±

x

,

±

y

,

±

z

), are assumed. For a cutter acting
on a feature alone, its theoretical TADs are fixed. However, interference may occur when considering the
part and tool geometry. One of the approaches to check such interference is to simulate the movement
of the cutter in a solid mode [Ma, 1999]. The solid model of a tool is moved from a predefined path
toward the feature along its theoretical TADs. After reaching the feature, it is moved to cover the entire
feature. During this simulation, any TAD that causes interference is discarded. If an OPT(M/T) does not
have any feasible TADs, it is discarded. Referring to the part shown in Figure 9.3, although drilling a
through-hole has two TADs in theory, a drill can only approach F5 along “+

x



Although a possible process plan can be a permutation generated from the OPM pool, it is considered
valid only if none of the precedence relationships (PRs) between operations caused by geometrical and
technological consideration need is violated. In other words, these PRs have to be identified to check if
a randomly generated sequence is valid. In general, the PRs between operations can be identified from
the following:
1.

PRs between the realisation of machining features

— These can be derived from process con-
straints such as fixture constraint, datum dependency, and good machining practices. Some typical
process constraints considered are as follows:
•

Fixture constraint:

A PR between two features exists when machining one feature first may
cause another to be unfixturable. An example is given in Figure 9.3 where F2 must be milled
before F1, F3, F4, F6, and F7. Otherwise, the supporting area for milling F2 is not sufficient.
•

Datum dependency:

When two features have a dimensional or geometrical tolerance relation-
ship, the feature containing the datum should be machined first. For example, F4 needs to be
machined before F6 since the side face of F4 is the datum of F6 (see Figure 9.3).
•

Parent–child dependency:


— For every set of OPTs obtained through
mapping from a feature, there exists a fixed PR among those OPTs, i.e., roughing operations come
before finishing operation (e.g., drilling comes before reaming, milling comes before grinding,
etc.).
Since the PRs generated based on the above considerations may contradict each other, they can be
categorized into two types: the

hard

PRs and

soft

PRs. The part cannot be manufactured if any of the
hard PRs are violated; while the part can still be manufactured even if several soft
PRs are violated,
although the practice is less preferred. For example, for the part in Figure 9.3, the PR of F2

→

F9 is a
hard one, while the PR of F4

→

F10 is a soft one. By categorizing the PRs into hard


conditional

PRs and the conditions are attached to them. When OPMs are selected
first, the conditional
PRs can be validated.
2.

Validity of OPMs (OPMs sequencing first)

— The validity of an operation method refers to the
feasibility of applying its M/T/TAD under particular circumstances. For instance, an
OPT(M/T/TAD) certainly depends on the availability of the M and T, which are naturally ensured
during the OPMs selection phase. When a sequence of OPMs (OPM templates, actually) is selected
first, some of the TADs identified earlier for the OPMs may become invalid. Referring to Figure
9.3, F8 (through-hole) has two alternative TADs, i.e., “+z” and “–

z

.” If OPM(F7) precedes OPM(F8)
in a preselected sequence, OPM(F8) with “–

z

” will be invalid. This indicates that sometimes the
validity of a TAD or OPM depends on the sequence of OPMs. These kinds of TADs are designated
as

change on the same machine, and tool change). For the cost due to machine usage, a fixed cost is assumed
every time a particular machine or a tool is used. For the cost due to set-ups, a fixed cost is assumed
when a particular set-up is required. Based on these assumptions, five cost factors (machine usage, tool
usage, machine change, set-up change, and tool change) for a process plan can be derived as follows:

©2001 CRC Press LLC

1. Machine usage cost (

MC

)
Equation (9.1)
where

n

is the total number of OPMs in the process plan and

MCI

i

is the machine cost index for
using machine

i

, a constant for a particular machine.
2. Tool usage cost (

is the machine change cost index, a constant, and is the ID of the machine used for
operation

i.

4. Set-up change cost (

SCC

): a set-up change is needed when two adjacent OPMs performed on the
same machine have different part orientations. Generally, when a part is placed on a machine
table, a TAD along which an OPM approaches a feature dictates the orientation of the part.
Therefore, TADs are used to represent the required orientations of the part.
Equation (9.4)
where

SCCI

is the set-up change cost index, a constant.
5. Tool change cost (

TCC

): a tool change is needed when two adjacent OPMs performed on the same
machine use different tools.
Equation (9.5)
where

TCCI


i
=×
+
=
∑
Ω()
1
1
–
Ω(–)MM
MM
MM
ij
ij
ij
=
≠
=





1 if
0 if
SCC SCCI M M TAD TAD
ii i i
i
n
=×

1
1
–– –
–
ΩΩ

©2001 CRC Press LLC

9.2.4 An Optimization Process Planning Model

Based on the above discussion, the solution space for a process planning problem can be explicitly formed
by all the OPTs required, the available OPMs for each OPT, possible sequences, and various constraints.
A modelling algorithm to obtain this solution space is described as follows:

Algorithm: process planning modelling

Input:

A set of features, job shop information (machines and tools).

Output:

Number of OPTs required, OPMs (M/T/TAD) for each OPT, precedence relationships
between OPTs.
1. For each feature, find all the OPTs that can achieve its attributes (shape, dimensions, tolerances,
and surface finish), based on shop level machining capabilities. The resulting OPTs for a feature
can be expressed as one or several sets of (OPT

1


F(Y)

AND

OPT(i)

∈

F(X)AND

OPT(j)

∈
F(Y)

THE

OPT(i)

→
OPT(j)

×

50

×

70. Therefore, the part consists of 14 features as shown in the figure.
This part is assumed to be machined in a job shop, in which the available machines are: one three-axis
conventional vertical milling machine (M1,

MCI

= 35), one three-axis CNC vertical milling machine
(M2,

MCI

= 70), one drill press (M3,

MCI

= 10), one conventional horizontal milling machine (M4,