Luong, L. H. S. et al "Genetic Algorithms in Manufacturing System Design"
Computational Intelligence in Manufacturing Handbook
Edited by Jun Wang et al
Boca Raton: CRC Press LLC,2001

©2001 CRC Press LLC

6

Genetic Algorithms
in Manufacturing

System Design

6.1 Introduction

6.2 The Design of Cellular Manufacturing Systems

6.3 The Concepts of Similarity Coefficients

6.4 A Genetic Algorithm for Finding the Optimum Process
Routings for Parts

6.5 A Genetic Algorithm to Cluster Machines
into Machine Groups

6.6 A Genetic Algorithm to Cluster Parts into
Part Families

6.7 Layout Design



L. H. S. Luong

University of South Australia

M. Kazerooni

Toosi University of Technology

K. Abhary

University of South Australia

©2001 CRC Press LLC

When some forms of automation are applied to a cellular manufacturing system, it is usually referred
to as a flexible manufacturing system (FMS). These forms of automation may include numerically
controlled machines, robotics, and automatic guided vehicles. For these reasons, FMS can be regarded
as a subset of cellular manufacturing systems, and the design procedures for both cellular manufacturing
systems and FMS are similar.
The benefits of cellular manufacturing system in comparison with the traditional functional layout
are many, including a reduction in set-up time, work-in-process, and manufacturing lead-time, and an
increase in product quality and job satisfaction. These benefits are well documented in literature. This
chapter presents an integrated methodology for the design of cellular manufacturing systems using genetic
algorithms.

6.2 The Design of Cellular Manufacturing Systems

The first step in the process of designing a cellular manufacturing system is called


and a

ji

is otherwise 0. Many attempts have
been made to convert this form of matrix to a block diagonal form, as shown in Figure 6.2. Each block
in Figure 6.2 represents a potential manufacturing cell. Not all incidence matrices can be decomposed
to a complete block diagonal form. This problem can come from both

exceptional elements

and

bot-
tleneck machines

. There are two possible ways to deal with exceptional elements. One way is to investigate
alternative routings for all exceptional elements and choose a process route that does not need any
machine from another cell. However, this solution cannot be achieved in most cases. Another way is
subcontracting the exceptional elements to other companies. If there are not many exceptional elements,
this way seems more reasonable, although it may incur extra handling costs and create problems with
production planning and control.
In the presence of bottleneck machines, the system cannot be decomposed into independent cells, and
some intercellular movements are inevitable. The impact of bottleneck machines on the system is increas-
ing usage of material handling devices due to parts moving amongst the cells. Obviously a high number
of intercellular movements will lead to an increase in material handling costs. Therefore, to decrease the

FIGURE 6.1

An init ial ma chine–component matrix.

29 1 11 1
30
11 1 111 1
M
A
C
H
I
N
E
S

©2001 CRC Press LLC

number of intercellular movements, some or all bottleneck machines should be duplicated. However,
duplicating of bottleneck machines is not always economical. To justify which machine is to be duplicated,
some subproblems including

clustering procedure

,
intracell layout,

and

intercell layout



FIGURE 6.2
A block diagonal f orm (BDF) o f machine–component matrix.
PARTS
9 27 21 39 24 14 18 1 13 35 16 11 2 31 20 26 3 10 12 22 29 23 15 4 17 19 28 25 8 5 33 38 30 40 6 7 32 37 34 36
61111
14 1 1 1 1
18 11 11 11
11 1 1 1 1 1
8111
19 11 111
20 11 111
9111111
15 1 1 1 1 1
16 1 1 1 1 1
10 1 1 1 1
12 1 1 11 11
13 1 1 1 1 1 1
17 1111111
21 1
1 111 1 11
22 111 11 11 1
24 111 11 11 1
2 11 11 1 1
7 111 111
30 111111 1
26 11111 11

problems of small scale.
This chapter presents an integrated methodology for cellular manufacturing system design based on
genetic algorithms. This methodology takes into account all relevant production data in the design
process. Other features of this methodology include design optimization and the ability to handle design
constraints such as cell size and machine duplication.

6.3 The Concepts of Similarity Coefficients

The basic idea of cellular manufacturing systems is to take the advantages of similarities in the process
routings of parts. Most clustering algorithms for cell formation rely upon the concept of similarity
coefficients. This concept is used to quantify the similarity in processing requirements between parts,
which is then used as the basis for cell formation heuristic methods. This section introduces the concept
of machine chain similarity (MCS) coefficient and part similarity coefficient that can be used to quantify
the similarities in processing requirements for use in the design process. A unique feature of these
similarity coefficients is that they take into consideration all relevant production data such as production
volume, process sequences, and alternative routings in the early step of cellular manufacturing design.

6.3.1 Mathematical Formulation of the MCS Coefficient
The MCS

ij

, which presents machine chain similarity between machines

i

and

N

= number of partsM

= number of machines
or mathematically,
MCS
if
if
ij
il
k
jl
k
k
N
k
N
l
M
kl kl
k
N
l






===
==
∑∑∑
∑∑
,
'
111
11
1
V
kl
'
P
kili
kili
il
k
=
≠
=
production volume for part moved between machines and if l
production volume for part moved between machines and if l

©2001 CRC Press LLC



i

and

l

, directly or indirectly
The extreme values for an MCS coefficient are 0 and 1. When the value of MCS

ij

is 1, it means that
all production volume transported in the system are moving between machines

i

and

j

. On the other
hand, an MCS

ij

with a value of zero means that there is no part transported between machines

i


2

and M

3

can be positioned in the same cell. Consequently,
the MCS coefficient for these machines is more than zero. On the other hand, if these two machines are
in separate cells, then their MCS coefficient would be zero.
Table 6.2 is the production volume matrix showing the volume of parts transported between any pair
of machines. The element

a

ij

in this table indicates the production volume transported between machines

i

and

j

(

i

≠



P

4

P

5

Production volume 100 150 70 150 160
Routing sequence M

1

-M

3

-M

5

-M

6

M

2


3

-M

6

-M

1

-M

3

M

5

-M

1

-M

3

TABLE 6.2

Production Volume Transported between Pair of Machines



2

0 360 0 150 0 360
M

3

560 0 810 0 410 400
M

4

0 150 0 300 0 150
M

5

410 0 410 0 510 250
M

6

250 360 400 150 250 760
P
il
k
=
=
≠

if
1 if { 1 or },
2 otherwise
llG
k
==



W
il
k
P
k
k
26
1
5
/
=
∑

©2001 CRC Press LLC

It should be noted that the first term in the above calculation (part 2) is due to the indirect relationship
between machines 2 and 6, while the second term indicates that there are three trips between these two
machines. In the case of

i = j


indicates the MCS coefficient between machines

i

and

j

. For example, the MCS coefficient between machines M

3

and M

6

can be computed as follows:
MCS

M
3
M
6

= = 0.3757
Once the MCS matrix is obtained, it can be normalized by dividing all elements in the matrix by the
largest element in that matrix (Table 6.4). In comparison with McAuley’s similarity coefficient [1972],
the results in Table 6.4 indicate that production volume and process sequence can make a significant
difference in the pairwise similarity between machines.



k

th

element of

MRV

i
N

kj

=

k

th

element of

MRV

j
2i

,

N

3i

, ...,

N

ki

, ...,

N

mi

] Equation (6.4)
where

k

is

k
th
machine and m is the total number of machines. N

()
+
()
+
()
+
()
+++++
PS N N
ij ki kj
k
M
min ,
()
=
∑
1
©2001 CRC Press LLC
N
ki
=
N
uki
shows the frequency that part i travels to and from machine k multiplied by the production volume
required for part i. For example, consider the problem of six machines and five parts shown in Table 6.1,
and lets assume that the machines have been sequenced in the order of [M
2
, M
3
, M

1
M
2
M
3
M
4
M
5
M
6
M
1
1 0.0723 0.5144 0.0434 0.4277 0.3324
M
2
1 0.1040 0.1301 0.0723 0.2514
M
3
1 0.0434 0.4277 0.3757
M
4
1 0.0434 0.1300
M
5
SYMMETRIC 1 0.3324
M
6
1
TABLE 6.4 The Normaliz ed MCS Matrix

1
Ni k
ik
uki
if part meets machine
0 if part does not meet machine



©2001 CRC Press LLC
the following chromosome representation shown in Figure 6.5 is used. In Figure 6.5, a
i
represents the
selected process routing for part i, and can be any number between 1 and p for part i. However, all parts
do not have the same number of routings and every number between 1 and p cannot be valid for all
parts. To overcome such a drawback, the following procedure is done to validate the value of all genes
regardless of the number of routings that the corresponding part has.
1. Set the counter i to 1.
2. Read p
i
, the maximum number of routings that part i can have.
FIGURE 6.4 The three stages in the cell formation process.
FIGURE 6.5 Chromosome representation of parts’ process routing s.
A GA-based algorithm to find the optimum process routings for parts
Aim: Minimizing the number of intercellular movements of parts.
Input: Normalized MCS matrix.
Objective: Maximize the number of zeros in the MCS matrix.
Output: A MCS matrix which represents the selected process routings
for parts which yield the maximum number of independent cells.
A GA-based algorithm to cluster machines into machine groups

i
=
5. If a
i
≥ p
i
, go to step 4 =, otherwise increment i by one.
6. If i > n (number of parts), stop, otherwise go to step 2.
With this procedure, for example if the value of the first gene in Figure 6.5 is 5 and there are only
three different alternative routings for part 1, then the gene value is changed to 2 (i.e., 5 – 3). Using the
above procedure, the gene values in the chromosome will be valid. It should be noted that if a part has
only one process plan, it should not participate in the chromosome, because its process routing has been
already specified.
6.4.1.1 The Crossover Operator
Since a gene in the chromosome can take any number between 1 and p, and repeated value for gene is
allowed, any normal crossover technique such as two-point crossover or multiple-point crossover can be
used in this algorithm.
6.4.1.2 The Fitness Function
The fitness function for this algorithm is to maximize the number of zeros in the MCS matrix.
6.4.1.3 The Convergence Policy
The entropic measure H
i
,

as suggested by Grefenstette [1987], is used for this algorithm. H
i
in the current
population can be computed using the following equation:
Equation (6.5)
where n


H
i
ij
j
p
ij
n
SP
Log
n
SP
Log p
=












()
=
∑
–*