An ant colony optimization metaheuristic for machine-part cell formation problems. (English) Zbl 1231.90407
Summary: We propose an ant colony optimization metaheuristic (ACO-CF) to solve the machine-part cell formation problem. ACO-CF is a max-min ant system, which is implemented in the hyper-cube framework to automatically scale the objective functions of machine-part cell formation problems. As an intensification strategy, we integrate an iteratively local search into ACO-CF. Based on the assignment of the machines or parts, the local search can optimally reassign parts or machines to cells. We carry out a series of experiments to investigate the performance of ACO-CF on some standard benchmark problems. The comparison study between ACO-CF and other methods proposed in the literature indicates that ACO-CF is one of the best approaches for solving the machine-part cell formation problem.
MSC:
| 90C90 | Applications of mathematical programming |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Software:
CF-GGAReferences:
| [1] | Shunk, D., Group technology provides organized approach to realizing benefits of cims, Industrial Engineering, 17, 74-80 (1985) |
| [2] | Hyer, N.; Brown, K.; Zimmerman, S., A socio-technical systems approach to cell design: case study and analysis, Journal of Operational Management, 17, 179-203 (1999) |
| [3] | Ballakur, A.; Steudel, H., A within-cell utilization based heuristic for designing cellular manufacturing systems, International Journal of Production Research, 25, 639-655 (1987) |
| [4] | McCormick, W. T.; Sehweitzer, P. J.; White, T. W., Problem decomposition and data reorganization by a clustering technique, Operations Research, 20, 993-1009 (1972) · Zbl 0249.90046 |
| [5] | King, J. R., Machine-component grouping in production flow analysis: an approach using a rank order clustering algorithm, International Journal of Production Research, 18, 213-232 (1980) |
| [6] | King, J.; Nakornchai, V., Machine-component group formation in group technology: review and extension, International Journal of Production Research, 20, 117-133 (1982) |
| [7] | Chandrasekharan, M. P.; Rajagopalan, R., Modroc: an extension of rank order clustering for group technology, International Journal of Production Research, 24, 1221-1264 (1986) |
| [8] | McAuley, D., Machine grouping for efficient production, The Production Engineering, 51, 53-57 (1972) |
| [9] | Seifoddini, H.; Wolfe, P. M., Application of the similarity coefficient method in group technology, IIE Transactions, 18, 3, 271-277 (1986) |
| [10] | Chandrasekharan, M. P.; Rajagopalan, R., An ideal seed non-hierarchical clustering algorithm for cellular manufacturing, International Journal of Production Research, 24, 2, 451-464 (1986) · Zbl 0582.90050 |
| [11] | Chandrasekharan, M. P.; Rajagopalan, R., ZODIAC—an algorithm for concurrent formation of part-families and machine-cells, International Journal of Production Research, 25, 6, 835-850 (1987) · Zbl 0623.90030 |
| [12] | Kusiak, A., The generalized group technology concept, International Journal of Production Research, 25, 561-569 (1987) |
| [13] | Srinivasan, G.; Narendran, T. T.; Mahadevan, R., An assignment model for the part-families problem in group technology, International Journal of Production Research, 28, 1, 145-152 (1990) |
| [14] | Gunasingh, K.; Lashkari, R., Simultaneous grouping of parts and machines in cellular manufacturing systems. An integer programming approach, Computer & Industrial Engineering, 20, 111-117 (1991) |
| [15] | Logendran, R., Binary integer programming approach for simultaneous machine-part grouping in cellular manufacturing systems, Computer & Industrial Engineering, 24, 329-336 (1993) |
| [16] | Adil, G.; Rajamani, D.; Strong, D., Cell formation considering alternate routings, International Journal of Production Research, 34, 1361-1380 (1999) · Zbl 0947.90543 |
| [17] | Albadawi, Z.; Bashir, H. A.; Chen, M., A mathematical approach for the formation of manufacturing cells, Computers & Industrial Engineering, 48, 1, 3-21 (2005) |
| [18] | Defersha, F.; Chen, M., A comprehensive mathematical model for the design of cellular manufacturing systems, International Journal of Production Economics, 103, 767-783 (2006) |
| [19] | Slomp, J.; Chowdary, B.; Suresh, N., Design of virtual manufacturing cells: a mathematical programming approach, Robotics and Computer-Integrated Manufacturing, 21, 273-288 (2005) |
| [20] | Tavakkoli-Moghaddam, R.; Javadian, N.; Javadi, B.; Safaei, N., Design of a facility layout problem in cellular manufacturing systems with stochastic demands, Applied Mathematics and Computation, 184, 721-728 (2007) · Zbl 1149.90054 |
| [21] | Mahdavi, I.; Javadi, B.; Fallah-Alipour, K.; Slomp, J., Designing a new mathematical model for cellular manufacturing system based on cell utilization, Applied Mathematics and Computation, 190, 662-670 (2007) · Zbl 1278.90131 |
| [22] | Boctor, F. F., A linear formulation of the machine-part cell formation problem, International Journal of Production Research, 29, 343-356 (1991) |
| [23] | Sofianopoulou, S., Application of simulated annealing to a linear model for the formulation of machine cells ingroup technology, International Journal of Production Research, 35, 501-511 (1997) · Zbl 0940.90539 |
| [24] | Xambre, A.; Vilarinho, P., A simulated annealing approach for manufacturing cell formation with multiple identical machines, European Journal of Operational Research, 151, 434-446 (2003) · Zbl 1053.90030 |
| [25] | Baykasoglu, A., A metaheuristic algorithm to solve quadratic assignment formulations of cell formation problems without presenting number of cells, Journal of Intelligent Manufacturing, 15, 753-759 (2004) |
| [26] | Lozano, S.; Adenso-Diaz, B.; Eguia, I.; Onieva, L., A one-step tabu search algorithm for manufacturing cell design, Journals on Behalf of the Operational Research Society, 50, 509-516 (1999) · Zbl 1054.90539 |
| [27] | Wu, T.; Low, C.; Wu, W., A tabu search approach to the cell formation problem, International Journal of Advanced Manufacturing Technology, 23, 916-924 (2004) |
| [28] | Venugopal, V.; Narendran, T., Genetic algorithm approach to the machine-component grouping problem with multiple objectives, Computer & Industrial Engineering, 22, 469-480 (1992) |
| [29] | Cheng, C. H.; Gupta, Y. P.; Lee, W. H.; Wong, K. F., A TSP-based heuristic for forming machine groups and part families, International Journal of Production Research, 36, 1325-1337 (1998) · Zbl 0947.90567 |
| [30] | Mak, K. L.; Wong, Y. S.; Wang, X. X., An adaptive genetic algorithm for manufacturing cell formation, International Journal of Advanced Manufacturing Technology, 16, 491-497 (2000) |
| [31] | Solimanpur, M.; Vrat, P.; Shankar, R., A multi-objective genetic algorithm approach to the design of cellular manufacturing systems, International Journal of Production Research, 42, 7, 1419-1441 (2004) · Zbl 1060.90084 |
| [32] | Rajagopalan, R.; Batra, J., A genetic algorithm approach for machine cell formation, Journal of Advance Manufacturing Systems, 5, 27-44 (2006) |
| [33] | Gonçalves, J.; Resende, M., An evolutionary algorithm for manufacturing cell formation, Computers & Industrial Engineering, 47, 247-273 (2004) |
| [34] | Stawowy, A., Evolutionary strategy for manufacturing cell design, The International Journal of Management Science, 34, 1-18 (2006) |
| [35] | Brown, E. C.; Sumichrast, R. T., CF-GGA: a grouping genetic algorithm for the cell formation problem, International Journal of Production Research, 39, 3651-3669 (2001) · Zbl 1114.90344 |
| [36] | Yasuda, K.; Hu, L.; Yin, Y., A grouping genetic algorithm for the multi-objective cell formation problem’, International Journal of Production Research, 43, 4, 829-853 (2005) |
| [37] | James, T.; Brown, E.; Keeling, K., A hybrid grouping algorithm for the cell formation problem, Computers & Operations Research, 34, 2059-2079 (2007) · Zbl 1189.90210 |
| [38] | Islier, A. A., Group technology by an ant system algorithm, International Journal of Production Research, 43, 5, 913-932 (2005) · Zbl 1068.90048 |
| [39] | Kao, Y.; Li, Y. L., Ant colony recognition systems for part clustering problems, International Journal of Production Research, 46, 15, 4237-4258 (2008) · Zbl 1153.90398 |
| [40] | Megala, N.; Rajendran, C.; Gopalan, R., An ant colony algorithm for cell-formation in cellular manufacturing systems, European Journal of Industrial Engineering, 2, 3, 298-336 (2008) |
| [41] | Xu, H.; Wang, H., Part family formation for gt applications based on fuzzy mathematics, International Journal of Production Research, 27, 1637-1651 (1989) |
| [42] | Josien, K.; Liao, T., Simultaneous grouping of parts and machines with an integrated fuzzy clustering method, Fuzzy Sets and Systems, 126, 1-21 (2002) · Zbl 0987.91507 |
| [43] | Pai, P.-F.; Chang, P.-T.; Lee, S.-Y., Part-machine family formation using genetic algorithms in a fuzzy environment, International Journal of Advanced Manufacturing Technology, 25, 1175-1179 (2005) |
| [44] | Torkul, O.; Cedimoglu, I.; Geyik, A., An application of fuzzy clustering to manufacturing cell design, Journal of Intelligent and Fuzzy Systems, 17, 173-181 (2006) |
| [45] | Kaparthi, S.; Suresh, N., An improved neural network leader algorithm for part-machine grouping in group technology, European Journal of Operational Research, 69, 342-356 (1993) · Zbl 0800.90514 |
| [46] | Venugopal, V.; Narendran, T. T., Machine-cell formation through neural network models, International Journal of Production Research, 32, 9, 2105-2116 (1994) · Zbl 0904.90081 |
| [47] | Kamal, S.; Burke, L., FACT: a new neural network-based clustering algorithm for group technology, International Journal of Production Research, 34, 919-946 (1996) · Zbl 0947.90518 |
| [48] | Saidi-Mehrabad, M.; Safaei, N., A new model of dynamic cell formation by a neural approach, International Journal of Advanced Manufacturing Technology, 33, 1001-1009 (2007) |
| [49] | Chandrasekharan, M.; Rajagopalan, R., GROUPABILITY: an analysis of the properties of binary data matrices for group technology, International Journal of Production Research, 27, 6, 1035-1052 (1989) |
| [50] | Kumar, C.; Chandrasekharan, M., 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 (1990) |
| [51] | Hsu C. Similarity coefficient approaches to machine component cell formation in cellular manufacturing: a comparative study. Dissertation, University of Wisconsin, USA; 1990.; Hsu C. Similarity coefficient approaches to machine component cell formation in cellular manufacturing: a comparative study. Dissertation, University of Wisconsin, USA; 1990. |
| [52] | Miltenburg, J.; Zhang, W., A comparative evaluation of nine well-known algorithms for solving the cell formation problem in group technology, Journal of Operations Management, 10, 44-72 (1991) |
| [53] | Nair, G.; Narendran, T., Grouping index: a new quantitative criterion for goodness of block-diagonal forms in group technology, International Journal of Production Research, 34, 2767-2782 (1996) · Zbl 0929.90024 |
| [54] | Sarker, B., Simultaneous route selection and cell formation: a mixed-integer programming time-cost model, Integrated Manufacturing Systems, 8, 374-377 (1997) |
| [55] | Sarker, B., Measure of grouping efficiency in cellular manufacturing systems, European Journal of Operational Research, 130, 588-611 (2001) · Zbl 0983.90017 |
| [56] | Sarker, B.; Khan, M., A comparison of existing grouping efficiency measures and a new weighted grouping efficiency measure, IIE Transactions, 33, 11-27 (2001) |
| [57] | Dorigo, M.; Stützle, T., Ant colony optimization (2004), The MIT Press: The MIT Press Massachusetts · Zbl 1092.90066 |
| [58] | Stützle, T.; Hoos, H. H., Max-min ant system, Future Generation of Computer Systems, 16, 889-914 (2000) |
| [59] | Blum, C.; Dorigo, M., The hyper-cube framework for ant colony optimization, IEEE Transactions on Systems, Man, and Cybernetics—Part B, 34, 2, 1161-1172 (2004) |
| [60] | Waghodekar, P. H.; Sahu, S., Machine-component cell formation in group technology: mace, International Journal of Production Research, 22, 937-948 (1984) |
| [61] | Seifoddini, H., A note on the similarity coefficient method and the problem of improper machine assignment in group technology applications, International Journal of Production Research, 27, 1161-1165 (1989) |
| [62] | Kusiak, A.; Cho, M., Similarity coefficient algorithms for solving the group technology problem, International Journal of Production Research, 30, 2633-2646 (1992) |
| [63] | Kusiak, A.; Chow, W., Efficient solving of the group technology problem, Journal of Manufacturing Systems, 6, 117-124 (1987) |
| [64] | Carrie, A., Numerical taxonomy applied to group technology and plant layout, International Journal of Production Research, 11, 399-416 (1973) |
| [65] | Kumar, K. R.; Vannelli, A., Strategic subcontracting for efficient disaggregated manufacturing, International Journal of Production Research, 25, 1715-1728 (1987) |
| [66] | Mosier, C.; Taube, L., The facets of group technology and their impact on implementation, OMEGA—The International Journal of Management Science, 13, 5, 381-391 (1985) |
| [67] | Stanfel, L., Machine clustering for economic production, Engineering Costs and Production Economics, 9, 73-81 (1985) |
| [68] | Chan, H. M.; Milner, D., Direct clustering algorithm for group formation in cellular manufacture, Journal of Manufacturing Systems, 1, 65-75 (1982) |
| [69] | Askin, R. G.; Subramanian, S. P., A cost-based heuristic for group technology configuration, International Journal of Production Research, 25, 1, 101-113 (1987) |
| [70] | Zolfaghari, S.; Liang, M., Comparative study of simulated annealing, genetic algorithms and tabu search for solving binary and comprehensive machine-grouping problems, International Journal of Production Research, 40, 9, 2141-2158 (2002) · Zbl 1044.90506 |
| [71] | Askin, R. G.; Standridge, C. R., Modeling and analysis of manufacturing systems (1993), Wiley: Wiley New York · Zbl 0840.90081 |
| [72] | de Witte, J., The use of similarity coefficients in production flow analysis, International Journal of Production Research, 18, 4, 503-514 (1980) |
| [73] | Mosier, C.; Taube, L., Weighted similarity measure heuristics for the group technology machine clustering problem, OMEGA—The International Journal of Management Science, 13, 6, 577-583 (1985) |
| [74] | Shafer, S. M.; Rogers, D. F., Similarity and distance measures for cellular manufacturing. Part II. An extension and comparison, International Journal of Production Research, 31, 6, 1315-1326 (1993) |
| [75] | Kumar, K.; Kusiak, A.; Vannelli, A., Grouping of parts and components in flexible manufacturing systems, European Journal of Operational Research, 24, 387-397 (1986) · Zbl 0599.90048 |
| [76] | Boe, W. J.; Cheng, C. H., A close neighbor algorithm for designing cellular manufacturing systems, International Journal of Production Research, 29, 10, 2097-2116 (1991) · Zbl 0729.90577 |
| [77] | Zolfaghari, S.; Liang, M., A new genetic algorithm for the machine/part grouping problem involving processing times and lot sizes, Computer & Industrial Engineering, 45, 713-731 (2002) |
| [78] | Birattari M. The problem of tuning metaheuristics as seen from a machine learning perspective. Dissertation, Universite Libre De Bruxelles, Belgium; 2005.; Birattari M. The problem of tuning metaheuristics as seen from a machine learning perspective. Dissertation, Universite Libre De Bruxelles, Belgium; 2005. · Zbl 1101.68748 |
| [79] | Srinivasan, G.; Narendran, T. T., GRAFICS—a nonhierarchical clustering algorithm for group technology, International Journal of Production Research, 29, 463-478 (1991) |
| [80] | Srinivasan, G., A clustering algorithm for machine cell formation in group technology using minimum spanning trees, International Journal of Production Research, 32, 9, 2149-2158 (1994) · Zbl 0897.90116 |
| [81] | Onwubolu, G.; Mutingi, M., A genetic algorithm approach to cellular manufacturing systems, Computer & Industrial Engineering, 39, 125-144 (2001) |
| [82] | Dimopoulos, C.; Mortt, N., A hierarchical clustering methodology based on genetic programming for the solution of simple cell-formation problems, International Journal of Production Research, 39, 1, 1-19 (2001) · Zbl 0976.90066 |
| [83] | Islier AA., Personal communication, 2008.; Islier AA., Personal communication, 2008. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
