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

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.

Show more Show less

References:

Adiri, I., & Pohoryles, D. (1982). Flowshop/no-idle or no-wait scheduling to minimize the sum of completion times. Naval Research Logistics Quarterly, 29(3), 495–504. https://doi.org/10.1002/nav.3800290311

Afsar, H. M., Lacomme, P., Ren, L., Prodhon, C., & Vigo, D. (2016). Resolution of a job-shop problem with transportation constraints: A master/slave approach. IFAC-PapersOnLine, 49(12), 898–903. https://doi.org/10.1016/j.ifacol.2016.07.889

Balogh, A., Garraffa, M., O’Sullivan, B., & Salassa, F. (2022). MILP-based local search procedures for minimizing total tardiness in the no-idle permutation flowshop problem. Computers and Operations Research, 146, 105862. https://doi.org/10.1016/j.cor.2022.105862

Baptiste, P. & Hguny, L. (1997). A branch and bound algorithm for the f/no- idle/cmax. In Proceedings of the International Conference on Industrial Engineering and Production Management, IEPM, 97, 429–438.

Bari, P., Karande, P. & Bag, V. (2024). Hybrid genetic algorithm to minimize scheduling cost with unequal and job dependent earliness tardiness cost. International Journal of Production Management and Engineering, 12(1), 19-30. https://doi.org/10.4995/ijpme.2024.19277

Bari, P., & Karande, P. (2023). Optimal job scheduling to minimize total tardiness by dispatching rules and community evaluation chromosomes. Decision Making: Applications in Management and Engineering, 6(2), 201–250. https://doi.org/10.31181/dmame060104052023b

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. https://doi.org/10.1007/s11047-008-9098-4

Choo, W. M., Wong, L. P., & Khader, A. T. (2016). A modified bee colony optimization with local search approach for job shop scheduling problems relevant to bottleneck machines. International Journal of Advances in Soft Computing and Its Applications, 8(2), 52–78.

Framinan, J. M., Leisten, R., & Ruiz-Usano, R. (2002). Efficient heuristics for flowshop sequencing with the objectives of makespan and flowtime minimisation. European Journal of Operational Research, 141(3), 559–569. https://doi.org/10.1016/S0377-2217(01)00278-8

Jourdan, L., Basseur, M., & Talbi, E. G. (2009). Hybridizing exact methods and metaheuristics: A taxonomy. European Journal of Operational Research, 199(3), 620–629. https://doi.org/10.1016/j.ejor.2007.07.035

Kemmoé, S., Lamy, D., & Tchernev, N. (2015). A job-shop with an energy threshold issue considering operations with consumption peaks. IFAC-PapersOnLine, 28(3), 788–793. https://doi.org/10.1016/j.ifacol.2015.06.179

Li, Y. Z., Meng, L. L., & Zhang, B. (2025). Two-stage iterated greedy algorithm for distributed flexible assembly permutation flowshop scheduling problems with sequence-dependent setup times. AIMS Mathematics, 10(5), 11488–11513. https://doi.org/10.3934/math.2025523

Lunardi, W. T., Birgin, E. G., Ronconi, D. P., & Voos, H. (2021). Metaheuristics for the online printing shop scheduling problem. European Journal of Operational Research, 293(2), 419–441. https://doi.org/10.1016/j.ejor.2020.12.021

Marti, R. & Reinelt, G. (2011) The linear ordering problem: Exact and heuristic methods in combinatorial optimization. Applied Mathematical Sciences. 175.

Mei, Y., Nguyen, S., Xue, B., & Zhang, M. (2017). An efficient feature selection algorithm for evolving job shop scheduling rules with genetic programming. IEEE Transactions on Emerging Topics in Computational Intelligence, 1(5), 339–353. https://doi.org/10.1109/TETCI.2017.2743758

Mencía, R., Sierra, M. R., Mencía, C., & Varela, R. (2015). Memetic algorithms for the job shop scheduling problem with operators. Applied Soft Computing Journal, 34, 94–105. https://doi.org/10.1016/j.asoc.2015.05.004

Mirmozaffari, M., Hejazi, S. M., Karamizadeh, N., & Montazeri, A. (2024). A mixed-integer non-linear no-wait open-shop scheduling model for minimizing makespan and total tardiness in manufacturing. Decision Analytics Journal, 10, 100403. https://doi.org/10.1016/j.dajour.2024.100403

Mousighichi, K., & Avci, M. G. (2024). The distributed no-idle permutation flowshop scheduling problem with due windows. Computational and Applied Mathematics, 43(4), 1–32. https://doi.org/10.1007/s40314-024-02702-w

Nip, K., Wang, Z., & Xing, W. (2016). A study on several combination problems of classic shop scheduling and shortest path. Theoretical Computer Science, 654, 175–187. https://doi.org/10.1016/j.tcs.2015.12.027

Riahi, V., Chiong, R., & Zhang, Y. (2020). A new iterated greedy algorithm for no-idle permutation flowshop scheduling with the total tardiness criterion. Computers and Operations Research, 117, 104839. https://doi.org/10.1016/j.cor.2019.104839

Ruiz, R., Vallada, E., & Fernández-Martínez, C. (2009). Scheduling in flowshops with no-idle machines. Studies in Computational Intelligence, 230, 21–51. https://doi.org/10.1007/978-3-642-02836-6_2

Sawik, T. (2000). Mixed integer programming for scheduling flexible flow lines with limited intermediate buffers. Mathematical and Computer Modelling, 31(13), 39–52. https://doi.org/10.1016/S0895-7177(00)00110-2

Shao, W., Pi, D., & Shao, Z. (2018). A hybrid discrete teaching-learning based meta-heuristic for solving no-idle flow shop scheduling problem with total tardiness criterion. Computers and Operations Research, 94, 89–105. https://doi.org/10.1016/j.cor.2018.02.003

Shen, J. N., Wang, L., & Wang, S. Y. (2015). A bi-population EDA for solving the no-idle permutation flow-shop scheduling problem with the total tardiness criterion. Knowledge-Based Systems, 74, 167–175. https://doi.org/10.1016/j.knosys.2014.11.016

Shi, F., Zhao, S., & Meng, Y. (2020). Hybrid algorithm based on improved extended shifting bottleneck procedure and GA for assembly job shop scheduling problem. International Journal of Production Research, 58(9), 2604–2625. https://doi.org/10.1080/00207543.2019.1622052

Sobeyko, O., & Mönch, L. (2016). Heuristic approaches for scheduling jobs in large-scale flexible job shops. Computers and Operations Research, 68, 97–109. https://doi.org/10.1016/j.cor.2015.11.004

Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2), 278–285. https://doi.org/10.1016/0377-2217(93)90182-M

Tasgetiren, F., Pan, Q. K., Suganthan, P. N., & Chen, A. H. L. (2010). A discrete artificial bee colony algorithm for the permutation flow shop scheduling problem with total flowtime criterion. 2010 IEEE World Congress on Computational Intelligence, WCCI 2010 - 2010 IEEE Congress on Evolutionary Computation, CEC 2010. https://doi.org/10.1109/CEC.2010.5586300

Tasgetiren, F., Pan, Q. K., Suganthan, P. N., & Oner, A. (2013). A discrete artificial bee colony algorithm for the no-idle permutation flowshop scheduling problem with the total tardiness criterion. Applied Mathematical Modelling, 37(10–11), 6758–6779. https://doi.org/10.1016/j.apm.2013.02.011

Utama, D. M., & Al Imron, C.N. (2024). A systematic literature review on no-idle flow shop scheduling problem. Operations Research Forum, 5. https://doi.org/10.1007/s43069-024-00304-0

Wang, J. B., & Xia, Z. Q. (2005). No-wait or no-idle permutation flowshop scheduling with dominating machines. Journal of Applied Mathematics and Computing, 17(1–2), 419–432. https://doi.org/10.1007/BF02936066

Williamson, D. P., & Shmoys D. B. (2011). The design of approximation algorithms. Cambridge University Press.

Zhang, J., Ding, G., Zou, Y., Qin, S., & Fu, J. (2019). Review of job shop scheduling research and its new perspectives under Industry 4.0. Journal of Intelligent Manufacturing, 30(4), 1809–1830. https://doi.org/10.1007/s10845-017-1350-2

Zhao, C., Wu, L., Zuo, C., & Zhang, H. (2024). An improved fruit fly optimization algorithm with Q-learning for solving distributed permutation flow shop scheduling problems. Complex and Intelligent Systems, 10(5), 5965–5988. https://doi.org/10.1007/s40747-024-01482-4

Show more Show less