A hybrid heuristic based clustering algorithm to design manufacturing cell

• Autorzy: Ghosh T. , Sengupta S. , Dan P. K.
• Języki publikacji: EN

Abstrakty

EN

The manufacturing cell formation problem consists of designing a subclass of machine cells and their corresponding part families with an objective to minimize the inter-cell and intracell moves of the items while enhancing the machine utilization. This paper demonstrates a hybrid heuristic algorithm namely HACCF (Heuristic based Agglomerative Clustering for Cell Formation) exploiting the centroid linkage clustering method and the Minkowski distance metric as dissimilarity coeffcient. An exhaustive heuristic technique is developed and combined with the proposed clustering method to form manufacturing cells. 15 widely practiced datasets are obtained from past literature and tested with the proposed technique. The computational results are exhibited using the grouping efficacy as performance measure for the abovementioned test problems. The proposed technique is shown to outperform the standard and published techniques such as ZODIAC, GRAFICS, TSP based genetic algorithm and simple genetic algorithm and attained 73.33% improved result by exceeding the solution quality on the test problems. Therefore the proposed technique could be extensively used and could be hybridized with intelligent approaches to obtain more improved result in the vicinity of future cellular manufacturing system.

Słowa kluczowe

EN

cellular manufacturing; group technology; cell formation; centroid linkage clustering technique; dissimilarity measure; heuristic; hybrid approach

PL

system produkcji; produkcja komórkowa; podejście hybrydowe; algorytm

• Wydawca: Production Engineering Committee of the Polish Academy of Sciences ; Polish Association for Production Management
• Czasopismo: Management and Production Engineering Review
• Rocznik: 2010
• Tom: Vol. 1, No. 4
• Strony: 26--37
• Opis fizyczny: Bibliogr. 60 poz., rys., tab.

Twórcy

autor

Ghosh T.

autor

Sengupta S.

autor

Dan P. K.

• West Bengal University of Technology, Department of Industrial Engineering and Management, BF 142, Salt Lake City, Kolkata 700064 India, phone: [phone],

Bibliografia

• [1] Burbidge J.L., “Production flow Analysis”, in Production Engineer, 42, 12 742-752, 1963.
• [2] Burbidge J.L., “Production flow Analysis”, in Production Engineer, 50, 139-152, 1971.
• [3] Burbidge J.L., “Production Flow Analysis For Planning Group Technology”, Oxford University Press, USA, pp. 192, 1996.
• [4] Lee-Post A., “Part family identification using a simple genetic algorithm”, International Journal of Production Research, 38, 793-810, 2000.
• [5] Selim M.S., Askin R.G., and Vakharia A.J., “Cell formation in group technology: review evaluation and directions for future research”, in Computers & Industrial Engineering, 34, 1, 3-20, 1998.
• [6] Papaioannou G. and Wilson J.M., “The evolution of cell formation problem methodologies based on recent studies (1997-2008): Review and directions for future research”, in European Journal of Operational Research, 206, 3, 509-521, 2010.
• [7] Unler A. and Gungor Z., “Applying K-harmonic means clustering to the part-machine classification problem”, in Expert Systems with Applications, 36, 1179-1194, 2009.
• [8] Ghosh T., Sengupta S., Chattopadhyay M., and Dan P.K., “Meta-heuristics in cellular manufacturing: A state-of-the-art review”, in International Journal of Industrial Engineering Computations, 2, 1, 87-122, 2011.
• [9] Chandrasekharan M.P. and Rajagopalan R., “ZODIAC: an algorithm for concurrent formation of part-families and machine-cells”, in International Journal of Production Research, 25, 6, 835-850, 1987.
• [10] Srinivasan G. and Narendran T.T., “GRAFICS: a non-hierarchical clustering algorithm for group technology”, in International Journal of Production Research, 29, 3, 463-478, 1991.
• [11] Srinivasan G., “A clustering algorithm for machine cell formation in group technology using minimum spanning trees”, in International Journal of Production Research, 32, 2149-2158, 1994.
• [12] Lozano S., Dobado D., Larraneta J., and Onieva L., “Modified fuzzy C-means algorithm for cellular manufacturing”, in Fuzzy Sets and Systems, 126, 23-32, 2002.
• [13] McAuley J., “Machine grouping for efficient production”, in Production Engineer, 51, 2, 53-57, 1972.
• [14] Prabhakaran G., Janakiraman T.N., and Sachithanandam M., “Manufacturing data based combined dissimilarity coefficient for machine cell formation”, in International Journal of Advanced Manufacturing Technology, 19, 889-897, 2002.
• [15] Seifoddini H., Wolfe P.M., “Application of the similarity coefficient method in group technology”, in IIE Transactions, 183, 271-277, 1986.
• [16] McCormick W.T., Schweitzer J.P.J., and White T.W., “Problem decomposition and data reorganization by a clustering technique”, in Operations Research, 20, 5, 993-1009, 1972.
• [17] Carrie A.S., “Numerical taxonomy applied to group technology and plant layout”, in International Journal of Production Research, 11, 4, 399-416, 1973.
• [18] 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.
• [19] King J.R. and Nakornchai V., “Machine-component group formation in group technology: review and extension”, in International Journal of Production Research, 20, 117-133, 1982.
• [20] Chan H.M. and Milner D., “Direct Clustering algorithm for group formation in Cellular Manufacturing”, in Journal of Manufacturing Systems, 1, 65-75, 1982.
• [21] Waghodekar P.H. and Sahu S., “Machine-component cell formation in group technology”, in International Journal of Production Research, 22, 6, 937-948, 1984.
• [22] Kusiak A., “The part families problem in flexible manufacturing systems”, in Annals of Operations Research, 3, 279-300, 1985.
• [23] Mosier C.T. and Taube L., “Weighted similarity measure heuristics for the group technology machine clustering problem”, in OMEGA, 13, 6, 577-583, 1985.
• [24] Stanfel L.E., “Machine clustering for economic production”, in Engineering Costs and Production Economics, 9, 73-81, 1985.
• [25] Chandrasekharan M.P. and Rajagopalan R., “An ideal seed non-hierarchical clustering algorithm for cellular manufacturing”, in International Journal of Production Research, 24, 2, 451-464, 1986a.
• [26] Chandrasekharan M.P. and Rajagopalan R., “MODROC: An extension of rank order clustering for group technology”, in International Journal of Production Research, 24, 5, 1221-1233, 1986b.
• [27] Kusiak A., “The generalized group technology concept”, in International Journal of Production Research, 25, 4, 561-569, 1987.
• [28] Seifoddini H., “Duplication process in machine cells formation in group technology”, in IIE Transactions, 21, 382-388, 1989.
• [29] Chu C.H. and Tsai M., “A Comparison of three array-based clustering techniques for manufacturing cell formation”, in International Journal of Production Research, 28, 8, 1417-1433, 1990.
• [30] Shafer S.M. and Rogers D.F., “Similarity and distance measures for cellular manufacturing”, in International Journal of Production Research, 31, 5, 1131-1142, 1993.
• [31] Dimopoulos C. and Mort N., “A hierarchical clustering methodology based on genetic programming for the solution of simple cell-formation problems”, in International Journal of Production Research, 39, 1, 1-19, 2001.
• [32] Rajagopalan R. and Batra J.L., “Design of Cellular production system - A graph theoretic approach”, in International Journal of Production Research, 13, 6, 567-579, 1975.
• [33] Ballakur A. and Steudel H.J., “A with-in cell utilization based heuristic for designing cellular manufacturing systems”, in International Journal of Production Research, 25, 5, 639-655, 1987.
• [34] Vohra T., Cheng D. and Chang J.L., “A network model for cell formation in CMS”, in International Journal of Production Research, 28, 11, 2075-2084, 1990.
• [35] Veeramani D. and Mani K., “A polynomial-time algorithm for optimal clustering in a special class of {0, 1}-matrices”, in International journal of production research, 34, 9, 2587-2611, 1996.
• [36] Tavakkoli-Moghaddam R., Aryanezhad M.B., Safaei N. and Azaron A., “Solving a dynamic cell formation problem using meta-heuristics”, Applied Mathematics and Computation, 170, 761-780, 2005.
• [37] Sarker B.R. and Mondal S., “Grouping efficiency measures in cellular manufacturing: a survey and critical review”, in International Journal of Production Research, 37, 2, 285-314, 1999.
• [38] Kumar S.C. and Chandrasekharan M.P., “Grouping efficacy: a quantitative criterion for goodness of block diagonal forms of binary matrices in group technology”, in International Journal of Production Research, 28, 2, 233-243, 1990.
• [39] Anderberg M.R., “Cluster Analysis for Applications”, Academic Press Inc., New York, 1973.
• [40] Kusiak A. and Chow W.S., “Efficient solving of the group technology problem”, in Journal of Manufacturing Systems, 6, 2, 117-124, 1987.
• [41] Boe W.J. and Cheng C.H., “A close neighbor algorithm for designing cellular manufacturing systems”, in International Journal of Production Research, 29, 10, 2097-2116, 1991.
• [42] Chandrasekharan M.P. and Rajagopalan R., “GROUPABILITY: an analysis of the properties of binary data matrices for group technology”, in International Journal of Production Research, 27, 6, 1035-1052, 1989.
• [43] Kumar K.R. and Vannelli A., “Strategic subcontracting for efficient disaggregated manufacturing”, in International Journal of Production Research, 25, 12, 1715-1728, 1987.
• [44] Cheng C.H., Gupta Y.P., Lee W.H. and Wong K.F., “A TSP-based heuristic for forming machine groups and part families”, in International Journal of Production Research, 36, 5, 1325-1337, 1998.
• [45] Onwubolu G.C. and Mutingi M., “A genetic algorithm approach to cellular manufacturing systems”, in Computers & Industrial Engineering, 39, 125-144, 2001.
• [46] Davidson I. and Ravi S.S., “Agglomerative Hierarchical Clustering with Constraints: Theoretical and Empirical Results”, in Knowledge Discovery in Databases: PKDD 2005, Lecture Notes in Computer Science, 3721, 59-70, 2005.
• [47] Tzacheva A.A., “Summaries of Action Rules by Agglomerative Clustering”, in Advances in Intelligent Information Systems, Studies in Computational Intelligence, 265, 259-271, 2010.
• [48] Boulif M. and Atif K., “A new branch-&-boundenhanced genetic algorithm for the manufacturing cell formation problem”, Computers & Operations Research, 33, 2219-2245, 2006.
• [49] Boulif M. and Atif K., “A new fuzzy genetic algorithm for the dynamic bi-objective cell formation problem considering passive and active strategies”, International Journal of Approximate Reasoning, 47, 141-165, 2008.
• [50] Defersha F.M. and Chen M., “Machine cell formation using a mathematical model and a geneticalgorithm-based heuristic”, International Journal of Production Research, 44, 12, 2421-2444, 2006.
• [51] Defersha F.M. and Chen M., “A parallel genetic algorithm for dynamic cell formation in cellular manufacturing systems”, International Journal of Production Research, 46, 22, 6389-6413, 2008a.
• [52] Defersha F.M. and Chen M., “A linear programming embedded genetic algorithm for an integrated cell formation and lot sizing considering product quality”, European Journal of Operational Research, 187, 46-69, 2008b.
• [53] Neto A.R.P. and Filho E.V.G., “A simulation-based evolutionary multiobjective approach to manufacturing cell formation”, Computers & Industrial Engineering, 59, 64-74, 2010.
• [54] Deljoo V., Al-e-hashem S.M.J.M., Deljoo F. and Aryanezhad M.B., “Using genetic algorithm to solve dynamic cell formation problem”, Applied Mathematical Modelling, 34, 1078-1092, 2010.
• [55] Wu T.H., Chung S.H. and Chang C.C., “Hybrid simulated annealing algorithm with mutation operator to the cell formation problem with alternative process routings”, Expert Systems with Applications, 36, 3652-3661, 2009.
• [56] Durán O., Rodriguez N. and Consalter L.A., “Collaborative particle swarm optimization with a data mining technique for manufacturing cell design”, Expert Systems with Applications, 37, 1563-1567, 2010.
• [57] Anvari M., Mehrabad M.S. and Barzinpour F., “Machine-part cell formation using a hybrid particle swarm optimization”, International Journal of Advanced Manufacturing Technology, 47, 745-754, 2010.
• [58] Arkat J., Saidi M. and Abbasi B., “Applying simulated annealing to cellular manufacturing system design”, International Journal of Advanced Manufacturing Technology, 32, 531-536, 2007.
• [59] Ateme-Nguema B.H. and Dao T.M., “Optimization of cellular manufacturing systems design using the hybrid approach based on the ant colony and tabu search techniques”, Proceedings of the IEEE IEEM, pp. 668-673, 2007.
• [60] Ateme-Nguema B.H. an Daod T.M., “Quantized Hopfield networks and tabu search for manufacturing cell formation problems”, International Journal of Production Economics, 121, 88-98, 2009.