Combinatorial framework for reducing tardiness in multi-machine scheduling using EDD, NEH and genetic algorithm

[EN] No-idle flow shop scheduling is a critical challenge in manufacturing, where minimising overall tardiness directly impacts efficiency and customer satisfaction. This study introduces a novel hybrid algorithm, EDD-NEH-GA (ENG), which integrates Earliest Due Date (EDD) and Nawaz-Enscore-Ham (NEH) heuristics with a Genetic Algorithm (GA) to balance global exploration and local optimisation. The objective is to overcome premature convergence and achieve superior tardiness reduction. Computational experiments on Taillard s benchmark instances demonstrate ENG s effectiveness compared to the Mixed Integer Linear Programming (MILP) based approach by Balogh. Across all tested cases, ENG updated 93% of previously best-known solutions, achieving an average tardiness reduction of 18 52%. These results confirm ENG as a robust and efficient solution for complex no-idle flow shop environments, offering significant gains in scheduling performance and operational productivity. After performing statistical analysis it is noted that ENG outperforms. ENG significantly improved scheduling performance, averaging 8430 units of reduction in overall tardiness. According to the standard error of the difference (SE = 1859), this improvement appears to be constant across cases.