An ODE-augmented matheuristic for the permutation flow shop scheduling problem with thermally driven processing times

Neus Garrido; Sandra Oltra-Crespo; Lucía Agud-Albesa; Daniel López-Rodríguez; Ángel A. Juan; Neus Garrido; Sandra Oltra-Crespo; Lucía Agud-Albesa; Daniel López-Rodríguez; Ángel A. Juan

doi:10.3934/math.2026794

AIMS Mathematics

2026, Volume 11, Issue 7: 19545-19566. doi: 10.3934/math.2026794

Previous Article Next Article

Research article Topical Sections

An ODE-augmented matheuristic for the permutation flow shop scheduling problem with thermally driven processing times

1.
Instituto de Matemática Multidisciplinar, Universitat Politècnica de València, 46022 Valencia, Spain
2.
Technological Institute of Informatics, Universitat Politècnica de València, 03801 Alcoy, Spain
3.
Dept. of Applied Mathematics, Universitat Politècnica de València, 03801 Alcoy, Spain
4.
CIGIP – ValgrAI, Universitat Politècnica de València, 03801 Alcoy, Spain
5.
UNIE Universidad, Av. Monforte de Lemos 28, 28029 Madrid, Spain

Received: 01 March 2026 Revised: 23 June 2026 Accepted: 24 June 2026 Published: 02 July 2026
MSC : 68W20, 90-10

This work analyzes a dynamic extension of the permutation flow shop scheduling problem (PFSP) in which processing times depend on the evolution of machine states. The proposed matheuristic combines a constructive heuristic, a biased randomization strategy, and a system of ordinary differential equations (ODEs) that models the thermal behavior of machines. This integration allows scheduling decisions to interact directly with time-varying machine conditions, producing schedules that adapt to operational degradation effects. The proposed ODE-enhanced matheuristic is evaluated on classical benchmark instances ranging from $ 20 $ to $ 100 $ jobs and up to $ 20 $ machines. Processing times are modified through a state-dependent thermal model that introduces performance degradation as machine load increases. The computational study compares static schedules, the dynamic evaluation of those schedules, and the solutions obtained by the proposed method. The results show that ignoring thermal effects leads to a substantial increase in makespan. In contrast, the proposed matheuristic consistently mitigates this degradation, achieving average improvements of $ 36.2\% $, $ 26.4\% $, and $ 25.9\% $ with respect to the dynamically evaluated static solutions. Furthermore, the proposed approach reduces the dispersion of makespan values across instances, indicating improved robustness under thermal fluctuations.
- permutation flow shop problem,
- dynamic processing times,
- matheuristics,
- first-order differential equations,
- thermodynamics,
- thermal stress
Citation: Neus Garrido, Sandra Oltra-Crespo, Lucía Agud-Albesa, Daniel López-Rodríguez, Ángel A. Juan. An ODE-augmented matheuristic for the permutation flow shop scheduling problem with thermally driven processing times[J]. AIMS Mathematics, 2026, 11(7): 19545-19566. doi: 10.3934/math.2026794

Related Papers:

Abstract

This work analyzes a dynamic extension of the permutation flow shop scheduling problem (PFSP) in which processing times depend on the evolution of machine states. The proposed matheuristic combines a constructive heuristic, a biased randomization strategy, and a system of ordinary differential equations (ODEs) that models the thermal behavior of machines. This integration allows scheduling decisions to interact directly with time-varying machine conditions, producing schedules that adapt to operational degradation effects. The proposed ODE-enhanced matheuristic is evaluated on classical benchmark instances ranging from $ 20 $ to $ 100 $ jobs and up to $ 20 $ machines. Processing times are modified through a state-dependent thermal model that introduces performance degradation as machine load increases. The computational study compares static schedules, the dynamic evaluation of those schedules, and the solutions obtained by the proposed method. The results show that ignoring thermal effects leads to a substantial increase in makespan. In contrast, the proposed matheuristic consistently mitigates this degradation, achieving average improvements of $ 36.2\% $, $ 26.4\% $, and $ 25.9\% $ with respect to the dynamically evaluated static solutions. Furthermore, the proposed approach reduces the dispersion of makespan values across instances, indicating improved robustness under thermal fluctuations.

References

[1]	J. M. Framinan, J. N. D. Gupta, R. Leisten, A review and classification of heuristics for permutation flow-shop scheduling with makespan objective, J. Oper. Res. Soc., 55 (2004), 1243–1255. https://doi.org/10.1057/palgrave.jors.2601784 doi: 10.1057/palgrave.jors.2601784
[2]	R. Ruiz, C. Maroto, A comprehensive review and evaluation of permutation flowshop heuristics, Eur. J. Oper. Res., 165 (2005), 479–494. https://doi.org/10.1016/j.ejor.2004.04.017 doi: 10.1016/j.ejor.2004.04.017
[3]	T. C. E. Cheng, Q. Ding, B. M. Lin, A concise survey of scheduling with time-dependent processing times, Eur. J. Oper. Res., 152 (2004), 1–13. https://doi.org/10.1016/S0377-2217(02)00909-8 doi: 10.1016/S0377-2217(02)00909-8
[4]	S. Chorghe, R. Kumar, M. S. Kulkarni, V. Pandhare, B. K. Lad, Smart scheduling for next generation manufacturing systems: a systematic literature review, J. Intell. Manuf., 36 (2025), 4447–4476. https://doi.org/10.1007/s10845-024-02484-2 doi: 10.1007/s10845-024-02484-2
[5]	W. C. Lee, C. C. Wu, C. C. Wen, Y. H. Chung, A two-machine flowshop makespan scheduling problem with deteriorating jobs, Comput. Ind. Eng., 54 (2008), 737–749. https://doi.org/10.1016/j.cie.2007.10.010 doi: 10.1016/j.cie.2007.10.010
[6]	Z. W. Sun, D. Y. Lv, C. M. Wei, J. B. Wang, Flow shop scheduling with shortening jobs for makespan minimization, Mathematics, 13 (2025), 363. https://doi.org/10.3390/math13030363 doi: 10.3390/math13030363
[7]	P. A. Villarinho, J. Panadero, L. S. Pessoa, A. A. Juan, F. L. Cyrino Oliveira, A simheuristic algorithm for the stochastic permutation flow-shop problem with delivery dates and cumulative payoffs, Int. Trans. Oper. Res., 28 (2021), 716–737. https://doi.org/10.1111/itor.12862 doi: 10.1111/itor.12862
[8]	M. Nawaz, E. E. Enscore, I. Ham, A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem, Omega, 11 (1983), 91–95. https://doi.org/10.1016/0305-0483(83)90088-9 doi: 10.1016/0305-0483(83)90088-9
[9]	J. Belloso, A. A. Juan, J. Faulin, An iterative biased-randomized heuristic for the fleet size and mix vehicle-routing problem with backhauls, Int. Trans. Oper. Res., 26 (2019), 289–301. https://doi.org/10.1111/itor.12379 doi: 10.1111/itor.12379
[10]	É. Taillard, Benchmarks for basic scheduling problems, Eur. J. Oper. Res., 64 (1993), 278–285. https://doi.org/10.1016/0377-2217(93)90182-M doi: 10.1016/0377-2217(93)90182-M
[11]	A. N. H. Zaied, M. M. Ismail, S. S. Mohamed, Permutation flow shop scheduling problem with makespan criterion: Literature review, J. Theor. Appl. Inf. Technol., 99 (2021), 830–848.
[12]	L. H. Sun, K. Cui, J. H. Chen, J. Wang, X. C. He, Research on permutation flow shop scheduling problems with general position-dependent learning effects, Ann. Oper. Res., 211 (2013), 473–480. https://doi.org/10.1007/s10479-013-1481-6 doi: 10.1007/s10479-013-1481-6
[13]	Y. Y. Lu, Research on no-idle permutation flowshop scheduling with time-dependent learning effect and deteriorating jobs, Appl. Math. Model., 40 (2016), 3447–3450. https://doi.org/10.1016/j.apm.2015.09.081 doi: 10.1016/j.apm.2015.09.081
[14]	X. Xin, Q. Jiang, C. Li, S. Li, K. Chen, Permutation flow shop energy-efficient scheduling with a position-based learning effect, Int. J. Prod. Res., 61 (2023), 382–409. https://doi.org/10.1080/00207543.2021.2008041 doi: 10.1080/00207543.2021.2008041
[15]	A. A. Juan, B. B. Barrios, E. Vallada, D. Riera, J. Jorba, A simheuristic algorithm for solving the permutation flow shop problem with stochastic processing times, Simul. Model. Pract. Theory, 46 (2014), 101–117. https://doi.org/10.1016/j.simpat.2014.02.005 doi: 10.1016/j.simpat.2014.02.005
[16]	E. M. Gonzalez-Neira, J. R. Montoya-Torres, J. F. Jimenez, A multicriteria simheuristic approach for solving a stochastic permutation flow shop scheduling problem, Algorithms, 14 (2021), 210. https://doi.org/10.3390/a14070210 doi: 10.3390/a14070210
[17]	J. Castaneda, X. A. Martin, M. Ammouriova, J. Panadero, A. A. Juan, A fuzzy simheuristic for the permutation flow shop problem under stochastic and fuzzy uncertainty, Mathematics, 10 (2022), 1760. https://doi.org/10.3390/math10101760 doi: 10.3390/math10101760
[18]	E. M. González-Neira, A. M. Urrego-Torres, A. M. Cruz-Riveros, C. Henao-García, J. R. Montoya-Torres, L. P. Molina-Sánchez, et al., Robust solutions in multi-objective stochastic permutation flow shop problem, Comput. Ind. Eng., 137 (2019), 106026. https://doi.org/10.1016/j.cie.2019.106026 doi: 10.1016/j.cie.2019.106026
[19]	K. Katragjini, E. Vallada, R. Ruiz, Flow shop rescheduling under different types of disruption, Int. J. Prod. Res., 51 (2013), 780–797. https://doi.org/10.1080/00207543.2012.666856 doi: 10.1080/00207543.2012.666856
[20]	P. Valledor, A. Gomez, P. Priore, J. Puente, Solving multi-objective rescheduling problems in dynamic permutation flow shop environments with disruptions, Int. J. Prod. Res., 56 (2018), 6363–6377. https://doi.org/10.1080/00207543.2018.1468095 doi: 10.1080/00207543.2018.1468095
[21]	G. Mosheiov, Scheduling jobs under simple linear deterioration, Comput. Oper. Res., 21 (1994), 653–659. https://doi.org/10.1016/0305-0548(94)90080-9 doi: 10.1016/0305-0548(94)90080-9
[22]	S. Alaswad, Y. Xiang, A review on condition-based maintenance optimization models for stochastically deteriorating system, Reliab. Eng. Syst. Saf., 157 (2017), 54–63. https://doi.org/10.1016/j.ress.2016.08.009 doi: 10.1016/j.ress.2016.08.009
[23]	T. Yang, Y. Kuo, I. Chang, Tabu-search simulation optimization approach for flow-shop scheduling with multiple processors—a case study, Int. J. Prod. Res., 42 (2004), 4015–4030. https://doi.org/10.1080/00207540410001699381 doi: 10.1080/00207540410001699381
[24]	R. Wallrath, M. B. Franke, Integration of MILP and discrete-event simulation for flow shop scheduling using Benders cuts, Comput. Chem. Eng., 189 (2024), 108809. https://doi.org/10.1016/j.compchemeng.2024.108809 doi: 10.1016/j.compchemeng.2024.108809
[25]	E. Azab, M. Nafea, L. A. Shihata, M. Mashaly, A machine-learning-assisted simulation approach for incorporating predictive maintenance in dynamic flow-shop scheduling, Appl. Sci., 11 (2021), 11725. https://doi.org/10.3390/app112411725 doi: 10.3390/app112411725
[26]	Y. Fu, Z. Li, K. Gao, A. M. Fathollahi-Fard, Z. Zhang, Integrated scheduling of distributed manufacturing with assembly and distribution: State of the art, challenges, and future directions, Int. J. Prod. Res., 64 (2026), 4669–4710. https://doi.org/10.1080/00207543.2025.2602898 doi: 10.1080/00207543.2025.2602898
[27]	A. M. Fathollahi-Fard, L. Woodward, O. Akhrif, A scenario-based robust optimization model for the sustainable distributed permutation flow-shop scheduling problem, Ann. Oper. Res., 2024. https://doi.org/10.1007/s10479-024-05940-7 doi: 10.1007/s10479-024-05940-7
[28]	D. M. Lei, B. Su, M. Li, Cooperated teaching-learning-based optimisation for distributed two-stage assembly flow shop scheduling, Int. J. Prod. Res., 59 (2021), 7232–7245. https://doi.org/10.1080/00207543.2020.1836422 doi: 10.1080/00207543.2020.1836422
[29]	M. Torkashvand, F. Ahmadizar, H. Farughi, Distributed production assembly scheduling with hybrid flowshop in assembly stage, Int. J. Eng., 35 (2022), 1037–1055. https://doi.org/10.5829/IJE.2022.35.05B.19 doi: 10.5829/IJE.2022.35.05B.19
[30]	G. H. Zhang, K. Y. Xing, G. Y. Zhang, Z. X. He, Memetic algorithm with meta-lamarckian learning and simplex search for distributed flexible assembly permutation flowshop scheduling problem, IEEE Access, 8 (2020), 96115–96128. https://doi.org/10.1109/ACCESS.2020.2996305 doi: 10.1109/ACCESS.2020.2996305
[31]	Y. D. Zuo, P. Wang, Z. Fan, M. Li, X. H. Guo, S. J. Gao, Minimizing fuzzy makespan in a distributed assembly flow shop by using an efficient artificial bee colony algorithm, J. Intell. Fuzzy Syst., 45 (2023), 7025–7046. https://doi.org/10.3233/JIFS-230592 doi: 10.3233/JIFS-230592
[32]	L. Cheng, L. Wang, J. C. Cai, A regional biogeography-based optimization algorithm for the distributed assembly permutation flow-shop scheduling problem with fuzzy processing time, J. Intell. Fuzzy Syst., 46 (2024), 3827–3841. https://doi.org/10.3233/JIFS-235854 doi: 10.3233/JIFS-235854
[33]	X. L. Jing, Q. K. Pan, L. Gao, Local search-based metaheuristics for the robust distributed permutation flowshop problem, Appl. Soft Comput., 105 (2021), 107247. https://doi.org/10.1016/j.asoc.2021.107247 doi: 10.1016/j.asoc.2021.107247
[34]	K. R. Baker, Introduction to sequencing and scheduling, Wiley, 1974.
[35]	C. L. Quintero-Araujo, J. P. Caballero-Villalobos, A. A. Juan, J. R. Montoya-Torres, A biased-randomized metaheuristic for the capacitated location routing problem, Int. Trans. Oper. Res., 24 (2017), 1079–1098. https://doi.org/10.1111/itor.12322 doi: 10.1111/itor.12322

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)