A simulated annealing approach to scheduling a manufacturing cell. (English) Zbl 0701.90049

Summary: This article proposes a new heuristic based on simulated annealing that schedules part families, as well as jobs within each part family, in a flow-line manufacturing cell. The new scheduling approach is compared to a branch and bound algorithm as well as two other family-based scheduling heuristics for different cell configurations. The results reveal that all the heuristics provide comparable solutions to the optimal procedure for small problems. However, when the problem size increases, the simulated annealing heuristic outperforms the other procedures not only in solution quality but also by requiring substantially less computation time.


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


[1] and , ”Simulated Annealing Methods with General Acceptance Probabilities,” Working Paper, Graduate School of Business, Columbia University, New York, 1985.
[2] Introduction to Sequencing and Scheduling, John Wiley and Sons, Inc., New York, 1974.
[3] The Introduction of Group Technology, John Wiley and Sons, Inc., New York, 1975.
[4] Campbell, Management Science 16 pp b630– (1970)
[5] Dannenbring, Management Science 23 pp 1174– (1977)
[6] and , ”Analysis of Simulated Annealing for Optimization,” Proceedings of the 24th Conference on Decision and Control, Ft. Lauderdale, 1985, pp. 779–786.
[7] , and , Group Technology, Kluwer-Nijhoff Publishing, Boston, 1985. · doi:10.1007/978-94-009-4976-8
[8] Hitomi, CIRP Annals 25 pp 419– (1976)
[9] , , and , ”An Experimental Investigation of Group Production Scheduling,” Proceedings of the 4th International Conference on Production Research, Tokyo, 1977, pp. 608–617.
[10] Hyer, Decision Sciences 13 pp 681– (1982) · doi:10.1111/j.1540-5915.1982.tb01899.x
[11] Johnson, Naval Research Logistics Quarterly 1 pp 61– (1954)
[12] , and , ”A Controlled Search Simulated Annealing Method for the General Job Shop Scheduling Problem,” Working Paper No. 03-04-88, Graduate School of Business, The University of Texas at Austin, 1988.
[13] Metropolis, Journal of Chemical Physics 21 pp 1087– (1985)
[14] , and , ”Convergence and Finite-Time Behavior of Simulated Annealing,” Proceedings of the 24th Conference on Decision and Control, Ft. Lauderdale, FL, 1985, pp. 761–767.
[15] and , ”Heuristic Implementation of Group Technology Scheduling,” AIDS Conference Proceedings, Toronto, Canada, 1984.
[16] Mosier, International Journal of Production Research 22 pp 857– (1984)
[17] Nawaz, OMEGA 11 pp 91– (1983)
[18] Park, International Journal of Production Research 22 pp 127– (1984)
[19] Flowline Group Production Planning, Business Publications, London, 1968.
[20] Vaithianathan, Journal of Manufacturing Systems 1 pp 149– (1982)
[21] and , Simulated Annealing: Theory and Applications, D. Reidel, Dordrecht, 1987. · doi:10.1007/978-94-015-7744-1
[22] and , ”Job and Family Scheduling of a Flow-Line Manufacturing Cell: A Simulation Study,” IIE Transactions, to be published.
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.