Métodos Heurísticos e Meta-Heurísticos para a Resolução do Problema de Sequenciamento de Ordens de Manutenção Preventiva de Longo Prazo / Heuristic and Meta-Heuristic Methods to Resolve the Long-Term Preventive Maintenance Scheduling Problem
Abstract
O sucesso de uma empresa requer o bom funcionamento e a confiabilidade de seus sistemas com máquinas e equipamentos em bom estado. Para isso, é essencial um bom plano de manutenção preventiva, que tende a ficar mais complexo com o aumento do número de equipamentos e o horizonte de planejamento. O objetivo deste estudo é desenvolver algoritmos meta-heurísticos eficientes para tratar o Problema de Planejamento de Ordens de Manutenção Preventiva de Longo Prazo (PPOMPLP). O trabalho se inicia com o desenvolvimento de uma heurística construtiva e de alocação, seguido do desenvolvimento de algoritmos de busca local e meta-heurísticos baseados em Greedy Randomized Adaptive Search Procedure (GRASP), Simulated Annealing (SA) e Iterated Local Search (ILS). O desempenho dos algoritmos desenvolvidos foi comparado entre eles e com os da literatura. Para a calibragem e validação dos algoritmos meta-heurísticos, foram resolvidas instâncias fictícias pequenas. Após a calibragem, os algoritmos meta-heurísticos foram aplicados à resolução de instâncias maiores e à real. Os experimentos mostraram que o ILS foi o algoritmo de melhor desempenho e seu resultado na instância real foi 40,5%, melhor que o apresentado na literatura.
Palavras Chave. Planejamento de Manutenção de Longo Prazo. Grasp. Simulated Annealing. Iterated Local Search. Meta-Heurísticas.
ABSTRACT
The success of a company requires the proper functioning and reliability of its systems with machines and equipment in good condition. For this, a good preventive maintenance plan is essential, which tends to become more complex as the number of equipment and the planning horizon increases. The present work aims to develop efficient meta-heuristic algorithms for the Long-Term Preventive Maintenance Scheduling Problem (PPOMPLP). The work begins with the development of a constructive and allocation heuristic, followed by the development of local search and meta-heuristic algorithms based on Greedy Randomized Adaptive Search Procedure (GRASP), Simulated Annealing (SA), and Iterated Local Search (ILS). The performance of the proposed algorithms was compared among themselves and with those of other studies in the literature. Small fictitious instances were used to calibrate and validate the meta-heuristic algorithms. After calibration, they were applied to solve larger and real instances. The experiments showed that the ILS was the best-performing algorithm, and its result for the real instance was 40.5% better than that presented in the literature.
Keywords: Long-Term Maintenance Scheduling. Grasp. Simulated Annealing. Iterated Local Search. Meta-Heuristics.
References
Alfares, H., Mohammed, A., e Ghaleb, M. (2021). Two-machine scheduling with aging effects and variable maintenance activities. Computers & Industrial Engineering, 160:107586.
Alfares, H. K. (2022). Plant shutdown maintenance workforce team assignment and job scheduling. Journal of Scheduling, 25(3):321–338.
Alidaee, B. e Rosa, D. (1997). Scheduling parallel machines to minimize total weighted and unweighted tardiness. Computers & Operations Research, 24(8):775–788.
Aquino, R. D., Chagas, J. B. C., e Souza, M. J. F. (2019). Abordagem exata e heurísticas para o problema de planejamento de ordens de manutenção de longo prazo: Um estudo de caso industrial de larga escala. Pesquisa Operacional para o Desenvolvimento, 11(3):159–182.
Avalos-Rosales, O., Angel-Bello, F., Álvarez, A., e Cardona-Valdés, Y. (2018). Including preventive maintenance activities in an unrelated parallel machine environment with dependent setup times. Computers & Industrial Engineering, 123:364–377.
Brown, I. e Mues, C. (2012). An experimental comparison of classification algorithms for imbalanced credit scoring data sets. Expert Systems with Applications, 39(3):3446–3453.
Delorme, M., Iori, M., e Mendes, N. F. (2021). Solution methods for scheduling problems with sequence-dependent deterioration and maintenance events. European Journal of Operational Research, 295(3):823–837.
Ebrahimipour, V., Najjarbashi, A., e Sheikhalishahi, M. (2015). Multi-objective modeling for preventive maintenance scheduling in a multiple production line. Journal of Intelligent Manufacturing, 26(1):111–122.
Ertem, M., As’ ad, R., Awad, M., e Al-Bar, A. (2022). Workers-constrained shutdown maintenance scheduling with skills flexibility: Models and solution algorithms. Computers & Industrial Engineering, p. 108575.
Fakher, H. B., Nourelfath, M., e Gendreau, M. (2016). A cost minimisation model for joint production and maintenance planning under quality constraints. International Journal of Production Research, 55(8):2163–2176.
Feo, T. A. e Resende, M. G. (1995). Greedy randomized adaptive search procedures. Journal of Global Optimization, 6(2):109–133.
Friedman, M. (1940). A comparison of alternative tests of significance for the problem of m rankings. The Annals of Mathematical Statistics, 11(1):86–92.
Fu, X., Chan, F. T., Niu, B., Chung, N. S., e Qu, T. (2019). A three-level particle swarm optimization with variable neighbourhood search algorithm for the production scheduling problem with mould maintenance. Swarm and Evolutionary Computation, 50:100572.
Hedjazi, D. (2015). Scheduling a maintenance activity under skills constraints to minimize total weighted tardiness and late tasks. International Journal of Industrial Engineering Computations, 6(2):135–144.
Kirkpatrick, S., Gelatt, C. D., e Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598):671–680.
Lee, H. e Cha, J. H. (2016). New stochastic models for preventive maintenance and maintenance optimization. European Journal of Operational Research, 255(1):80–90.
Levitin, G., Xing, L., e Dai, Y. (2021). Optimal operation and maintenance scheduling in m-out-of-n standby systems with reusable elements. Reliability Engineering & System Safety, 211:107582.
Liu, Y., Zhang, Q., Ouyang, Z., e Huang, H.-Z. (2021). Integrated production planning and preventive maintenance scheduling for synchronized parallel machines. Reliability Engineering & System Safety, 215:107869.
López-Ibáñez, M., Dubois-Lacoste, J., Cáceres, L. P., Birattari, M., e Stützle, T. (2016). The irace package: Iterated racing for automatic algorithm configuration. Operations Research Perspectives, 3:43–58.
Lourenço, H. R., Martin, O. C., e Stützle, T. (2019). Iterated local search: Framework and applications. In Handbook of metaheuristics, p. 129–168. Springer.
Lu, S., Pei, J., Liu, X., e Pardalos, P. M. (2021). A hybrid DBH-VNS for high-end equipment production scheduling with machine failures and preventive maintenance activities. Journal of Computational and Applied Mathematics, 384:113195.
Ma, J., Xia, D., Wang, Y., Niu, X., Jiang, S., Liu, Z., e Guo, H. (2022). A comprehensive comparison among metaheuristics (MHs) for geohazard modeling using machine learning: Insights from a case study of landslide displacement prediction. Engineering Applications of Artificial Intelligence, 114:105150.
Marmier, F., Varnier, C., e Zerhouni, N. (2009). Static et dynamic scheduling of maintenance activities under the constraints of skills. Journal of Operations and Logistics, 2(3):I–1.
Pinedo, M. (2016). Scheduling: theory, algorithms, and systems. Springer, Cham, 5 edition.
Qi, X., Chen, T., e Tu, F. (1999). Scheduling the maintenance on a single machine. Journal of the Operational Research Society, 50(10):1071–1078.
Ruiz-Torres, A. J., Paletta, G., e M’Hallah, R. (2016). Makespan minimisation with sequencedependent machine deterioration and maintenance events. International Journal of Production Research, 55(2):462–479.
Sheldon, M. R., Fillyaw, M. J., e Thompson, W. D. (1996). The use and interpretation of the friedman test in the analysis of ordinal-scale data in repeated measures designs. Physiotherapy Research International, 1(4):221–228.
Upasani, K., Bakshi, M., Pandhare, V., e Lad, B. K. (2017). Distributed maintenance planning in manufacturing industries. Computers & Industrial Engineering, 108:1–14.
Vallada, E. e Ruiz, R. (2011). A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times. European Journal of Operational Research, 211 (3):612–622.
Wang, J. e Miao, Y. (2021). Optimal preventive maintenance policy of the balanced system under the semi-markov model. Reliability Engineering & System Safety, 213:107690.
Wang, Y., Huang, H., Huang, L., e Zhang, X. (2018). Source term estimation of hazardous material releases using hybrid genetic algorithm with composite cost functions. Engineering Applications of Artificial Intelligence, 75:102–113.
Xu, J., Liu, S.-C., Zhao, C., Wu, J., Lin, W.-C., e Yu, P.-W. (2019). An iterated local search and tabu search for two-parallel machine scheduling problem to minimize the maximum total completion time. Journal of Information and Optimization Sciences, 40(3):751–766.
DOI: http://dx.doi.org/10.12819/2023.20.10.9
Refbacks
- There are currently no refbacks.
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
ISSN 1806-6356 (Print) and 2317-2983 (Electronic)