JSSM  Vol.3 No.4 , December 2010
Manufacturing Cells Formation Based on Graph Coloring
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.

Cite this paper
nullJ. 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.
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.

 
 
Top