×

Cell formation in manufacturing systems through simulated annealing: An experimental evaluation. (English) Zbl 0766.90034

Summary: Simulated annealing is a general random search method for finding near- global optimal solutions for optimization problems and, in particular, for certain NP-complete problems in combinatorial optimization. This paper presents an algorithm based on simulated annealing to solve the machine-component grouping problem for the design of cells in a manufacturing system. The proposed algorithm has been tested on sample problems and its sensitivity to some of its parameters, investigated. When compared with the \(K\)-means algorithm, the algorithm fares better for large problems. It is also easy to implement.

MSC:

90B30 Production models
90C27 Combinatorial optimization
90-08 Computational methods for problems pertaining to operations research and mathematical programming
90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aarts, E. H.L.; Van Laarhoven, P. J.M., Statistical cooling: Approach to combinatorial optimization problems, Philips Journal of Research, 40/4, 193-226 (1985)
[2] Bonomi, E.; Lutton, J., The \(N\)-city Travelling Salesman Problem: Statistical Mechanics and the Metropolis Algorithm, SIAM Review, 36/4, 551-568 (1984) · Zbl 0551.90095
[3] Burbidge, J. L., Production flow analysis, Production Engineer, 42, 472 (1963)
[4] Burkard, R. E.; Rendl, F., A thermodynamically motivated simulation procedure for combinatorial optimization problems, European Journal of Operational Research, 17, 169-174 (1984) · Zbl 0541.90070
[5] Chan, H. M.; Milner, D. A., Direct clustering algorithm for group formation in cellular manufacture, Journal of Manufacturing Systems, 1/1, 65-75 (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 rank order 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] Debasis Mitra, Fabio Romeo, Convergence and finite-time behaviour of simulated annealing, Advances in Applied Probability, 747-771 (1986) · Zbl 0604.60067
[10] Garey, M.R., and Johnson, D.S., Computers and Intractability: A Guide to Theory of NP-Completeness; Garey, M.R., and Johnson, D.S., Computers and Intractability: A Guide to Theory of NP-Completeness · Zbl 0411.68039
[11] King, J. R., Machine-component grouping in production flow analysis; an approach using a rank order clustering algorithm, International Journal of Production Research, 18/2, 213-232 (1980)
[12] Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P., Optimization by simulated annealing, Science, 220/4598, 671-680 (1983) · Zbl 1225.90162
[13] Lenstra, K., Clustering a data array and the traveling salesman problem, Operations Research, 413-414, 22 (1974) · Zbl 0274.90034
[14] Lundy, M.; Mees, A., Convergence of an annealing algorithm, Mathematical Programming, 111-124, 34 (1986) · Zbl 0581.90061
[15] MacQueen, J. B., Some methods for classification and analysis of multivariate observations, (Proceedings of the Fifth Symposium on Mathematical Statistics and Probability (1967), University of California: University of California Berkeley, CA), 281-297 · Zbl 0214.46201
[16] McCauley, J., Machine grouping for efficient production, Production Engineer, 51/2, 53-57 (1972)
[17] McCormick, W. T.; Schweitzer, P. J.; White, T. W., Problem decomposition and data reorganization by a clustering technique, Operations Research, 20/5, 992-1009 (1972) · Zbl 0249.90046
[18] Ravikumar, K.; 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
[19] Rutenbar, R. A., Simulated Annealing algorithms: An overview, IEEE Circuits and Devices Magazine, 19-26 (January 1989)
[20] Skiscim, C.C., and Golden, B.L., “Optimization by Simulated Annealing: A preliminary computational study for the TSP”, in: Proceedings of the 1983 Winter Simulation Conference; Skiscim, C.C., and Golden, B.L., “Optimization by Simulated Annealing: A preliminary computational study for the TSP”, in: Proceedings of the 1983 Winter Simulation Conference
[21] Van Laarhoven, P. J.M.; Aarts, E. H.L., Simulated Annealing: Theory and Applications (1987), Reidel: Reidel Boston, MA · Zbl 0643.65028
[22] Wilhelm, M. R.; Ward, T. L., Solving Quadratic Assignment Problems by ‘Simulated Annealing’, IIE Transactions, 107-119 (March 1987)
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.