Ga Machine Cell
Ga Machine Cell
Ga Machine Cell
Cellular Manufacturing Systems (CMS) have been the key to the success of manufac-
turing industries in the recent past. Machine cell design, which involves formation of
machine cells and component groups, represents the most important step in the design
of CMS. Even though a tremendous amount of research has been conducted in this
area, the gap between theoretical research and practice is widening primarily because
of the lack of consideration of key production data such as production volumes, oper-
ations sequences, machine sequence inside the cells, processing times, setup times, and
machine costs during the cell design stage. This paper discuses the development of a
Genetic Algorithm Model (GAM), designed to assist in the formation of manufacturing
cells. The GAM aims at the minimization of the material handling and the penalty costs
while considering the effects of inter-cell, intra-cell, backtracking, and machine skipping
movements.
1. Introduction
Increased competition and fluctuating market demands have driven many manu-
facturing firms to consider novel approaches to improve productivity and eliminate
waste. In the past two decades, manufacturing industries have undergone a revo-
lution, widely considered as the third industrial revolution.1 Many innovative con-
cepts have surfaced, and only a few among them has been successful. The concept
of Group Technology (GT) is one of such successful principles embraced by most
industries.
Group Technology (GT) is the exploitation of the similarities among processes
and component designs in such a way that it increases the utilization of resources,
and eliminates/reduces nonvalue added activities, i.e., material handling, scraps,
downtime, etc. GT exploits similarities in three different ways: (1) by performing
alike activities together, (2) by standardizing similar tasks, and (3) by efficiently
storing and retrieving information about recurring problems.2 GT forms the basis
27
April 24, 2006 17:5 WSPC/180-JAMS 00071
Figure 3 shows a feasible solution generated for the problem under consideration.
The calculation of the overall cost using the heuristic is discussed as follows.
Component 1 has a production volume (PV) of 100, and its sequence of opera-
tions is 1-2-3. As per the solution shown in Fig. 3, component 1 belongs to cell 1. For
this component, there is no inter-cell cost since all the machines required to process
it are located in cell 1 itself. There is an intra-cell movement associated with the
movement from machine 1 to 2 that involves a machine skipping. A backtracking
cost, without machine skipping, is associated with this component as it moves from
machine 2 to 3. This move is considered as backtracking because the direction of
part movement (machine 2–3) is opposite to that of the direction in which these
two machines are located (machine 3 followed by machine 2). The penalty cost is
zero since all the machines required for component 1 are located in cell 1, the cell
to which component 1 is assigned. Therefore:
YES NO
operation no
=1
mpcellno
R. Rajagopalan & D. J. Fonseca
compcellno
operation no= operation no+1
NO NO machcellno(current)= YES
machcellno(previous)
PC=PC+(ST*MR/60)+(PT*MR*PV/60)
00071
PC=PC+(ST*MR/60)+(PT*MR*PV/60)
Current Machine Postion
operation no= operation no+1 IRC=IRC+(PV*Intercell_cost)
> Previous Machine
YES Position NO
NO YES
machcellno(current)= operation no= operation no+1
PC=PC+(ST*MR/60)+(PT*MR*PV/60) PC=PC+(ST*MR/60)+(PT*MR*PV/60)
machcellno(previous)
IAC=IAC+(Current Position-Previous BC=BC+(Previous Position-Current
IRC=IRC+(PV*Intercell_cost) Position)*Intra_cell_cost*PV Position)*Backtrack_cost*PV
Step-3
Current Machine Postion
operation no= operation no+1 operation no= operation no+1
operation no= operation no+1 > Previous Machine
YES Position NO
Step-3
Step-3
Machines
1 2 3 4 5
1 1 2 3 0 0
2 1 2 0 3 0
3 2 1 0 0 0
4 0 0 0 1 2
5 0 0 1 2 3
6 0 0 0 2 1
1 5 4 3 0 0
2 6 2 0 3 0
3 4 5 0 0 0
Components
4 0 0 0 4 6
5 0 0 4 3 2
6 0 0 0 3 4
Setup Time in Each Machine (Minutes) = {120, 75, 100, 60, 100}
Machine Cost for Each Machine ($/Hour) = {25, 35, 50, 20, 40}
1 3 2 4 5
Cell 1 Cell 2
Machines 1 2 3 4 5 6
1 2 1 1 2 1
Cells
In a similar fashion, the different cost elements can be calculated for all the
components as shown in Table 1. The overall cost incurred by all the components
is $5628.33. This cost is treated as the fitness function for the GAM, and this
effectively guides the GAM toward the optimal/near-optimal solution.
Comp No. Material Handling Costs ($) Penalty Costs ($) Overall Cost ($)
Inter Intra Back Total Setup Process Total
1 0 200 200 400 0 0 0 400
2 1500 600 0 2100 20 300 320 2420
3 0 0 800 800 0 0 0 800
4 0 250 0 250 0 0 0 250
5 750 150 0 900 8.33 500 508.33 1408.33
6 0 0 350 350 0 0 0 350
4800 828.33 5628.33
April 24, 2006 17:5 WSPC/180-JAMS 00071
Machines 1 2 3 4 5 6
Machine
1 4 5 2 3 6
Sequence
Machines 1 2 3 4 5 6
Cells 1 2 1 1 2 1
Machine
Sequence 1 4 5 2 3 6
Machines (Stage 1) 1 3 4 6 2 5
Cells 1 1 1 1 2 2
Grouped
Corresponding
1 5 2 6 4 3
Sequence
Machines (Stage 2) 1 4 3 6 5 2
Cells
1 1 1 1 2 2
Grouped
Sequence in
Ascending
Order 1 2 5 6 3 4
Final Machine
Sequence 1 4 3 6 5 2
Cell 1 Cell 2
which corresponds to the sequence of machines inside the cell 1. Similarly, the
sequence of machines inside cell 2 is 5 and 2.
The coding scheme used for component grouping is very similar to the one
defined for the machine cells. The only difference being that the total num-
ber of positions is equal to the number of components and not the number of
machines.
April 24, 2006 17:5 WSPC/180-JAMS 00071
procedure is implemented to check for empty cells every time the crossover operation
is implemented. If an empty cell is detected, the chromosome is removed, and
the crossover operator is applied again to generate a valid chromosome. The same
crossover operator with a similar checking procedure is applied for the component
population.
For the machine sequence population, a crossover operator called Partially
Matched Crossover (PMX) is applied. This operator ensures that the continuity
of number sequence is maintained. In this PMX, two chromosomes are randomly
selected for crossover, and two crossover sites are picked at random along the length
of the strings. A matching section is formed between the two crossover sites, and a
position-by-position exchange is executed to perform the crossover operation along
the matching section. PMX crossover is illustrated in Fig. 7. In this position wise
exchange, 5 from chromosome 1 is exchanged with 2 of chromosome 2. To avoid
repetition of sequence numbers, 5 also replaces 2 in chromosome 1. In this way,
PMX crossover is carried out between each position in the matching zone. The
probability of applying these crossover operators dictates the effectiveness of the
GA under consideration. A crossover probability of 0.8 was found to be effective in
most of the problems.
Before Crossover
9 8 4 5 6 7 1 3 2 10
8 7 1 2 3 10 9 5 4 6
After Crossover
9 8 4 2 3 10 1 6 5 7
8 10 1 5 6 7 9 2 4 3
are also exchanged along with their sequences. The probability of mutation usually
is kept very low, and in the GAM, a probability of mutation of 0.001 was found to
be effective.
5. Model Validation
For validating the GAM, several examples from the literature were used. The results
obtained from one such example are discussed here. The problem under considera-
tion is a 10 — machine, 16 — component problem.19 Figure 8 shows the sequence
matrix of this problem. This defines the sequence of operations followed by each
component. For example, component 1 is processed in machine 3 first, then in
machine 10, and finally in machine 2.
The 3-cell solution generated by the conventional methods, which do not take
into account any of the production data discussed before, is shown in Fig. 9. Accord-
ing to the solution, the designed cell accounts for one inter-cell movement as part 15
moves from machine 5 to 8. The number of voids, number of zeros, in the main diag-
onal is 16. The resulting grouping efficacy20 is 68.51%.
Figure 10 shows the inputs used for the GAM, and Fig. 11 displays the solution
generated by the GAM. Figure 12 shows the machine arrangements inside each
MC1 MC2 MC3 MC4 MC5 MC6 MC7 MC8 MC9 MC10
PR1 3 1 2
PR2 1 2
PR3 1 3 2
PR4 1 2
PR5 1 3 2
PR6 2 1
PR7 1 2
PR8 1 2
PR9 2 1
PR10 3 1 2
PR11 1 2
PR12 2 1
PR13 1 2
PR14 1 2
PR15 1 2 3
PR16 2 1 3
MC10 MC3 MC6 MC2 MC5 MC4 MC1 MC8 MC7 MC9
PR1 3 1 0 2
PR7 0 1 2 0
PR5 2 1 3 0
PR3 0 3 2 1
PR6 0 0 1 2
PR4 2 0 1
PR9 0 1 2
PR16 3 1 2
PR2 2 1 0
PR11 0 2 1
PR15 2 1 0 3
PR13 2 1 0
PR8 1 0 2
PR12 0 2 1
PR10 1 3 2
PR14 0 1 2
MC1 MC2 MC3 MC4 MC5 MC6 MC7 MC8 MC9 MC10
PR1 3 4 5
PR2 5 6
PR3 7 4 3
PR4 8 3
PR5 2 4 3
PR6 2 2
PR7 3 2
PR8 8 7
PR9 3 4
PR10 7 2 2
PR11 2 4
PR12 3 3
PR13 2 3
PR14 2 2
PR15 3 7 4
PR16 4 2 3
Production Volume
{100, 50, 150, 250, 600, 400, 200, 75, 300, 250, 50, 100, 500, 250, 150, 100}
Setup Time in Each Machine (Minutes)
{0, 60, 75, 100, 80, 45, 70, 120, 75, 100, 45,}
Machine Rate per Hour ($/Hr)
{25, 20, 15, 30, 35, 25, 40, 45, 20, 25}
Material Handling Cost per Unit
Inter-Cell Material Handling Cost per Unit = $ 5.00
Intra-Cell Material Handling Cost per Unit = $1.00
Backtracking Material Handling Cost per Unit = $2.00
MC3 MC10 MC6 MC2 MC8 MC7 MC9 MC4 MC1 MC5
PR1 1 2 0 3
PR3 3 0 2 1
PR5 1 2 3 0
PR6 0 0 1 2
PR7 1 0 2 0
PR8 1 0 2
PR10 1 2 3
PR12 0 2 1
PR13 2 1 0
PR14 0 1 2
PR2 1 0 2
PR4 0 1 2
PR9 1 2 0
PR11 2 1 0
PR15 3 1 0 2
PR16 1 2 3
Cell 1 Cell 2
Cell 3
cell as generated by the GAM. As far as the machine cells and the component
groups are concerned, the solution generated by the GAM is the same as that
generated by the conventional method. The number of inter-cell moves is 1 due
to part movement from machine 5 to 8; and the number of voids inside the main
diagonal is unchanged from the conventional- method solution at 16, resulting in
the same grouping efficacy of 68.51%.
However, the effect of intra-cell, backtracking, and machine skipping costs, and
the consideration of machine sequences inside the cells is evident in the difference
between the overall costs incurred by the two methods. Table 2 summarizes the vari-
ous material handling movements, and incurred costs. The inclusion of the machine
sequences has resulted in the reduction of the backtracking moves from 12 to 4
April 24, 2006 17:5 WSPC/180-JAMS 00071
6. Conclusions
The GAM has several advantages over the existing methods. In the GAM, the
consideration of the machine sequences at the cell design stage itself gives a more
realistic estimate of the material handling costs. Most of the existing methods
consider the sequencing of machines in the layout stage; and hence, the material
handling costs calculated by most of these methods are far from being realistic.
April 24, 2006 17:5 WSPC/180-JAMS 00071
Also, most of the existing cell formation techniques do not consider the effects of
backtracking and machine skipping in arriving at the material handling costs. Many
of them just consider the inter-cell costs alone. The GAM, however, considers all
the elements of the material handling costs in the right magnitude. Moreover, the
methods developed earlier involved stages of complex computations. The GAM,
on the other hand, is a one-step method that is computationally less tedious, and
provides effective solutions in minimal time.
References
1. J. T. Black, The Design of the Factory with a Future (McGraw-Hill Inc., New York,
1991).
2. N. Singh, Systems Approach to Computer-integrated Design and Manufacturing (John
Wiley & Sons Inc., New York, 1996).
3. N. Singh and D. Rajamani, Cellular Manufacturing Systems: Design, Planning and
Control (Chapman & Hall, London, 1996).
4. J. McAuley, Machine grouping for efficient production, The Production Engineer 51
(1972) 53–57.
5. J. R. King, Machine-component grouping in production flow analysis: an approach
using rank order clustering algorithm, International of Journal of Production Research
18 (1980) 213–232.
6. H. M. Chan and D. A. Milner, Direct clustering algorithm for group formation in
cellular manufacture, Journal of Manufacturing Systems 1(1982) 65–74.
7. M. P. Chandrasekharan and R. Rajagopalan, MODROC: An extension of rank order
clustering for group technology, International Journal of Production Research 24
(1986) 1221–1233.
8. S. Sankaran and R. G. Kasilingam, An integrated approach to cell formation and
part routing in group technology manufacturing systems, Engineering Optimization
16 (1990) 235–245.
9. R. Logendran, A workload based model for minimizing total inter-cell and intra-cell
moves in cellular manufacturing, International Journal of Production Research 28
(1990) 913–925.
10. R. Logendran, Impact of sequence of operations and layout of cells in cellular manu-
facturing, International Journal of Production Research 29 (1991) 375–390.
11. B. R. Sarker and C. V. Balan, Cell formation with operation times of jobs for even
distribution of workloads, International Journal of Production Research 34 (1996)
1447–1468.
12. P. Verma and F. Y. Ding, A sequence-based materials flow procedure for design-
ing manufacturing cells, International Journal of Production Research 33 (1995)
3267–3287.
13. G. K. Adil, D. Rajamani and D. Strong, Cell formation considering alternate routings,
International Journal of Production Research 34 (1996) 1361–1380.
14. Y. Won and K. C. Lee, Group technology cell formation considering operation
sequences and production volumes, International Journal of Production Research 39
(2001) 2755–2768.
15. G. Harhalakis, R. Nagi and J. M. Proth, An efficient heuristic in manufacturing
cell formation of group technology applications, International Journal of Production
Research 28 (1990) 185–198.
April 24, 2006 17:5 WSPC/180-JAMS 00071