Hybrid Genetic Algorithm Performance for PFSP: Leveraging NEH Heuristics in Initial Population
DOI:
https://doi.org/10.5281/zenodo.18070179Keywords:
Permutation Flowshop Scheduling Problem (PFSP), Genetic Algorithm (GA), Nawaz-Enscore-Ham (NEH) Heuristic, Makespan Minimization, Hybrid Metaheuristics.Abstract
The Permutation Flowshop Scheduling Problem (PFSP), with the objective of minimizing the maximum completion time, remains a critical and computationally challenging NP-hard problem in manufacturing. This study investigates the strategic impact of hybridizing a standard Genetic Algorithm (GA) by injecting high-quality solutions generated by the Nawaz-Enscore-Ham (NEH) constructive heuristic into the initial population. Two distinct models, GA-Random (purely randomized baseline) and GA-Hybrid (5% NEH initialization), were rigorously compared using the complete Taillard benchmark dataset. The results demonstrate that the GA-Hybrid model significantly outperforms the baseline GA-Random model across all problem sizes and exhibits competitive performance against the best-known solutions reported in the literature. The findings underscore that for NP-hard scheduling problems, superior performance is achieved through strategic hybridization that combines the global exploration of GAs with the powerful local exploitation provided by problem-specific heuristics during the initialization phase.
References
Campbell, H. G., Dudek, R. A., & Smith, M. L. (1970). A heuristic algorithm for the multi-stage production scheduling problem. Management Science, 16(10), B630-B637.
Duman, K., & Ceylan, C. (2020). A hybrid meta-heuristic algorithm for the permutation flow shop scheduling problem. Journal of Manufacturing Systems, 55, 247-257.
Fernandez-Viagas, V., Ruiz, R., & Framinan, J. M. (2018). An efficient iterated greedy algorithm for the permutation flow shop scheduling problem with makespan criterion. European Journal of Operational Research, 269(3), 875-885.
Framinan, J. M., Leisten, R., & Ruiz, R. (2005). Production scheduling in the process industry: Challenging flow shop models. Springer.
García-González, G. P., & Salmerón-Navarro, S. (2023). Discrete whale optimization algorithm for the permutation flow shop scheduling problem with makespan minimization. Expert Systems with Applications, 213(Pt C), 118931.
Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research, 1(2), 117-129.
Goldberg, D. E., & Lingle, R. (1985). Alleles, loci, and the traveling salesman problem. In Proceedings of the First International Conference on Genetic Algorithms and Their Applications (pp. 154-159). Lawrence Erlbaum Associates.
Holland, J. H. (1975). Adaptation in natural and artificial systems. University of Michigan Press.
Johnson, S. M. (1954). Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly, 1(1), 61-68.
Liu, J., Liu, K., & Liu, G. (2013). A discrete genetic algorithm for the permutation flowshop scheduling problem with total flow time criterion. Computers & Industrial Engineering, 64(2), 654-663.
Marichelvam, M. K., Pridhar, S. S., & Srivatsan, P. (2021). An efficient hybrid differential evolution algorithm for permutation flow shop scheduling problems. Arabian Journal for Science and Engineering, 46(2), 1649-1662.
Nawaz, M., Enscore, E. E., & Ham, I. (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, 11(1), 91-95.
Palmer, D. S. (1965). Sequencing jobs through a multi-stage process—A practical approach. Operational Research Quarterly, 16(3), 293-303.
Pan, Q., & Ruiz, R. (2012). An effective iterated greedy algorithm for the permutation flowshop sequencing problem with makespan criterion. Journal of the Operational Research Society, 63(9), 1310-1319.
Pinedo, M. (2002). Scheduling: Theory, algorithms, and systems (2nd ed.). Prentice Hall.
Qing-dao, N., Wu-qing, W., & Zai-yong, W. (2012). An improved hybrid algorithm for permutation flow shop scheduling problem. Applied Soft Computing, 12(3), 1010-1017.
Reeves, C. R. (1995). A genetic algorithm for flowshop sequencing. Computers & Operations Research, 22(1), 5-13.
Ribas, I., Leisten, R., & Framinan, J. M. (2015). A critical review and analysis of the existing literature on block scheduling in flow shop problems. European Journal of Operational Research, 241(1), 1-13.
Ruiz, R., & Maroto, C. (2005). A comprehensive review and evaluation of permutation flowshop heuristics. European Journal of Operational Research, 165(2), 479-494.
Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2), 278-285.
Tseng, L. Y., & Lin, Y. T. (2009). A hybrid genetic algorithm for the permutation flowshop scheduling problem. International Journal of Production Economics, 117(2), 386-392.
Wang, S. Y., Huang, R. H., & Liu, F. (2018). An improved hybrid genetic algorithm for permutation flow shop scheduling problem with makespan criterion. International Journal of Advanced Manufacturing Technology, 96(5), 1801-1816.
Zobolas, G. I., Tarantilis, C. D., & Ioannou, G. (2009). Minimizing makespan in permutation flow shop scheduling problems using a hybrid metaheuristic algorithm. Computers & Operations Research, 36(4), 1249-1267.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 MÜNİRE YALÇİN
This work is licensed under a Creative Commons Attribution 4.0 International License.
