Sage Journals: Discover world-class research

Abstract

Though there are a number of benefits associated with cellular manufacturing systems, its implementation (identification of part families and corresponding machine groups) for real life problems is still a challenging task. To handle the complexity of optimizing multiple objectives and larger size of the problem, most of the researchers in the past two decades or so have focused on developing genetic algorithm (GA) based techniques. Recently this trend has shifted from standard GA to hybrid GA (HGA) based approaches in the quest for greater effectiveness as far as convergence on to the optimum solution is concerned. In order to prove the point, that HGAs possess better convergence abilities than standard GAs, a methodology, initially based on standard GA and later on hybridized with a local search heuristic (LSH), has been developed during this research. Computational experience shows that HGA maintains its accuracy level with increase in problem size, whereas standard GA looses its effectiveness as the problem size grows.

1. Introduction and Literature Review

The current manufacturing systems are facing a number of challenges in the form of globalization, shrinking product life cycles, variable demand patterns, more customized products, and ever decreasing “time to market.” These challenges can be tackled through effective and reliable manufacturing systems that can reduce the manufacturing cost and meet the manufacturing requirements timely and effectively, thus helping the manufacturer to compete with his competitors. Implementation of cellular manufacturing systems (CMS) can help the modern day manufacturers to face these challenges efficiently all in terms of cost, quality, and availability.

CMS is based on the philosophy of group technology (GT) which means similar tasks should be grouped together and handled in a similar fashion. According to Hyde [1] “GT is a technique for manufacturing small to medium lot size batches of parts of similar processes, of somewhat dissimilar materials, geometry, and size, which are produced in a committed small cell of machines which have been grouped together physically, specifically tooled, and scheduled as a unit.” Mitrofanov [2], Ranson [3], and Burbidge [4] provided guidelines for implementing GT in a cost effective and efficient manner without investing hugely in new equipment. According to Askin and Standridge [5], GT is a philosophy in which production of similar products is performed in a similar fashion. GT is mainly focused on the grouping of parts or products into specific cells based on similarities in their production requirement. At shop floor, the term traditionally used for the description of such systems is “cellular manufacturing (CM).” “(CM) is the formation of independent groups of functionally dissimilar machines and workstation types, located together on the floor, dedicated to the manufacture of a family of similar parts or products” (Irani, [6]). Singh [7] reported a number of benefits such as reduced setup time and throughput, increased worker satisfaction, and product quality.

In spite of so many benefits, implementation of CM (identification of part families and corresponding machine groups) is a challenging task. This is the reason that this problem has been extensively researched around the world for the last 60 years or so. A number of techniques have been reported in literature for solving the CMS design problem. Some widely known methods include classification and coding, array based clustering, similarity coefficient, mathematical programming, and artificial intelligence (AI) based algorithms.

Classification and coding technique is based on assigning numerical codes to different design and manufacturing attributes of a part and then grouping of parts is carried out on the basis of these codes. Mitrofanov [2] and Opitz [44] have put in a great deal of effort in developing this technique. Generally it is considered as a complex and hugely time consuming technique.

Array based clustering is considered as one of the simplest CMS design techniques. It uses machine part incident matrix in the form of 0's and 1's as input and provide results in block diagonalized shape. McAuley [45], Carrie [41], and Miltenburg and Zhang [46] used clustering techniques in their models. In similarity coefficient approach similarity among parts is developed based on their design and manufacturing attributes and on the basis of these similarities grouping is carried out. Lozano et al. [47] and Yin and Yasuda [48] used similarity coefficient approach in their models.

Mathematical programming based approaches possess the potential of solving the CMS design problem optimally and this is the reason that such approaches have been extensively used to solve the cell formation problem. According to Mungawattana [49], “Obtaining optimal solution for the mathematical programming approaches can be infeasible due to combinatorial complexity of the CMS design problem.” Chen & Heragu [50], Won [51], and Akturk and Turkcan [52] used mathematical programming based approaches in their models.

In the last two decade or so, AI based approaches have been extensively used to solve the cell formation problem (CFP). The main reason is their ability to handle large size problems and convergence to optimum solutions within the physically possible time. The widely known techniques of AI are (i) artificial neural network (ANN) (Kao and Moon [53]), (ii) fuzzy logic (FZ) (Susanto et al. [54]), (iii) simulated annealing (SA) (Tavakkoli-Moghaddam et al. [55]), and (iv) genetic algorithm (gA) Gupta et al. [56], Gravel et al. [57], Zhao and Wu [58], and Uddin and Shanker [59].

According to Ghosh et al. [60], among all the AI based techniques, GA is considered to be the most competent algorithm in handling the CMS design problem. Earlier, similar views were given by Mungawattana [49]. A large number of researchers used GA to solve the CFP such as Venugopal and Narendran [61], Joines et al. [62], Gravel et al. [57], Mak and Wong [63], Zhao and Wu [58], Wu et al. [64], Chu and Tsai [10], and Chan et al. [65].

Since GA is considered as an effective tool for the optimization of CFP therefore it remained the focus of prime interest of researchers in the early 90's. As the manufacturing systems became more and more complex with the passage of time, the researchers’ interest abstracted towards the development of multiobjective models. This increased the complexity of the CFP, thus requiring higher computational effort, time, and accuracy. To achieve these objectives and to enhance the convergence capabilities of GA, the focus of researchers shifted from standard GA to HGA based methodologies. A number of such approaches are listed in Table 1.

Table 1:

List of researchers who use hybrid genetic techniques.

Author's name	Technique

Zhao et al. [8]	GA-fuzzy
Hwang and Sun[9]	GA-greedy heuristic
Chu and Tsai[10]	GGA-greedy heuristic
Chi and Yan[11]	GA-fuzzy Logic
Gonçalves and Resende[12]	GA-local search heuristic
Pai et al.[13]	GA-fuzzy Logic
Nsakanda et al.[14]	GA-large scale optimization technique
Boulif and Atif[15]	GA-branch & bound
James et al. [16]	Grouping GA-local search heuristic
Chee and Ponnambalam [17]	GA-particle swarm optimization
Defersha and Chen[18]	GA-linear programming
Tunnukij and Hicks[19]	GGA-greedy heuristic
Tariq et al. [20]	GA-local search heuristic
Cao et al.[21]	GA-simplex linear programming
Ghezavati and Saidi-Mehrabad[22]	GA-simulated annealing
Rezaeian et al.[23]	GA-artificial neural network
Payder and Mehrabad[24]	GA-variable neighborhood search

Most of these approaches have produced some incredible results. Apparently this effectiveness seems to be because of the hybrid nature of these strategies, thus suggesting that HGAs have better convergence abilities than standard GAs. This has been generally reported in literature by a number of researchers but exact quantification of the difference has been rarely carried out. Therefore, this was the basic motive of this research to quantifiably verify this difference. For this purpose a methodology initially based on standard GA is developed during this research and a number of benchmark problems are solved. Later on the approach is converted into an HGA by combining it with a local search heuristic (LSH) and solving the same benchmark problems again using the similar parameters. A comparison of the result shows that HGA easily outperforms the standard GA.

2. CFP

The CFP can generally be divided into two subproblems. Identification of part families followed by grouping of corresponding machines into cells with the aim of reducing intercellular moves and increasing the within cell machine utilization. In some techniques these two subproblems are solved sequentially whereas in some they are handled simultaneously. The approach developed during this research is a simultaneous one. It uses information about the total number of parts and machines in the system, the total number of cells in which the system is required to be divided into and machine part incidence matrix (MPIM) in 1-0 form of size M × P (M = Total Machines, P = Total Parts) as inputs. Grouping efficacy (GE) has been chosen as the objective function (performance factor) as it possesses the ability of minimizing intercellular moves and at the same time maximizing the within cell machine utilization. The output of the approach is the block diagonalized form of the MPIM identifying different part families and their respective machine groups.

3. Model

A mathematical model for the above mentioned problem is developed based on the following considerations:

maximizing GE is to be the objective function;

each cell is to be assigned at least one machine and one part

Objective Function = Max. GE = Max. \frac{E - E_{out}}{E + E_{voids}}

(1)

subject to

\sum_{i = 1}^{NC} X_{i} \geq 1,

(2)

where NC = Total number of Cells, X_i = Total 1's in Cell “i,” i = 1,…, NC, and E = Total number of 1's in MPIM

E = \sum_{m = 1}^{M} \sum_{n = 1}^{P} a_{m * n} If a_{m * n} = 1,

(3)

where a = Any entry in the machine part incidence matrix (it can be either 0 or 1), M = Total number of Machines, P = Total number of Parts, m = 1,…, M (Total number of Machines), n = 1,…, P (Total number of Parts), E_voids = Total number of 0's inside the cells (Block Diagonals)

\begin{array}{l} E_{voids} = \sum_{i = 1}^{NC} \sum_{m = 1}^{M_{n}} \sum_{n = 1}^{P_{n}} b_{i * m * n} \\ if a_{i * m * n} = 0 then b_{i * m * n} = 1 else b_{i * m * n} = 0, \end{array}

(4)

b = A variable used to count voids in a cell, M_n = Number of Machines in cell “i,” P_n = Number of Parts in cell “i,” and E_in = Total number of 1's inside the cells (Block Diagonals)

E_{in} = \sum_{i = 1}^{NC} \sum_{m = 1}^{M_{n}} \sum_{n = 1}^{P_{n}} a_{i * m * n} if a_{i * m * n} = 1

(5)

E_out = Total number of 1's outside the cells (Block Diagonal), E_out = E − E_in.

4. Methodology

The methodology developed during this research mainly consists of two steps. In the first step a standard GA based algorithm is developed. After getting it tested with a number of benchmark problems it is converted into an HGA by combining it with an LSH and testing it again with the same benchmark problems. The HGA methodology is shown in Figure 1.

Figure 1:

HGA methodology.

4.1. Genetic Algorithm (GA)

The idea of GA is based on Darwin's theory of evolution and was initially introduced by John Holland in 1975. It uses the principles of natural genetics and natural selection for searching out the optimum solution of a problem. The ability of GA to avoid local optimums has made it more attractive as far as combinatorial optimization problems are concerned.

GA starts with an initial population of randomly generated solutions and then by using the genetic operators of crossover, mutation, and selection, the continuous evolutionary improvement of the solutions is carried out till the time the optimum is achieved.

4.1.1. Representation

Representation is the first step in implementing GA to a problem. In this paper, integer based representation is used. The length of each chromosome in the population is equal to the sum of the total number of parts and total number of machines in the system. The location of each gene is associated with a machine or part whereas its value represents the cell number which that machine/part is assigned to. For example, if the total number of parts and machines are 7 and 5, respectively, and they are to be arranged in 2 cells then a chromosome can be represented as shown in Table 2.

Table 2:

Chromosome representation.

Machines/parts	MC 1	MC 2	MC 3	MC 4	MC 5	Pr 1	Pr 2	Pr 3	Pr 4	Pr 5	Pr 6	Pr 7

Gene number	0	1	2	3	4	5	6	7	8	9	10	11
Location (cell number)	1	2	1	1	2	2	1	1	2	1	1	1

MC: machine & Pr: part.

4.1.2. Fitness Evaluation

As GE possesses the ability of simultaneously minimizing intercellular moves and maximizing machine utilization in cells, therefore it is chosen as the fitness function for this problem. The fitness value is calculated with the help of (1).

4.1.3. Genetic Operators

For GA its operators are very important as they are the ones responsible for inducing the property of evolution in GA. This is the reason that ultimate level of care is required while selecting the type of an operator for a particular application.

Crossover. Crossover is the genetic operator in which two parent chromosomes are subjected to produce two new offspring. The type used during this research is a multipoint (two point) crossover technique. The first two chromosomes from the population are selected on the basis of their higher fitness value and allowed to take part in the crossover operation.

Two parent chromosomes are shown as MPA₁ and MPA₂:

\begin{matrix} Parent 1 {MPA}_{1} = [\begin{bmatrix} 1 & 2 & 1 & 1 & 2 & 2 & 1 & 1 & 2 & 1 & 1 & 1 \end{bmatrix}] \\ Parent 2 {MPA}_{2} = [\begin{bmatrix} 1 & 2 & 2 & 1 & 1 & 1 & 2 & 2 & 1 & 2 & 2 & 1 \end{bmatrix}] . \end{matrix}

(6)

A random number is generated for the machine portion (range: from 1 to number of machines). Let us suppose the number is 3. All the genes in the machine portion of Parent 1 from position 3 onwards are replaced with the genes of Parent 2. Similarly a random number is generated for the parts portion. Suppose that number is 4. Then the same process is repeated for the parts portion too. The two new children produced are as shown below:

\begin{matrix} Child 1 {MPA}_{3} = [\begin{bmatrix} 1 & 2 & 2 & 1 & 1 & 2 & 1 & 1 & 1 & 2 & 2 & 1 \end{bmatrix}] \\ Child 2 {MPA}_{4} = [\begin{bmatrix} 1 & 2 & 1 & 1 & 2 & 1 & 2 & 2 & 2 & 1 & 1 & 1 \end{bmatrix}] . \end{matrix}

(7)

In case of better fitness values these children would replace the weakest solutions in the population. The code is developed in such a way that it would not include any illegal child into population. Illegal chromosome is that in which any cell number (between 1 and total number of cells) is missing in any of the portions (parts and machines). The crossover rate used in this research is 60%.

Mutation. Mutation is another important genetic operator which is used to impart diversity into the population, thus helping GA to avoid local optimums. The type used during this research is swap mutation.

In this type of mutation initially a solution is randomly selected. Then two genes (having different values) each in the parts’ and machines’ portion of the selected chromosome are randomly picked. After swapping their positions the solution is decoded and in case of having better fitness value it replaces the weakest solution in the population. The procedure is elaborated with the help of an example as follows.

Randomly selected solution and its genes:

Parent 1 {MPA}_{1} = [\begin{bmatrix} 1 & 2 & 1 & 1 & 2 & 2 & 1 & 1 & 2 & 1 & 1 & 1 \end{bmatrix}] .

(8)

After swapping the mutated chromosome:

Child 1 {MPA}_{1} = [\begin{bmatrix} 1 & 1 & 1 & 2 & 2 & 2 & 1 & 2 & 1 & 1 & 1 & 1 \end{bmatrix}] .

(9)

The rate chosen for mutation is 5% of the total number of genes in the population.

4.1.4. Selection

The procedure of breeding new generations from the existing is called selection. There are a number of methods developed and used over the years by researchers, for example, Roulette Wheel selection criterion, Tournament selection, Stochastic Universal Sampling, and so forth. The approach used during this research is Stochastic Universal Sampling (SUS) as it is less biased towards the stronger solutions, thus maintaining the diversity of the population and helping GA to avoid local optimums.

4.2. Local Search Heuristic (LSH)

In order to improve the convergence abilities of GA it has been hybridized by combining it with an LSH. A detailed block diagram explaining the local improvement procedure applied to the best solution in each generation of GA is shown in Figure 2.

Figure 2:

LSH methodology.

The uniqueness of this LSH is that unlike Tariq et al. [20] it only changes the cell numbers of those parts/machines which are ill placed that is, having more intercellular moves than the number of operations inside the cell. Such type of local improvement can definitely save time and computational effort.

5. Computational Results

In order to carry out a comparison between the standard GA and HGA, developed during this research, 22 benchmark problems have been solved by both the methodologies using similar crossover/mutation rates and population size. Initially both the algorithms were given a run for similar number of generations; that is, if HGA got the best solution for a problem in 5 generations then GA was also given a run for 5 generations. Once comparison on the similar number of generations was completed then GA was given a complete run for maximum number of generations (150) so that it should have sufficient opportunity to reach the optimum. In addition to these a comparison on the basis of CPU time (using Intel Core 2 Duo 2.66 GHz, having 4 GB RAM) has also been carried out and is given in Table 3 along with the results obtained in both the cases. They clearly show that HGA has outperformed the standard GA, both in terms of accuracy and speed.

Table 3:

Computational results.

Problems				Results
				Comparison of GA with HGA at same number of generations					GA results at max. number of generations
Sr #	Source	Size	Number of cells	GA		HGA		% age Gap	Efficacy	CPU time(s)	Number ofgen.
Sr #	Source	Size	Number of cells	Efficacy	CPU time (s)	Efficacy	CPU Time (s)	% age Gap	Efficacy	CPU time(s)	Number ofgen.

1	King and Nakornchai [25]	5 × 7	2	73.68	0.396	73.68	0.45	0	73.68	0.40	1
2	Waghodekar and Sahu [26]	5 × 7	2	60.87	0.201	69.57	0.28	12.51	69.57	0.57	5
3	Seifoddini [27]	5 × 18	2	62.50	0.647	79.59	0.79	21.47	64.15	0.75	5
4	Kusiak [28]	6 × 8	2	76.92	0.508	76.92	0.60	0	76.92	0.51	4
5	Kusiak [29]	7 × 11	3	48.48	0.760	58.62	0.79	17.30	50.00	0.74	5
6	Boctor [30]	7 × 11	3	53.33	0.563	70.37	0.72	24.21	53.33	0.56	4
7	Seifoddini and Wolfe [31]	8 × 12	3	61.90	0.513	68.29	0.77	9.36	61.90	0.51	6
8	Chandrasekharan and Rajagopalan [32]	8 × 20	3	43.75	0.808	85.25	1.39	48.68	43.75	0.81	6
9	Chandrasekharan and Rajagopalan [33]	8 × 20	3	44.00	0.612	58.72	1.42	25.07	47.62	1.17	5
10	Mosier and Taube [34]	10 × 10	3	46.15	0.783	70.59	1.54	34.62	59.46	4.50	5
11	Chan and Milner [35]	10 × 15	3	54.84	1.207	92.00	2.60	40.39	59.02	4.68	8
12	Askin and Subramanian [36]	14 × 23	5	35.56	2.270	70.83	5.97	49.80	39.18	11.64	12
13	McCormick et al. [37]	16 × 24	6	30.17	6.737	51.96	11.71	41.94	34.62	6.38	15
14	Srinivasan et al. [38]	16 × 30	4	32.58	4.179	67.83	10.28	51.97	35.00	6.57	18
15	King[39]	16 × 43	5	27.45	6.450	54.86	9.90	49.96	27.45	6.45	12
16	Vannelli et al. [40]	20 × 23	5	28.30	8.555	49.65	12.01	43.00	31.46	13.26	19
17	Carrie [41]	20 × 35	4	33.19	10.513	76.14	13.65	56.41	37.72	16.92	28
18	Boe and Cheng [42]	20 × 35	5	26.96	7.115	58.38	14.01	53.82	33.38	27.19	30
19	Chandrasekharan and Rajagopalan [43]	24 × 40	7	26.05	9.731	100	15.21	73.95	32.51	39.14	32
20	Chandrasekaran and Rajagopalan [43]	24 × 40	7	25.47	11.042	85.11	17.71	70.07	28.84	26.41	24
21	Chandrasekharan and Rajagopalan [43]	24 × 40	7	26.54	13.604	73.51	23.74	63.90	32.11	34.95	32
22	Chandrasekharan and Rajagopalan [43]	24 × 40	9	21.32	13.100	52.83	55.06	59.64	23.76	36.71	34

In order to further elaborate the difference, results of the tested problems are plotted on graphs as shown in Figures 3, 4, and 5.

Figure 3:

Comparison of GA with HGA (similar number of generations).

Figure 4:

Comparison of GA with HGA (GA given maximum number of generations).

Figure 5:

Comparison of GA with HGA (CPU time).

The results tabulated in Table 3 and plotted in Figures 3 and 4 show a definite pattern. As the problem size grows the convergence of standard GA on to optimum strays even further especially in the case for similar number of generations as HGA. This behavior, widening in gap of GE for larger problems, is somewhat reduced when GA is given a run for maximum number of generations. On the other hand the results of HGA are consistent and for every problem it returns the best result reported in literature so far (with the constraint on the number of cells). This clearly proves that HGA has better convergence abilities than standard GA.

In addition to the above another comparison on the basis of CPU time is also carried out as shown in Table 3 and Figure 5. Here also, an interesting situation can be witnessed. In case of similar number of generations GA is completing its run quickly but the accuracy is very low as compared to HGA.

In case of maximum number of generations the accuracy of GA has slightly improved but at the cost of CPU time which is even larger than HGA for most of the benchmark problems. So finally it can be concluded that for NP-hard combinatorial optimization problems, HGA based methodologies can prove to be more effective as they tend to reduce the dependence of GA on its parameters in addition to increasing its level of accuracy.

6. Statistical Analysis

The difference in performance, presented in Table 3 and Figure 3, of both the approaches is statistically validated as well. To carry out statistical validation it is necessary to first verify whether the data is normal or not. For this purpose Anderson-Darling and Lilliefors tests are used during this research. The normality tests show that the results of both the methadologies are normal as shown in Table 4. The normality of the data can also be clearly visualized in the graph shown in Figure 6.

Table 4:

Test for normality of the data.

Anderson-Darling test (HGA)		Anderson-Darling test (GA)

A ₂	0.306	A ₂	0.717
P value	0.538	P value	0.052
Alpha	0.05	Alpha	0.05
Since P Value > alpha so the data is normal		Since P value > alpha so the data is normal

Lilliefors test (HGA)		Lilliefors test (GA)

D	0.125	D	0.170
D (standardized)	0.584	D (standardized)	0.796
P value	0.502	P value	0.099
Alpha	0.05	Alpha	0.05
P value > alpha Normality of the data is proved		P value > alpha Normality of the data is proved

Figure 6:

Normality test.

After the normality check, paired t-test is applied to the results of both methodologies by using 95% confidence interval (CI). The value of t-stat is 6.90, which shows that both the methodologies are not performing similarly. The performance of HGA (Mean = 70.21 and St. Dev. = 13.29) is much better than GA (Mean = 42.72 and St. Dev. = 16.78). The results of paired t-test are shown in Table 5.

Table 5:

Paired t-test for HGA versus GA.

	N	Mean	St. dev.	SE mean

HGA	22	70.21	13.29	2.83
GA	22	42.73	16.78	3.58
Difference		27.48	3.49	0.75

95% CI for mean difference: (19.20, 35.76).

t-test of mean difference = 0 (vs not = 0): t-value = 6.90, P value = 0.000.

7. Conclusion

The initial aim of this paper was to assess and compare the convergence abilities of standard GA and HGA. For this purpose, initially a standard GA was developed for the CFP and used to solve a reasonable number of benchmark problems. Later on the same standard GA was hybridized by combining it with an LSH and solving the same benchmark problems again. A comparison of the computational results, based on first giving GA a run for similar number of generations as HGA and then maximum number of generations, shows that HGA has better convergence abilities than standard GA in both the situations as it returned optimum result for each one of the tested problems. The percentage solution gap between the results grows with the increase in problem size, thus proving a point that HGA maintains its accuracy whereas standard GA strays even further. This behavior has been further verified statistically as well.

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

References

Hyde

W. F.

, Improving Productivity by Classification and Coding and Data Base Standardization, Marcel Dekker, New York, NY, USA, 1981.

Mitrofanov

S. P.

, Scientific Principles of Group Technology, Defense Technical Information Center, Yorkshire, UK, 1966.

Ranson

G. M.

, Group Technology: A Foundation for Better Total Company Operation, McGraw-Hill, London, UK, 1972.

Burbidge

J. L.

, The Introduction of Group Technology, Halste Press, John Wiley, New York, NY, USA, 1975.

Askin

R. G.

and Standridge

C. R.

, Modelling and Analysis of Manufacturing System, Wiley, New York, NY, USA, 1993.

Irani

S. A.

, Handbook of Cellular Manufacturing Systems, 1999.

Singh

, “Design of cellular manufacturing systems: an invited review,” European Journal of Operational Research, vol. 69, no. 3, pp. 284–291, 1993.

Zhao

Tsujimura

, and Gen

, “Genetic algorithm for fuzzy clustering,” in Proceedings of the IEEE International Conference on Evolutionary Computation (ICEC '96), pp. 716–719, May 1996.

Hwang

and Sun

J.-U

, “A genetic-algorithm-based heuristic for the GT cell formation problem,” Computers & Industrial Engineering, vol. 30, no. 4, pp. 941–955, 1996.

10.

Chu

C.-H.

and Tsai

C.-C.

, “A heuristic genetic algorithm for grouping manufacturing cells,” in Proceedings of the Congress on Evolutionary Computation vol. 1, pp. 310–317, 2001.

11.

Chi

S. C.

and Yan

M. C.

, “A fuzzy genetic algorithm for hightech cellular manufacturing system design,” in Proceedings of the IEEE Annual Meeting of the Fuzzy Information vol. 2, pp. 907–912, 2004.

12.

Gonçalves

J. F.

and Resende

M. G. C.

, “An evolutionary algorithm for manufacturing cell formation,” Computers and Industrial Engineering, vol. 47, no. 2–3, pp. 247–273, 2004.

13.

Pai

P. F.

Chang

P. T.

, and Lee

S. H.

, “Part-machine family formation using genetic algorithms in a fuzzy environment,” International Journal of Advanced Manufacturing Technology, vol. 25, no. 11–12, pp. 1175–1179, 2005.

14.

Nsakanda

A. L.

Diaby

, and Price

W. L.

, “Hybrid genetic approach for solving large-scale capacitated cell formation problems with multiple routings,” European Journal of Operational Research, vol. 171, no. 3, pp. 1051–1070, 2006.

15.

Boulif

and Atif

, “A new branch-&-bound-enhanced genetic algorithm for the manufacturing cell formation problem,” Computers and Operations Research, vol. 33, no. 8, pp. 2219–2245, 2006.

16.

James

T. L.

Brown

E. C.

, and Keeling

K. B.

, “A hybrid grouping genetic algorithm for the cell formation problem,” Computers and Operations Research, vol. 34, no. 7, pp. 2059–2079, 2007.

17.

Chee

L. M.

and Ponnambalam

S. G.

, “A hybrid GA/PSO for the concurrent design of cellular manufacturing system,” in Proceedings of the IEEE International Conference on Systems, Man and Cybernetics (SMC '08), pp. 1855–1860, October 2008.

18.

Defersha

F. M.

and Chen

, “A linear programming embedded genetic algorithm for an integrated cell formation and lot sizing considering product quality,” European Journal of Operational Research, vol. 187, no. 1, pp. 46–69, 2008.

19.

Tunnukij

and Hicks

, “An enhanced grouping genetic algorithm for solving the cell formation problem,” International Journal of Production Research, vol. 47, no. 7, pp. 1989–2007, 2009.

20.

Tariq

Hussain

, and Ghafoor

, “A hybrid genetic algorithm for machine-part grouping,” Computers & Industrial Engineering, vol. 56, no. 1, pp. 347–356, 2009.

21.

Cao

Defersha

F. M.

, and Chen

, “Grouping operations in cellular manufacturing considering alternative routings and the impact of run length on product quality,” International Journal of Production Research, vol. 47, no. 4, pp. 989–1013, 2009.

22.

Ghezavati

V. R.

and Saidi-Mehrabad

, “An efficient hybrid self-learning method for stochastic cellular manufacturing problem: a queuing-based analysis,” Expert Systems with Applications, vol. 38, no. 3, pp. 1326–1335, 2011.

23.

Rezaeian

Javadian

Tavakkoli-Moghaddam

, and Jolai

, “A hybrid approach based on the genetic algorithm and neural network to design an incremental cellular manufacturing system,” Applied Soft Computing Journal, vol. 11, no. 6, pp. 4195–4202, 2011.

24.

Payder

M. M.

and Mehrabad

M. S.

, “A hybrid genetic - variable neighborhoods search algorithm for the cell formation problem based on grouping efficacy,” Computers & Industrial Engineering, vol. 40, pp. 980–990, 2013.

25.

King

J. R.

and Nakornchai

, “Machine-component group formation in group technology: review and extension,” International Journal of Production Research, vol. 20, no. 2, pp. 117–133, 1982.

26.

Waghodekar

P. H.

and Sahu

, “Machine-component cell formation in group technology: MACE,” International Journal of Production Research, vol. 22, no. 6, pp. 937–948, 1984.

27.

Seifoddini

, “Single linkage versus average linkage clustering in machine cells formation applications,” Computers and Industrial Engineering, vol. 16, no. 3, pp. 419–426, 1989.

28.

Kusiak

, “Group Technology: models and solutions approaches,” in Proceedings of 1st Industrial Engineering Research Conference, pp. 349–352, 1992.

29.

Kusiak

, “The generalized group technology concept,” International Journal of Production Research, vol. 25, no. 4, pp. 561–569, 1987.

30.

Boctor

, “Linear formulation of the machine-part cell formation problem,” International Journal of Production Research, vol. 29, no. 2, pp. 343–356, 1991.

31.

Seifoddini

and Wolfe

, “Application of similarity coefficient method in group technology,” IIE Transactions, vol. 18, no. 3, pp. 271–277, 1986.

32.

Chandrasekharan

M. P.

and Rajagopalan

, “An ideal seed non-hierarchical clustering algorithm for cellular manufacturing,” International Journal of Production Research, vol. 24, no. 2, pp. 451–463, 1986.

33.

Chandrasekharan

M. P.

and Rajagopalan

, “MODROC: an extension of rank order clustering for group technology,” International Journal of Production Research, vol. 24, no. 5, pp. 1221–1233, 1986.

34.

Mosier

and Taube

, “The facets of group technology and their impacts on implementation,” OMEGA, vol. 13, no. 6, pp. 381–391, 1985.

35.

Chan

H. M.

and Milner

D. A.

, “Direct clustering algorithm for group formation in cellular manufacture,” Journal of Manufacturing Systems, vol. 1, no. 1, pp. 65–75, 1982.

36.

Askin

R. G.

and Subramanian

S. P.

, “A cost-based heuristic for group technology configuration,” International Journal of Production Research, vol. 25, no. 1, pp. 101–113, 1987.

37.

McCormick

W. T.

Schweitzer

P. J.

, and White

T. W.

, “Problem decomposition and data reorganization by a clustering technique,” Operations Research, vol. 20, no. 5, pp. 993–1009, 1972.

38.

Srinivasan

Narendran

, and Mahadevan

, “An assignment model for the part-families problem in group technology,” International Journal of Production Research, vol. 28, no. 1, pp. 145–152, 1990.

39.

King

J. R.

, “Machine-component grouping in production flow analysis: an approach using a rank order clustering algorithm,” International Journal of Production Research, vol. 18, no. 2, pp. 213–232, 1980.

40.

Vannelli

and Kumar

K. R.

, “A method for finding minimal bottleneck cells for grouping part-machine families,” International Journal of Production Research, vol. 24, no. 2, pp. 387–400, 1986.

41.

Carrie

A. S.

, “Numerical taxonomy applied to group technology and plant layout,” International Journal of Production Research, vol. 11, no. 4, pp. 399–416, 1973.

42.

Boe

W. J.

and Cheng

C. H.

, “A close neighbour algorithm for designing cellular manufacturing system,” International Journal of Production Research, vol. 29, no. 10, pp. 2097–2116, 1991.

43.

Chandrasekharan

M. P.

and Rajagopalan

, “GROUPABILITY: analysis of the properties of binary data matrices for group technology,” International Journal of Production Research, vol. 27, no. 6, pp. 1035–1052, 1989.

44.

Opitz

, A Classification System to Describe Work Pieces, Pergamon Press, New York, NY, USA, 1970.

45.

McAuley

, “Machine grouping for efficient production,” Production Engineer, vol. 51, no. 2, pp. 53–57, 1972.

46.

Miltenburg

and Zhang

, “A comparative evaluation of nine well-known algorithms for solving the cell formation problem in group technology,” Journal of Operations Management, vol. 10, no. 1, pp. 44–72, 1991.

47.

Lozano

Adenso-Diaz

Eguia

, and Onieva

, “A one-step tabu search algorithm for manufacturing cell design,” Journal of the Operational Research Society, vol. 50, no. 5, pp. 509–516, 1999.

48.

Yin

and Yasuda

, “Similarity coefficient methods applied to the cell formation problem: a taxonomy and review,” International Journal of Production Economics, vol. 101, no. 2, pp. 329–352, 2006.

49.

Mungawattana

, Design of cellular manufacturing systems for dynamic and uncenain production requirements with presence of routing flexibility, [PhD dissertation, Doctor of Philosophy in Industrial and Systems Engineering], Virginia Polytechnic Institute and State University, 2000.

50.

Chen

and Heragu

S. S.

, “Stepwise decomposition approaches for large scale cell formation problems,” European Journal of Operational Research, vol. 113, no. 1, pp. 64–79, 1999.

51.

Won

, “Two-phase approach to GT cell formation using efficient p-median formulations,” International Journal of Production Research, vol. 38, no. 7, pp. 1601–1613, 2000.

52.

Akturk

M. S.

and Turkcan

, “Cellular manufacturing system design using a holonistic approach,” International Journal of Production Research, vol. 38, no. 10, pp. 2327–2347, 2000.

53.

Kao

and Moon

Y. B.

, “A unified group technology implementation using the backpropagation learning rule of neural networks,” Computers and Industrial Engineering, vol. 20, no. 4, pp. 425–437, 1991.

54.

Susanto

Kennedy

R. D.

, and Price

J. W. H.

, “A new fuzzy-c-means and assignment technique-based cell formation algorithm to perform part-type clusters and machine-type clusters separately,” Production Planning and Control, vol. 10, no. 4, pp. 375–388, 1999.

55.

Tavakkoli-Moghaddam

Aryanezhad

M. B.

Safaei

, and Azaron

, “Solving a dynamic cell formation problem using metaheuristics,” Applied Mathematics and Computation, vol. 170, no. 2, pp. 761–780, 2005.

56.

Gupta

Kumar

, and Sundram

, “Minimizing total intercell and intracell moves in cellular manufacturing: a genetic algorithm approach,” International Journal of Computer Integrated Manufacturing, vol. 8, no. 2, pp. 92–101, 1995.

57.

Gravel

Nsakanda

A. L.

, and Price

, “Efficient solutions to the cell-formation problem with multiple routings via a double-loop genetic algorithm,” European Journal of Operational Research, vol. 109, no. 2, pp. 286–298, 1998.

58.

Zhao

and Wu

, “A genetic algorithm for manufacturing cell formation with multiple routes and multiple objectives,” International Journal of Production Research, vol. 38, no. 2, pp. 385–395, 2000.

59.

Uddin

M. K.

and Shanker

, “Grouping of parts and machines in presence of alternative process routes by genetic algorithm,” International Journal of Production Economics, vol. 76, no. 3, pp. 219–228, 2002.

60.

Ghosh

Dan

P. K.

Sengupta

, and Cappopadhyay

, “Genetic rule based techniques in cellular manufacturing (1992–2010): a systematic survey,” International Journal of Science & Technology, vol. 2, no. 5, pp. 198–215, 2010.

61.

Venugopal

and Narendran

T. T.

, “A genetic algorithm approach to the machine-component grouping problem with multiple objectives,” Computers and Industrial Engineering, vol. 22, no. 4, pp. 469–480, 1992.

62.

Joines

J. A.

Culbreth

C. Thomas

, and King

R. E.

, “Manufacturing cell design: an integer programming model employing genetic algorithms,” IIE Transactions, vol. 28, no. 1, pp. 69–85, 1996.

63.

Mak

K. L.

and Wong

Y. S.

, “Genetic design of cellular manufacturing systems,” Human Factors and Ergonomics in Manufacturing, vol. 10, no. 2, pp. 177–192, 2000.

64.

Chu

C.-H.

Wang

, and Yan

, “A genetic algorithm for integrated cell formation and layout decisions,” in Proceedings of the IEEE Congress on Evolutionary Computation vol. 2, pp. 1866–1871, 2002.

65.

Chan

F. T. S.

Lau

K. W.

, and Chan

P. L. Y.

, “A holistic approach to manufacturing cell formation: incorporation of machine flexibility and machine aggregation,” Journal of Engineering Manufacture, vol. 218, no. 10, pp. 1279–1296, 2004.

A Comparison of a Standard Genetic Algorithm with a Hybrid Genetic Algorithm Applied to Cell Formation Problem

Abstract

1. Introduction and Literature Review

2. CFP

3. Model

4. Methodology

4.1. Genetic Algorithm (GA)

4.1.1. Representation

4.1.2. Fitness Evaluation

4.1.3. Genetic Operators

4.1.4. Selection

4.2. Local Search Heuristic (LSH)

5. Computational Results

6. Statistical Analysis

7. Conclusion

Conflict of Interests

References