A hybrid evolutionary metaheuristic proposal applied to job-shop scheduling problems with earliness and tardiness penalties

Authors

DOI:

https://doi.org/10.20397/2177-6652/2024.v24i1.2583

Keywords:

Scheduling, Earliness and tardiness costs, Genetic algorithm, Local search.

Abstract

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.

Author Biographies

Júlio Cesar Vasconcelos Conserva, Universidade Federal de Campina Grande

Graduado em Engenharia de Produção pela Universidade Federal de Campina Grande.

Yuri Laio Teixeira Veras Silva, Universidade Federal de Campina Grande

Doutor em Engenharia Mecânica. Graduado e Mestre em Engenharia de Produção. Professor Adjunto do Departamento de Engenharia de Produção da Universidade Federal de Campina Grande.

References

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

Published

2024-04-09

How to Cite

Conserva, J. C. V., & Silva, Y. L. T. V. (2024). A hybrid evolutionary metaheuristic proposal applied to job-shop scheduling problems with earliness and tardiness penalties. Journal of Management & Technology, 24(1), 31–57. https://doi.org/10.20397/2177-6652/2024.v24i1.2583

Issue

Vol. 24 No. 1 (2024)

Section

ARTIGO

License

Copyright (c) 2024 Journal of Management & Technology

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

Authors who publish with this journal agree to the following terms: • 1. The author(s) authorize the publication of the article in the journal. • 2. The author(s) ensure that the contribution is original and unpublished and is not being evaluated in other journal(s). • 3. The journal is not responsible for the opinions, ideas and concepts expressed in the texts because they are the sole responsibility of the author(s). • 4. The publishers reserve the right to make adjustments and textual adaptation to the norms of APA. • 5. Authors retain copyright and grant the journal right of first publication, with the work [SPECIFY PERIOD OF TIME] after publication simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal. • 6. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal. • 7. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access) at http://opcit.eprints.org/oacitation-biblio.html