Enhanced Imperialist Competitive Algorithm for the Cell Formation Problem Using Sequence Data

Authors: S. H. Borghei, E. Teymourian, M. Mobin, G. M. Komaki, S. Sheikh

Abstract:

Imperialist Competitive Algorithm (ICA) is a recent meta-heuristic method that is inspired by the social evolutions for solving NP-Hard problems. The ICA is a population-based algorithm which has achieved a great performance in comparison to other metaheuristics. This study is about developing enhanced ICA approach to solve the Cell Formation Problem (CFP) using sequence data. In addition to the conventional ICA, an enhanced version of ICA, namely EICA, applies local search techniques to add more intensification aptitude and embed the features of exploration and intensification more successfully. Suitable performance measures are used to compare the proposed algorithms with some other powerful solution approaches in the literature. In the same way, for checking the proficiency of algorithms, forty test problems are presented. Five benchmark problems have sequence data, and other ones are based on 0-1 matrices modified to sequence based problems. Computational results elucidate the efficiency of the EICA in solving CFP problems.

Keywords: Cell formation problem, Group technology, Imperialist competitive algorithm, Sequence data.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1109637

References:

[1] E. Aarts, E., Lenstra, J.K., 1997. Local Search in Combinatorial Optimization. John Wiley & Sons, New York, ISBN: 0471948225.
[2] E. Atashpaz-Gargari, C. Lucas, “Imperialist competitive algorithm: An algorithm for optimisation inspired by imperialistic competition,” In: IEEE Congress on Evolutionary Computation, pp. 4661–4667, 2007.
[3] A.H. Banisadr, M. Zandieh, I. Mahdavi, “A hybrid imperialist competitive algorithm for single-machine scheduling problem with linear earliness and quadratic tardiness penalties,” Int. J. Adv. Manuf. Technol., vol. 65, no. 5-8, pp.981–989, 2013.
[4] E.C. Brown, R.T. Sumichrast, “CF-GGA: a grouping genetic algorithm for the cell formation problem,” Int. J. Prod. Res., vol. 39, no. 16, 3651- 3669, 2001.
[5] B.A. Elbenani, J. Ferland, J. Bellemare, “Genetic algorithm and large neighborhood search to solve the cell formation problem,” Expert Syst. Appl., vol. 39, no. 3,pp. 2408–2414, 2012.
[6] S. Forouharfard, M. Zandieh, “An imperialist competitive algorithm to schedule of receiving and shipping trucks in cross-docking systems,” Int. J. Adv. Manuf. Technol., vol. 51, no. 9-12, pp. 1179–1193, 2010.
[7] J.F. Gonçalves, M.G.C. Resende, “An evolutionary algorithm for manufacturing cell formation,” Comput. Ind. Eng., vol. 47, no. 2-3, pp. 247–273, 2004.
[8] M. Gravel, A.L. Nsakanda, W. Price, “Efficient solutions to the cellformation problem with multiple routings via a double-loop genetic algorithm,” Eur. J. Oper. Res., vol. 109, no. 2, pp. 286–298, 1998.
[9] Kaveh, A., Talatahari, S., 2010. Optimum design of skeletal structures using imperialist competitive algorithm. Computers and Structures, 88(21-22), 1220–1229, 2010.
[10] V. Kayvanfar, M. Zandieh, “The economic lot scheduling problem with deteriorating items and shortage: an imperialist competitive algorithm,” Int. J. Adv. Manuf. Technol., vol. 62, no. 5-8, pp. 759-773, 2012.
[11] K.B. Keeling, E.C. Brown, T.L. James, “Grouping efficiency measures and their impact on factory measures for the machine-part cell formation problem: A simulation study,” Eng. Appl. Artif. Intel., vol. 20, no. 1, pp. 63–78,2007.
[12] K. Lian, C. Zhang, L. Gao, X. Shao, “A modified colonial competitive algorithm for the mixed-model U-line balancing and sequencing problem,” Int. J. Prod. Res., vol. 50, no. 18, pp. 5117-5131, 2011.
[13] K. Lian, C. Zhang, X. Shao, L. Gao, “Optimization of process planning with various flexibilities using an imperialist competitive algorithm,” Int. J. Adv. Manuf. Technol., vol. 59, no. 5-8, pp. 815–828, 2012.
[14] I. Mahdavi, E. Teymourian, N. Tahami Baher, V. Kayvanfar, “An integrated model for solving cell formation and cell layout problem simultaneously considering new situations,” J. Manuf. Sys., vol. 32, no. 4, 655-663, 2013
[15] I. Mahdavi, B. Mahadevan, “CLASS: An algorithm for cellular manufacturing system and layout design using sequence data,” Robot. Com-Int. Manuf., vol. 24, no. 3, pp. 488–497, 2008.
[16] A.S. Mamaghani, M.R. Meybodi, “An application of Imperialist Competitive Algorithm to solve the quadratic assignment problem,” In: Internet Technology and Secured Transactions (ICITST), International Conference, pp. 562-565, 2011.
[17] H. Moradi, M. Zandieh, “An imperialist competitive algorithm for a mixed-model assembly line sequencing problem,” J. Manuf. Sys., vol. 32, no. 1, pp.46–54, 2013.
[18] G.J. Nair, T.T. Narendran, “CASE: A clustering algorithm for cell formation with sequence data,” Int. J. Prod. Res., vol. 36, no. 1, pp. 157–180, 1998.
[19] S. Nazari-Shirkouhi, H. Eivazy, R. Ghodsi, K. Rezaie, E. Atashpaz- Gargari, “Solving the integrated product mix-outsourcing problem using the Imperialist Competitive Algorithm,” Expert Syst. Appl., vol. 37, no. 12, pp. 7615–7626, 2010.
[20] H. Nouri, S.H. Tanga, B.T. Hang Tuaha, M.K. Anuara, “BASE: A bacteria foraging algorithm for cell formation with sequence data,” J. Manuf. Sys., vol. 29, no. 2-3, pp. 102–110, 2010.
[21] G. Papaioannou, J.M. Wilson, “The evolution of cell formation problem methodologies based on recent studies (1997–2008): review and directions for future research,” Eur. J. Oper. Res., vol. 206, no. 3, pp. 509–521, 2010.
[22] D.T. Pham, A.A. Afify, E. Koç, 2007. Manufacturing cell formation using the Bees Algorithm. In: innovation production machines and systems virtual conference. Cardiff, UK.
[23] E. Shokrollahpour, M. Zandieh, B. Dorri, “A novel imperialist competitive algorithm for bi-criteria scheduling of the assembly flowshop problem,” Int. J. Prod. Res., vol. 49, no. 11, pp. 3087–3103, 2010.
[24] K. Spiliopoulos, S. Sofianopoulou, “An efficient ant colony optimization system for the manufacturing cells formation problem,” Int. J. Adv. Manuf. Technol., vol. 36, no. 5-6, pp.589–597, 2008.
[25] A. Talebi, M.A. Molaei, B. Ashrafi, “Application of an Imperialist Competitive Algorithm in Portfolio Optimization,” World Appl. Sci. J., vol. 14, no. 10, pp. 1576-1598, 2011.
[26] T.-H. Wu, S.-H., Chung, C.-C., Chang, “A water flow-like algorithm for manufacturing cell formation problems,” Expert Syst. Appl., vol. 205, no. 2, pp. 346–360, 2010.
[27] T.-H. Wu, C. Low, W.-T. Wu, “A tabu search approach to the cell formation problem,” Int. J. Adv. Manuf. Technol., vol. 23, no. 1, pp. 916–924, 2004.
[28] T-H. Wu, C-C. Chang, S-H. Chung, “A simulated annealing algorithm for manufacturing cell formation problems,” Eur. J. Oper. Res., vol. 34, no. 3, pp. 1609–1617, 2008.
[29] M. Yousefi-khoshbakht, M. Sedighpour, “A New Imperialist Competitive Algorithm to Solve the Traveling Salesman Problem,” Int. J. Comput. Math., vol. 90, no. 7, pp. 1495-1505. 2013
[30] J.R. King, and V. Nakornchai, “Machine-component group formation in group technology: Review and extension,” Int. J. Prod. Res., vol. 20, no. 2, pp. 117-133, 1982.
[31] A. Kusiak, W. and Chow, “Efficient solving of the group technology problem,” J. Manuf. Sys., vol. 6, no. 2, pp. 117-124, 1987.
[32] H. Seifoddini, “Single linkage versus average linkage clustering in machine cells formation applications”, Comput. Ind. Eng., vol. 16, no. 3, pp. 419-426, 1989.
[33] C.T. Mosier, L. Taube, “The facets of group technology and their impact on implementation,” OMEGA, vol. 13, no. 6, pp. 381-391, 1985.
[34] H.M. Chan, D. A. Milner, “Direct clustering algorithm for group formation in cellular manufacture,” J. Manuf. Sys., vol. 1, pp. 65-75, 1982.
[35] M. P. Chandrashekharan, R. Rajagopalan, “An ideal seed nonhierarchical clustering algorithm for cellular manufacturing,” Int. J. Prod. Res., vol. 24, no. 2, pp. 451-464, 1986.
[36] M. P. Chandrashekharan, R. Rajagopalan, “MODROC: An extension of rank order clustering for group technology,” Int. J. Prod. Res., vol. 24, no. 5, pp. 1221-1233, 1986.
[37] R. G. Askin, S. Subramanian, “A cost-based heuristic for group technology configuration,” Int. J. Prod. Res., vol. 25, no. l, pp. 101-113, 1987.
[38] C.T. Mosier, L. Taube, “Weighted similarity measure heuristics for the group technology machine clustering problem,” OMEGA, vol. 13, no. 6, pp. 577-583, 1985.
[39] S. Carrie, “Numerical Taxonomy applied to Group Technology and Plant Layout,” Int. J. Prod. Res., vol. 11, pp. 399-416, 1973.
[40] K.R. Kumar, A. Kusiak, A. Vannelli, “Grouping of parts and components in flexible manufacturing systems,” Eur. J. Oper. Res., vol. 24, pp. 387-397, 1986.
[41] J.R. King, “Machine-component grouping in production flow analysis: An approach using a rank order clustering algorithm,” Int. J. Prod. Res., vol. 18, no. 2, pp. 213-232, 1980.
[42] W. Boe, C.H. Cheng, “A close neighbor algorithm for designing cellular manufacturing systems,” Int. J. Prod. Res., vol. 29, no. 10, pp. 2097- 2116, 1991.
[43] M.P. Chandrasekharan, R. Rajagopalan, “GROUPABILITY: Analysis of the properties of binary data matrices for group technology,” Int. J. Prod. Res., vol. 27, no. 6, pp. 1035-1052, 1989.
[44] M.P. Chandrasekharan, R. Rajagopalan, “ZODIAC - An algorithm for concurrent formation of part families and machine cells,” Int. J. Prod. Res., vol. 25, no. 6, pp. 835-850, 1987.
[45] P. H. Waghodekar, S. Sahu, “Machine-component cell formation in group technology: MACE,” Int. J. Prod. Res., vol. 22, no. 6, pp. 937- 948, 1984.
[46] A. Kusiak, Group technology: Models and solution approaches. In First Industrial Engineering Research Conference (pp. 349-352), 1992.
[47] F. F. Boctor, “A linear formulation of the machine-part cell formation problem,” Int. J. Prod. Res., vol. 29, no. 2, pp. 343-356, 1991.
[48] R.S. Pandian, S. S. Mahapatra, “Manufacturing cell formation with production data using neural networks,” Comput. Ind. Eng., vol. 56, no. 4, pp. 1340-1347, 2009.
[49] L.E. Stanfel, “Machine clustering for economic production,” Eng. Costs Prod. Econ., vol. 9, no. 1, pp. 73-81, 1985.
[50] W. T. McCormick, P. J. Schweitzer, T. W. White, “Problem decomposition and data reorganization by a clustering technique,” Oper. Res., vol. 20, no. 5, pp. 993–1009, 1972.
[51] H. Seifoddini, P.M. Wolfe, “Application of the similarity coefficient method in group technology,” IIE Trans., vol. 18, no. 3, pp. 271–277, 1986.