A hybrid evolutionary metaheuristic proposal applied to job-shop scheduling problems with earliness and tardiness penalties
DOI:
https://doi.org/10.20397/2177-6652/2024.v24i1.2583Palavras-chave:
Scheduling, Earliness and tardiness costs, Genetic algorithm, Local search.Resumo
Objective: The present study aims to propose an efficient hybrid evolutionary metaheuristic based on a genetic algorithm with local search structures, which allows for high-performance treatment of Job-Shop Scheduling (JSS) problems with earliness and tardiness penalties (JSS-ETC).
Methodology/Approach: The research is characterized as experimental and was carried out by developing the proposed hybrid heuristic to solve the mathematical model problem, JSS-ETC, aiming to achieve efficient results.
Originality/Relevance: A new hybridization approach was proposed for solving JSS-ETC problems based on two heuristics that adopt mechanisms of different natures, demonstrating a vast potential and relevance in the solvability of complex problems, especially scheduling.
Main results: The results showed that the proposed hybrid algorithm (in its two variations) achieved high performance, mathematically and computationally, compared to consolidated methods in the literature. Superior results were achieved in approximately 30% of the tested instances.
Theoretical/methodological contributions: The present study contributes to a better understanding of the problem addressed and the methods used to solve it, presenting a comprehensive literature review on the problem. Additionally, the proposed hybrid algorithm demonstrated high potential for solving and can be considered for other optimization problems.
Contributions to management: The developed algorithm allows for better production planning and control and efficient management of organizational resources.
Referências
Ahmadian, M. M., Salehipour, A., & Cheng, T. C. E. (2021). A meta-heuristic to solve the just-in-time job-shop scheduling problem. European Journal of Operational Research, 288(1), 14-29.
Ahmadian, M. M., Salehipour, A., & Kovalyov, M. (2020). An efficient relax-and-solve heuristic for open-shop scheduling problem to minimize total weighted earliness-tardiness. Available at SSRN 3601396.
Amjad, M. K., Butt, S. I., Kousar, R., Ahmad, R., Agha, M. H., Faping, Z., ... & Asgher, U. (2018). Recent research trends in genetic algorithm based flexible job shop scheduling problems. Mathematical Problems in Engineering, 2018, 1-32.
Asadzadeh, L. (2015). A local search genetic algorithm for the job shop scheduling problem with intelligent agents. Computers & Industrial Engineering, 85, 376-383.
Asadzadeh, L., & Zamanifar, K. (2010). An agent-based parallel approach for the job shop scheduling problem with genetic algorithms. Mathematical and Computer Modelling, 52(11-12), 1957-1965.
Biskup, D., & Feldmann, M. (2001). Benchmarks for scheduling on a single machine against restrictive and unrestrictive common due dates. Computers & Operations Research, 28(8), 787-801.
De CM Nogueira, J. P., Arroyo, J. E. C., Villadiego, H. M. M., & Gonçalves, L. B. (2014). Hybrid GRASP heuristics to solve an unrelated parallel machine scheduling problem with earliness and tardiness penalties. Electronic Notes in Theoretical Computer Science, 302, 53-72.
De Giovanni, L., & Pezzella, F. (2010). An improved genetic algorithm for the distributed and flexible job-shop scheduling problem. European journal of operational research, 200(2), 395-408.
Fang, J. (2022). An Effective Hybrid Multiobjective Flexible Job Shop Scheduling Problem Based on Improved Genetic Algorithm. Scientific Programming, 2022.
Fazlollahtabar, H., Saidi-Mehrabad, M., & Balakrishnan, J. (2015). Mathematical optimization for earliness/tardiness minimization in a multiple automated guided vehicle manufacturing system via integrated heuristic algorithms. Robotics and Autonomous Systems, 72, 131-138.
Freitas, D. M. D. (2018). Geração evolucionária de heurísticas para localização de defeitos de software.
Gao, K. Z., Suganthan, P. N., Pan, Q. K., Chua, T. J., Cai, T. X., & Chong, C. S. (2016). Discrete harmony search algorithm for flexible job shop scheduling problem with multiple objectives. Journal of Intelligent Manufacturing, 27, 363-374.
Gao, K., Cao, Z., Zhang, L., Chen, Z., Han, Y., & Pan, Q. (2019). A review on swarm intelligence and evolutionary algorithms for solving flexible job shop scheduling problems. IEEE/CAA Journal of Automatica Sinica, 6(4), 904-916.
Goldberg, D. E., & Deb, K. (1991). A comparative analysis of selection schemes used in genetic algorithms. In Foundations of genetic algorithms (Vol. 1, pp. 69-93). Elsevier.
Holland, J. H. (1992). Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. MIT press.
Huang, R. H., Yang, C. L., & Cheng, W. C. (2013). Flexible job shop scheduling with due window—a two-pheromone ant colony approach. International Journal of Production Economics, 141(2), 685-697.
Kayvanfar, V., Mahdavi, I., & Komaki, G. M. (2013). Single machine scheduling with controllable processing times to minimize total tardiness and earliness. Computers & Industrial Engineering, 65(1), 166-175.
Khanh Van, B., & Van Hop, N. (2021). Genetic algorithm with initial sequence for parallel machines scheduling with sequence dependent setup times based on earliness-tardiness. Journal of Industrial and Production Engineering, 38(1), 18-28.
Kianpour, P., Gupta, D., Krishnan, K. K., & Gopalakrishnan, B. (2021). Automated job shop scheduling with dynamic processing times and due dates using project management and industry 4.0. Journal of Industrial and Production Engineering, 38(7), 485-498.
Kramer, A., & Subramanian, A. (2019). A unified heuristic and an annotated bibliography for a large class of earliness–tardiness scheduling problems. Journal of Scheduling, 22(1), 21-57.
Kundakcı, N., & Kulak, O. (2016). Hybrid genetic algorithms for minimizing makespan in dynamic job shop scheduling problem. Computers & Industrial Engineering, 96, 31-51.
Li, X., & Gao, L. (2016). An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem. International Journal of Production Economics, 174, 93-110.
Liangxiao, J., & Zhongjun, D. (2015). An improved genetic algorithm for flexible job shop scheduling problem. In 2015 2nd International Conference on Information Science and Control Engineering (pp. 127-131). IEEE.
May, G., Stahl, B., Taisch, M., & Prabhu, V. (2015). Multi-objective genetic algorithm for energy-efficient job shop scheduling. International Journal of Production Research, 53(23), 7071-7089.
Montoya-Torres, J. R., Gutierrez-Franco, E., & Pirachicán-Mayorga, C. (2010). Project scheduling with limited resources using a genetic algorithm. International Journal of Project Management, 28(6), 619-628.
Pacheco, A. (2017). O algoritmo genético – GA. Computação Inteligente [Web page]. https://computacaointeligente.com.br/algoritmos/o-algoritmo-genetico/
Rahmani Hosseinabadi, A. A., Vahidi, J., Saemi, B., Sangaiah, A. K., & Elhoseny, M. (2019). Extended genetic algorithm for solving open-shop scheduling problem. Soft computing, 23, 5099-5116.
Ronconi, D. P., & Kawamura, M. S. (2010). The single machine earliness and tardiness scheduling problem: lower bounds and a branch-and-bound algorithm. Computational & applied mathematics, 29, 107-124.
Salido, M. A., Escamilla, J., Giret, A., & Barber, F. (2016). A genetic algorithm for energy-efficiency in job-shop scheduling. The International Journal of Advanced Manufacturing Technology, 85, 1303-1314.
Schaller, J., & Valente, J. M. (2013). A comparison of metaheuristic procedures to schedule jobs in a permutation flow shop to minimise total earliness and tardiness. International Journal of Production Research, 51(3), 772-779.
Schaller, J., & Valente, J. M. (2019). Heuristics for scheduling jobs in a permutation flow shop to minimize total earliness and tardiness with unforced idle time allowed. Expert Systems with Applications, 119, 376-386.
Scofield, W. (2002). Aplicação de Algoritmos Genéticos ao Problema Job-Shop. Universidade Federal de Ouro Preto. MG. Brasil.
Silva, Y. L. T., Subramanian, A., & Pessoa, A. A. (2018). Exact and heuristic algorithms for order acceptance and scheduling with sequence-dependent setup times. Computers & operations research, 90, 142-160.
Siqueira, F. R. D., & Müller, C. A. D. S. (2022). Integração entre Teoria dos Stakeholders e Visão Baseada em Recursos: trajetória percorrida pela literatura de Administração.
Tanaka, S., Fujikuma, S., & Araki, M. (2009). An exact algorithm for single-machine scheduling without machine idle time. Journal of Scheduling, 12, 575-593.
Tavakkoli-Moghaddam, R., Azarkish, M., & Sadeghnejad-Barkousaraie, A. (2011). A new hybrid multi-objective Pareto archive PSO algorithm for a bi-objective job shop scheduling problem. Expert Systems with Applications, 38(9), 10812-10821.
Wang, Y. (2012). A new hybrid genetic algorithm for job shop scheduling problem. Computers & Operations Research, 39(10), 2291-2299.
Yazdani, M., Aleti, A., Khalili, S. M., & Jolai, F. (2017). Optimizing the sum of maximum earliness and tardiness of the job shop scheduling problem. Computers & Industrial Engineering, 107, 12-24.
Yuce, B., Fruggiero, F., Packianather, M. S., Pham, D. T., Mastrocinque, E., Lambiase, A., & Fera, M. (2017). Hybrid Genetic Bees Algorithm applied to single machine scheduling with earliness and tardiness penalties. Computers & Industrial Engineering, 113, 842-858.
Zambrano Rey, G., Bekrar, A., Trentesaux, D., & Zhou, B. H. (2015). Solving the flexible job-shop just-in-time scheduling problem with quadratic earliness and tardiness costs. The International Journal of Advanced Manufacturing Technology, 81, 1871-1891.
Downloads
Publicado
Como Citar
Edição
Seção
Licença
Copyright (c) 2024 Revista Gestão & Tecnologia
Este trabalho está licenciado sob uma licença Creative Commons Attribution-NonCommercial 4.0 International License.
Os direitos, inclusive os de tradução, são reservados. É permitido citar parte de artigos sem autorização prévia desde que seja identificada a fonte. A reprodução total de artigos é proibida. Em caso de dúvidas, consulte o Editor.
