Cell formation, one of the most important stages in CMS, is to group
parts with similar geometry, function, material and process into part
families and the corresponding machines into machine cells. Design of
cellular manufacturing systems (CMSs) is a complex, multi-criteria and
multi-step process. In the design of CMSs, design objective (s) must be
specified. Minimizing inter-cell moves, distances, costs and the number
of exceptional parts (parts that need more than one cell for processing)
are common design objectives. An exceptional part can be also called an
exceptional element or a bottleneck part. An example is given in order
to introduce some of the terminology to be used in this study.
An example from Kusiak (1992) of 5 part types and 4 machine types was used
in order to form cells. A machine-part matrix is one way to represent the processing
requirements of part types on machine types as shown in Table 1.
A 1 entry on row i and column j indicates that part type j has one or more operations
on machine type i. For instance, part type 1 has operations on machine types
1 and 3. Manufacturing cells are formed with the objective of minimizing inter-cell
moves. Two cells (clusters) are formed as shown in Table 1.
Cell 1 consists of machine type 2 and 4 and produces part type 5 and 2. Cell
2 consists of machine type 1 and 3 and produces part type 3, 1 and 4. Part type
3 needs to be processed on machine type 1 and 3 in cell 2, however, it also
needs to be processed on machine type 2 which is assigned in cell 1. Therefore,
an inter-cell move is required: the symbol * represents an inter-cell move of
part type 3. Part type 3 is an exceptional part, so these two cells (clusters)
are called partially separable.
||Illustration of machine-part matrix before and after cell
Analogous to an exceptional part, a bottleneck machine is one that processes
parts belonging to more than one cell. Two possible approaches to eliminate
exceptional parts are by considering alternative process plans for parts or
additional machines. In Table 1, 0 represents a void in cell
2. A void indicates that a machine assigned to a cell is not required for the
processing of a particular part in the cell. In this example, machine type 3
is not necessary for part type 4. The presence of voids leads to inefficient
large cells, which in turn could lead to additional intra-cell material handling
costs and complex control requirements. Any cell configuration should satisfy
operational goals (constraints) such as desired machine utilization, production
volume, number of manufacturing cells, cell sizes, etc.
In the last three decades, several research papers and practical reports
have been published in the field of CM, seeking effective methods for
designing CMSs. Reviews of existing CM literature can be found in Joines
et al. (1996) and Selim et al. (1998). According to those
reviews, the existing CM design methods in the CMSs can be classified
into the following categories: part coding analysis, cluster techniques,
similarity co-efficient, graph partitioning, mathematical programming,
heuristic search and AI-based approaches.
Each design approach considers different numbers of design objectives
and constraints to different extent, depending upon the scope and interest
of each. For instance, clustering analysis approaches consider only one
objective, the minimization of inter-cell moves. In the design process
of clustering techniques, only part operations and the machines for processing
those operations are considered. Other product data (such as operational
sequences and processing times) and production requirements (such as production
rate) are not incorporated into the design process. Thus, solutions obtained
may be valid in limited situations. However, they are simple to implement
and solutions can be obtained in reasonable amounts of time. Minimizing
inter-cell flows of parts is fundamental to achieving many of the benefits
associated with CM (Cao and Caen, 2005). The cell formation problem is
complicated by the existence of exceptional parts and/or exceptional machines.
Both exceptional parts and exceptional machines cause intercellular movement
of parts. Ideally a part-cluster is processed in a single machine cell
for its entire operations. In practice, however, it is a very rare case.
Extensive work has been done by many researchers to provide new techniques
for solving this problem.
The recent shift toward heuristic solutions to the Machine-Part Cell
Formation (MPCF) problem is due, in part to the fact that the problem
is NP-complete. With heuristic approaches showing promise in this area,
present study focuses on the application of genetic algorithm, tabu search
and memetic algorithm to the MPCF problem. An objective function provides
the basis for evaluating the machine groupings arrived at by a searching
method such as GA, TS. This work uses the metaheuristics of GA, TS and
memetic algorithm for cell formation with an objective of minimizing the
exceptional elements. The proposed memetic algorithm approach combines
genetic algorithm with tabu search heuristic. The objective of the heuristic
is to construct a set of machine/product groups and improve it, if possible.
The proposed Memetic Algorithm is validated with the test cases studied
in the literature and comparisons are presented.
The major drawback of mathematical programming approaches is computational
timing required for large problems. So heuristic approaches have been
used as alternatives to obtain reasonably good solutions. Nowadays metaheuristics
are widely used to solve important practical combinatorial optimization
problems. A metaheuristic is a set of concepts that can be used to define
heuristic methods that can be applied to a wide set of different problems.
Examples of metaheuristics include Simulated Annealing (SA), tabu search
(TS), genetic algorithm and Ant Colony Optimization (ACO).
Genetic Algorithms are search and optimization procedures that are
motivated by the principle of natural genetics and natural selection.
GA is a metaheuristic for solving combinatorial optimization problems
(Goldberg, 1989). GA is a heuristic solution technique that works by encoding
a population of solutions to a given problem and manipulating these solutions
through the use of operators such as crossover and mutation in an attempt
to evolve superior solutions. The new population is further evaluated
and tested for termination. If the termination criterion is met, GA process
stops otherwise, the above cycle is followed until the termination criterion
Reproduction is usually the first operator applied on population. Reproduction
selects good strings in a population and forms a mating pool. There exist
a number of reproduction operators in GA literature and rank selection
method is used for reproduction. The individuals in the population are
ranked according to fitness and the expected value of each individual
depends on its rank rather than on its absolute fitness.
Reproduction selects good strings in a population and forms a mating
pool. The linear ranking method proposed by Baker (1987) is as follows:
Each individual in the population is ranked in increasing order of fitness
from 1 to N. The expected value of each individual i in the population
at time t is given by:
After calculating the expected value of each rank, reproduction is performed
using Monte Carlo simulation by employing random numbers.
In the crossover, new strings are created by exchanging information among
strings of the mating pool. In single point crossover, one crossover point
is selected; binary string from beginning of chromosome to the crossover
point is copied from one parent and the rest is copied from the second
Mutation is also done randomly for each gene and it depends upon another
parameter called mutation probability. Here one gene is selected at random
and the mutation operation is performed.
Tabu search is a meta-strategy for guiding known heuristics to overcome
local optimality. Tabu Search (TS) has its antecedents in methods designed
to cross boundaries of feasibility or local optimality standard treated
as barriers and to systematically impose and release constraints to permit
exploration of otherwise forbidden regions.
The philosophy of Tabu Search is to derive and exploit a collection of
principles of intelligent problem solving. A fundamental element underlying
tabu search is the use of flexible memory. From the standpoint of tabu
search, flexible memory embodies the dual processes of creating and exploiting
structures for taking advantage of history (hence combining the activities
of acquiring and profiting from information). TS methods operate under
the assumption that a neighborhood can be constructed to identify adjacent
solutions that can be reached from any current solution (Baykasoglu and
Gindy, 2000; Tavakkoli and Arunlzhar, 2005).
||Move attribute: The pair of sites of the string
||History record: List of sites of the string classified under
Tabu restrictions with record of on which iterations each of them
classified as tabu.
||Tabu classification/Restriction: The sites of string swapped
in the previous iterations will not be considered for swapping.
||Tabu tenure: The tabu restriction of a site is lifted after
a consecutive three iterations.
||Aspiration criterion: Tabu restrictions are lifted for the
solutions under tabu classification, with the value of the objective,
10% or more, less than that of the current solution.
||Choice criterion: The solution with the minimum Objective
value among the neighboring solutions of the current solution.
||Termination criteria: Reaching a predefined minimum value
of objective or 50 numbers of iterations whichever occurs first.
GA are not well suited for fine tuning structures, which are close to
optimal solutions. MAs are EAs that apply a separate local search process
to refine individuals (i.e., improve their fitness by tabu search algorithm).
Under different context and situations, MAs are also known as hybrid EAs,
genetic local searchers (Muruganandam et al., 2005). The operation
of MA begins with a population of random strings representing design and
decision variables. Thereafter each string is evaluated to find the objective
value. The population is then operated by 4 main operators reproduction,
crossover, mutation and TS.
Pseudo-code for a simple MA
||Until (termination criteria);
In this study, an objective of minimization of exceptional elements is
considered to evaluate the goodness of the cell formation.
Minimization of exceptional elements is considered as the objective function
||No. of manufacturing cell
||No. of machines
||Total number of parts
||Binary value indicating if machine i is assigned to cell k
||Bbinary value indicating if part j is assigned to cell k
||Element of machine part incident matrix
||1 if machine type i is assigned to cell k.
||1, if part/component j is assigned to cell k
Representation forms a key role in the development of Genetic Algorithm,
Tabu Search and Memetic Algorithm. A problem can be solved once it is
represented in the form of solution string. In the problem, each gene
represents whether the machine or part is in that cell or not.
For 16x30 size problem (Boctor, 1991), each cell or the string is coded
and decoded as shown in Table 2.
After representation, an initial solution can be generated using random
numbers and the generated solution is subjected to iterations or generations.
The appropriate values of the GA parameters are arrived at, based on the
satisfactory performance of the trials conducted for this application
with different ranges of values. The crossover probability varied from
0.4 to 0.9 and it was found that the solution was improving faster for
a crossover probability of 0.60. Similarly in the range from 0.001 to
0.020, the mutation probability of 0.015 was found to retain better solutions
than worse solutions.
||Coded and decoded information for 16x30 problem
To demonstrate the performance of the proposed MA, 7 Group Technology
(GT) problems of different sizes from the information collected from the
literature were tested. The selected matrices range from dimension 4x18
to 24x40. The matrix sizes and their sources are shown in the Table
The objective function of number of exceptional elements obtained by
the proposed MA with that of GA and TS are compared and the algorithm
was coded in C++.
From the test results, it is observed that out of 87 trials for the 7
problems with total number of cells as 2 and 3 for different possibilities
of minimum number of machines which could be accommodated in either 2
cells or 3 cells, the objective function of MA is minimum or equally good
for 72 cases compared to GA and TS. Similarly GA has the minimum or equal
number of exceptional elements for 14 cases out of 87. And TS has the
minimum or equal number of exceptional elements for 11 cases out of 87
trials (Table 4).
The computational experience has shown that for most of the problems,
MA results in solutions with lower objective function value. Even though
MA yields higher values in few cases compared to other approaches, it
results in better solution and requires very little computational effort.
||Selected GT problems from the literature
||Comparative results of objective function (exceptional elements)
for GA, TS and MA with different cell sizes
A MA approach for obtaining machine cells and product families has
been presented. Computational experience with the algorithm, on a set
of Seven GT problems from the literature has shown that the MA heuristic
performs better than GA and TS algorithm as far as the objective function
of minimizing the exceptional elements are concerned. It is inferred from
the results obtained that the proposed MA heuristic is efficient either
in the quality of the solutions or in the speed that gets the solutions.