Impacto da Solução Inicial na Otimização por Simulated Annealing: Uma Análise Comparativa entre GRASP e HPG
Resumo
Este artigo avalia o impacto de heurísticas construtivas (Heurística Parcialmente Gulosa HPG e GRASP) na qualidade da solução final quando combinada com o Simulated Annealing (SA) para o problema de sequenciamento de tarefas de manutenção em máquinas paralelas (PSTEEM). O objetivo principal é investigar como a escolha da heurística construtiva para gerar a solução inicial afeta a performance do SA em termos de makespan e tempo computacional. Foram utilizadas instâncias aleatórias baseadas em dados de um sistema ERP de uma indústria de mineração. Os resultados demonstraram que a abordagem GRASP+SA consistentemente superou a HPG+SA, alcançando makespans de melhor qualidade e apresentando um tempo computacional mais baixo, especialmente para instâncias de maior complexidade. O estudo evidencia a eficácia de abordagens híbridas como ferramentas eficientes para problemas complexos de manutenção industrial, equilibrando qualidade da solução e tempo computacional.
Referências
Baker, K. R., & Trietsch, D. (2018). Principles of sequencing and scheduling. John Wiley & Sons.
Glover, F. W., & Kochenberger, G. A. (Eds.). (2003). Handbook of metaheuristics (Vol. 57). Springer Science & Business Media.
Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598), 671–680.
Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computers & Operations Research, 13(5), 533–549.
Lourenço, H. R., Martin, O., & Stützle, T. (2007). Iterated local search. In Handbook of Metaheuristics (pp. 321–353). Springer.
Feo, T. A., & Resende, M. G. C. (1995). A probabilistic heuristic for a computationally difficult set covering problem. Operations Research Letters, 17(2), 67–71.
Resende, M. G. C., & Ribeiro, C. C. (2003). GRASP: Greedy Randomized Adaptive Search Procedures. In Handbook of Metaheuristics (pp. 219–249). Springer.
Guimarães, R. S. S., Cavalcante, A. A. B., & Resende, M. G. C. (2020). A GRASP-Simulated Annealing approach applied to solve Multi-Objective Flexible Job Shop Scheduling Problem. In 2020 IEEE Congress on Evolutionary Computation (CEC) (pp. 1–8). IEEE. [link]
Al-Fawzan, A. S. M. (2009). Design and comparison of simulated annealing algorithm and greedy randomized adaptive search procedure (GRASP) to minimize the makespan in a flow shop scheduling problem. Journal of Software Engineering and Applications, 2(04), 215–221. [link]
Delavar, M. R., Gholami, M. R., & Mousavi, S. M. (2016). Tabu search, genetic, GRASP, and simulated annealing algorithms for urban land-use allocation optimization. Computers, Environment and Urban Systems, 60, 10–21. [link]
Rodrigues, J. M. (2022). Aplicação de um modelo matemático para o sequenciamento de tarefas de manutenção em uma indústria de mineração de gnaisse. Simpósio Brasileiro de Pesquisa Operacional.
Rodrigues, J. M. (2023). Simulated Annealing: Uma abordagem eficiente para problemas de sequenciamento de ordens de manutenção. Simpósio Brasileiro de Pesquisa Operacional.
Siegel, S., & Castellan, N. J. (1988). Nonparametric statistics for the behavioral sciences. McGraw-Hill.
Manoukian, E. B. (2022). Mathematical nonparametric statistics. Routledge.
Talbi, E. G. (2009). Metaheuristics: From design to implementation. John Wiley & Sons.
Xie, J., Li, X., Gao, L., & Gui, L. (2023). A hybrid genetic tabu search algorithm for distributed flexible job shop scheduling problems. Journal of Manufacturing Systems, 71, 82–94.
