Impact of the Initial Solution in Simulated Annealing Optimization: A Comparative Analysis between GRASP and HPG
Abstract
This paper evaluates the impact of constructive heuristics (Partially Greedy Heuristic – PGH and GRASP) on the quality of the final solution when combined with Simulated Annealing (SA) for the Parallel Machine Maintenance Scheduling Problem (PMMSP). The main objective is to investigate how the choice of constructive heuristic for generating the initial solution affects SA’s performance in terms of makespan and computational time. Random instances based on data from an ERP system of a mining company were used. The results showed that the GRASP+SA approach consistently outperformed PGH+SA, achieving better-quality makespans and lower computational times, especially for more complex instances. The study highlights the effectiveness of hybrid approaches as efficient tools for complex industrial maintenance problems, balancing solution quality and computational effort.
References
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.
