Manufacturing Cells Formation Based on Graph Coloring
José Francisco Ferreira Ribeiro
.
DOI: 10.4236/jssm.2010.34056   PDF    HTML     8,062 Downloads   12,504 Views   Citations

Abstract

A method for cellular manufacturing design in Group Technology is presented in this paper. The proposed method computes the dissimilarities between parts and organizes the production system in part-families and group-machines. A graph corresponding to the production system is generated and a coloring algorithm is activated in order to obtain a number of cells equal to the desired number of cells. The corresponding program was written in Matlab language and runs on a microcomputer. The results obtained on several examples found in the literature are consistently equivalent to or even better than those hitherto proposed, in terms of inter-cell moves and dimensions of the cells.

Share and Cite:

J. Ribeiro, "Manufacturing Cells Formation Based on Graph Coloring," Journal of Service Science and Management, Vol. 3 No. 4, 2010, pp. 494-500. doi: 10.4236/jssm.2010.34056.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1] J. L. Burbidge, “The Introduction of Group Technology,” John Wiley, 1975.
[2] J. F. F. Ribeiro and S. Meguelati, “Organiza??o de um Sistema de Produ??o em Células de Fabrica??o,” Revista Gest?o e Produ??o, Vol. 9, No. 1, 2002, pp. 62-77.
[3] N. L. Hyer and U. Wemmerlow, “GT in US Manufacturing Industry,” International Journal of Production Research, Vol. 27, No. 8, 1989, pp. 1287-1304.
[4] F. Mah-moodi, K. J. Dooley and P. J. Starr, “An Investigation of Dy-namic Group Scheduling Heuristics in a Job Shop Manufactur-ing Cell,” International Journal of Production Research, Vol. 28, No. 9, 1990, pp. 1695-1711.
[5] A. Kusiak, “The Gener-alized Group Technology Concept,” International Journal of Production Research, Vol. 25, No. 4, 1987, pp. 561-569.
[6] N. Singh, “Design of Cellular Manufacturing Systems: An Invited Review,” European Journal of Opera-tional Research, Vol. 69, No. 3, 1993, pp. 284-291.
[7] F. F. Boctor, “A Linear Formulation of the Machine–Part Cell For-mation Problem,” International Journal of Production Re-search, Vol. 29, No. 2, 1991, pp. 343-356.
[8] F. F. Boctor, “The Minimum Cost - Machine–Part Cell Formation,” Interna-tional Journal of Production Research, Vol. 34, No. 4, 1996, pp. 1045-1063.
[9] S. Oliveira, J. F. F. Ribeiro and S. C. Seok, “A Spectral Clustering Algorithm for Manufacturing Cell For-mation,” Computers and Industrial Engineering, Vol. 57, No. 3, 2009, pp. 1008-1014.
[10] V. Ramabhatta and R. Nagi, “An Integrated Formulation of Manufacturing Cell Formation,” Operations Research, Vol. 77, No. 1, 1998, pp. 79-95.
[11] S. M. Shafer and G. M. Kern, “A Mathematical Programming Approach for Dealing with Exceptional Elements in Cellular Manufacturing,” International Journal of Production Research, Vol. 30, No. 5, 1992, pp. 1029- 1036.
[12] J. Slomp, B. V. Chowdary and N. Suresh, “Design of Virtual Manufacturing Cells: A Mathematical Programming Approach,” Robotics and Computer Integrated Manufacturing, Vol. 21, No. 3, 2005, pp. 273-288.
[13] S. Viswanathan, “Configuring Cellular Manu-facturing Systems: A Quadratic Integer Programming Formula-tion and A Simple Interchange Heuristic,” International Jour-nal of Production Research, Vol. 33, No. 2, 1995, pp. 361-376.
[14] Y. Won, “Two–Phase Approach to GT Cell Formation Using Efficient P–Median Formulations,” Interna-tional Journal of Production Research, Vol. 38, No. 7, 2000, pp. 1601-1613.
[15] M. Boulif and K. Atif, “A New Branch–And–Bound Enhanced Genetic Algorithm for the Manufacturing Cell Formation,” Computers and Operations Research, Vol. 33, No. 8, 2006, pp. 2219-2245.
[16] I. Al-Qattan-Al, “Designing Flexible Manufacturing Cells Using a Branch–and–Bound Method,” International Journal of Pro-duction Research, Vol. 28, No. 2, 1990, pp. 325-336.
[17] C. H. Chu and J. C. Hayya, “A Fuzzy Clustering Approach to Manufacturing Cell Formation,” International Industrial Engi-neering Conference, Orlando, 1991, pp. 495-500.
[18] H. Xu and H. P. Wang, “Part-Family Formation for Group Technol-ogy Applications Based on Fuzzy Mathematics,” International Journal of Production Research, Vol. 27, No. 9, 1989, pp. 1637-1651.
[19] C. Dimipoulos and N. A. Mort, “Hierarchical Clustering Methodology Based on Genetic Programming for the Solution of Simple Cell–Formation Problems,” Interna-tional Journal of Production Research, Vol. 39, No. 17, 2001, pp. 1-19.
[20] G. Jeon and H. R. Leep, “Forming Part Families by Using Genetic Algorithm and Designing Machine Cells under Demand Changes,” Computers and Operations Research, Vol. 33, No. 1, 2006, pp. 263-283.
[21] A. Rajagopalan and D. J. Fonseca, “Volume Sensitivity Analysis for Manufacturing Cells: A Genetic Algorithm,” Journal of Advanced Manufac-turing Systems, Vol. 4, No. 2, 2005, pp. 167-183.
[22] V. Venugopal and T. T. Narendran, “Cell Formation in Manufac-turing Systems through Simulated Annealing: An Experimental Evaluation,” European Journal of Operational Research, Vol. 63, No. 2, 1992, pp. 409-422.
[23] C. Zhao and Z. A. Wu, “Genetic Algorithm for Manufacturing Cell Formation with Multiple Routes and Multiples Objectives,” International Journal of Production Research, Vol. 38, No. 1, 2000, pp. 385-395.
[24] A. Kusiak and Y. Chung, “GT/ART: Using Neural Networks to Form Machine Cells,” Manufacturing Re-view, Vol. 4, No. 4, 1991, pp. 293-301.
[25] H. Lee, C. O. Malave and S. Ramachandran, “Neural Network–Based Design of Cellular Manufacturing Systems,” Journal of Intelligent Manufacturing, Vol. 3, 1992, pp. 325-332.
[26] Y. B. Moon and S. C. Chi, “Generalized Part–Family Formation Using Neural Network Techniques,” Journal of Manufacturing Sys-tems, Vol. 11, No. 3, 1992, pp. 149- 159.
[27] G. K. Adil, D. Rajanani and D. Strong, “Assignment Allocation and Simulated Annealing Algorithms for Cell Formation,” IIE Transactions, Vol. 29, No. 1, 1997, pp. 53-67.
[28] S. Sofianopoulou, “Manufacturing Cell Design with Alternative Process Plans and/or Replicate Machines,” International Journal of Produc-tion Research, Vol. 37, No. 3, 1999, pp. 707-720.
[29] V. Venugopal and T. T. Narendran, “A Genetic Algorithm Ap-proach to the Machine–Component Grouping Problem with Multiple Objectives,” Computers and Industrial Engineering, Vol. 22, No. 4, 1992, pp. 469-480.
[30] S. J. Deutsch, S. F. Freeman and M. Helander, “Manufacturing Cell Formation Using an Improved P–Median Model,” Computers and Indus-trial Engineering, Vol. 34, No. 1, 1998, pp. 135-146.
[31] G. Harhalalkis, R. Nagi and J. M. Proth, “An Efficient Heuristic in Manufacturing Cell Formation for Group Technology Applica-tions,” International Journal of Production Research, Vol. 28, No. 1, 1990, pp. 185-198.
[32] S. Meguelati, “Methodes de Classification Pour la Constitution d’ilots de Fabrication,” Rapport LAAS 98175, Toulouse, 1998.
[33] J. F. F. Ribeiro and B. Pradin, “A Methodology for Cellular Manufacturing Design,” International Journal of Production Research, Vol. 31, No. 1, 1993, pp. 235-250.
[34] A. Aho, J. Hopcroft and J. Ullman, “Data Structure and Algorithms,” Addison Wesley, Massachusetts, 1983.
[35] M. R. Garey and D. S. Johnson, “Computers and Intractability,” Freeman, 1979.
[36] S. Oliveira, J. F. F. Ribeiro and S. C. Seok, “A Comparative Study of Similarity Measures for Manufacturing Cell Formation,” Journal of Manufacturing Systems, Vol. 27, No. 1, 2008, pp. 19-25.
[37] A. Guenoche, “Enumeration des Partitions de Diametre Minimum,” Discrete Mathematics, Vol. 111, No. 1-3, 1993, pp. 227-287.
[38] G. Srinivasan, “An Assignment Model for the Part-Families Problem in Group Technology,” Interna-tional Journal of Production Research, Vol. 28, No. 1, 1990, pp. 145-152.
[39] K. R. Kumar and A. Vanelli, “Strategic Subcontratcting for Efficient Disaggregated Manufacturing,” International Journal of Production Research, Vol. 25, No. 12, 1987, pp. 1715-1728.
[40] J. C. Wei and G. M. Kern, “Com-monality Analysis: A linear Cell Clustering Algorithm for Group Technology,” International Journal of Production Re-search, Vol. 27, No. 12, 1989, pp. 2053-2062.
[41] H. M. Chan and D. A. Milner, “Direct Cluster Algorithm for Group Formation in Cellular Manufacture,” Journal of Manufacturing Systems, Vol. 1, 1981, pp. 235-242.
[42] A. Ballakur and H. J. Steudel, “A within Cell Based Heuristic for Designing Cellular Manufacturing Systems,” International Journal of Production Research, Vol. 25, No. 5, 1987, pp. 639-665.
[43] P. H. Wag-hodekar and S. Sahu, “Machine-Component Cell Formation in Group Technology: MACE,” International Journal of Produc-tion Research, Vol. 22, No. 6, 1984, pp. 937-948.

Copyright © 2024 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.