Machine-part grouping and cluster analysis: similarities, distances and grouping criteria

• Autorzy: Owsiński J.W.
• Języki publikacji: EN

Abstrakty

EN

The paper considers the machine-part grouping problem, as equivalent to partitioning the set of machines and operations into subsets, corresponding to block diagonalisation with constraints. The attempts to solve the problem with clustering methods are outlined. The difficulties encountered are presented, related to (i) ambiguity of formulations; (ii) selection of criteria; and (iii) lack of effective algorithms. These are illustrated in more detail with a limited survey of similarity and distance definitions, and of criteria used, constituting the main body of the paper. The return is proposed to the basic paradigm of cluster analysis, as providing simple and fast algorithms, which, even if not yielding optimal solutions, can be controlled in a simple manner, and their solutions improved.

Słowa kluczowe

EN

group technology; cell formation; machine-part grouping; cluster analysis; agglomerative clustering; similarity definitions; distance definitions

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2009
• Tom: Vol. 57, nr 3
• Strony: 217--228
• Opis fizyczny: Bibliogr. 53 poz., rys., tab.

Twórcy

autor

Owsiński J.W.

• Systems Research Institute, Polish Academy of Sciences, 6 Newelska St., 01-447 Warszawa, Poland,

Bibliografia

• [1] J.L. Burhridge, "Production flow analysis", Production fill fleering 4, 139-152 (1971).
• [2] J. McAuley, "Machine grouping for efficient production". The Production Engineer 51, 53-57 (1972).
• [3] A.S. Carrie, "Numerical taxonomy applied to group technology and plant layout", IJPR 11, 399-416 (1973).
• [4] Ch.H. Cheng, A. Kumar, and J. Motwani, "A comparative examination of selected cellular manufacturing clustering algorithms", Int. J. Operations & Prod. Mgmt. 15 (12), (1995).
• [5] Y. Crania and M. Oosten, "Models for machine-part grouping in cellular manufacturing", IJPR 34 (6), 1693-1713 (1996)
• [6] B.R. Sarker and S. Mondal, "Grouping efficiency measures cellular manufacturing: a survey and critical review", IJPR 37 (2), 285-314 (1999).
• [7] B.R. Sarker and M. Khan, "A comparison of existing grouping efficiency measures and a new weighted grouping efficiency measure", IIE Trans. 1, 32 (2000).
• [8] U.R. Kulkarni and M.Y. Kiang, "Dynamic grouping of parts in flexible manufacturing systems - a self-organizing networks approach", EJOR 84, 192-212 (1995).
• [9] A. Kusiak, A. Vannelli and K.R. Kumar, "Clustering analysis: models and algorithms", Control and Cybernetics 15 (2), 139-154 (1986).
• [10] K.R. Kumar, A. Kusiak, and A. Vannelli, "Grouping parts and components in flexible manufacturing systems", E.IOR 24, 387-397 (1986).
• [11] A. Vannelli and K.R. Kumar, "A method for finding minimal bottleneck cells for grouping part-machine families", IJPR 24, 387-400 (1986).
• [12] A. Kusiak, "The generalized group technology concept", JJPR 25, 561-569 (1987).
• [13] R.G. Askin, S.H. Cresswell, J.B. Goldberg, and A.J. Vakharia, "A Hamiltonian path approach to reordering the part machine matrix for cellular manufacturing", IJPR 29 (6), 1081-1100 (1991).
• [14J D. Veeramani and K. Mani, "A polynomial-time algorithm for optimal clustering in a special class of {0-1} matrices", IJPR 34(9), 2587-2611 (1996).
• [15] F.F. Boctor, "A linear formulation of the machine-part cell formation problem", IJPR 29 (3), 343-356 (1991).
• [16] F.F. Boctor, "The minimum-cost machine-part cell formation problem", IJPR 34 (4), 1045-1063 (1996).
• [17] A. Stawowy, Z. Mazur, and J. Obrzud, "Application of a genetic algorithm in product grouping"; in Optimization in Combinatorial Problems, vol. 1, pp. 185-193, eds A. Straszak, J. Joszczuk-Januszewska, and Z. Nahorski, Gdynia, 1996, (in Polish).
• [18] D.F. Rogers and Sh.S. Kulkarni, "Optimal bivariate clustering and a genetic algorithm with an application in cellular manufacturing", EJOR 160 (2), 423-444 (2005).
• [19] K. Yasuda, L. Hu, and Y. Yin, "A grouping genetic algorithm for the multi-objective cell formation problem", IJPR 43 (4), 829-853 (2005).
• [20] A. Kusiak and Y.K. Chung, "GT/ART: using neural network to form machine cells", Manufacturing Review 4 (4), 293-301 (1991).
• [21] S. Kaparth and N.C. Suresh, "Machine-component cell formation in group technology: MACE", IJPR 30 (6), 1353-1367 (1992).
• [22] I. Arizono, M. Kalo, A. Yamamoto, and H. Ohta, "A new stochastic neural network model and its application to grouping parts and tools in flexible manufacturing systems", IJPR 33 (6), 1535-1548 (1995).
• [23] R.J. Kuo, Y.T. Su, C.Y. Chiu, K.-Y. Chen, and F.C. Tien, "Part family formation through fuzzy ART2 neural network". Decision Support Systems 42 (1), 89-103 (2006).
• [24] R. Shankar, M. Solimanpur, and P. Vral, "Ant colony optimization algorithm to the inter-cell layout problem in cellular manufacturing", EJOR 157 (3), 592-606 (2004).
• [25] A.E. Smith, G. Ozdemir, and B.A. Norman, "Incorporating heterogeneous distance metrics within block layout design", IJPR 41 (5), 1045-1056(2003).
• [26] I. Castillo and B. Peters, "An extended distance-based facility layout problem", IJPR 41 (11), 2451-2479 (2003).
• [27] T. Dunker, G. Radons, and E. Westkamper, "A coevolutionary algorithm for a facility layout problem", IJPR 41 (15), 3479-3500 (2003).
• [28] D. Lei and Z. Wu, "Tabu-search approach based on a similarity coefficient for cell formation in generalized group technology", IJPR 43 (19), 4035-4047 (2005).
• [29] M.-Sh. Yang, W.-L. Hung, and F.-Ch. Cheng, "Mixed-variable fuzzy clustering approach to part family and machine cell formation for group technology applications", IJPE 103 (1), 185-198 (2006).
• [30] F. Alhourani and H. Seifoddini, "Machine cell formation for production management in cellular manufacturing systems", IJPR 45 (4), 913-934 (2007).
• [31] C.O. Kim, J.-G. Back, and J.-K. Back, "A two-phase heuristic algorithm for cell formation problems considering alternative part routes and machine sequences", IJPR 42 (18), 3911-3927 (2004).
• [32] I. Mahdavi, J. Rezacian, K. Shanker, and Z.R. Amiri, "A set partitioning based heuristic procedure for incremental cell formation with routing flexibility", IJPR 44 (24), 5343-5361 (2006).
• [33] C.H. Chu and J.C. Hayya, "A fuzzy clustering approach to manufacturing cell formation", IJPR 29 (7), 1475-1487 (1991).
• [34] N.N.Z. Gindy, T.M. Ratchev, and K. Case, "Component grouping for group technology applications - a fuzzy clustering approach with validity measure", IJPR 33 (9), 2493-2509 (1995).
• [35] S. Susanto, R.D. Kennedy and J.W.H. Price, "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 10 (4), 375-388 (1999).
• [36] J. Li, C.-H. Chu, Y. Wang, and W. Yan, "An improved fuzzy clustering method for cellular manufacturing", IJPR 45 (5), 1049-1062 (2007).
• [37] H. Wang, B. Alidaee, F. Glover, and G. Kochenberger, "Solving group technology problems via clique partitioning", IJFMS 18 (2), 77-97 (2006).
• [38] Y. Won and K.R. Currie, "Efficient p-median mathematical programming approaches to machine-part grouping in group technology manufacturing". Engineering Optimization 36 (5), 555-573 (2004)
• [39] Y. Won and K.-Ch. Lee, "Modified p-median approach for efficient group technology cell formation". Computers & Industrial Engineering 46 (3), 495-510 (2004).
• [40] S.M. Shafer and D.F. Rogers, "Similarity and distance measures for cellular manufacturing. Part I: A survey", IJPR 31 (5), 1133-1142 (1993).
• [41] S.M. Shafer and D.F. Rogers, "Similarity and distance measures for cellular manufacturing. Part II: An extension and comparison", IJPR 31 (6), 1315-1326 (1993).
• [42] K.M. Saiful Islam and B.R. Sarker, "A similarity coefficient measure and machine-parts grouping in cellular manufacturing systems", IJPR 38 (3), 699-720 (2000).
• [43] S. Viswanathan, "A new approach for solving the P-median problem in group technology", IJPR 34 (10), 2691-2700 (1996).
• [44] K. Yasuda and Y. Yin, "A dissimilarity measure for solving the cell formation problem in cellular manufacturing", Computers & Industrial Engineering 39, 1-17 (2001).
• [45] Y. Yin and K. Yasuda, "Manufacturing cells design in consideration of various production factors", IJPR 40, 885-906 (2002).
• [46] C. Dimopoulos and N. Mort, "Evolving knowledge for the solution of clustering problems in cellular manufacturing", IJPR 42 (19), 4119-4133 (2004).
• [47] O.K. Adil and J.B. Ghosh, "Maximum diversity / similarity models with extension to part grouping", ITOR 12 (3), 311-324 (2005).
• [48] M.S. Akturk and H.O. Balkose, "Part-machine grouping using a multi-objective cluster analysis", IJPR 34 (8), 2299-2315 (1996).
• [49] G.J.K. Nair and T.T. Narendran, "Grouping index: a new quantitative criterion for goodness of block-diagonal forms in group technology", IJPR 34 (10), 2767-2782 (1996).
• [50] H.H. Bock, "Classification and clustering: problems for the future", New Approaches in Classification and Data Analysis 1, 3-24(1994).
• [51] J. Stańczak, Seminar at the Systems Research Institute, IBS, Warsaw, 2002.
• [52] J.W. Owsiński, "On a quasi-objective global clustering method", in Data Analysis and Informatics, pp. 293-305 E. Diday, North Holland, Amsterdam, 1984.
• [53] J.W. Owsiński, "On a new naturally indexed quick clustering method with global objective function", Appl. Stoch. Models & Data Analysis 6, 157-171 (1991).