Direct Clustering Algorithm for Group Formation in

Cellular Manufacture
H.M. Chan, D.A. Milner, Dept. of Production Technology and Production Management
The University of Aston in Birmingham, Birmingham, England

production system and to determine those families

Abstract of components which are related by a similarity in
This paper describes a new algorithm which production facilities required to manufacture them.
has been developed for forming component One well known method is Production Flow
families and machine groups for cellular manu- Analysis developed by BurbidgeL This is a material
facture by progressively r e s t r u c t u r i n g the flow simplification technique based on the assump-
machine component matrix. The method allows tions that the majority of components and machines
interaction from the user w h e n exceptions and
overlap between groups cause the iterative in a factory already belong to clearly defined
algorithm to prematurely stop. This is an effective families and groups, and that these groups and
and efficient approach which offers great flexi- families can be identified by a progressive analysis
bility in determining the optimum families and of the information contained in the route cards and
groups. The algorithm is specifically designed the plant list. The advantage of this method is that it
for computer use in dealing with large amounts is only concerned with the plant, toolings and
of data obtainable in realistic situations, although
the procedures are simple, and can be carried methods of manufacture which are at present being
out manually for the analysis of small machine used in the factory. It provides an economic
component matrices. approach to cellular manufacture applications and
Keywords: Cellular Manufacture, Group in many circumstances, this can be the only sensible
Analysis, Direct Clustering AIgorithm, Multiple approach.
Machines, Exceptional Elements.
There are three main stages in Production
Flow Analysis, namely (1) factory flow analysis to
determine the departmental structure in the factory;
Cellular manufacture has been recognized as a (2) group analysis to determine the component
technique which allows small batch production to families and machine groups in each department
achieve similar economic advantages to those and, (3) line analysis to determine the ultimate
associated with continuous flow line production. In layout of each machine group. Group analysis
order to design cellular manufacturing groups, forms the major part of this work which is the actual
several methods based on the analysis of production formation of component families and machine
information have been developed as alternatives to groups for cellular manufacture layout. This stage is
the classification and coding approaches. These probably the most difficult and critical in the
methods are different with respect to the underlying application of PFA. The basic steps include the
assumptions and the techniques of analysis, but formation of a machine component matrix consti-
their general approach is to study a company's total tuting the data required, and the derivation of
65
Journal of Manufacturing Systems
Volume I, Number I

machine groups and c o m p o n e n t families by a f o r m o f the m a t r i x . H o w e v e r , a f t e r v a r i o u s

quantitative analysis of this data. However, since exchanges of the relative positions of rows and
the introduction of P F A ; there exists the problem of columns, the matrix can be converted into a clustered
defining a general procedure which would convert a form as shown in Figure lb. In this clustered form
given machine c o m p o n e n t matrix into a clustered the original matrix entries are unaltered but distinct
form from which independent groups can be identi- machine c o m p o n e n t groupings are formed along
fied. The method must be suitable for computer the diagonal of the matrix as a result of the rows and
applications since manual methods can be tedious columns rearrangements. N o w it can be seen clearly
and not applicable for the analysis of large amounts that c o m p o n e n t s n u m b e r 2, 3 and 5 are to be
of data obtainable in realistic situations. As Burbidge processed in the group consisting of machines
stated in his book2: "It is comparatively simple to n u m b e r 1,2, 4 and 6 and that components number 1
find the groups and families by eye with a small and 4 are to be processed in the second group
sample. The mental processes used combine pattern consisting of machines number 3, 5 and 7. Hence the
regonition, the application of production know how problem of group analysis is solved.
and intuition. However, it has proved to be surpris-
ingly difficult to find a method suitable for the M/C NO
COMP I 2 3 4 5 6 7
computer which will obtain the same results". NO
1 X X X
2 X
This p a p e r describes a Direct Clustering
4 l X X
Algorithm for solving the problem. This method is 5 X X X

specifically developed for c o m p u t e r use although Figure la

the procedures are simple and can be carried out Original Matrix
manually for the analysis of small machine-compo-
M/C NO
nent matrices. COMP I 2 4 6 3 5 7
NO
2 X X X X
5 X X X
3 X X X
I X X X
The Problem 4 X X X

Figure lb
The problem can be summarized as to divide The Same Matrix Showing a Clustered
components into families and machines into groups, Pattern ~ith Two Groups
in such a way that each c o m p o n e n t can be fully
processed in one group. The stage preceding group For a small machine component matrix, it is
analysis involves the formation of a machine- comparatively easy to determine by visual inspection
c o m p o n e n t matrix with the rows labelled with the appropriate rows and columns rearrangements.
c o m p o n e n t numbers and the columns with machine The difficulty is to find a systematic analytical
numbers. An entry o f " X " in cell I and J means that method which would convert any original matrix
c o m p o n e n t I requires processing on machine J and a into a clustered form in order to deal with realistic
blank entry means that it does not. This opposes problems.
the conventional way of labelling a machine compo-
nent matrix. However, since the number of c o m p o -
nents in a factory is usually more than and more Problem Solving Contributions
likely to vary than the number of machines, it would
be desirable to store c o m p o n e n t information in The approach as suggested by Burbidge used a
rows in order to facilitate easier data handling. This punched card sorting technique. This was later
convention will be adopted throughout this paper adopted by Gallagher et al in an application of P F A
except in the last example where a machine compo- in the plastic moulding industry ~. However, it was
nent matrix presented by another researcher will be found that the technique worked in so far as it
used for illustrating the application of the Direct created a detailed chart of flow sequences, but it
Clustering Algorithm. failed to provide a suitable means of establishing
Consider the illustrative example shown in groups from this data. This difficulty was recognized
Figure la and no particular pattern of machine by Burbidge who later found a technique of Nuclear
c o m p o n e n t grouping can be seen in this original Synthesis 4. In this method, the low usage machines
66
 Journal of Manufacturing Systems
Volume 1, Number I

are identified as key machines which eventually to generate diagonalized groupings in a machine
become the nuclei to which other machines required component matrix. It requires the pattern of cell
for the same components may be added to form entries in the rows and columns of the matrix to be
groups. Larger sized groups can be formed by read as binary words. The corresponding decimal
appropriately combining these nuclear groups. A equivalence of these binary words are then used as
computer programme was written to use this method the basis for the ranking of the rows and columns.
which has led to the development of a new manual The algorithm rearranges rows and columns in an
method based on the same principle s. iterative manner and eventually produces a matrix
Another approach was described by EI-Essawy in which columns and rows are positioned in an
and Torrence in their work of Component Flow order of decreasing binary values. When the size of
Analysis6. This method uses computer assistance the machine component matrix becomes larger, the
in identifying similar manufacturing sequences. The process of calculating the equivalent decimal values
output which shows the complexity as well as the of the binary words can become very tedious and
similarity between each of the machine tool combi- time consuming. This was recognized by King who
nations for the components, provides the basic data later suggested a pairwise word comparison process
for analysis. The component families and machine in replacement of evaluating the binary numbers t3.
groups are formed by. a subjective process, taking It is claimed that the major advantage of this Rank
into consideration the group size, machining opera- Order Clustering Algorithm over the other methods
tions, component features, workload on each group is its ability to deal easily with the problems of
and other restricting factors. This method is exceptional elements and bottleneck machines.
generally manually biased although computer tech-
niques are also used. The major part of group
formation is carried out manually since the use of a The Direct Clustering Algorithm
computerized method has been proved to be unjusti-
Direct Clustering A l g o r i t h m is a newly
fiably sophisticated.
developed technique which provides a simple and
McAulley proposed the use of a similarity effective way of clustering data directly from any
coefficient and Single Linkage Cluster Analysis for given machine component matrix. The method is
solving the group formation problem 7. This is based based on the ideas of finding the families and groups
on the numerical taxonomic algorithm as published by using blocks and rods, and by changing the
by RossL The similarity coefficient for any machine sequence in which components and machines are
pair is first computed and the result is represented listed on the matrix. A systematic procedure is used
pictorially by a dendrogram at an appropriate instead of relying on intuition in determining what
similarity level. The method requires a secondary row and column rearrangements are required to
process of component allocation to the machine achieve the desired result. Also a computer pro-
groups after the groups are formed. This approach gramme is used in replacement of the blocks and
was adopted by several other researchers. It was also rods.
used by Carrie as one of the several facilities for For convenience those cells entered with "X"
determining the extent to which the work of the in the machine component matrix will be termed the
design of a production system may be done by positive cells and those with blank entries the
computer 9.
negative cells. The Direct Clustering Algorithm
Other computer simulation methods being consists of going through the matrix sequentially,
developed for clustering solutions a r e due to moving the rows with the 'left-most' positive cells to
CrookalU 0 and McCromick~. The former uses the top and the columns with the 'top-most' positive
known data to simulate group manufacture condi- cells to the left of the matrix. In repeated trips the
tions by Monte Carlo method. The latter optimizes positive cells will be squashed toward the diagonal
the bond energy between adjoining row and column of the matrix and a clustered pattern will eventually
elements in a matrix and forms groups. be formed extending from the top left corner of the
Another computerized clustering technique matrix. The basic rule is that each component or
was developed by King, called the Rank Order machine number must be moved together with its
Clustering Algorithm ~2. This method is designed respective row or column entries during matrix
67
 Journal of Manufacturing Systems
Volume I, Number I

transformation as if the cells or the blocks are linked cell entries in this column are components number
together by an imaginary rod. The procedures of the 9, 4, 3 and 6. These are moved to the top of the new
algorithm are described in the following. matrix in the same order as they appear in the
current matrix. Next, the second column is con-
(1) C o u n t the number of positive cell entries " K "
sidered but nothing happens since all the positive
in each column and row in turn. Rearrange the
entries in this column have already been reallocated.
machine c o m p o n e n t matrix with columns in
The algorithm applies to the third column consisting
decreasing order o f " K " a n d rows in increasing
of machine n u m b e r 15 which groups together
order of "K".
c o m p o n e n t s n u m b e r 8, 5 and 2. The other rows are
(2) Starting with the first column of the matrix,
rearranged in a similar manner and the resulting
transfer the rows which have positive cell
matrix after the first rows rearrangements is as
entries in this column to the top of the matrix.
shown in Figure 2e. N o w the algorithm is repeated
Repeat the procedure with the second column,
on the matrix of Figure2e, but this time the columns
then the other columns, until all the rows are
are arranged instead of the rows. Figure 2d shows
rearranged.
the example matrix after the first columns rearrange-
(3) Are the current matrix and the one immedi~itely
ments, clustered machine c o m p o n e n t groups can be
preceding this the same?
identified along the diagonal of this matrix. Applying
If yes, go to 6.
the iterative algorithm again will not change the
If no, go to 4.
pattern of the matrix in Figure2d, therefore it is the
(4) Starting with the first row of the matrix,
finalized form.
transfer the columns which have positive cell
entries in this row to the left-most position of
M/C NO.
the matrix. Repeat the procedure with the COMP 1 2 3 4 5 6 7 8 9 10 II 12 13 14 15
NO
second row, then the other rows, until all the 1 X X X X 4
2 X X X X X 5
columns are rearranged. 3
4
X
X X
X X
X
X
X
4
4
5 X X X X X 5
(5) Are the current matrix and the one immediately 6 X X X X X 5
7 X X X X X 5
preceding this the same? 8
9
X
X
X
X
X
X
X
X
X 5
4
10 X X X X X 5
If yes, go to 6. 3 3 3 3 3 3 2 3 4 3 3 3 3 4 4

If no, go to 2.
Figure 2a
(6) Stop. Example Matrix
This algorithm can work with any starting
form of machine c o m p o n e n t matrix. The procedure
M/C NO.
is iterative and the ultimate result will be the same. It COMP
NO.
14 9 15 13 12 11 10 8 6 5 4 3 2 1 7

9 X X X X 4
will converge in a limited number of iterations, and 4 X X X X 4
3 X X X X 4
will find the groups and families directly from the 1 X X X X 4
IO X X X X X 5
matrix. The algorithm is readily computerized which 8
7
X X
X X X
X X X
X X
5
5
6 X X X X X 5
allows the practical difficulties of data analysis for 5 X X X X X 5
2 X X X X X 5
large matrices to be overcome. 4 4 3 3 3 3 3 3 3 3 3 3 3 3 2

The method is best illustrated with an example Figure 2b

problem: Consider a machine c o m p o n e n t matrix as Matrix after Initial Arrangement
shown in Figure 2a. The n u m b e r of positive cell
entries in each column or row is calculated and listed
at the end of the respective column or row. Figure2b MIC NO
COMP 14 9 15 13 12 II 10 8 6 5 4 3 8 I
shows the same matrix after initial arrangements, NO.
9 X X X X
the columns and rows are respectively ranked in 4
3
X
X -X
X
X
X X
X
6 X X X X X
order of decreasing and increasing values of the 8 X X X X X
5 X X x X X
number of positive cell entries. This becomes the 2
I
X X
X X X
X X X
X
10 X X X
9 starting matrix for the iterative algorithm. The first 7 X X X
x
X

column to be considered is that consisting of

Figure 2c
machine number 14. The rows which have positive After Row Rearrangements

68
 Journal of Manufacturing Systems
Volume 1, Number I

divided is the one consisting of machine number 6.

M/CNO
COMP
NO.
1 4 9 6 4 1 16 13 8 5 3 12 I1 I0 2 7 Thus to improve the solution, machine 6 has to
9 l l X ~
4 XX X become a multiple machine. The positive entries in
3 X X X X
6 X X X X X
X X X X X
this column are temporarily overwritten by the plus
8
5
2
I xl xX X
X
X
X
symbol (+) which will be considered as equivalent to
Ix IX fX I xX X
a negative entry in the computation. Applying the
7
Direct Clustering Algorithm to this modified matrix,
Figure2d finalized pattern as shown in Figure 3c is obtained.
The Finalized Pattern
The matrix shows that three machine groups have
been generated. However, the first two groups are
Sometimes one or more machines may be
required by a large proportion of the components. not mutually independent due to the overlap or
In such cases, the machine component groupings requirements on machines number 7 and 11. One
formed will be very large, less dense and not component from the first family and two compo-
mutually independent. For example, consider a nents from the second family require processing on
machine 7. Whereas one component from the first
machine component matrix as shown in Figure 3a.
By applying the Direct Clustering Algorithm, a family and three components from the second
finalized pattern as shown in Figure 3b is obtained family require processing on machine 11. In such
which cannot be changed any further. However, this cases where obstruction is caused by only a few cell
matrix does not show a desirable solution since the entries, it would be uneconomical to introduce
multiple machines. The extra machine component
first machine group formed is too large and scattered.
pairings should be considered as exceptions which
In order to let the algorithm continue, the column
should be excluded from the grouping process.
entries causing obstruction must be temporarily
deleted. Here assumptions are made that one
machine type can exist in several groups, and that M/C NO
COMP 14 3 1 7 4 II 12 2 15 13 I0 9 8 5 6
the columns which are deleted consist of machine NO.
3 X X X +
types which are readily available to all groups 9
4
X
X
X
X X
X X
X
+
+
8 X X X X X +
whenever required. These machines which will be 6 X X X X +
I X X X X +
allocated to more than one machine groups are 7
10
X X X
X X X X X
+
+
5 X X X X X
termed multiple machines. 2 X X X X X

Figure3c
M/C NO Result after Second Iteration with Obstruction Removed
COMP 1 2 3 4 5 6 7 8 9 I0 I1 12 13 14 15
NO
1 X X X X X
2
3 X x
X X X X X An examination of Figure 3c shows that the
4 x ^ X X
5 X X X X X singleton entries which cause obstructions in
6 X X X X X
7
8 X
X
X X
X
X
X
X
X
X
columns machine 7 and 11 are cells (9, 7) and (8, 11)
9
10
X X X X
X X X X X
respectively. In order to improve the solution further,
these exceptional cell entries are overwritten by the
Figure3a
Example Matrix asterisk symbol (*) which will be considered as
equivalent to a negative entry during computation.
M/C NO
Figure 3d shows the same machine component
COMP 6 12 I1 2 14 3 1 7 4 15 13 10 9 8 5
NO. matrix, with the multiple machine entries and the
7 X X X X
3
9
X
X
X
X
X
X
X
X
exceptional cell entries marked with the appropriate
8
6
X
X X
X
X X
X X X
X symbols and with the initial arrangements into
4 X X X X X
1 X X X X X decreasing column sums and increasing row sums.
10
5
~ X X X
X X X Applying the Direct Clustering Algorithm to this
2 X X X ' X
newest version of the matrix results in the generation
Figure3b
Result after First Iteration of a finalized pattern as shown in Figure 3e. Now
this matrix shows an acceptable solution because
Referring to Figure 3b, the column which mutually independent machine groups and compo-
prevents the first family grouping to be further nent families are readily observed. The multiple
69
Journal of Manufacturing Systems
Volume I, Number i

machine entries are shown on t h e right of the any practical restrictions which may exist in the
matrix. These entries can be reinstated into the problem. This offers much greater flexibility in
appropriate groupings to form an ultimate solution deciding between possible options and is therefore
matrix which is shown in Figure 3f more preferable to a completely mechanistic process.

M/C NO
COMP 14 3 15 13 12 I1 I0 9 4 2 I 8 7 5 6
NO
9
7
X X
X X
X
X
"~ A Case Study
3 X X X ~"
8 X X ~" X X +
6
4 X X
X X
X
X
X
X *
+
Burbidge p r e s e n t e d a p r o b l e m with 16
I X X X X +
I0 X X X X X machines and 43 components which was also used
5 ^ X X x X
2 X X X X X by King for illustrating the application of his Rank
Figure 3d Order Clustering approach =3. Burbidge used a
Matrix with Obstruction and Exceptions Marked hand computed trial-and-error method and finally
came to a solution with five machine component
M/CNO groupings and three exceptional elements. King
COMP 1 4 3 4 1 1 5 1 3 1 0 9 8 5 1 2 1 1 2 7 6
NO used Rank Order Clustering Algorithm and came to
9 X X X ~*
3
8
XX
X X X X
X
~
+
+
a resulting solution with four component groupings
4
10
X X X X
X X l ~ X and two exceptional elements. Here this same
5 X X X X
2 X X X X X problem will be used for illustrating the application
7 X ~ X 9
6
1
X
X X X
X ~ +
9
of the Direct Clustering Algorithm.
The initial machine component matrix is as
Figure 3e
Result a~er Last Iteration shown in Figure 4a where the rows are labelled with
machine numbers and the columns with component
M/C ~0 numbers (this will not create any problems for the
COMP 1 4 3 4 1 6 1 5 1 3 1 0 9 8 5 1 2 1 1 2 7 6
NO algorithm because it is designed to cope with either
9 X X X *
3
8
XX
X ~ X X *
X+ convention. The only change will be that when
4 X XX
10 l X X ~ X introducing multiple machines, rows instead of
5 X X X X
2
7
X X X X X
X X ~
columns will be deleted). After the first run of the
6
1
xx
X X X X §
X DCA, this matrix is converted to a finalized pattern
as shown in Figure 4b. However, this is not a
Figure 3] desirable solution since no mutually independent
The Final Matrix
groups are readily observed. It is apparent that the
Problems similar to the second example in machines number 6 and 8 are heavily demanded by a
which some machines are required by many of the large number of components and create obstruc-
components are common situations in industry. tions. Thus they are made multiple machines and
This method allows flexibility in deciding the struc- the positive entries in these two rows are overwritten
tures and sizes of the groups. The multiple machines by the plus symbol (+). This modified matrix is
are identified from the resulting matrix fifter the first analyzed again by using the DCA and another
run of the algorithm, then the exceptional entries finalized pattern as shown in Figure 4c is obtained.
are identified. This progressive procedure provides It can be seen that clustered groups begin to form
an easy way of detecting the bottleneck machines or along the diagonal of the matrix, though not all of
the odd process route. Additional machines can be them are mutually independent. It is not difficult to
considered for the cases of overlap of component see that there are overlap requirements of machine
requirements between machine groups, and the groups by components number 2, 7 and 9. The
exceptional machine component pairings can be exceptiorial cell entries, which are identified as (14,
eliminated by rerouting or redesigning of the compo- 2) (16, 7) and (11, 9) are encircled in Figure 4c, and
nents. As illustrated in the second example, this overwritten by the asterisk symbol (*) before the
method uses an interactive approach which means matrix is used for the next iteration. Applying the
that the parameters can be altered at intervals Direct Clustering Algorithm to this latest edition of
during computation, taking into consideration of the matrix generates a final pattern as shown in
70
 Journal of ManufacturingSystems
Volume I, Number I

Figure 4d. Five machine-component groupings can matrix with mutually exclusive groups can be
be clearly and independently distinguished. The formed simply be reinstating the positive entries o f
multiple machine entries are shown at the bottom of the multiple machines to the clustered groups as
the matrix which ean easily be associated with the shown in Figure 4e.
appropriate groups formed. The ultimate solution
COMP. NO
M/C 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 31 38 39 40 4l 42 43
NO
1 X X
2 x X X x x X X x
3 X X x x -x
'5 1 x Xxx x x x x
x x x x x~ x x x x. x x x x x x ~ x x ~ x
? X X X
8 X X X X X X X X X X X X X X X X X X X X
9 X X X X X X X X X X
I0 X X X X X X X
II X X X
,, x x 1 1 x
13 X X
14 X X X X
15 X X X- X X X X
IG X X X X X X X X

Figure4a
The Machine Component Matrix Presented by Burbidge

COMP. NO.
M/C 37 42 2 38 32 10 7 18 40 28 4 19 43 23 14 1 33 17 13 12 8 39 34 6 24 21 9 41 27 3 31 20 1.5 11 35 3G ,5 29 16 2,5 26 30 22
NO.
1
IG X X x x x x x x
2 X X X X X
9 X X X X X X X X X X
6 X X X X X X x xxx xx x x~ xx xx
8 X X X X X X X X X X X X X X
v~ X x x x x x
3 X
,5 x ~ ~, x II ~X
, 1
,5 X X X X X X X X X X X

107 x ~x x x ~ x
13 ~ x x
12 ~ x x x x
11 x x

Figure 4b
The Result after Applying Direct Clustering AIgqrithm

COMP. NO
M/C 42 37 2 38 32 TO 18 7 40 28 4 35 17 6 36 34 24 3 30 27 22 11 9 20 21 19 14 5 29 23 43 41 33 16 15 8 25 13 I 39 31 26 12
NO.

' ~
T6 xx
9 ~ X X X X X X ~ X
14 X X X X
3 X X X XX
13 ~ X
12 X X X X
114 X X X X ~X
5 x I I I I I I ~ x x x x x
15 X l X l

'
10 I I I l l l X
8 § 2 4 7 + § + + + + + * * * § ~+ * + *
6 § § § § ++ § +~ * + § *

Figure4e
Result after Second Iteration ~ith Obstructing Rows Deleted

COMP.NO
M/C 42 37 38 32 10 2 18 40 28 4 24 3 30 27 22 II 20 21 19 14 5 43 41 3 3 - 29 23 9 16 15 8 35 17 6 36 34 7 25 13 I 39 31 26 12
NO
1
16
2
x ~ ] ~ x
9 X X X X X X X X X
13 X X
12 x x X ~ xx
11 X ~
15
4 ~ ~xx ~ ~ ~ x x
5 X X X X X X X
14
3 ~ X x x x
?
10 X X X X X
8
6

Figure 4d
Result after Final Iteration Showing Five Groups with Multiple and Exceptional Entries

71
Journal of Manufacturing Systems
Volume I, Number I

COMP. NO
~d/c 42 37 38 32 10 2 18 40 28 4 24 3 30 27 22 11 20 21 19 14 5 43 41 33 29 23 9 16 1,5 8 35 17 6 36 34 7 25 13 I 39 31 26
NO

16' I ~, x x ,, x x .j
2 l X X X X X X
9 X X X X X X X X X
$ + + +
6 § + * + §
13 ~x
11
I1 xxx~XX, x
8 + 9 9 § +
1.5
4
5 ~ ~ ~ ~ x ~ X
+
8
6 +
14
3
-v
x*** x x x X
6 *
7
10 X x~ ~xxxx
8
6 # + +

Figure 4e
The Solution IVlatrix by Using DCA Method, Compare this with Burbidge's Solution and King's Solution

Another facility provided by the Direct Cluster- and one machine 8 should be allocated to each of
ing Algorithm is the clear representation of the group 2 and group 3, accordingly.
bottleneck or exceptional entries which allows extra Case 3 - - N o additional machine is available
flexibilities in the final design of the actual groupings. and no exceptional component route can be changed
Referring to the solution matrix in Figure 4d, there due to practical restrictions. This is not u n c o m m o n
can be three ways of g r o u p i n g the m a c h i n e s in industry for there is usually resistanceto substan-
depending on the availability of resources. tial changes, especially when new investments are
Case 1 - - A s many additional machines as involved. The solution is to allocate the available
required are installed (in this example, four of each machines to the most demanding machine groups as
of machines 6 and 8 are required). The machine in Case 2, i.e., only machines 6 and 8 should be
groups formed will be mutually exclusive as shown allocated to machine group 3. Alternatively, the
in Figure 4e. Each component family can be fully bottleneck machines can form an independent group
processed within one machine group only, provided which will be visited by.components from the other
all the exceptional machine component pairings can machine groups, i.e., machines 6 and 8 together
be eliminated by rerouting or redesigning of the become the sixth machine group.
components. This is the ideal Cellular manufacture In both Cases 2 and 3, there would be some
situation where there is no inter cell material flow. components flowing between cells but most of the
The flow of components will be between each material flow would be restricted to within the same
machine group and the receiving and delivery points group. The inter cell flow can be determined by
only. considering the solution matrix. For example, it can
Case 2 - - L e s s a d d i t i o n a l m a c h i n e s t h a n be seen in Figure 4d that component 2 will require
required--say, two of each t y p e - - a r e available, and processing in machine groups 1,4 and 3 if machines
only some of the exceptional components can be rerouted. 6 and 8 are available in machine group 3 only. Thus
This may be due to lack of resources or other the flow of material a m o n g these three groups can
practical restricting factors. In this case, the solution be determined from the batch quantity of component
is to allocate the multiple machines to the most 2. This inter cell flow value will be the essential data
demanding machine groups. This can be determined required for the layout planning of the machine
by considering the number of plus entries (+) groups for cellular manufacture.
associated with each machine group and the batch Figure 5 shows Burbidge's manual solution
quantities of the respective components. For and Figure 6 shows King's ROC solution to the
example, in Figure 4d, the first and the third same problem. A comparison of Figure 4e with
machine groups have the most n u m b e r of pluses (+), these two alternative solutions shows that the
5 a n d 6 respectively, associated with machine 6. number and structure of the machine component
Also the second and third machine groups have the groups, and also the exceptional elements are in fact
most number of pluses (+), 5 and 8 respectively, identical in Burbidge's manual solution and in the
associated with machine 8. Therefore one machine 6 s o l u t i o n d e r i v e d f r o m the Direct C l u s t e r i n g
should be allocated to each of group I and group 3, Algorithm. However, King's solution shows some
72
 Journal of Manufacturing Systems
Volume I, Number 1

differences in the number of machine-component and bottleneck machines which frequently arise in
groups (4 compared with 5) and in the exceptional practical problems. However, it is also concluded
elemerrts (two instead of three and different that the ROC Algorithm is simply a ranking and not

CQMP. NO ,-
M/C I 13 39 25 12 31 26 42 37 2 32 38 l0 40 28 18 4 27 24 3 20 30 II 22 17 7 35 6 34 36 19 23 14 43 5 9 21 41 15 29 8 r IG
NO

7 X X X
8 X X X
,2 I I I I I I I I .x
,66 l i l l x . " x
8 X X X
1 X X
11
12
6
13 x
3 x x x x
6 x x x
14 x X x ~ ~ ~ x ~ ~ ~ x x ~ x x x
6
4 x X ~ x xx x~
6
15 ,.,. XX X X X X X X
8

Figure5
The Solution Matrix by Burbidge

COMP. NO.
M/t; I 12 13 39 31 25 26 2 37 42 31 28 38 10 413 18 4 7 6 34 17 35 36 24 3 27 9 20 I1 30 22 19 14 21 5 23 29 33 41 43 8 15 16.
NO.
1O X ~ X X X X X
6 X XX
8 XX X
7 X X X
9
2
6 I x x ~ Ixx
16 x ~ X X x x
x x x
B
14 X X XX
1 XX
3 X X X X X
8
II
13 x x
12 X X X X X
5 x x x ~ ~ ~ x x x x x x
4 1 X X X
Ifi ~ x ~xx
6
8 x ~ ~ xxlx

Figure 6
The Solution Matrix by King

elements). In all three cases, 4 machine 8 and 4 an optimizing procedure, and that the solution
machine 6 are required in order to achieve a solution- generated is determined by the form of the initial
_with mutually exclusive g_roups. matrix. The Direct C-lustering Algorithm effectively
The fact that Burbidge's manuai me]-laocland deals with the problems of exceptional elements and
the DCA approach had come to two identical bottleneck machines with a progressive procedure,
solutions is not merely a coincidence. This is It also regulates the initial matrix by pre-arranging
probably because the Direct Clustering Algorithm the rows and columns in orders of their positive
uses an approach based on the blocks and rods entries numbers, thus it can work with any starting
method which is believed to be the basis of Burbidge's form of machine component matrix and obtain the
trial-and-error method also. When the DCA solution same result. In more complicated problems the
is compared with the ROC solution, it is observed ultimate solution also depends on the choices of
that the groups formed in the former case are more multiple machines and exceptions: This is well taken
dense which means a higher machine utilization care of because decisions will be made with the
within the machine groups. It is claimed that the assistance of the intermediate solutions. The
major advantage for the Rank Order Clustering obstructing columns or exceptional entries can
Algorithm over the other methods lies in its ability to easily be spotted in the finalized pattern at the end of
deal easily with the problems of exceptional elements each run. As many columns and single entries as
73
"Journal of Manufacturing Systems
Volume I, Number 1

required can be temporarily deleted, though not 50 c o l u m n s t h e n only 24K of core store is required.
necessarily at the same time, until a satisfactory The D C A method is being used to implement
solution is finall3,obtained. cellular manufacture by a factory producing m o t o r
car components.

Applications to Realistic Problems

Concluding Remarks
A c o m m o n criticism on the various methods
developed for group formation is that they have The Direct Clustering Algorithm not only can
been applied to only machine c o m p o n e n t matrices cluster data from any given machine component
with relatively small numbers of elements. In realistic matrix, but also can effectively deal with exceptional
situations a large n u m b e r of c o m p o n e n t s and elements and bottleneck machines. The algorithm
machines may be involved. This is the type of provides a feasible approach to group formation in
problems which the group forming algorithms will cellular manufacture. Based on the same principle,
have to deal with in practice. The Direct Clustering the algorithm can be used in conjunction with a data
Algorithm provides a facility in solving this type of field matrix for grouping similar characteristics
problem. from a range of objects, when no classification is
First form a machine c o m p o n e n t matrix with suitable for coding the attributes relevant to the
the whole range of machines and only a fraction of analysis. In fact, the Direct Clustering A l g o r i t h m
the whole c o m p o n e n t r a n g e - - t h e size of the matrix can serve as a means of universal classification. The
will be dependent on the capacity of the computer. Direct Clustering Algorithm is a powerful tool for
Determine the machine groups and c o m p o n e n t group formation, and therefore can be used in many
families from this matrix by applying the Direct areas.
Clustering Algorithm. Each c o m p o n e n t family
formed is then renamed and treated as a new
c o m p o n e n t which has a production route consisting References
of the machines included in the respective machine
1. Burbidge, J.L. "Production Flow Analysis", The Production
group. Repeat the process with the other components Engineer, April 1971, pp. 139-152.
until the whole range of components to be considered 2. Burbidge, J.L. The Introduction o f Group Technology,
Heinemanff, London, 1975.
is analyzed. The result will be a list of new compo- 3. Gallagher,-C.C., Grayson, T.J., Collier, W. and Moore. P. "Group
nents, each represents a number of components, and Technology in the Plastic Moulding Industry", The Production Engi-
neer, April 1973, pp. 127-132.
each requires processing on the range of machines. 4. Burbidge, J.L. "Production Flow Analysis on the Computer", The
Using the original list of machines and the new list of Institution of Production Engineers Group Technology Division. Third
Annual Conference. 1973.
components as data and applying the D C A method 5. Burbidge, J.L. "A Manual Method of Production Flow Analysis",
again, new c o m p o n e n t families and machine groups The Production Engineer, October 1977, pp. 34-38.
will be formed. These new c o m p o n e n t families will 6. EI-Essawy, I.G. and Torrance, J. "Component Flow Analysis--An
Effective Approach to Production Systems Design", The Production
be composed of the old component families obtained Engineer, May 1972, pp. 165-169.
from the last iteration. The original components can 7. McAulley. J. "'Machine Grouping for Efficient Production", The
Production Engineer, February 1972, pp. 53-57.
then be reinstated into the final matrix to obtain the 8. Ross, G.J.S. "Algorithms ASI3, ASI4 and ASI5", Applied
ultimate solution. Statistics, 18, (i), 1969, pp. 103-110.
9. Carrie, A.S. "Numerical Taxonomy Applied to Group Technology
Theoretically, with this iterative approach, and Plant Layout", lnt J Prod Res, April 1973, pp. 399-416.
unlimited number of components can be analyzed, 10. Crookall, J.R. and Baldwin, K.I. "'An Investigation into Applica-
tion of Grouping Principles and Cellular Manufacture using Monte
although the m a x i m u m number of machines is Ca rlo Simulat ion", Manufacturing System (C. I. R.P.), 1972, pp. 193-208.
limited by the m a x i m u m size of the machine c o m p o - I1. McCormii:k, W.T., Schweitzer, P.J., and White, T. "Problem
Decomposition and Data Reorganization by a Clustering Technique".
nent m a t r i x . The c o m p u t e r p r o g r a m a l r e a d y Operations Research, 1972, pp. 993-1009.
developed can handle a matrix with'500 rows and 50 12. King, J.R. "Machine Component Group Fol:mation in Group
columns. A test run revealed that a core store of 82K Technology", Vth ICPR, Amsterdam, August 1979, pp. 40-44.
13. King, J.R. " M a c h i n e Component Grouping Using ROC
is needed. If the matrix is reduced to 100 rows times Algorithm", Int J Prod Res, April 1980, pp. 213-231.

74
 Journal of Manufacturing Systems
Volume I, Number I

Author Biography
H.M. Chan attended King's College in Hong Kong and obtained a higher diploma in Production
Engineering at Hong Kong Polytechnic. In 1978 he completed his undergraduate studies with First Class
honors in Production Technology and Production Management at the University of Aston in Birmingham,
England. Mr. Chan later became a contract research assistant with the University. He is currently conducting
research in the design and control of cellular manufacturing systems for his doctorate.
Douglas A. Milner received his technical education concurrently with an indentured apprenticeship in
general engineering practice. He is a member of the Institutions of Mechanical and Production Engineering,
has a teaching diploma, and is a graduate of the University of London. His doctorate was awarded for work in
the field of on-line control of manufacturing systems. Dr. Milner is currently a reader with responsibility for
automated systems in the Department of Production Technology and Production Management at the
University of Aston in Birmingham, England.

75