Manufacturing cell formation by state-space search. (English) Zbl 0857.90053
Summary: This paper addresses the problem of grouping machines in order to design cellular manufacturing cells, with an objective to minimize inter-cell flow. This problem is related to one of the major aims of group technology (GT): to decompose the manufacturing system into manufacturing cells that are as independent as possible. This problem is NP-hard. Thus, nonheuristic methods cannot address problems of typical industrial dimensions because they would require exorbitant amounts of computing time, while fast heuristic methods may suffer from poor solution quality. We present a branch-and-bound state-space search algorithm that attempts to overcome both these deficiencies. One of the major strengths of this algorithm is its efficient branching and search strategy. In addition, the algorithm employs the fast inter-cell traffic minimization method to provide good upper bounds, and computes lower bounds based on a relaxation of merging.
MSC:
| 90B30 | Production models |
Keywords:
machine grouping; design cellular manufactoring; branch-and-bound state-space search algorithmReferences:
| [1] | R.H. Ahmadi and C.S. Tang, An operation partitioning problem for automated assembly system design, Operations Research 39, 1991, 824–835. · Zbl 0729.91005 · doi:10.1287/opre.39.5.824 |
| [2] | R. Askin and S.B. Subramanian, A cost-based heuristic for group technology configuration, International Journal of Production 25, 1987, 101–113. · doi:10.1080/00207548708919825 |
| [3] | R. Askin, S.H. Cresswell, J.B. Goldberg and A. Vakharia, A Hamiltonian path approach to reordering the part-machine matrix for cellular manufacturing, International Journal of Production Research 29, 1991, 1081–1100. · doi:10.1080/00207549108930121 |
| [4] | A.S. Carrie, Numerical taxonomy applied to group technology and plant layout, International Journal of Production Research 11, 1973, 399–416. · doi:10.1080/00207547308929988 |
| [5] | H.M. Chan and D.A. Milner, Direct clustering algorithm for group formation in cellular manufacturing, Journal of Manufacturing Systems 1, 1982, 65–74. · doi:10.1016/S0278-6125(82)80068-X |
| [6] | M.P. Chandrasekharan and R. Rajagopalan, ZODIAC – an algorithm for concurrent formation of part-families and machine-cells, International Journal of Production Research 25, 1987, 835–850. · Zbl 0623.90030 · doi:10.1080/00207548708919880 |
| [7] | C.Y. Chen and S. Irani, Cluster first-sequence last heuristics for generating block diagonal forms for a machine-part matrix, International Journal of Production Research 31, 1993, 2623–2647. · doi:10.1080/00207549308956887 |
| [8] | F. Choobineh, A framework for the design of cellular manufacturing systems, International Journal of Production Research 26, 1988, 1161–1172. · doi:10.1080/00207548808947932 |
| [9] | B.B. Flynn and F. R. Jacobs, A simulation comparison of group technology with traditional job shop manufacturing, International Journal of Production Research 24, 1986, 1171–1192. · doi:10.1080/00207548608919795 |
| [10] | C.C. Gallagher and W.A. Knight,Group Technology Production Methods in Manufacture, Ellis-Horwood, 1986. |
| [11] | H. Garcia and J.M. Proth, Group technology in production management: the short horizon planning level, Applied Stochastic Models and Data Analysis 1, 1985, 25–34. · Zbl 0583.90044 · doi:10.1002/asm.3150010105 |
| [12] | H. Garcia and J.M. Proth, A new cross-decomposition algorithm: the gpm. comparison with the bond energy method, Control and Cybernetics 15, 1986, 155–164. · Zbl 0611.90063 |
| [13] | M.R. Garey and D.S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, New York, 1979. · Zbl 0411.68039 |
| [14] | I. Ham, K. Hitomi and T. Yoshida,Group Technology – Applications to Production Management, Kluwer-Nijhoff, 1985. · Zbl 1179.90108 |
| [15] | G. Harhalakis, R. Nagi and J. M. Proth, An efficient heuristic in manufacturing cell formation for group technology applications, International Journal of Production Research 28, 1990, 185–198. · doi:10.1080/00207549008942692 |
| [16] | G. Harhalakis, J.M. Proth and X.L. Xie, Manufacturing cell design using simulated annealing, Journal of Intelligent Manufacturing 1, 1990, 185–191. · doi:10.1007/BF01572637 |
| [17] | G. Harhalakis, T. Lu, I. Minis and R. Nagi, A practical method for hybrid-type production facilities, accepted in International Journal of Production Research (1995). · Zbl 0946.90546 |
| [18] | E. Horowitz and S. Sahni,Fundamentals of Computer Algorithms, Computer Science Press, Potomac, MD, 1978. · Zbl 0442.68022 |
| [19] | S.S. Heragu and Y.P. Gupta, A heuristic for designing cellular manufacturing facilities, International Journal of Production Research 32, 1994, 125–140. · Zbl 0905.90097 · doi:10.1080/00207549408956920 |
| [20] | S.A. Irani, P.H. Cohen and T.M. Cavalier, Design of cellular manufacturing systems, ASME Transactions of Engineering for Industry 114, 1992, 352–361. |
| [21] | S.K. Khator and S.A. Irani, Cell-formation in group technology: A new approach, Computers and Industrial Engineering 12, 1987, 561–569. · doi:10.1016/0360-8352(87)90006-4 |
| [22] | J.R. King, Machine-component grouping formation in group technology, OMEGA: The International Journal of Management Science 8, 1979, 193–199. · doi:10.1016/0305-0483(80)90023-7 |
| [23] | J.R. King, Machine-component grouping in production flow: An approach using rank order clustering, International Journal of Production Research 18, 1980, 213–232. · doi:10.1080/00207548008919662 |
| [24] | A. Kusiak and W.S. Chow, Efficient solving of the group technology problem, Journal of Manufacturing Systems 6, 1987, 117–124. · doi:10.1016/0278-6125(87)90035-5 |
| [25] | A. Kusiak and S.S. Heragu, Group technology, Computers in Industry 9, 1987, 83–91. · doi:10.1016/0166-3615(87)90002-9 |
| [26] | A. Kusiak and W.S. Chow, Decomposition of manufacturing systems, IEEE Journal of Robotics and Automation 4, 1988, 457–471. · doi:10.1109/56.20430 |
| [27] | Z. Leskowsky, L. Logan and A. Vannelli, Group technology decision aids in an expert system for plant layout,Modern Production Management Systems, Elsevier Science, 1987. |
| [28] | R. Logendran, P. Ramakrishna and C. Sriskandarajah, Tabu search-based heuristics for cellular manufacturing systems in the presence of alternative process plans, International Journal of Production Research 32, 1994, 273–297. · Zbl 0911.90187 · doi:10.1080/00207549408956933 |
| [29] | A. Mahanti, S. Ghosh and A.K. Pal, A high performance limited-memory admissible and real time search algorithm for networks, Technical Report, CS-TR-92-34. Department of Computer Science, University of Maryland, 1992. |
| [30] | J. McAuley, Machine grouping for efficient production, The Production Engineer 51, 1972, 53–57. · doi:10.1049/tpe.1972.0006 |
| [31] | W.T. McCormick, P.J. Schweitzer and T.E. White, Problem decomposition and data re-organization by a clustering technique, Operations Research 20, 1972, 993–1009. · Zbl 0249.90046 · doi:10.1287/opre.20.5.993 |
| [32] | I. Minis, G. Harhalakis and S. Jajodia, Manufacturing cell formation with multiple, functionally identical machines, Manufacturing Review 3, 1990, 252–261. |
| [33] | R. Nagi, G. Harhalakis and J.M. Proth, Multiple routings and capacity considerations in group technology applications, International Journal of Production Research 28, 1990, 2243–2257. · doi:10.1080/00207549008942864 |
| [34] | O.G. Okogbaa, M.T. Chen, C. Changchit and R.L. Shell, Manufacturing system cell formation and evaluation using a new inter-cell flow reduction heuristic, International Journal of Production Research 30, 1992, 1101–1118. · doi:10.1080/00207549208942945 |
| [35] | J. Pearl, Heuristics,Intelligent Search Strategies for Computer Problem Soving, Addison-Wesley, 1984. |
| [36] | K.R. Gunasingh and R.S. Lashkar, Machine grouping problem in cellular manufacturing systems – an integer programming approach, International Journal of Production Research 27, 1989, 1465–1473. · doi:10.1080/00207548908942634 |
| [37] | H. Seifoddini and P.M. Wolfe, Application of the similarity coefficient method in group technology, IIE Transactions 18, 1986, 271–277. · doi:10.1080/07408178608974704 |
| [38] | S. Song and K. Hitomi, GT cell formation for minimizing the intercell parts flow, International Journal of Production Research 30, 1992, 2737–2753. · doi:10.1080/00207549208948188 |
| [39] | M.T. Tabucanon and R. Ojha, ICRMA – a heuristic approach for intercell flow reduction in cellular manufacturing systems, Material Flow 4, 1987, 189–197. |
| [40] | A.J. Vakharia and U. Wemmerlöv, Designing a cellular manufacturing system: A material flow approach based on operation sequences, IIE Transactions 22, 1990, 84–97. · doi:10.1080/07408179008964161 |
| [41] | T. Vohra, D.S. Chen, J.C. Chang and H.C. Chen, A network approach to cell formation in cellular manufacturing, International Journal of Production Research 28, 1990, 2075–2084. · doi:10.1080/00207549008942854 |
| [42] | U. Wemmerlöv and N.L. Hyder, Procedures for the part family/machine group identification problem in cellular manufacturing, Journal of Operations Management 6, 1986, 125–148. · doi:10.1016/0272-6963(86)90021-5 |
| [43] | U. Wemmerlöv and N.L. Hyder, Cellular manufacturing in the U.S. industry: A survey of user, International Journal of Production Research 27, 1989, 1511–1530. · doi:10.1080/00207548908942637 |
| [44] | P.C.T. Willey and B.G. Dale, Manufacturing characteristics and management performance of companies under group technology,Proceedings of the 18th International Machine Tool Design and Research Conference, 1977, p. 777. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
