An Efficient Algorithm to Solve Utilization-based Model for Cellular Manufacturing Systems

Document Type : Research Paper


1 MAPNA Turbine Engineering & Manufacturing Co. (TUGA), P.O.Box: 15875-5643, Tehran, Iran

2 Department of Industrial Engineering, Mazandaran University of Science and Engineering, Babol, Iran

3 Department of Industrial and Management Systems Engineering, University of Nebraska-Lincoln, Lincoln, Nebraska, USA


The design of cellular manufacturing system (CMS) involves many structural and operational issues. One of the important CMS design steps is the formation of part families and machine cells which is called cell formation. In this paper, we propose an efficient algorithm to solve a new mathematical model for cell formation in cellular manufacturing systems based on cell utilization concept. The proposed model is to minimize the number of voids in cells to achieve higher cell utilization. The proposed model is a non-linear model which cannot be optimally solved. Thus, a linearization approach is used and the linearized model is then solved by linear optimization software. Even after linearization, the large-sized problems are still difficult to solve, therefore, a Simulated Annealing method is developed. To verify the quality and efficiency of the SA algorithm, a number of test problems with different sizes are solved and the results are compared with solutions obtained by Lingo 8 in terms of objective function values and computational time.


Main Subjects

[1] Adil G. K., Ragamani D., Strong D. (1993), A mathematical model for cell formation considering
investment and operational costs; European Journal of Operational Research 69; 330–341.
[2] Albadawi Z., Bashir H.A., Chen M. (2005), A mathematical approach for the formation of
manufacturing cells; Computers & Industrial Engineering 48; 3–21.
[3] Chen S.J., Cheng C.S. (1995), A neural network based cell formation algorithm in cellular
manufacturing; International Journal of Production Research 33(2); 293- 318.
[4] Collet S., Spicer R. (1995), Improving productivity through cellular manufacturing; Production and
Inventory Management Journal 36(1); 71–75.
[5] Fallahalipour K., Shamsi R., A mathematical model for cell formation in CMS using sequence data
(2008); Journal of Industrial and Systems Engineering 2(2); 144-153.
[6] Goncalves J., Resende M. (2004), An evolutionary algorithm for manufacturing cell formation;
Computers & Industrial Engineering 47; 247–273.
[7] Heragu S.S. (1994), Group technology and cellular manufacturing; IEEE Transactions on Systems,
Man and Cybernetics 24(2); 203–214.
[8] Hyer N. (1984), The Potential of Group Technology for U.S. Manufacturing; Journal of Operations
Management 4(3); 183-202.
[9] Hyer N., Wemmerlov U. (1984), Group technology and productivity; Harvard Business Review, July-
August; 140-149.
[10] Joines J.A., King R.E., Culbreth C.T. (1996), A comprehensive review of production oriented
manufacturing cell formation techniques; International Journal of Flexible Automation and Integrated
Manufacturing 3; 225–265.
[11] Kirkpatrick S., Gelatt C. D., Vecchi M. P. (1983), Optimization by simulated annealing; Science 220; 671-680.
[12] Kusiak A. (1987), The generalized group technology concept; International Journal of Production Research 25(4); 561–569.
[13] Lozano S., Adenso-Diaz B., Eguia I., Onieva L. (1999), A one-step tabu search algorithm for manufacturing cell design; Journal of the Operational Research Society 50; 509–16.
[14] Majeed Ali A. A., Vrat P. (1999), Manufacturing cell formation: a neural network approach; Proceedings of the International Conference on Operations Management for Global Economy Challenges and Prospects; Indian Institute of Technology, New Delhi, India, 565-571.
[15] Mahdavi I., Kaushal O.P., Chandra M. (2001), Graph-neural network approach in cellular manufacturing on the basis of a binary system; International Journal of Production Research 39(13); 2913–2922.
[16] Mahdavi I., Javadi B., Fallah-Alipour K., Slomp J. (2007), Designing a new mathematical model for cellular manufacturing system based on cell utilization; Applied Mathematics and Computation 190; 662–670.
[17] Megala N., Rajendran C., Gopalan R. (2008), An ant colony algorithm for cell-formation in cellular manufacturing systems; European Journal of Industrial Engineering 2(3); 298-336.
[18] Nair G.J., Narendran T.T. (1998), CASE: A clustering algorithm for cell formation with sequence data; International Journal of Production Research 36; 157–179.
[19] Onwubolu G.C., Mutingi M. (2001), A genetic algorithm approach to cellular manufacturing systems; Computers & Industrial Engineering 39, 125–44.
[20] Papaioannou G., Wilson J.M. (2010), The evolution of cell formation problem methodologies based on recent studies (1997–2008): Review and directions for future research; European Journal of Operational Research 206(3); 509-521.
[21] Ronald B.H. (1997), Forming minimum-cost machine cells with exceptional parts using zero-one integer programming; Journal of Manufacturing Systems 16(2); 79-90.
[22] Safaei N., Saidi-Mehrabad M., Jabal-Ameli M.S. (2008), A hybrid simulated annealing for solving an extended model of dynamic cellular manufacturing system; European Journal of Operation Research 185; 563–592.
[23] Selim H.M., Askin R.G., Vakharia A.J. (1998), Cell formation in group technology: review, evaluation and directions for future research; Computers and Industrial Engineering 34; 3–20.
[24] Singh N. (1993), Design of cellular manufacturing systems: an invited review; European Journal of Operational Research 69; 284–291.
[25] Singh N., Rajamani D. (1996), Cellular manufacturing systems design, planning and control; Chapman and Hall Publishing; London, UK.
[26] Sofianopoulou S. (1997), Application of simulated annealing to a linear model for the formation of machine cells in group technology; International Journal of Production Research 35, 501–511.
[27] Soleymanpour M., Vrat P., Shanker R. (2002), A transiently chaotic neural network approach to the design of cellular manufacturing; International Journal of Production Research 40(10), 2225-2244.
[28] Wemmerlov U., Hyer N.L. (1989), Cellular manufacturing in the US industry: a survey of users; International Journal of Production Research 27(9); 1511–1530.
[29] Wemmerlov U., Johnson D.J. (1997), Cellular manufacturing at 46 user plants: implementation experiences and performance improvements; International Journal of Production Research 35(1); 29–49.
[30] Wu T., Low C., Wu W. (2004), A tabu search approach to the cell formation problem; International Journal ofAdvanced Manufacturing Technology 23; 916–924.
[31] Wu T.H., Chang C.C., Chung S.H. (2008), A simulated annealing algorithm for manufacturing cell formation problems; Expert Systems with Applications 34; 1609–1617.
[32] Yin Y., Yasuda K. (2006), Similarity coefficient methods applied to the cell formation problem: A taxonomy and review; International Journal of Production Economics 101; 329-352.