Worst-case analysis of an algorithm for cellular manufacturing. (English) Zbl 0783.90044
Summary: Two measures for the efficiency of grouping in cellular manufacturing are discussed in this paper. We first analyze the effectiveness of the first measure, grouping efficiency. A worst case bound is then derived for the minimum spanning tree algorithm with respect to this measure. We then show a newly proposed measure, grouping efficacy, is not suitable from an algorithmic point of view. A weighted grouping efficacy is then proposed and worst case bounds are derived with respect to this new measure. We also propose several policies to improve grouping efficiency and grouping efficacy during the decomposition of larger machine cells. Computational results will also be presented to demonstrate the effectiveness of these measures and the worst case bounds.
MSC:
| 90B30 | Production models |
| 90-08 | Computational methods for problems pertaining to operations research and mathematical programming |
Keywords:
cluster analysis; heuristics; efficiency of grouping; cellular manufacturing; worst case boundReferences:
| [1] | Askin, R. G.; Cresswell, S. H.; Goldberg, J. B.; Vakharia, A. J., A Hamiltonian path approach to reordering the part-machine matrix for cellular manufacturing, International Journal of Production Research, 29, 6, 1081-1100 (1991) |
| [2] | Burbidge, J. L., An introduction of group technology, (Proceedings of Seminar on Group Technology. Proceedings of Seminar on Group Technology, Turin (1969)) |
| [3] | Burbidge, J. L., The Introduction of Group Technology (1975), Heinemann: Heinemann London |
| [4] | Carrie, A. S., Numerical taxonomy applied to group technology and plant layout, International Journal of Production Research, 11, 4, 399-416 (1973) |
| [5] | Chan, H. M.; Milner, D. A., Direct clustering for group formation in cellular manufacture, Journal of Manufacturing Systems, 1, 65-74 (1982) |
| [6] | Chandrasekharan, M. P.; Rajagopalan, R., An ideal seed non-hierarchical clustering algorithm for cellular manufacturing, International Journal of Production Research, 24, 2, 451-464 (1986) · Zbl 0582.90050 |
| [7] | Chandrasekharan, M. P.; Rajagopalan, R., MODROC: An extension of order rank clustering for group technology, International Journal of Production Research, 24, 5, 1221-1233 (1986) |
| [8] | Chandrasekharan, M. P.; Rajagopalan, R., ZODIAC - An algorithm for concurrent formation of part-families and machine-cells, International Journal of Production Research, 25, 6, 835-850 (1987) · Zbl 0623.90030 |
| [9] | Chandrasekharan, M. P.; Rajagopalan, R., Groupability: An analysis of the properties of binary data matrices for group technology, International Journal of Production Research, 27, 6, 1035-1052 (1989) |
| [10] | Kumar, C. S.; Chandrasekharan, M. P., Grouping efficacy: A quantitative criterion for goodness of block diagonal forms of binary matrices in group technology, International Journal of Production Research, 28, 2, 233-243 (1990) |
| [11] | Kumar, K. R.; Kusiak, A.; Vannelli, A., Grouping of parts and components in flexible manufacturing systems, European Journal of Operational Research, 24, 387-397 (1986) · Zbl 0599.90048 |
| [12] | Kusiak, A., Intelligent Manufacturing Systems (1990), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0691.90035 |
| [13] | Ng, S. M., Characterizing the independent cells in group technology, (Working Paper 1989-18. Working Paper 1989-18, Operations Research (1989), Department of Industrial and Systems Engineering, University of Southern California: Department of Industrial and Systems Engineering, University of Southern California Los Angeles, CA), Submitted to |
| [14] | Ng, S. M., Bond energy, rectilinear distance and a worst case bound for the group technology problem, Journal of the Operational Research Society, 42, 7, 571-578 (1991) |
| [15] | Panneerselvam, R.; Balasubtanmanian, K. N., Algorithm grouping of operations sequences, Engineering Costs and Production Economics, 9, 125-135 (1985) |
| [16] | Seifoddini, H.; Wolfe, P. M., Application of similarity coefficient method in group technology, IIE Transactions, 18, 271-277 (1986) |
| [17] | Srinivasan, G.; Narendran, T. T.; Mahadevan, B., An assignment model for the part-families problem in group technology, International Journal of Production Research, 28, 145-152 (1990) |
| [18] | Wemmerloöv, U.; Hyer, N. L., Cellular manufacturing in the US industry: A survey of users, International Journal of Production Research, 27, 9, 1511-1530 (1989) |
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.
