×

A graph theory approach to subcontracting, machine duplication and intercell moves in cellular manufacturing. (English) Zbl 0804.90066

Summary: We address in this paper the problem of finding an optimal strategy for dealing with bottleneck machines and bottleneck parts in the cell formation process in group technology. Three types of economic decisions are considered: subcontracting, machine duplication and intercell moves. The problem is formulated as a minimum weighted node covering problem in a hypergraph, and we show that it can be solved in polynomial time by finding a maximum weighted stable set in a bipartite graph. We extend this result to cellular manufacturing systems in which the sequence of operations of each part is known in advance.

MSC:

90B30 Production models
90C35 Programming involving graphs or networks
05C65 Hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baker, K. R., Introduction to Sequencing and Scheduling (1974), Wiley: Wiley New York
[2] Berge, C., Graphes (1983), Gauthier-Villars: Gauthier-Villars Paris · Zbl 0213.25702
[3] Berge, C., Hypergraphes—Combinatoire des Ensembles Finis (1987), Gauthier-Villars: Gauthier-Villars Paris · Zbl 0623.05001
[4] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman New York · Zbl 0411.68039
[5] A. Hertz, B. Jaumard and C.C. Ribeiro, A multi-criteria tabu search approach to cell formation problems in group technology with multiple objectives, RAIRO Rech. Opér., to appear.; A. Hertz, B. Jaumard and C.C. Ribeiro, A multi-criteria tabu search approach to cell formation problems in group technology with multiple objectives, RAIRO Rech. Opér., to appear. · Zbl 0830.90065
[6] Hopcroft, J. E.; Karp, R. M., An \(n^{52}\) algorithm for maximum matching in bipartite graphs, SIAM J. Comput., 2, 225-231 (1973) · Zbl 0266.05114
[7] Karzanov, A. V., Determining the maximal flow in a network by the method of preflows, Soviet Math. Dokl., 15, 434-437 (1974) · Zbl 0303.90014
[8] King, J. R.; Nakornchai, V., Machine-component group formation in group technology: review and extension, Internat. J. Prod. Res., 20, 117-133 (1982)
[9] Koenig, D., Graphen und Matrizen, Mat. Fiz. Lapok, 38, 116-119 (1931)
[10] Kumar, K. R.; Vannelli, A., Strategic subcontracting for efficient disaggregated manufacturing, Internat. J. Prod. Res., 25, 1715-1728 (1983)
[11] Kusiak, A.; Heragu, S. S., Group technology, Comput. Indust., 9, 83-91 (1987)
[12] Logendran, R., A workload based model for minimizing total intercell and intracell moves in cellular manufacturing, Internat. J. Prod. Res., 28, 913-925 (1990)
[13] Logendran, R., A model for duplicating bottleneck machines in the presence of budgetary limitations in cellular manufacturing, Internat. J. Prod. Res., 30, 683-694 (1992)
[14] Malhotra, V. M.; Kumar, M. P.; Maheshwari, S. N., An \(O (|V|^3)\) algorithm for finding maximum flows in networks, Inform. Process. Lett., 7, 277-278 (1978) · Zbl 0391.90041
[15] Miscimara, P. A., The NLRB and Managerial Discretion: Plant Closings, Relocations, Subcontracting, and Automation (1983), University of Pennsylvania: University of Pennsylvania Philadelphia
[16] Rajagopalan, R.; Batra, J. L., Design of cellular production systems: a graph-theoretic approach, Internat. J. Prod. Res., 13, 567-579 (1982)
[17] Seifoddini, H., Duplication process in machine cells formation in group technology, IIE Trans., 21, 382-388 (1989)
[18] Seifoddini, H.; Wolfe, P. M., Application of the similarity coefficient method in group technology, IIE Trans., 18, 271-277 (1986)
[19] Vakharia, A. J.; Chang, Y.-L., A simulated annealing approach to scheduling a manufacturing cell, Naval Res. Logist. Quart., 37, 559-577 (1990) · Zbl 0701.90049
[20] Vannelli, A.; Kumar, K. R., A method for finding minimal bottle-neck cells for grouping part-machine families, Internat. J. Prod. Res., 24, 387-400 (1986) · Zbl 0583.90045
[21] Vannelli, A.; Kumar, K. R., Minimal bottleneck cell approach for generating part-machines families in cellular manufacturing, (Turkara, I. B., Computer Integrated Manufacturing (1988), Springer: Springer Berlin)
[22] Wei, J. C.; Gaither, N., A capacity constrained multiobjective cell formation method, J. Manuf. Systems, 9, 222-232 (1990)
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.