Hybrid Genetic Algorithm Performance for PFSP: Leveraging NEH Heuristics in Initial Population

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.