×

An improved simulated annealing simulation optimization method for discrete parameter stochastic systems. (English) Zbl 1073.90026

Summary: This paper proposes a new heuristic algorithm for the optimization of a performance measure of a simulation model constrained under a discrete decision space. It is a simulated annealing-based simulation optimization method developed to improve the performance of simulated annealing for discrete variable simulation optimization. This is accomplished by basing portions of the search procedure on inferred statistical knowledge of the system instead of using a strict random search. The proposed method is an asynchronous team-type heuristic that adapts techniques from response surface methodology and simulated annealing.
Testing of this method is performed on a detailed simulation model of a semi-conductor manufacturing process consisting of over 40 work-stations with a cost minimization objective. The proposed method is able to obtain superior or equivalent solutions to an established simulated annealing method during each run of the testing experiment.

MSC:

90C15 Stochastic programming
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Goldsman, D.; Nelson, B., Ranking, selection and multiple comparisons in computer simulation, (Sadowski, D.; Seila, A.; Tew, J.; Manivannan, S., Proceedings of the 1994 Winter Simulation Conference (1994), Institute of Electrical and Electronics Engineers: Institute of Electrical and Electronics Engineers Piscataway, NJ), 192-199
[2] Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P., Optimization by simulated annealing, Science, 220, 671-680 (1983) · Zbl 1225.90162
[3] Bulgak, A.; Sanders, J., Integrating a modified simulated annealing algorithm with the simulation of a manufacturing system to optimize buffer sizes in automatic assembly systems, (Haigh, P.; Comfort, J.; Abrams, M., Proceedings of the 1988 Winter Simulation Conference (1988), Institute of Electrical and Electronics Engineers: Institute of Electrical and Electronics Engineers Piscataway, NJ), 684-690
[4] Haddock, J.; Mittenthal, J., Simulation optimization using simulated annealing, Computers and Industrial Engineering, 22, 387-395 (1992)
[5] So D, Dowsland K. Simulated annealing: an application to simulation optimization. Proceedings of the OR35 Conference, 1993.; So D, Dowsland K. Simulated annealing: an application to simulation optimization. Proceedings of the OR35 Conference, 1993.
[6] Ahmed, M.; Alkhamis, T.; Hasan, T., Optimizing discrete stochastic systems using simulated annealing and simulation, Computers and Industrial Engineering, 32, 823-846 (1997)
[7] Alkhamis, T.; Ahmed, M.; Tuan, V., Simulated annealing for discrete optimization with estimation, European Journal of Operational Research, 116, 530-544 (1999) · Zbl 1009.90076
[8] Alrefaei, M.; Andradottir, S., A simulated annealing algorithm with constant temperature for discrete stochastic optimization, Management Science, 45, 748-764 (1999) · Zbl 1231.90315
[9] Ahmed, M.; Alkhamis, T., Simulation-based optimization using simulated annealing with ranking and selection, Computers and Operations Research, 29, 387-402 (2002) · Zbl 0994.90102
[10] Box, G.; Wilson, K., On the experimental attainment of optimal conditions, Journal of the Royal Statistical Society, B13, 1-45 (1951) · Zbl 0043.34402
[11] Hood, S.; Welch, D., Response surface methodology and its application in simulation, (Russel, E.; Biles, W.; Evans, G.; Mollaghasemi, M., Proceedings of the 1993 Winter Simulation Conference (1993), Institute of Electrical and Electronics Engineers: Institute of Electrical and Electronics Engineers Piscataway, NJ), 115-122
[12] Parthasarathy, S.; Rajendran, C., A simulated annealing heuristic for scheduling to minimize mean weighted tardiness in a flowshop with sequence-dependent setup times of jobs a case study, Production Planning and Control, 8, 475-483 (1997)
[13] Harmonosky, C.; Miller, J.; Rosen, S.; Traband, M.; Tillotson, R.; Robbie, D., Interfacing simulation with costing software to drive the transformation from prototype manufacturing to high volume manufacturing, (Sturrock, D.; Evans, G.; Farrington, P.; Nemhard, H., Proceedings of the 1999 Winter Simulation Conference (1999), Institute of Electrical and Electronics Engineers: Institute of Electrical and Electronics Engineers Piscataway, NJ), 1359-1364
[14] Hajek, B., Cooling schedules for optimal annealing, Mathematics of Operations Research, 13, 311-329 (1988) · Zbl 0652.65050
[15] Sasaki, G.; Hajek, B., The time complexity of maximum matching by simulated annealing, Journal of the Association of Computing Machinery, 35, 387-403 (1988) · Zbl 0825.68416
[16] Johnson, D.; Aragon, C.; McGeoch, L.; Schevon, C., Optimization by simulated annealingan experimental evaluation; Part I, Graph partitioning, Operations Research, 6, 865-892 (1989) · Zbl 0698.90065
[17] Rosen, S. A new simulation optimization approach for discrete parameter stochastic systems. MS Thesis, The Pennsylvania State University, USA, 2000.; Rosen, S. A new simulation optimization approach for discrete parameter stochastic systems. MS Thesis, The Pennsylvania State University, USA, 2000.
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.