A Comprehensive Study of Metaheuristic Performance on Job-Shop Scheduling Problems
DOI:
https://doi.org/10.24425/mper.2025.157217Abstract
The article presents an in-depth literature review on the performance of metaheuristics in operations scheduling problems and aims to evaluate the use of metaheuristics, concerning job-shop scheduling problems. In the first part, a literature review was conducted on the significance of operations scheduling and its different types, as well as metaheuristics and jobshop scheduling problems, providing historical context to the three topics. The methodology for the selection of the papers included in the bibliometric study is explained. Twenty articles from Genetic Algorithms, Particle Swarm Optimization, Simulated Annealing and Tabu Search, addressing job-shop problems were selected. Then, various statistical analyses were conducted, such as the analysis of the evolution of results throughout the years and the performance comparison analysis between metaheuristics. Finally, a discussion about the results obtained is held, presenting the conclusions. The statistical analyses revealed that the performance of metaheuristics depends on multiple factors and that their evaluation should not be carried out in isolation. In terms of practical results, the analysis showed that Genetic Algorithms achieved the highest average makespan reduction, followed by Simulated Annealing, Particle Swarm Optimization, and Tabu Search. For example, GA consistently reduced makespan by more than 15% compared to industrial cases, while Tabu Search showed the least consistent performance across studies.References
Abdolrazzagh-Nezhad, M., Abdullah, S. (2017). Job Shop Scheduling: Classification, Constraints and Objective Functions. International Journal of Computer, Electrical, Automation, Control and Information Engineering, 11 (4), 386–391.
Albayrak, E., Önüt, S. (2024). Energy-efficient scheduling for a flexible job shop problem considering rework processes and new job arrival. International Journal of Industrial Engineering Computations, 15 (4), 871-886.
Almufti, S.M. (2019). Historical survey on metaheuristics algorithms. International Journal of Scientific World, 7 (1), 1–12.
Auger, A. (2005). Convergence results for the (1,λ)-SAES using the theory of ϕ-irreducible Markov chains. Theoretical Computer Science, 334 (1–3), 35–69.
Baker, K.R. (1974). Introduction to Sequencing and Scheduling. 1st edn. John Willey & Sons, New York.
Bianchi, L., Dorigo, M., Gambardella, L.M., Gutjahr, W.J. (2009). A survey on metaheuristics for stochastic combinatorial optimization. Natural Computing, 8 (2), 239–287.
Darwin C. (1859). The Origin of The Species.
Georgiadis, G.P., Elekidis, A.P., Georgiadis, M.C. (2019). Optimization-Based Scheduling for the Process Industries: From Theory to Real-Life Industrial Applications. Processes, 7 (7), 1–35.
Glover, F. (1986). Future Paths for Integer Programming and Links to Artificial Intelligence. Computers and Operations Research, 13 (5), 533–549.
Graves, S.C. (1981). A Review of Production Scheduling. Operations Research, 29 (4), 646–675.
Guerreiro, R., Santos, A.S., Tereso, A. (2023). Online Scheduling: A Survey. In: 18th Iberian Conference on Information Systems and Technologies (CISTI), 53–58. IEEE, Aveiro, Portugal.
Holland, J. (1975). Adaptation in Natural and Artificial Systems: An Introductory Analysis with Application to Biology, Control, and Artificial Intelligence, 1st edn. University of Michigan Press.
Katoch, S., Chauhan, S.S., Kumar, V. (2021). A review on genetic algorithm: past, present, and future. Multimedia Tools and Applications, 5 (80), 8091–8126.
Kaveh, A. (2021). Advances in Metaheuristic Algorithms for Optimal Design of Structures. 3rd edn. Springer.
Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P. (1983). Optimization by simulated annealing. Science, 220 (4598), 671–680.
Koskinen, J., Raduly-Baka, C., Johnsson, M., Nevalainen, O.S. (2020). Rolling horizon production scheduling of multi-model PCBs for several assembly lines. International Journal of Production Research, 58 (4), 1052–1073.
Leung, J. (2004). Handbook of Scheduling: Algorithms, Models, and Performance Analysis, 1st edn. Chapman & Hall/CRC, New York.
Martí, R., Sevaux, M., Sörensen, K. (2024). Fifty years of metaheuristics. European Journal of Operational Research, 321 (2), 345–362.
Ouelhadj, D., Petrovic, S. (2009). A survey of dynamic scheduling in manufacturing systems. Journal of Scheduling, 12 (4), 417–431.
Pinedo, M.L. (2008). Scheduling: Theory, Algorithms, and Systems. 3rd edn. Springer, New York.
Polya, G. (1945). How to Solve It, 1st edn. Princeton University Press.
Santos, A. S., Madureira, A.M., Varela, L.R. 2022). A SelfParametrization Framework for Meta-Heuristics. Mathematics, 10 (3), 1–23.
Santos, A.S., Madureira, A.M., Varela, M.L.R. (2016). Study on the impact of the NS in the performance of meta-heuristics in the TSP. In: 2016 IEEE International Conference on Systems, Man, and Cybernetics (SMC), 001110–001115. IEEE, Budapest, Hungary.
Santos, A.S., Madureira, A.M. (2014). Ordered minimum completion time heuristic for unrelated parallelmachines problems. In: 2014 9th Iberian Conference on Information Systems and Technologies (CISTI), 1–6. IEEE, Barcelona, Spain.
Sequeiros, J.A., Silva, R., Santos, A.S., Bastos, J., Varela, L.R., Madureira, A.M. (2021). A Novel Discrete Particle Swarm Optimization Algorithm for the Travelling Salesman Problems. In: Machado, J., Soares, F., Trojanowska, J., Ivanov, V. (eds) Innovations in Industrial Engineering, 48–55. Springer Cham.
Sörensen, K., Sevaux, M., Glover, F. (2018). A History of Metaheuristics. In: Martí, R., Pardalos, P.M., Resende, M.G.C. (eds.) Handbook of Heuristics, 791–808. Springer International Publishing.
Torres-Jiménez, J., Pavón, J. (2014). Applications of metaheuristics in real-life problems. Progress in Artificial Intelligence, 2 (4), 175–176.
Varela, L.R., Alves, C.F., Santos, A.S., Vieira, G.G., Lopes, N., Putnik, G.D. (2022). Analysis of a Collaborative Scheduling Model Applied in a Job Shop Manufacturing Environment. Machines, 10 (12), 1–16.
Wu, A.S., Banzhaf, W. (1998). Introduction to the Special Issue: Variable-Length Representation and Noncoding Segments for Evolutionary Algorithms. Evolutionary Computation, 6 (4), 3–6.
