Improved algorithms for the two-machine flow shop scheduling problem with uncertain setup times to minimize total tardiness

Muberra Allahverdi; Ali Allahverdi; Muberra Allahverdi; Ali Allahverdi

doi:10.3934/jimo.2026070

Journal of Industrial and Management Optimization

2026, Volume 22, Issue 4: 1905-1927. doi: 10.3934/jimo.2026070

Previous Article Next Article

Research article

Improved algorithms for the two-machine flow shop scheduling problem with uncertain setup times to minimize total tardiness

Muberra Allahverdi ^{1
,
,},
Ali Allahverdi ²

1.
Department of Mathematics, Faculty of Engineering and Natural Sciences, Ankara Yıldırım Beyazıt University, Ankara, Turkey
2.
Department of Industrial Engineering, Faculty of Engineering, Gazi University, Ankara, Turkey

Received: 08 December 2025 Revised: 03 March 2026 Accepted: 05 March 2026 Published: 19 March 2026
90B35, 90C27

We address the two-machine flow shop scheduling problem with the objective of minimizing total tardiness, where setup times are modeled as uncertain. Accordingly, setup times are represented using lower and upper bounds without assuming any probability distribution. We first develop a mathematical dominance relation for the problem and then present two novel heuristic algorithms that incorporate this dominance relation. Through extensive computational experiments using multiple problem sizes, due-date settings, and both symmetric and extreme uncertainty distributions, supported by statistical hypothesis testing, we show that both proposed algorithms significantly outperform the best existing algorithm in the literature. In particular, the computational results indicate that the error of the leading algorithm in the literature is approximately 38 to 115 times larger than that of our proposed algorithms.
- scheduling,
- flow shop,
- total tardiness,
- heuristic algorithms,
- uncertain setup times
Citation: Muberra Allahverdi, Ali Allahverdi. Improved algorithms for the two-machine flow shop scheduling problem with uncertain setup times to minimize total tardiness[J]. Journal of Industrial and Management Optimization, 2026, 22(4): 1905-1927. doi: 10.3934/jimo.2026070

Related Papers:

Abstract

We address the two-machine flow shop scheduling problem with the objective of minimizing total tardiness, where setup times are modeled as uncertain. Accordingly, setup times are represented using lower and upper bounds without assuming any probability distribution. We first develop a mathematical dominance relation for the problem and then present two novel heuristic algorithms that incorporate this dominance relation. Through extensive computational experiments using multiple problem sizes, due-date settings, and both symmetric and extreme uncertainty distributions, supported by statistical hypothesis testing, we show that both proposed algorithms significantly outperform the best existing algorithm in the literature. In particular, the computational results indicate that the error of the leading algorithm in the literature is approximately 38 to 115 times larger than that of our proposed algorithms.

References

[1]	H. Y. Fuchigami, S. Rangel, A survey of case studies in production scheduling: analysis and perspectives, J. Comput. Sci., 25 (2018), 425–436. https://doi.org/10.1016/j.jocs.2017.06.004 doi: 10.1016/j.jocs.2017.06.004
[2]	S. Rahmativala, J. Ghahremani, A robust optimization method for hybrid flow shop scheduling with uncertain setup times, Decis. Anal. J., 2025, 100609. https://doi.org/10.1016/j.dajour.2025.100609 doi: 10.1016/j.dajour.2025.100609
[3]	B. D. A. Prata, L. R. D. Abreu, V. Fernandez-Viagas, A systematic review of permutation flow shop scheduling with due-date-related objectives, Comput. Oper. Res., 177 (2025), 106989. https://doi.org/10.1016/j.cor.2025.106989 doi: 10.1016/j.cor.2025.106989
[4]	J. R. Birge, F. Louveaux, Introduction to stochastic programming, Springer, 2011. https://doi.org/10.1007/978-1-4614-0237-4
[5]	A. Ben-Tal, L. E. Ghaoui, A. Nemirovski, Robust optimization, University Press, 2018. https://doi.org/10.1515/9781400831050
[6]	D. Bertsimas, D. B. Brown, C. Caramanis, Theory and applications of robust optimization, SIAM Rev., 53 (2011), 464–501. https://doi.org/10.1137/080734510 doi: 10.1137/080734510
[7]	H. Emmons, G. Vairaktarakis, Flow shop scheduling: Theoretical results, algorithms, and applications, Springer, 18 (2012), 334. https://doi.org/10.1007/978-1-4614-5152-5
[8]	A. Gharbi, T. Ladhari, M. K. Msakni, M. Serairi, The two-machine flowshop scheduling problem with sequence-independent setup times: New lower bounding strategies, Eur. J. Oper. Res., 231 (2013), 69–78. https://doi.org/10.1016/j.ejor.2013.05.031 doi: 10.1016/j.ejor.2013.05.031
[9]	S. Gawiejnowicz, Models and algorithms of time-dependent scheduling, Springer Berlin Heidelberg, 2020. https://doi.org/10.1007/978-3-662-59362-2
[10]	A. Agnetis, J. C. Billaut, M. Pinedo, D. Shabtay, Fifty years of research in scheduling–Theory and applications, Eur. J. Oper. Res., 327 (2025), 367–393. https://doi.org/10.1016/j.ejor.2025.01.034 doi: 10.1016/j.ejor.2025.01.034
[11]	S. Gawiejnowicz, Theory and methodology of time-dependent scheduling: Past, present and future, Eur. J. Oper. Res., 329 (2025), 719–746. https://doi.org/10.1016/j.ejor.2025.05.024 doi: 10.1016/j.ejor.2025.05.024
[12]	J. Ksciuk, S. Kuhlemann, K. Tierney, A. Koberstein, Uncertainty in maritime ship routing and scheduling: A Literature review, Eur. J. Oper. Res., 308 (2023), 499–524. https://doi.org/10.1016/j.ejor.2022.08.006 doi: 10.1016/j.ejor.2022.08.006
[13]	M. Allahverdi, Minimizing total tardiness in a two-machine flowshop with uncertain and bounded processing times, RAIRO-Oper. Res., 57 (2023), 1353–1375. https://doi.org/10.1051/ro/2023023 doi: 10.1051/ro/2023023
[14]	C. Pessan, J. L. Bouquard, E. Neron, An unrelated parallel machines model for an industrial production resetting problem, Eur. J. Ind. Eng., 2 (2008), 153–171. https://doi.org/10.1504/EJIE.2008.017349 doi: 10.1504/EJIE.2008.017349
[15]	A. Allahverdi, C.T. Ng, T. E. Cheng, M.Y. Kovalyov, A survey of scheduling problems with setup times or costs, Eur. J. Oper. Res., 187 (2008), 985–1032. https://doi.org/10.1016/j.ejor.2006.06.060 doi: 10.1016/j.ejor.2006.06.060
[16]	A. Allahverdi, The third comprehensive survey on scheduling problems with setup times/costs, Eur. J. Oper. Res., 246 (2015), 345–378. https://doi.org/10.1016/j.ejor.2015.04.004 doi: 10.1016/j.ejor.2015.04.004
[17]	H. Aydilek, A. Aydilek, A. Allahverdi, Algorithms to minimize total completion time in a two-machine flowshop problem with uncertain set-up times, Eng. Optim., 53 (2021), 1417–1430. https://doi.org/10.1080/0305215X.2020.1796999 doi: 10.1080/0305215X.2020.1796999
[18]	A. Allahverdi, H. M. Soroush, The significance of reducing setup times/setup costs, Eur. J. Oper. Res., 187 (2008), 978–984. https://doi.org/10.1016/j.ejor.2006.09.010 doi: 10.1016/j.ejor.2006.09.010
[19]	Y. J. Feng, J. L. Kong, Multi-objective hybrid flow-shop scheduling in parallel sequential mode while considering handling time and setup time, Appl. Sci., 13 (2023), 3563. https://doi.org/10.3390/app13063563 doi: 10.3390/app13063563
[20]	S. Aqil, Effective population-based meta-heuristics with neh and grasp heuristics minimizing total weighted flow time in no-wait flow shop scheduling problem under sequence-dependent setup time constraint, Arab. J. Sci. Eng., 49 (2024), 12235–12258. https://doi.org/10.1007/s13369-023-08642-7 doi: 10.1007/s13369-023-08642-7
[21]	S. Zhao, Scheduling jobs with general truncated learning effects including proportional setup times, Comp. Appl. Math., 41 (2022), 146. https://doi.org/10.1007/s40314-022-01851-0 doi: 10.1007/s40314-022-01851-0
[22]	C. Y. Cheng, P. Pourhejazy, K. C. Ying, Y. H. Liao, New benchmark algorithms for No-wait flowshop group scheduling problem with sequence-dependent setup times, Appl. Soft Comput., 111 (2021), 107705. https://doi.org/10.1016/j.asoc.2021.107705 doi: 10.1016/j.asoc.2021.107705
[23]	K. Jansen, K. M. Klein, M. Maack, M. Rau, Empowering the configuration-IP: new PTAS results for scheduling with setup times, Math. Program., 195 (2022), 367–401. https://doi.org/10.1007/s10107-021-01719-3 doi: 10.1007/s10107-021-01719-3
[24]	M. Ertem, F. Ozcelik, T. Saraç , Single machine scheduling problem with stochastic sequence-dependent setup times, Int. J. Prod. Res., 57 (2019), 3273–3289. https://doi.org/10.1080/00207543.2019.1581383 doi: 10.1080/00207543.2019.1581383
[25]	B. J. Joo, P. Xirouchakis, A production scheduling problem with uncertain sequence-dependent set-up times and random yield, Int. J. Prod. Res., 53 (2015), 2820–2835. https://doi.org/10.1080/00207543.2014.998790 doi: 10.1080/00207543.2014.998790
[26]	M. E. Bruni, S. Khodaparasti, E. Demeulemeester, The distributionally robust machine scheduling problem with job selection and sequence-dependent setup times, Comput. Oper. Res., 123 (2020), 105017. https://doi.org/10.1016/j.cor.2020.105017 doi: 10.1016/j.cor.2020.105017
[27]	S. C. Kim, P. M. Bobrowski, Scheduling jobs with uncertain setup times and sequence dependency, Omega, 25 (1997), 437–447. https://doi.org/10.1016/S0305-0483(97)00013-3 doi: 10.1016/S0305-0483(97)00013-3
[28]	İ. Yanıkoğlu, T. Yavuz, Branch-and-price approach for robust parallel machine scheduling with sequence-dependent setup times, Eur. J. Oper. Res., 301 (2022), 875–895. https://doi.org/10.1016/j.ejor.2021.11.023 doi: 10.1016/j.ejor.2021.11.023
[29]	A. Stanković, N. Simić, M. Stanković, Metaheuristic optimization for stochastic job scheduling in parallel machine systems with uncertain processing and setup times, J. Eng. Manag. Syst. Eng., 4 (2025), 206–217. https://doi.org/10.56578/jemse040304 doi: 10.56578/jemse040304
[30]	M. Allahverdi, A. Allahverdi, Minimizing total completion time in a two-machine no-wait flowshop with uncertain and bounded setup times, J. Ind. Manag. Optim., 16 (2020), 2439–2457. https://doi.org/10.3934/jimo.2019062 doi: 10.3934/jimo.2019062
[31]	A. Allahverdi, M. Allahverdi, Two-machine no-wait flowshop scheduling problem with uncertain setup times to minimize maximum lateness, Comp. Appl. Math., 37 (2018), 6774–6794. https://doi.org/10.1007/s40314-018-0694-3 doi: 10.1007/s40314-018-0694-3
[32]	A. Aydilek, H. Aydilek, A. Allahverdi, Increasing the profitability and competitiveness in a production environment with random and bounded setup times, Int. J. Prod. Res., 51 (2013), 106–117. https://doi.org/10.1080/00207543.2011.652263 doi: 10.1080/00207543.2011.652263
[33]	A. Aydilek, H. Aydilek, A. Allahverdi, Production in a two-machine flowshop scheduling environment with uncertain processing and setup times to minimize makespan, Int. J. Prod. Res., 53 (2015), 2803–2819. https://doi.org/10.1080/00207543.2014.997403 doi: 10.1080/00207543.2014.997403
[34]	A. Allahverdi, M. Allahverdi, Minimizing total tardiness in flowshops with uncertain setup times, GITMA, 2025, 82–87.
[35]	M. Jafari-Nikpay, Z. Arabzade-Nosratabad, F. Momayezi, Optimizing smart home energy management with branch and bound method: A novel model for daily and weekly scheduling of smart appliances, Spectr. Oper. Res., 3 (2026), 252–274. https://doi.org/10.31181/sor31202643 doi: 10.31181/sor31202643
[36]	J. Ahn, H. J. Kim, A branch and bound algorithm for scheduling of flexible manufacturing systems, IEEE Trans. Autom. Sci. Eng., 21 (2023), 4382–4396. https://doi.org/10.1109/TASE.2023.3296087 doi: 10.1109/TASE.2023.3296087
[37]	W. Bożejko, J. Pempera, M. Uchroński, M. Wodecki, Quantum annealing-driven branch and bound for the single machine total weighted number of tardy jobs scheduling problem, Future Gener. Comput. Syst., 155 (2024), 245–255. https://doi.org/10.1016/j.future.2024.02.016 doi: 10.1016/j.future.2024.02.016
[38]	X. Li, Z. W. He, N. M. Wang, A branch-and-bound algorithm for the proactive resource-constrained project scheduling problem with a robustness maximization objective, Comput. Oper. Res., 166 (2024), 106623. https://doi.org/10.1016/j.cor.2024.106623 doi: 10.1016/j.cor.2024.106623
[39]	L. Liu, M. Urgo, A branch-and-bound approach to minimise the value-at-risk of the makespan in a stochastic two-machine flow shop, Int. J. Prod. Res., 62 (2024), 2107–2123. https://doi.org/10.1080/00207543.2023.2217279 doi: 10.1080/00207543.2023.2217279
[40]	Z. Wang, Q. Zeng, A branch-and-bound approach for AGV dispatching and routing problems in automated container terminals, Comput. Ind. Eng., 166 (2022), 107968. https://doi.org/10.1016/j.cie.2022.107968 doi: 10.1016/j.cie.2022.107968

Reader Comments

Your name:*

Email:*
© 2026 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)