A method for finding minimal bottle-neck cells for grouping part-machine families. (English) Zbl 0583.90045

The selection of parts and machines poses an important problem in the design and planning phases of cellular manufacturing and flexible manufacturing systems. In most real-life situations, this grouping invariably leads to ”bottleneck” parts and machines. This paper discusses a method of identifying the minimal number of bottle-neck cells (machines or parts) which, when dealt with through either duplication of machines or subcontracting of parts, will result in perfect part-machine groupings with no overlap. The polynomially bounded algorithms used in the analysis are oriented towards finding minimal cut-nodes in either partition of the bipartite part-machine graph.


90B30 Production models
90B35 Deterministic scheduling theory in operations research
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI


[1] BARNES E. R., Society for Industrial and Applied Mathematics Journal of Algorithms and Discrete Methods 3 pp 541– (1982)
[2] BASAK P. C., Journal of Institute of Engineers (India)–Mechanical Engineers 61 pp 204– (1981)
[3] BURBIDGE J. L., Third Annual Conference of the Institution of Production Engineers (1973)
[4] BURBIDGE J. L., The Introduction of Group Technology (1975)
[5] DOI: 10.1049/tpe.1977.0129 · doi:10.1049/tpe.1977.0129
[6] CHAKRAVARTY A. K., Proceedings of First Operations Research Society of America/The Institute of Management Sciences Special Interest Conference on Flexible Manufacturing Systems (1984)
[7] HARARY F., Journal of Mathematics and Physics 38 pp 104– (1959)
[8] KING J. R., Fifth International Conference on Production Research pp 40– (1979)
[9] DOI: 10.1080/00207548008919662 · doi:10.1080/00207548008919662
[10] DOI: 10.1080/00207548208947754 · doi:10.1080/00207548208947754
[11] KUSIAK , A. , 1984 , The part families problem in flexible manufacturing systems , Technical University of Nova Scotia , Department of Industrial Engineering. Working Paper 06/84.
[12] LEE J. G., Institute of Electrical and Electronic Engineers Transactions on Supply and Maintenance Command 9 pp 369– (1979)
[13] LEE J. G., Institute of Electrical and Electronic Engineers Transactions on Supply and Maintenance Command 12 pp 410– (1982)
[14] DOI: 10.1109/TPAS.1970.292682 · doi:10.1109/TPAS.1970.292682
[15] DOI: 10.1137/1004088 · Zbl 0112.34602 · doi:10.1137/1004088
[16] STEWARD D. V., Journal of Numerical Analysis 2 pp 345– (1965) · Zbl 0141.13502
[17] VANNELLI A., The Institute of Management Sciences/Operations Research Society of America Meeting (1984)
[18] ZABORSKY J., Institute of Electrical and Electronic Engineers Transactions on Circuits and Systems 29 pp 747– (1982) · Zbl 0504.93009 · doi:10.1109/TCS.1982.1085095
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.