×

A new branch and bound-enhanced genetic algorithm for the manufacturing cell formation problem. (English) Zbl 1086.90057

Summary: This paper deals with the manufacturing cell formation (MCF) problem, which is based on group technology principles, using a graph partitioning formulation. An attempt has been made to take into account the natural constraints of real-life production systems, such as operation sequences, minimum and maximum numbers of cells, and maximum cell sizes. Cohabitation constraints were added to the proposed model in order to deal with the necessity of grouping certain machines in the same cell for technical reasons, and non-cohabitation constraints were included to prevent placing certain machines in close vicinity.
First, the problem is solved with a genetic algorithm (GA), using a binary coding system that has proved superior to the classic integer coding systems. A new Branch-and-Bound (B&B) enhancement is then proposed to improve the GA’s performance. The results obtained for medium-sized instances using this enhancement are better than those obtained using the GA alone. Given these results, it is reasonable to assume that the B&B enhancement will provide good results for large real-life problems.

MSC:

90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C59 Approximation methods and heuristics in mathematical programming
90C35 Programming involving graphs or networks
90B30 Production models
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Souilah A. Les Systèmes cellulaires de production: agencement intracellulaire. Dissertation, University of Metz; 1994.; Souilah A. Les Systèmes cellulaires de production: agencement intracellulaire. Dissertation, University of Metz; 1994.
[2] King, J. R., Machine-component grouping in production flow analysis: an approach using rank order clustering algorithm, International Journal of Production Research, 18, 213-232 (1980)
[3] Kusiak, A.; Chow, W. S., Efficient solving of the group technology problem, Journal of Manufacturing Systems, 6, 117-124 (1987)
[4] McAuley, J., Machine grouping for efficient production, Production Engineer, 52, 53-57 (1972)
[5] Seifoddini, H., Single linkage v/s average linkage clustering in machine cells formation applications, Computers and Industrial Engineering, 16, 419-426 (1989)
[6] Gupta, T.; Seifoddini, H., Production data based similarity coefficient for machine-component grouping decision in the design of a cellular manufacturing system, International Journal of Production Research, 28, 1247-1269 (1990)
[7] Jayakrishnan Nair, G.; Narendran, T. T., CASE: a clustering algorithm for cell formation with sequence data, International Journal of Production Research, 36, 157-179 (1998) · Zbl 0943.90513
[8] Yin Y, Yasuada K. Similarity coefficient methods applied to the cell formation problem: a taxonomy and review. URL, from Internet.; Yin Y, Yasuada K. Similarity coefficient methods applied to the cell formation problem: a taxonomy and review. URL, from Internet.
[9] Logendran, R.; Ramakrishna, P., Manufacturing cell formation in the presence of lot splitting and multiple units of same machine, International Journal of Production Research, 33, 675-693 (1995) · Zbl 0915.90131
[10] Harhalakis, G.; Proth, J.-M.; Xie, X., Manufacturing cell design using simulated annealing, International Journal of Production Research, 1, 185-191 (1990)
[11] Venugopal, V.; Narendran, T. T., Cell formation in manufacturing systems through simulated annealing: an experimental evaluation, European Journal of Operational Research, 63, 409-422 (1992) · Zbl 0766.90034
[12] Chen, C.; Cotruvo, N. A.; Baek, W., A simulated annealing solution for the cell formation problem, International Journal of Production Research, 33, 2601-2614 (1995) · Zbl 0910.90155
[13] Kaparthi, S.; Suresh, N. C., Machine-component cell formation in group technology: a neural network approach, International Journal of Production Research, 30, 6, 1353-1367 (1992) · Zbl 0825.90501
[14] Zolfaghari, OTHS.; Liang, M., An objective guided ortho synapse Hopfield network approach to machine grouping problems, International Journal of Production Research, 35, 10, 2773-2792 (1997) · Zbl 0942.90532
[15] Gupta, Y. P.; Gupta, M. C.; Kumar, A.; Sundram, C., Minimizing total intercell and intracell moves in cellular manufacturing: a genetic algorithm approach, International Journal of Computer Integrated Manufacturing, 8, 2, 92-101 (1995)
[16] AL-Sultan, K. S.; Fedjki, C. A., A genetic algorithm for part family formation problem, Production Planning & Control, 8, 8, 788-796 (1997)
[17] Joines JA, Kay MG, King RE. A hybrid genetic algorithm for manufacturing cell design. Technical Report, Department of Industrial Engineering, North Carolina State University; 1997.; Joines JA, Kay MG, King RE. A hybrid genetic algorithm for manufacturing cell design. Technical Report, Department of Industrial Engineering, North Carolina State University; 1997.
[18] Su, C. T.; Hsu, C. M., Multi-objective machine-part cell formation through parallel simulated annealing, International Journal of Production Research, 36, 8, 2185-2207 (1998) · Zbl 0940.90527
[19] Gonçalves JF, Resende MGC. A hybrid genetic algorithm for manufacturing cell formation. AT&T Labs Research Technical Report TD-5FE6RN; 2002.; Gonçalves JF, Resende MGC. A hybrid genetic algorithm for manufacturing cell formation. AT&T Labs Research Technical Report TD-5FE6RN; 2002.
[20] Vakharia, A. J.; Wemmerlov, U., Designing a cellular manufacturing system: a material flow approach based on operation sequences, IIE Transactions, 22, 1, 84-97 (1990)
[21] Garey, D. L.; Johnson, D. S., Computers and intractability: a guide to the theory of NP-completeness (1979), W.H.Freeman & Co.: W.H.Freeman & Co. San Francisco · Zbl 0411.68039
[22] Boulif M. Composition de cellules flexibles dans les systèmes cellulaires de production statiques et dynamiques. Magister Dissertation, University of Sciences and Technology Houari Boumedienne, No. 03/2000-M/IN, March 2000.; Boulif M. Composition de cellules flexibles dans les systèmes cellulaires de production statiques et dynamiques. Magister Dissertation, University of Sciences and Technology Houari Boumedienne, No. 03/2000-M/IN, March 2000.
[23] Goldberg, D. E., Genetic algorithms in search, optimization and machine learning (1989), Addison-Wesley: Addison-Wesley Reading · Zbl 0721.68056
[24] Holland, J. H., Adaptation in natural and artificial systems (1975), University of Michigan Press: University of Michigan Press Ann Arbor
[25] Murthy, C. V.R.; Srinivasan, G., Fractional cell formation in group technology, International Journal of Production Research, 33, 5, 1323-1337 (1995) · Zbl 0916.90133
[26] Chen, J.; Heragu, S. S., Stepwise decomposition approaches for large scale cell formation problems, European Journal of Operation Research, 113, 64-79 (1999) · Zbl 0933.90020
[27] Papadimitriou, C. H.; Steiglitz, K., Combinatorial optimization: algorithm and complexity (1981), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ
[28] Gondran M, Minoux M. Graphes et algorithmes. Eyrolles; 1979.; Gondran M, Minoux M. Graphes et algorithmes. Eyrolles; 1979. · Zbl 0497.05023
[29] Nagi, R.; Harhalakis, G.; Proth, J.-M., Multiple routeing and capacity considerations in group technology applications, International Journal of Production Research, 28, 12, 2243-2257 (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.