Skip to main content
SpringerLink
Log in

A heuristic algorithm for cell formation problems with consideration of multiple production factors

  • ORIGINAL ARTICLE
  • Published:
The International Journal of Advanced Manufacturing Technology Aims and scope Submit manuscript

Abstract

For the design of manufacturing cells, numerous mathematical models and various algorithms have been extensively investigated in the literature. However, most of the proposed models and algorithms have more or fewer drawbacks on the issues with real-life situations. In this paper, we propose a mathematical model that incorporates multiple key real-life production factors simultaneously, namely, production volume, batch size, alternative process routings and perfect coefficient of each routing, cell size, unit cost of intercell/intracell movements, and path coefficient of material flows. Then, to solve this NP-hard model, we develop a heuristic algorithm with three stages: (1) form the temporary machine group plan according to the alternative process routings of each part, (2) select the appropriate process routing of each part with respect to the over-all material movement cost, and (3) configure the regular manufacturing cells based on the appropriate process routing. A simple numerical example and an industrial case are used to test the computational performance of the proposed algorithm. The test results imply that it is useful for manufacturing cell design in both quality and speed.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. Ham I, Hitomi K (1985) Group technology applications to production management. Kluwer-Nijhoff, Boston

    Google Scholar 

  2. Burbidge JL (1979) Group technology in engineering industry. Mech Eng, London

    Google Scholar 

  3. Wemmerlov U, Johnson DJ (1997) Cellular manufacturing at 46 user plants: implementation and performance improvements. Int J Prod Res 35:29–49

    Article  Google Scholar 

  4. Balakrishnan J, Cheng CH (2007) Multi-period planning and uncertainty issues in cellular manufacturing: a review and future directions. Eur J Oper Res 177:281–309

    Article  MATH  Google Scholar 

  5. Reisman A, Kumar A, Motawani J, Cheng CH (1997) Cellular manufacturing: a statistical review of the literature (1965–1995). Oper Res 45(4):508–520

    Article  MATH  Google Scholar 

  6. Wei JC, Gaither N (1990) A capacity constrained multiobjective CF method. J Manuf Sys 9:222–232

    Article  Google Scholar 

  7. Selim HM, Askin RG, Vakharia AJ (1998) Cell formation in group technology: review, evaluation and direction for future research. Comput Ind Eng 34:3–20

    Article  Google Scholar 

  8. Mansouri SA, Husseini SM, Newman ST (2000) A review of the modern approaches to multi-criteria cell design. Int J Prod Res 38:1201–1218

    Article  MATH  Google Scholar 

  9. Yin Y, Yasuda K (2006) Similarity coefficient methods applied to the cell formation problem: a taxonomy and review. Int J Prod Econ 101:329–352

    Article  Google Scholar 

  10. Defersha FM, Chen M (2006) A comprehensive mathematical model for the design of cellular manufacturing systems. Int J Prod Econ 103:767–783

    Article  Google Scholar 

  11. Greene T, Sadowski R (1984) A review of cellular manufacturing assumptions, advantages, and design techniques. J Oper Manag 4:85–97

    Article  Google Scholar 

  12. Joines J, Culbreth C, King R (1996) A comprehensive review of production oriented cell formation techniques. Int J Fact Auto Info Manag 3:225–265

    Google Scholar 

  13. Goncalves JF, Resende MGC (2004) An evolutionary algorithm for manufacturing cell formation. Comput Ind Eng 47:247–273

    Article  Google Scholar 

  14. Askin RJ, Vakharia AJ (1990) Group technology-cell formation and operation. In: Cleland DI, Bidanda B (eds) Automated factory handbook: technology and management. TAB, New York, pp 317–366

    Google Scholar 

  15. McAuley J (1972) Machine grouping for efficient production. Prod Eng 51:53–57

    Article  Google Scholar 

  16. Stanfel L (1985) Machine clustering for economic production. Eng Costs Prod Econ 9:73–81

    Article  Google Scholar 

  17. Gupta T, Seifoddini H (1990) Production data based similarity coefficient for machine-component grouping decisions in the design of a cellular manufacturing system. Int J Prod Res 28:1247–1269

    Article  Google Scholar 

  18. Khan M, Islam S, Sarker B (2000) A similarity coefficient measure and machine-parts grouping in cellular manufacturing systems. Eng Costs Prod Econ 38:699–720

    MATH  Google Scholar 

  19. Yasuda K, Yin Y (2001) A dissimilarity measure for solving the cell formation problem in cellular manufacturings. Comput Ind Eng 39:1–17

    Article  Google Scholar 

  20. Srinivasan G, Narendran TT (1991) GRAFICS-a nonhierarchical clustering-algorithm for group technology. Int J Prod Res 29:463–478

    Article  Google Scholar 

  21. Chandrasekharan MP, Rajagopalan R (1987) ZODIACan algorithm for concurrent formation of part families and machine cells. Int J Prod Res 25:835–850

    Article  MATH  Google Scholar 

  22. Nair GJ, Narendran TT (1998) CASE: a clustering algorithm for cell formation with sequence data. Int J Prod Res 36:157–179

    Article  MATH  Google Scholar 

  23. Nair GJ, Narendran TT (1998) ACCORD: a bi-criterion algorithm for cell formation using ordinal and ratio-level data. Int J Prod Res 37:539–556

    Article  Google Scholar 

  24. Miltenburg J, Zhang W (1991) A comparative evaluation of nine well-known algorithms for solving the cell formation in group technology. J Oper Manag 10:44–72

    Article  Google Scholar 

  25. Rajagopalan R, Batra JL (1975) Design of cellular production systems—a graph theoretic approach. Int J Prod Res 13:567–579

    Article  Google Scholar 

  26. Askin RG, Cresswell SH, Goldberg JB, Vakharia AJ (1991) Hamiltonian path approach to reordering the part-machine matrix for cellular manufacturing. Int J Prod Res 29:1081–1100

    Article  Google Scholar 

  27. Mukhopadyay SK, Ramesh BK, Vijai SKV (2000) Modified Hamiltonian chain: a graph theoretic approach to group technology. Int J Prod Res 38:2459–2470

    Article  Google Scholar 

  28. Srinivasan G (1994) A clustering algorithm for machine cell formation in group technology using minimum spanning trees. Int J Prod Res 32:2149–2158

    Article  MATH  Google Scholar 

  29. Ng S (1993) Worst-case analysis of an algorithm for cellular manufacturing. Euro J Oper Res 69:384–398

    Article  MATH  Google Scholar 

  30. Ng S (1996) On the characterization and measure of machine cells in group technology. Oper Res 44:735–744

    Article  MATH  Google Scholar 

  31. Askin RG, Chiu KS (1990) A graph partitioning procedure for machine assignment and cell formation in group technology. Int J Prod Res 28:1555–1572

    Article  MATH  Google Scholar 

  32. Kusiak A (1987) The generalized group technology concept. Int J Prod Res 25:561–569

    Article  Google Scholar 

  33. Boctor F (1991) A linear formulation of the machine-part cell formation problem. Int J Prod Res 29:343–356

    Article  Google Scholar 

  34. Choobineh F (1988) A framework for the design of cellular manufacturing systems. Int J Prod Res 26:1161–1172

    Article  Google Scholar 

  35. Co HC, Araar A (1988) Configuring cellular manufacturing systems. Int J Prod Res 26:1511–1522

    Article  Google Scholar 

  36. Vakharia A, Chang Y (1997) Cell formation in group technology: a combinatorial search approach. Int J Prod Res 35:2025–2043

    Article  MATH  Google Scholar 

  37. Steudel H, Ballakur A (1987) A dynamic programming based heuristic for machine grouping in manufacturing cell formation. Comput Ind Eng 12:215–222

    Article  Google Scholar 

  38. Shafer SM, Rogers DF (1991) A goal programming approach to the cell formation problem. J Oper Manag 10:28–43

    Article  Google Scholar 

  39. Venugopal V (1999) Soft-computing-based approaches to the group technology problem: a state-of-the-art review. Int J Prod Res 37:3335–3357

    Article  MATH  Google Scholar 

  40. Basu A, Hyer N, Shtub A (1995) An expert system based approach to manufacturing cell design. Int J Prod Res 33:2739–2755

    Article  MATH  Google Scholar 

  41. ElMaraghy HA, Gu P (1988) Knowledge-based system for assignment of parts to machines. Int J Adv Manuf Technol 3:33–44

    Article  Google Scholar 

  42. Moon YB (1990) Forming part-machine families for cellular manufacturing: a neural network approach. Int J Adv Manuf Technol 5:278–291

    Article  Google Scholar 

  43. Kusiak A, Chung Y (1991) GT/ART: using neural networks to form machine cells. Manuf Rev 4:293–301

    Google Scholar 

  44. Moon YB, Chi SC (1992) Generalized part family formation using neural network techniques. J Manuf Syst 11:149–159

    Article  Google Scholar 

  45. Venugobal V, Narendran TT (1994) Machine-cell formation through neural network models. Int J Prod Res 32:2105–2116

    Article  Google Scholar 

  46. Ahmed P, Moghaddam TR, Safaei N (2004) A comparison of heuristic methods for solving a cellular manufacturing model in a dynamic environment. Working Paper WP007/04, University of Wolverhampton

  47. Holland JH (1975) Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor

    Google Scholar 

  48. Gupta Y, Gupta M, Kumar A, Sundram C (1995) Minimizing total inter-cell and intera-cell moves in cellular manufacturing: a genetic algorithm. Int J Comput Integr Manuf 8:92–101

    Article  Google Scholar 

  49. Joines J, Culberth C, King R (1996) Manufacturing cell design: an integer programming model employing genetic algorithms. IIE Trans 28:69–85

    Article  Google Scholar 

  50. Venugopal V, Narendran T (1992) A genetic algorithm approach to the machine component grouping problem with multiple objectives. Comput Ind Eng 22:469–480

    Article  Google Scholar 

  51. Gen M, Cheng R (1997) Genetic algorithms and engineering design. Wiley, New York

    Google Scholar 

  52. Wu X, Chu CH, Wang Y, Yan W (2006) A genetic algorithm for cellular manufacturing design and layout. Eur J Oper Res 181:156–167

    Article  Google Scholar 

  53. James TL, Brown EC, Keeling KB (2007) A hybrid grouping genetic algorithm for the cell formation problem. Comput Oper Res 34:2059–2079

    Article  MATH  Google Scholar 

  54. Glover F (1989) Tabu search: part I. ORSA J Comput 1:190–206

    MATH  MathSciNet  Google Scholar 

  55. Glover F (1990) Tabu search: part II. ORSA J Comput 2:4–32

    MATH  Google Scholar 

  56. Logendran R, Ramakrishna P, Srikandarajah C (1994) Tabu search based heuristic for cellular manufacturing systems in the presence of alternative process plans. Int J Prod Res 32:273–297

    Article  MATH  Google Scholar 

  57. Lozano S, Adenso-Diaz B, Onieva L (1999) A one-step Tabu search algorithm for manufacturing cell design. J Oper Res Soc 50:509–516

    Article  MATH  Google Scholar 

  58. Cao D, Chen M (2004) Using penalty function and Tabu search to solve cell formation problems with fixed cell cost. Comput Oper Res 31:21–37

    Article  MATH  MathSciNet  Google Scholar 

  59. Schaller J (2005) Tabu search procedures for the cell formation problem with intra-cell transfer costs as a function of cell size. Comput Ind Eng 49:449–462

    Article  Google Scholar 

  60. Boctor FF (1991) A linear formulation of the machine-part cell formation problem. Int J Prod Res 29:343–356

    Article  Google Scholar 

  61. Chen M (1998) A mathematical programming model for systems reconfiguration in a dynamic cellular manufacturing environment. Ann Oper Res 77:109–128

    Article  MATH  Google Scholar 

  62. Sofianopoulou S (1997) Application of simulated annealing to a linear model for the formulation of machine cells in group technology. Int J Prod Res 35:501–511

    Article  MATH  Google Scholar 

  63. Vakharia A, Chang Y (1997) Cell formation in group technology: a combinatorial search approach. Int J Prod Res 35:84–97

    Google Scholar 

  64. Wang TY, Wu KB, Liu YW (2001) A simulated annealing algorithm for facility layout problems under variable demand in cellular manufacturing systems. Comput Ind 46:181–188

    Article  Google Scholar 

  65. Xambre AR, Vilarinho PM (2003) A simulated annealing approach for manufacturing cell formation with multiple identical machines. Eur J Oper Res 151:434–446

    Article  MATH  MathSciNet  Google Scholar 

  66. Sofianopoulou S (1999) Manufacturing cells design with alternative process plans and/or replicate machines. Int J Prod Res 29:463–479

    Google Scholar 

  67. Uddin MK, Shanker K (2002) Grouping of parts and machines in presence of alternative process routes by genetic algorithm. Int J Prod Econ 76:219–228

    Article  Google Scholar 

  68. Won Y, Lee KC (2001) Group technology cell formation considering operation sequence and production volume. Int J Prod Res 39:2755–2768

    Article  MATH  Google Scholar 

  69. Vakharia AJ, Wemmerlov U (1990) Designing a cellular manufacturing system: a materials flow approach based on operation sequences. IIE Trans 22:84–97

    Article  Google Scholar 

  70. Onwubolu GC, Mutingi M (2001) A genetic algorithm approach to cellular manufacturing systems. Comput Ind Eng 39:125–144

    Article  Google Scholar 

  71. Heragu SS, Chen JR (1998) Optimal solution of cellular manufacturing system design: benders decomposition approach. Eur J Oper Res 107:175–192

    Article  MATH  Google Scholar 

  72. Adil GK, Rajamani D (2001) The trade-off between intracell and intercell moves in group technology cell formation. J Manuf Syst 19:305–317

    Article  Google Scholar 

  73. Yin Y, Yasuda K (2002) Manufacturing cells design in consideration of various production factors. Int J Prod Res 40:885–906

    Article  MATH  Google Scholar 

  74. Gupta T (1993) Design of manufacturing cells for fliexible environment considering alternative routeing. Int J Prod Res 31:1259–1273

    Article  Google Scholar 

  75. Yasuda K, Hu L, Yin Y (2005) A grouping genetic algorithm for the multi-objective cell formation problem. Int J Prod Res 43:829–853

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Management, Xi’an University of Technology, Xi’an, 710048, China

    ChenGuang Liu & Jie Lian

  2. Mathematical Institute, Tohoku University, Sendai, 980-8578, Japan

    ChenGuang Liu

  3. Department of Economics and Business Management, Yamagata University, Yamagata, 990-8560, Japan

    Yong Yin

  4. School of Management, University of Texas at Dallas, Richardson, TX, 75080, USA

    Yong Yin

  5. Graduate School of Economics and Management, Tohoku University, Sendai, 980-8576, Japan

    Kazuhiko Yasuda

Authors
  1. ChenGuang Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yong Yin
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Kazuhiko Yasuda
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Jie Lian
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to ChenGuang Liu.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Liu, C., Yin, Y., Yasuda, K. et al. A heuristic algorithm for cell formation problems with consideration of multiple production factors. Int J Adv Manuf Technol 46, 1201–1213 (2010). https://doi.org/10.1007/s00170-009-2170-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00170-009-2170-0

Keywords

Search

Navigation