Simulated annealing algorithm applied to a flow-shop problem
DOI:
https://doi.org/10.18041/1794-4953/avances.1.295Keywords:
Combinatorial optimization, Flow-shop problema, Simulated annealingAbstract
In this paper a detailed description of the simulated annealing algorithm is presented. This strategy was employed to solve a well know flow-shop problem, which behavior is featured by the combinatorial explosion and non linear modeling. Therefore, the strategy could be focused to analyze the efficiency of the production in facilities with limited resources. Simulations results performed in a problem in the literature are presented. By this mean, the wide versatility, efficiency, and the easy implementation of the proposed algorithm is verified.
Downloads
References
Toro Ocampo, E. M., Restrepo G., J.S. and Granada E., M.: Algoritmo Genético Modificado Aplicado al Problema de Secuenciamiento de Tareas en Sistemas de Producción Lineal – Flow Shop. Scientia et Technica, año XII, No 30, mayo 2006, pp. 285-290.
Kirkpatrick, S. and Toulouse, G.: 1985, Configuration space analysis of travelling salesman problems, J. Physique, 46 pp. 1277–1292.
Cerny, V.: 1985, Thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm, J. of Optimization Theory and Applications, 45(1) pp. 41–51.
Metropolis, N., R. A. R. M. T. A. and Teller, E.: 1953, Equation of state calculations by fast computing machines, J. Chem. Phys., 21 pp. 1087–1090.
Yong, Z. and Sannomiya, N.: 2000, A method for solving large-scale flowshop problems by reducing search space of genetic algorithms, IEEE International Conference on Systems, vol. 3 pp. 1776–1781.
Kirkpatrick, S., G. C. and Vecchi, M.: 1983, Optimization by simulated annealing, Science, 220(4598) pp. 671–680.
Rammal, R., T. G. and Virasoro, M.: 1986, Ultrametricity for physicists, Reviews of Modern Physics, 58(3) pp. 765–788.
Solla, S., S. G. and White, S.: 1986, “Configuration space analysis for optimization problems”, In Bienenstock, E., Fogelman Soulie, F., and Weisbuch, G., editors, Disordered Systems and Biological Organization, New York, Springer-Verlag. pp. 283–292.
Dréo, J., P. A. S. P. and Taillard, E.: 2003, Metaheuristics for Hard Optimization. Springer.
Reeves Colin. A generis Algorithm for FlowshopSequencing. Pergamon. Computers Ops Res. Vol 22No 1, pp 5-13, 1995 Great Britain.
Aarts, E. H. L. and Van Laarhoven, P. J. M.: 1985, Statistical cooling: a general approach to combinatorial optimization problems, Philips J. of Research, 40 pp. 193–226.
Hajek, B.: 1988, Cooling schedules for optimal annealing, Math. Oper. Res., 13 pp. 311–329.
Hajek, B. and Sasaki, G.: 1989, Simulated annealing to cool or not, Systems and Control Letters, 12 pp. 443–447.
