A tabu search algorithm for the cell formation problem with part machine sequencing

• Autorzy: Papaioannou G. , Wilson J. M.
• Języki publikacji: EN

Abstrakty

EN

This paper presents extensions of the IP model where part-machine assignment and cell formation are addressed simultaneously and part machine utilisation is considered. More specifically, an integration of inter-cell movements of parts and machine set-up costs within the objective function, and also a combination of machine set-up costs associated with parts revisiting a cell when the part machine operation sequence is taken into account are examined and an enhanced model is formulated. Based upon this model’s requirements, an initial three stage approach is proposed and a tabu search iterative procedure is designed to produce a solution. The initial approach consists of the allocation of machines to cells, the allocation of parts to machines in cells and the evaluation of the objective function’s value. Special care has been taken when allocating parts to machine cells as part machine operation sequence is preserved making the system more complex but more realistic. The proposed tabu search algorithm integrates short term memory and an overall iterative searching strategy where two move types, single and exchange, are considered. Computational experiments verified both the algorithm’s robustness where promising solutions in reasonably short computational effort are produced and also the algorithm’s effectiveness for large scale data sets.

Słowa kluczowe

EN

cell formation; mixed integer linear programming; part machine operation sequence

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2012
• Tom: Vol. 37, No. 2
• Strony: 97--127
• Opis fizyczny: Bibliogr. 54 poz.

Twórcy

autor

Papaioannou G.

• School of Business & Economics, Loughborough University, Loughborough, LE11 3TU, UK

autor

Wilson J. M.

• School of Business & Economics, Loughborough University, Loughborough, LE11 3TU, UK
• School of Management & Business, Aberystwyth University, Aberystwyth, SY23 3DD

Bibliografia

• [1] Adil, G.K., Rajamani, D. and Strong, D. (1997). Assignment allocation and simulated annealing algorithms for cell formation, IIE Transactions, 29 (11), 53-67.
• [2] Ahkioon, S., Bulgak, A.A. and Bektas, T. (2007). Cellular manufacturing systems design with routing flexibility, machine procurement production planning, and dynamic system reconfiguration, International Journal of Production Research, iFirst, 1-28.
• [3] Askin, R.G., Goldberg, J.B., Cresswell, S.H. and Strong, D. (1991). A Hamiltonian path approach to reordering the part-machine matrix for cellular manufacturing, International Journal of Production Research, 29 (6), 1081-1100.
• [4] Askin, R.G., Selim, H.M. and Vakharia, A.J. (1997). A methodology for designing flexible cellular manufacturing systems, IIE Transactions, 29, 599-610.
• [5] Beaulieu, A., Gharbi, A. and Ait-Kadi. (1997). An algorithm for the cell formation and machine selection problems in the design of a cellular manufacturing system, International Journal of Production Research, 35 (7), 1857-1875.
• [6] Boe, W.J. and Cheng, G.H. (1991). A close neighbour algorithm for designing cellular manufacturing systems, International Journal of Production Research, 29 (10), 2097-2116.
• [7] Burbidge, J.L. (1989). Production flow analysis for planning group technology, UK, Oxford Science Publications.
• [8] Chandrasekharan, M.P. and Ragagopalan, R. (1986). An ideal-seed nonhierarchical clustering algorithm for cellular manufacturing, International Journalof Production Research, 24 (2), 451-464.
• [9] Chan, W.M., Chan, C.Y. and Ip, W.H. (2003). A heuristic algorithm for machine assignment in cellular layout, Computers and Industrial Engineering , 44, 49-73.
• [10] Chan, H.M. and Milner, D.A. (1982). Direct clustering algorithm for group formation in cellular manufacturing, Journal of Manufacturing Systems, 1 (1), 65-75.
• [11] Congawave, T. and Ham, I. (1981). Cluster analysis applications for group technology manufacturing systems, Proceedings, North American Manufacturing ResearchConference (NAMRC), 9T H (Dearborn), 65-75.
• [12] De Witte, J. (1980). The use of similarity coefficients in production flow analysis, International Journal of Production Research, 18 (4), 503-514.
• [13] Dorigo, M., Maniezzo, V. and Colorni, A. (1996). Ant system: Optimisation by a colony of cooperating agents, IEEE Transactions on Systems, Man andCybernetics - Part B Cybernetics, 26, 29-41.
• [14] Foulds, L.R., French, A.P. and Wilson, J.M. (2006). The sustainable cell formation problem: manufacturing cell creation with machine modification costs, Computers and Operations Research, 33, 1010-1032.
• [15] Garey, M.R. and Johnson, D.S. (1979). Computers and Intractability, San Fransisco, CA: Freeman.
• [16] Glover, F. (1986). Future paths for integer programming and links to artificial intelligence, Computers and Operations Research, 13, 533-549.
• [17] Glover, F. (1989). Tabu Search - Part I, ORSA Journal on Computing , 1 (3), 190-206.
• [18] Glover, F. (1990). Tabu Search - Part II, ORSA Journal on Computing , 2 (1), 4-32.
• [19] Glover, F. and Laguna, M. (1997). Tabu Search, Norwell, MA: Kluwer Academic.
• [20] Holland, J.H. (1975). Adaptation in Natural and Artificial Systems, Ann Arbor, University of Michigan, Michigan.
• [21] Jayaswal, S. and Adil, G.K. (2004). Efficient algorithm for cell formation with sequence data, machine replications and alternative process routings, InternationalJournal of Production Research, 42 (12), 2419-2433.
• [22] Kim, C.O, Baek, J.G. and Baek, J.K. (2004). A hybrid grouping genetic algorithm for the cell formation problem, Computers and Operations Research, 34, 2059-2079.
• [23] Kim, C.O, Baek, J.G. and Baek, J.K. (2004). A two-phase heuristic algorithm for cell formation problems considering alternative part routes and machine sequences, International Journal of Production Research, 18, 3911-3927.
• [24] King, J.R. (1980). Machine-component grouping in production flow analysis: an approach using rank order clustering algorithm, International Journal of Production Research, 18 (2), 213-232.
• [25] King, J.R. and Nakornchai, V. (1982). Machine-component group formation in group technology: review and extension, International Journal of Production Research, 20 (2), 117-133.
• [26] Kirkpatrick, S., Gelatt Jr., C.D. and Vecchi, M.P. (1983). Optimisation by simulated annealing, Science, 220, 671-680.
• [27] Kumar, K.R., Kusiak, A. and Vannelli, A. (1986). Grouping of parts and components in flexible manufacturing systems, European Journal of Operational Research, 24, 387-397.
• [28] Kusiak, A. (1987). The generalized group technology concept, International Journal of Production Research, 25, 561-569.
• [29] Kusiak, A. and Heragu. S.S. (1987). Group Technology, Computers in Industry , 9, 83-91.
• [30] Mak, K.L. and Wong, Y.S. and Wang, X.X. (2000). An adaptive genetic algorithm for manufacturing cell formation, International Journal of Advanced Manufacturing Technology , 16, 491-497.
• [31] McCormick, W.T., Schweitzer, P.J. and White, T.W. (1972). Problem Decomposition and data reorganisation by a clustering technique, Operations Research, 20, 993-1009.
• [32] Mukattash, A.M., Adil, M.B. and Tahboub, K.K. (2002). Heuristic approaches for part assignment in cell formation, Computers and Industrial Engineering , 42, 329-341.
• [33] Onwubolu, G.C. and Mutingi, M. (2001). A genetic algorithm approach to cellular manufacturing systems, Computers & Industrial Engineering , 69, 373-383.
• [34] 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.
• [35] Purcheck, G.F. (1975). Programming method for combinatorial group of an incomplete power set, Journal of Cybernetics, 5, 51-76.
• [36] Sankaran, S. (1990). Multiple objective decision making approach to cell formation - A goal programming model, International Journal of Production Research, 13, 71-81.
• [37] Sankaran, S. and Kasilingam, R.G. (1993). On cell size and machine requirements planning in group technology systems, European Journal of Operational Research, 69, 373-383.
• [38] Selim, M.S., Askin, R.G. and Vakharia, A.J. (1998). Cell Formation in Group Technology: Review Evaluation and Directions for Future Research, Computersand Industrial Engineering , 34, 3-20.
• [39] Singh, N. (1993). Design of Cellular Manufacturing Systems: An Invited Review, European Journal of Operational Research, 69, 284-291.
• [40] Solimanpur, M. and Vrat, P. and Shankar, R. (2004). Ant colony optimisation algorithm to the inter-cell layout problem in cellular manufacturing, European Journal of Operational Research, 157, 592-606.
• [41] Spiliopoulos, K. and Sofianopoulou, S. (2003). Designing manufacturing cells: a staged approach and a tabu search algorithm, International Journal of Production Research, 41 (11), 2531-2546.
• [42] Stanfel, L.E. (1985). Machine clustering for economic production, Engineering Costs and Production Economics , 9, 73-81.
• [43] Vakharia, A.J. and Chang, Y.-L. (1997). Cell formation in group technology: a combinatorial search approach, International Journal of Production Research, 35 (7), 2025-2043.
• [44] Vakharia, A.J. and Wemmerlov, U. (1990). Designing a cellular manufacturing system: a materials flow approach based on operation sequences, IIE Transactions, 22 (1), 84-97.
• [45] Vannelli, A. and Kumar, K.R. (1986). A method for finding minimal bottle-neck cells for grouping part-machine families, International Journal of Production Research, 24 (2), 387-400.
• [46] Venugopal, V. and Narendran, T.T. (1992). A genetic algorithm approach to the machine-component grouping problem with multiple objectives, Computers and Industrial Engineering , 22 (4), 469-480.
• [47] Wang, J. (1998). A linear assignment algorithm for formation of machine cells and part families in cellular manufacturing, Computers and Industrial Engineering ,35, 81-84.
• [48] Wei, J.C. and Gaither, N. (1992). An optimal model for cell formation decisions, Decision Sciences, 21, 416-433.
• [49] Wemmerlov, U. and Hyer, N.L. (1986). Procedures for the Part/Machine Group Identification Problem in Cellular Manufacturing, Journal of Operations Management , 6, 125-147.
• [50] Wemmerlov, U. and Hyer, N.L. (1986). Cell Manufacturing in the US Industry: A Survey of Users, International Journal of Production Research, 27, 1511-1530.
• [51] Wu, T.-H., Low, C. and Wu, W.-T. (2004). A tabu search approch to the cell formation problem, International Journal of Advanced Manufacturing Technology , 23, 916-924.
• [52] Xambre, A.R. and Vilarinho, P.M. (2003). A simulated annealing approach for manufacturing cell formation with multiple identical machines, European Journal of Operational Research, 151 (3), 434-446.
• [53] Xpress-MP. Dash Optimisation, Blisworth, Northamptonshire, UK.
• [54] Zhu, Z., Heady, R.B. and Reiners, S. (1995). An efficient zero-one formulation of the cell formation problem, Computers and Industrial Engineering , 28, 911-916.