Abstract

The Cell Formation (CF) problem has met with a significant amount of attention in recent years by demonstrating great potential for productivity improvements in production environment. The study is focused to present a Genetic Algorithm (GA) that is tested with the sample problems extract from the open literature. The evaluation of GA is carried out against the modified ART1, K-means and C-linkage algorithm that are well known from the literature sources as well. To measure, the performance of the CF algorithms, group efficiency is calculated based on number of exceptional elements and workload.

---

INTRODUCTION

The cell formation problem has received a significant amount of attention in recent years by demonstrating great potential for productivity improvements. Cellular Manufacturing System (CMS) combines the advantages of job and flow shop to reduce setup times, WIP levels, etc. The main problem in the design of cellular manufacturing system is the formation process of part families and corresponding groups of machines.

The researchers have initiated to develop various methods like Similarity Coefficient Method (SCM) by McAuley (1972), Graph theory by Rajagopalan and Batra (1975), etc., with aim to automate the whole cell formation process. In this trend, modeling of CMS through mathematical programming by Arthanari and Dodge (1981) has been involved because it has incorporated more real life constraints on the problem. Later researchers like Hendizadeh et al. (2008) have started developing heuristics and meta-heuristics to explore the best optimal solutions for the cell formation problems. Since, soft computing techniques expand their applications to various fields like telecommunications, networking, design and manufacturing, current research in CMS is being carried out using these soft computing techniques like fuzzy set theory by Leem and Chen (1996) and neural networks by Kulkarni and Kiang (1995). It is well-known that very few studies focus on CF considering production factors such as operational time, operational sequence, batch size, etc.

Research background: The concept of Cellular Manufacturing System (CMS) as the application of GT philosophy was originally proposed by Burbidge (1979) who defines it as an approach to the organization of research in which the organizational units are relatively independent groups each responsible for the production of a given family of products. One of the key, aspects of CMS is the formation of machine-part cells in which parts and machines are assigned to distinct cells where the machine utilization within a cell is maximized and inter cells movement of parts is minimized. The Machine-part Cell Formation (MPCF) problem was formally defined by Burbidge (1971) with his research focused on heuristic approaches to solve the block-diagonal problem for a Machine-part Incidence Matrix (MPIM).

Many methods have been developed for the MPCF problem so far. However, the methods like SC methods by De Witte (1980), Rank Order Clustering (ROC) by King (1980) and Graph theory methods by Faber and Carter (1986) have been developed, only to solve the machine grouping in the CF problem and grouping of parts into part families is done in the supplementary step of the procedure only. Later Clustering methods such as ZODIAC by Chandrasekaran and Rajagopalan (1987) and GRAFICS by Srinivasan and Narendran (1991) are reported for solving the cell formation problems.

Subsequently, algorithms based on meta-heuristics approaches have also developed and adjusted for solving the CF problems. The Simulated Annealing (SA) proposed by Kirkpatrick et al. (1983) is one of the Meta-heuristic methods for finding the global minimum of objective function that may possess several local minima. The inspiration for developing SA method has come from annealing in metallurgy where it represents a technique involving heating and controlled cooling of a material to increase the size of its crystals and reduce their defects. Tabu Search (TS) poposed by Pierre and Houeto (2002) is also classified as Meta-heuristic method. TS method uses the flexible structures memory where stores a potential solutions. Once, a potential solution has been determined, it is marked as taboo so that the algorithm does not visit that possibility repeatedly.

Genetic Algorithm (GA) represents a search technique used in soft computing to find exact or approximate solutions and search problems. Once, the genetic representation and the objective function are defined, GA proceeds to initialize a population of solutions randomly and then improves it through repetitive application of mutation, crossover, inversion and selection operators. Meanwhile, many researchers have proposed Artificial Neural Network (ANN) based methodologies for solving the cell formation problems.

MATERIALS AND METHODS

In order to enhance, the production flow analysis process a genetic algorithm has been proposed from the previous research. The GA is illustrated by the flow chart diagram together with a description of its important steps. Subsequently, alternative algorithms are selected to put them to the test against the GA.

Every algorithm is tested under the conditions of 24 data sets. For this purpose each of 24 binary Machine Part Incidence Matrices (MPIM) is transformed into real valued operational time data with aim to consider some of the real-time production factors in the study. It is supposable that soft computing technique is more suitable for such type of problems and capable to give optimal results.

The evaluation process of the proposed genetic algorithm includes performance comparison with alternative algorithms such as modified ART1, K-means clustering and C-linkage algorithm by use of modified grouping efficiency. The objective of the evaluation process is to determine an optimal data set solution that has minimal exceptional elements.

Workload matrix representation: The conventional MPIM uses binary form as it is shown in Fig. 1 a. The entries in the matrix are 1s or 0s which indicate a part processed on machine or otherwise.

Fig. 1:	Machine-part incidence matrix of size 6x8 matrix with: a) binary values; b) operational times and c) block-diagonal matrix

The input of the proposed GA based algorithm presents the workload matrix in which cell entries indicate the operational times. Let M be the total number of machines and N total number of parts then workload matrix size becomes MxN as shown in Fig. 1b. The output of the algorithm is block-diagonal structure that as shown in Fig. 1c. The elements outside the block-diagonal structure are denoted as Exceptional Elements (EE) that represent inter-cell moves.

Genetic algorithm: The CF problem focuses on the several objectives that are known from the literature like inter-cell and intra-cell moves, measure of performance and exceptional element. On the other hand, all these objectives do not reflect exactly the smooth material flow leading to Work-in-Process (WIP) inventories reduction and productivity increase. For that reason a cell load variation must be considered.

Genetic algorithm is suggested for cell formation with objective to minimize both the cell load variation and the exceptional elements. All these goals are expressed as objective function denoted as Z in Eq. 1 proposed by Venugopal and Narendran (1992):

where, X is a machine-cell membership matrix of 1s and 0s which indicate a machine is in a cell or otherwise; W is a machine-part matrix in terms of the workload on a machine induced by part and M is a cell-part matrix of average cell load. The solution of the problem is naturally represented in GA as a chromosome. The genetic algorithm then creates a population of solutions and applies genetic operators such as mutation and crossover to evolve the solutions in order to find the best one(s). This presentation outlines, the three most important aspects of the genetic algorithm that need to be defined and subsequently implemented:

•	Objective function
•	Genetic representation
•	Genetic operators

The proposed genetic algorithm consists of the several steps that are presented by flow chart diagram as shown in Fig. 2. The GA is adopted to find out the machine clusters to form cells. In the genetic algorithm, a candidate solution is represented by sequence of genes named chromosome. A set of selected chromosomes (population) is subjected to generations (number of iterations). In each generation crossover and mutation operators are performed to get new population. The proposed GA uses coding method where each solution is coded as a set of numbers. The sum of numbers will be equal to the sum of machines to be grouped. The position of the number denotes the machine number and the value of the number represents the machine cell where belongs the particular machine. The main steps of the genetic algorithm are described below:

Reproduction: In this step of the genetic algorithm, a fitness function value is computed for each string in the population to find a string with the maximum fitness function value. Due to objective of minimizing both the total cell load variation and the exceptional elements, fitness function is appropriate to use according to Goldberg (1989).

Crossover and mutation: In the crossover, operation a pair of strings is selected at random with a crossover probability. Crossover is exchange of a portion of strings at a point called crossover site, denoted as S. The genes (numbers) after the crossover site are swapped to produce the pair of offspring strings. Here partial, mapped crossover given by Zbigniew (1996) is performed.

The mutation is also done randomly with some probability denoted as mutation probability. In this method, inversion mutation is adopted where one gene is selected at random, comes out from one cell and goes to another cell while a machine from latter cell comes to the former.

Fig. 2:	Flow chart diagram of proposed GA algorithm

Eliminating machine cells with single machine: If single machine found in any cell, the following operations are carried out to merge the single machine cells with other cells. The average workload of each part in the cell and the euclidean distance between the cells are calculated. The minimum euclidean distance between cells is found out. Cells with single machine are merged to the cells with minimum Euclidean distance.

Part assignment: The following procedure given by Zolfaghari and Liang (2003) is used to assign parts into the machine cells. A machine cell which processes the part for a larger number of operations than any other machine cell is found out and the corresponding part is assigned into that cell. Ties are broken by choosing the machine cell which has the largest percentage of machines visited by the part. In the case of tie again, the machine cell with the smallest identification number is selected. Thus, all the parts are assigned to all the cells which form part families using membership index.

Performance measure: There are several performance measures proposed by the researchers in last two decades. Each of them has its own advantages and drawbacks depending on the data considered for the CF problem. However, no grouping efficiency can be considered for the generalized cell formation with maximum available information. The modified grouping efficiency denoted as MGE is presented to find out the performance of the cell formation method that deals with workload matrix due to consideration of voids (idle machines) inside the cells.

For the cell formation problems using workload (operational time) information, the grouping efficiency has to be found out from the ratio of total workload inside the cells denoted as E_vt and the total workload of the matrix. When the total workload is being calculated, the number of voids presented inside the cells is taken into account and the proportionate value of voids with the number of elements presented inside the cells are calculated using the weighting factor to the voids ratio. The elements outside the cells represent exceptional elements denoted as E_e. The MGE is calculated using Eq. 2:

RESULTS AND DISCUSSION

In the study, an efficient algorithm based on genetic algorithm has been proposed for cell formation problem considering operational time of the parts instead of classic 0-1 incidence matrix with the objective of minimizing the total of the exceptional elements. The proposed algorithm has been coded in C++ and run on a PC with 2 GB memory running a windows on an Intel Core i3 540 processor.

The real valued matrix has been produced by assigning random numbers in the range of 0.5-1 as uniformly distributed values by replacing the ones in the incidence matrix and zeros to remain in its same positions. The model developed using GA has been tested with 24 benchmark problems of varied sizes ranging from 5x7 to 30x50 from open literature.

Fig. 3:	Performance improvement of genetic algorithm compared with: a) K-means; b) C-linkage and c) modified ART1 algorithms

The results of the proposed GA algorithm have been compared with three other algorithms: K-means clustering, C-linkage clustering and modified ART1 algorithms. Based on exhaustive experiments, it has been confirmed that GA is an appropriate solution method to such type of optimization problems. Enhancement of the genetic algorithm is shown in the Fig. 3 in the form of the graphs. The best improvements in compare with the K-means algorithm are in the data set number 7, 15, 19 and 24. The similar enhancement shows also comparison to C-linkage algorithm. Modified ART1 algorithm is weakest in the data set number 23 while other data sets do not show considerable progress by proposed algorithm.

CONCLUSION

In this study, the GA based algorithm has been used to solve the cell formation problem using the non binary real valued workload data as an input matrix. The genetic algorithm has been tested with benchmark problems found in the literature and the results have been compared with the well-known algorithms (K-means, C-linkage and MART1). In addition to the commonly used measure of performance that is the number of exceptional elements, a newly developed performance measure namely Modified Grouping Efficiency (MGE) has been also applied to evaluate the grouping efficiency of the genetic algorithm. The GA based algorithm outperforms the existing methods both in terms of exceptional elements and modified grouping efficiency. The GA algorithm could be employed after few modifications to solve the cell formation problem with other non-binary real value data like machine capacity, production volume and product sequence.

How to cite this article:

Peter Knuth, Pavol Semanco, Vladimir Modrak and R. Sudhakara Pandian. Using Genetic Algorithm for Elimination of Exceptional Elements in the Stage of PFA.
DOI: https://doi.org/10.36478/jeasci.2011.122.126
URL: https://www.makhillpublications.co/view-article/1816-949x/jeasci.2011.122.126