Cellular Manufacturing System (CMS) is an application of Group Technology (GT) in which similar parts and machines are grouped into part families and machine cells. In this study, a metaheuristic called Memetic Algorithm (MA) is introduced to solve the machine cell formation problem. This study is conducted to minimize the intercellular movement of parts known as exceptional elements. MA is incorporated using Genetic Algorithm (GA) and Tabu Search (TS) Algorithm. In the MA approach, local optimization (TS) is applied to each newly generated offspring at the end of genetic algorithm. The MA is tested on a number of problems of various sizes and its performance is evaluated. The results obtained by MA are highly comparable with an objective obtained by Metaheuristics GA, TS and there is a considerable reduction in computational effort.
PDF Abstract XML References Citation
How to cite this article
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 formation
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 is met.
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 parent.
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 being swapped.
|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 (Z)
|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 3.
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.
- Al Ahmari, A.M.A., 2002. Fuzzy analysis approach for part-machine grouping cellular manufacturing systems. J. Integrat. Manufact. Syst., 13: 489-497.
- Baker, J.E., 1985. Adaptive Selection Methods for Genetic Algorithms. Proceedings of the 1st International Conference on Genetic Algorithms, July 24-26, 1985, L. Erlbaum Associates Inc., Hillsdale, NJ., USA., pp: 101-111.