Hybrid Genetic Algorithm for Machine-Component Cell Formation

Abstract

This paper considers machine-component cell formation problem of cellular manufacturing system. Since this problem comes under combinatorial category, development of a meta-heuristic is a must. In this paper, a hybrid genetic algorithm is presented. Normally, in genetic algorithm, the initial population is generated by random assignment of genes in each of the chromosomes. In this paper, the initial population is created using ideal seed heuristic. The proposed algorithm is compared with four other algorithms using 28 problems from literature. Through a completed factorial experiment, it is observed that the proposed algorithm outperforms the other algorithms in terms of grouping efficiency as well as grouping efficacy.

Share and Cite:

Pachayappan, M. and Panneerselvam, R. (2015) Hybrid Genetic Algorithm for Machine-Component Cell Formation. Intelligent Information Management, 7, 107-122. doi: 10.4236/iim.2015.73010.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1] Mahdavi, I., Paydar, M.M., Solimanpur, M. and Saidi-Mehrabad, M. (2010) A Mathematical Model for Integrating Cell Formation Problem with Machine Layout. International Journal of Industrial Engineering & Production Research, 21, 61-70.
[2] Khaksar-Haghani, F., Kia, R., Javadian, N., Tavakkoli-Moghaddam, R. and Baboli, A. (2011) A Comprehensive Mathematical Model for the Design of a Dynamic Cellular Manufacturing System Integrated with Production Planning and Several Manufacturing Attributes. International Journal of Industrial Engineering & Production Research, 22, 199-212.
[3] Arkat, J., Naseri, F. and Ahmadizar, F. (2011) A Stochastic Model for the Generalized Cell Formation Problem Considering Machine Reliability. International Journal of Computer Integrated Manufacturing, 24, 1095-1102.http://dx.doi.org/10.1080/0951192X.2011.627944
[4] Saeedi, S., Solimanpur, M., Mahdavi, I. and Javadian, N. (2010) Heuristic Approaches for Cell Formation in Cellular Manufacturing. Journal of Software Engineering & Applications, 3, 674-682.
http://dx.doi.org/10.4236/jsea.2010.37077
[5] Banerjee, I. and Das, P. (2012) Group Technology Based Adaptive Cell Formation Using Predator-Prey Genetic Algorithm. Applied Soft Computing, 12, 559-572.
http://dx.doi.org/10.1016/j.asoc.2011.07.021
[6] Arkat. J., Hosseini, L. and Farahani, M.H. (2011) Minimization of Exceptional Elements and Voids in the Cell Formation Problem Using a Multi-Objective Genetic Algorithm. Expert System with Applications, 38, 9597-9602.http://dx.doi.org/10.1016/j.eswa.2011.01.161
[7] Yin, X.F. and Khoo, L.P. (2011) An Exact Schema Theorem for Adaptive Genetic Algorithm and Its Application to Machine Cell Formation. Expert Systems with Applications, 38, 8538-8552.
http://dx.doi.org/10.1016/j.eswa.2011.01.055
[8] Ozcelik, F. and Sarac, T. (2012) A Genetic Algorithm Extended Modified Sub-Gradient Algorithm for Cell Formation Problem with Alternative Routings. International Journal of Production Research, 50, 4025-4037.http://dx.doi.org/10.1080/00207543.2011.588264
[9] Saraç, T. and Ozcelik, F. (2012) A Genetic Algorithm with Proper Parameters for Manufacturing Cell Formation Problems. Journal of Intelligent Manufacturing, 23, 1047-1061.
http://dx.doi.org/10.1007/s10845-010-0446-8
[10] Wu, T.-H., Chang, C.-C. and Yeh, J.-Y. (2009) A Hybrid Heuristic Algorithm Adopting both Boltzmann Function and Mutation Operator for Manufacturing Cell Formation Problems. International Journal of Production Economics, 120, 669-688. http://dx.doi.org/10.1016/j.ijpe.2009.04.015
[11] Lin, S.W., Ying, K.C. and Lee, Z.J. (2010) Part-Machine Cell Formation in Group Technology Using a Simulated Annealing-Based Meta-Heuristic. International Journal of Production Research, 48, 3579-3591. http://dx.doi.org/10.1080/00207540902896212
[12] Paydar, M.M., Mahdavi, I., Sharafuddin, I. and Solimanpur, M. (2010) Applying Simulated Annealing for Designing Cellular Manufacturing Systems Using MDmTSP. Computers & Industrial Engineering, 59, 929-936. http://dx.doi.org/10.1016/j.cie.2010.09.003
[13] Kia, R., Baboli, A., Javadian, N., Tavakkoli-Moghaddam, R., Kazemi, M. and Khorrami, J. (2012) Solving a Group Layout Design Model of a Dynamic Cellular Manufacturing System with Alternative Process Routings, Lot Splitting and Flexible Reconfiguration by Simulated Annealing. Computers & Operations Research, 39, 2642-2658. http://dx.doi.org/10.1016/j.cor.2012.01.012
[14] Rezaeian, J., Javadian, N., Tavakkoli-Moghaddam, R. and Jolai, F. (2011) A Hybrid Approach Based on the Genetic Algorithm and Neural Network to Design an Incremental Cellular Manufacturing System. Applied Soft Computing, 11, 4195-4202. http://dx.doi.org/10.1016/j.asoc.2011.03.013
[15] Ghezavati, V.R. and Saidi-Mehrabad, M. (2011) An Efficient Hybrid Self-Learning Method for Stochastic Cellular Manufacturing Problem: A Queuing-Based Analysis. Expert Systems with Applications, 38, 1326-1335. http://dx.doi.org/10.1016/j.eswa.2010.07.012
[16] Elbenani, B. and Ferland, J.A. (2012) An Exact Method for Solving the Manufacturing Cell Formation Problem. International Journal of Production Research, 50, 4038-4045.
http://dx.doi.org/10.1080/00207543.2011.588622
[17] Rafiei, H. and Ghodsi, R. (2013) A Bi-Objective Mathematical Model toward Dynamic Cell Formation Considering Labor Utilization. Applied Mathematical Modelling, 37, 2308-2316.
http://dx.doi.org/10.1016/j.apm.2012.05.015
[18] Paydar, M.M. and Saidi-Mehrabad, M. (2013) A Hybrid Genetic-Variable Neighborhood Search for the Cell Formation Problem Based on Group Efficiency. Computers & Operations Research, 40, 980-990.
http://dx.doi.org/10.1016/j.cor.2012.10.016
[19] Dalfard, V.M. (2013) New Mathematical Model for Problem of Dynamic Cell Formation Based on Number and Average Length of Intra and Intercellular Movements. Applied Mathematical Modelling, 37, 1884-1896. http://dx.doi.org/10.1016/j.apm.2012.04.034
[20] Srinivasan, G. and Narendran, T.T. (1991) GRAFICS—A Nonhierarchical Clustering-Algorithm for Group Technology. International Journal of Production Research, 29, 463-478.
http://dx.doi.org/10.1080/00207549108930083
[21] Srinivasan, G. (1994) A Clustering Algorithm for Machine Cell Formation in Group Technology Using Minimum Spanning Trees. International Journal of Production Research, 32, 2149-2158.
http://dx.doi.org/10.1080/00207549408957064
[22] Miltenburg, J. and Zhang, W. (1991) A Comparative Evaluation of Nine Well-Known Algorithms for Solving the Cell Formation Problem in Group Technology. Journal of Operations Management, 10, 44-72. http://dx.doi.org/10.1016/0272-6963(91)90035-V
[23] Kao, Y. and Li, Y.L. (2008) Ant Colony Recognition Systems for Part Clustering Problems. International Journal of Production Research, 46, 4237-4258. http://dx.doi.org/10.1080/00207540601078054
[24] Nambirajan, T. and Panneerselvam, R. (1999) Machine-Component Cell Design Using Simulated Annealing. International Journal of Management and Systems, 15, 185-208.
[25] Holland, J.H. (1975) Adaptation in Natural and Artificial Systems. The University of Michigan Press, Ann Arbor.
[26] Goldberg, D.E. (1989) Genetic Algorithms in Search Optimization & Machine Learning. Addison Wesley, Boston.
[27] Venugopal, V. and Narendran, T.T. (1992) A Genetic Algorithm Approach to the Machine-Component Grouping Problem with Multiple Objectives. Computers & Industrial Engineering, 22, 469-480.
http://dx.doi.org/10.1016/0360-8352(92)90022-C
[28] Balakrishnan, J. and Jog, P.D. (1995) Manufacturing Cell Formation Using Similarity Coefficients and a Parallel Genetic TSP Algorithm: Formulation and Comparison. Mathematical and Computer Modelling, 21, 61-73. http://dx.doi.org/10.1016/0895-7177(95)00092-G
[29] Joines, A.J., Culbreth, C.T. and King, E.R. (1996) Manufacturing Cell Design: An Integer Programming Model Employing Genetic Algorithms. IIE Transactions, 28, 69-85.
http://dx.doi.org/10.1080/07408179608966253
[30] Su, C.T. and Hsu, C.M. (1998) Manufacturing Cell Formation Using Genetic Algorithm vs. Neural Networks. Journal of the Chinese Institute of Industrial Engineers, 15, 127-139.
http://dx.doi.org/10.1080/10170669.1998.10432953
[31] Mahdavi, I., Paydar, M.M., Solimanour, M. and Heidarzade, A. (2009) Genetic Algorithm Approach for Solving a Cell Formation Problem in Cellular Manufacturing. Expert Systems with Applications, 36, 6598-6604. http://dx.doi.org/10.1016/j.eswa.2008.07.054
[32] James, T.L., Brown, E.C. and Keeling, K.B. (2007) A Hybrid Grouping Algorithm for the Cell Formation Problem. Computers & Operations Research, 34, 2059-2079.
http://dx.doi.org/10.1016/j.cor.2005.08.010
[33] Keeling, K.B., Brown, E.C. and James, T.L. (2007) Grouping Efficiency Measures and Their Impact on Factory Measures for the Machine-Part Cell Formation Problem: A Simulation Study. Engineering Applications of Artificial Intelligence, 20, 63-78. http://dx.doi.org/10.1016/j.engappai.2006.04.001
[34] Tunnukij, T. and Hicks, C. (2009) An Enhanced Grouping Genetic Algorithm for Solving the Cell Formation Problem. International Journal of Production Research, 47, 1989-2007.
http://dx.doi.org/10.1080/00207540701673457
[35] Tariq, A., Hussain, I. and Ghafoor, A. (2009) A Hybrid Genetic Algorithm for Machine-Part Grouping. Computers & Industrial Engineering, 56, 347-356. http://dx.doi.org/10.1016/j.cie.2008.06.007
[36] Pailla, A., Trinbade, A.R., Parada, V. and Ochi, L.S. (2010) A Numerical Comparison between Simulated Annealing and Evolutionary Approaches to the Cell Formation Problem. Expert Systems with Applications, 37, 5476-5483. http://dx.doi.org/10.1016/j.eswa.2010.02.064
[37] Vin, E. and Delchambre, A. (2014) Generalized Cell Formation: Iterative versus Simultaneous Resolution with Grouping Genetic Algorithm. Journal of Intelligent Manufacturing, 25, 1113-1124.
http://dx.doi.org/10.1007/s10845-013-0749-7
[38] Li, J., Wang, A. and Tang, C. (2014) Production Planning in Virtual Cell of Reconfiguration Manufacturing System Using Genetic Algorithm. International Journal of Advanced Manufacturing Technology, 74, 47-64. http://dx.doi.org/10.1007/s00170-014-5987-0
[39] Deep, K. and Singh, P.K. (2015) Design of Robust Cellular Manufacturing System for Dynamic Part Population Considering Multiple Processing Routes Using Genetic Algorithm. Journal of Manufacturing Systems, 35, 155-163. http://dx.doi.org/10.1016/j.jmsy.2014.09.008
[40] Chandrasekharan, M.P. and Rajagopalan, R. (1986) An Ideal Seed Non-Hierarchical Clustering Algorithm for Cellular Manufacturing. International Journal of Production Research, 24, 451-464.
http://dx.doi.org/10.1080/00207548608919741
[41] Chandrasekharan, M.P. and Rajagopalan, R. (1986) MODROC: An Extension of Rank Order Clustering for Group Technology. International Journal of Production Research, 24, 1221-1233.
http://dx.doi.org/10.1080/00207548608919798
[42] Kumar, C.S. and Chandrasekharan, M.P. (1990) Grouping Efficacy: A Quantitative Criterion for Goodness of Block Diagonal Forms of Binary Matrices in Group Technology. International Journal of Production Research, 28, 233-243. http://dx.doi.org/10.1080/00207549008942706
[43] Chandrasekharan, M.P. and Rajagopalan, R. (1987) ZODIAC—An Algorithm for Concurrent Formation of Part Families and Machine Cells. International Journal of Production Research, 25, 835-850.
http://dx.doi.org/10.1080/00207548708919880
[44] Nambirajan, T. and Panneerselvam, R. (1995) Nonhierarchical Clustering of Machine-Component Cells Using Seeds from an Efficient Seed Generation Algorithm. Industrial Engineering Journal, 24(11), 10-16 & 24(12), 1-17.
[45] King, J.R. and Nakornchai, V. (1982) Machine-Component Group Formation in Group Technology: Review and Extension. International Journal of Production Research, 20, 117-133.
http://dx.doi.org/10.1080/00207548208947754
[46] Waghodekar, P.H. and Sahu, S. (1984) Machine-Component Cell Formation in Group Technology: MACE. International Journal of Production Research, 22, 937-948.
http://dx.doi.org/10.1080/00207548408942513
[47] Nambirajan, T. (1998) Machine-Component Cell Design Using Simulated Annealing with an Efficient Seed Generation Algorithm. Ph.D. Dissertation, Pondicherry University, Puducherry.
[48] Vohra, T., Chen, D.S., Chang, J.C. and Chen, H.C. (1990) A Network Approach to Cell Formation in Cellular Manufacturing. International Journal of Production Research, 28, 2075-2084.
http://dx.doi.org/10.1080/00207549008942854
[49] Choobineh, F. (1988) A Framework for the Design of Cellular Manufacturing Systems. International Journal of Production Research, 26, 1161-1172. http://dx.doi.org/10.1080/00207548808947932
[50] Safer, S.M., Kern, G.M. and Wei, J.C. (1992) A Mathematical Programming Approach for Dealing with Exceptional Elements in Cellular Manufacturing. International Journal of Production Research, 30, 1029-1036. http://dx.doi.org/10.1080/00207549208942940
[51] De Witte, J. (1980) The Use of Similarity Coefficient in Production Flow Analysis. International Journal of Production Research, 18, 503-514. http://dx.doi.org/10.1080/00207548008919686
[52] Tam, K.Y. (1990) An Operation Sequence Based Similarity Coefficient for Part Families Formations. Journal of Manufacturing Systems, 9, 55-68. http://dx.doi.org/10.1016/0278-6125(90)90069-T
[53] Askin, R.G. and Subramanian, S.P. (1987) A Cost-Based Heuristic for Group Technology Configuration. International Journal of Production Research, 25, 101-113.
http://dx.doi.org/10.1080/00207548708919825
[54] Stanfel, L.E. (1985) Machine Clustering for Economic Production. Engineering Costs and Production Economics, 9, 73-81. http://dx.doi.org/10.1016/0167-188X(85)90012-6
[55] Balasubramanian, K.N. and Panneerselvam, R. (1993) Covering Technique-Based Algorithm for Machine Grouping to form Manufacturing Cells. International Journal of Production Research, 31, 1479-1504. http://dx.doi.org/10.1080/00207549308956803
[56] Chan, H.M. and Milner, D.A. (1982) Direct Clustering Algorithm for Group Formation in Cellular Manufacturing. Journal of Manufacturing Systems, 1, 65-75.
http://dx.doi.org/10.1016/S0278-6125(82)80068-X
[57] Mosier, C. and Taube, L. (1985) Weighted Similarity Measure Heuristics for the Group Technology Machine Clustering Problem. Omega, 13, 577-583. http://dx.doi.org/10.1016/0305-0483(85)90046-5
[58] Chandrasekharan, M.P. and Rajagopalan, R. (1989) Groupability: An Analysis of the Properties of Binary Data Matrices for Group Technology. International Journal of Production Research, 27, 1035-1052. http://dx.doi.org/10.1080/00207548908942606
[59] Panneerselvam, R. (2012) Design and Analysis of Experiments. PHI Learning Pvt. Limited, New Delhi.

Copyright © 2023 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.