The no-wait flow shop problem with makespan objective and learning effects

Jia-Ming Gu; Lin Lin; Ji-Bo Wang; Jia-Ming Gu; Lin Lin; Ji-Bo Wang

doi:10.3934/jimo.2026182

Journal of Industrial and Management Optimization

2026, Volume 22, Issue 10: 5275-5307. doi: 10.3934/jimo.2026182

Previous Article Next Article

Research article Special Issues

The no-wait flow shop problem with makespan objective and learning effects

School of Computer, Shenyang Aerospace University, Shenyang 110136, P.R. China

Received: 01 August 2026 Revised: 30 August 2026 Accepted: 11 September 2026 Published: 21 September 2026
90B35

The annealing operation of cold rolled coils follows a no-wait constraint between heating and rapid cooling, and manual operations generate learning effects on job processing times. This paper abstracts the annealing process of cold rolled coils as a two-machine no-wait flow shop scheduling problem with learning effects in which the actual processing time of a job depends on the sum of the logarithmic basic processing times of previous jobs. The optimization objective of this problem is minimizing the makespan to improve production efficiency for cold rolled coil annealing. We propose polynomial algorithms to solve two special dominating machine constraints and two special fixed processing times on the machine. For the problem, we propose a worst-case approximation ratio, a branch-and-bound algorithm and some heuristic algorithms. Computational results demonstrate that the genetic algorithm performs well for small-scale instances, while the $ NEH $ (Nawaz-Enscore-Ham) algorithm achieves better performance for large-scale instances.
- no-wait,
- flow shop scheduling,
- learning effect,
- branch-and-bound,
- heuristic
Citation: Jia-Ming Gu, Lin Lin, Ji-Bo Wang. The no-wait flow shop problem with makespan objective and learning effects[J]. Journal of Industrial and Management Optimization, 2026, 22(10): 5275-5307. doi: 10.3934/jimo.2026182

Related Papers:

Abstract

The annealing operation of cold rolled coils follows a no-wait constraint between heating and rapid cooling, and manual operations generate learning effects on job processing times. This paper abstracts the annealing process of cold rolled coils as a two-machine no-wait flow shop scheduling problem with learning effects in which the actual processing time of a job depends on the sum of the logarithmic basic processing times of previous jobs. The optimization objective of this problem is minimizing the makespan to improve production efficiency for cold rolled coil annealing. We propose polynomial algorithms to solve two special dominating machine constraints and two special fixed processing times on the machine. For the problem, we propose a worst-case approximation ratio, a branch-and-bound algorithm and some heuristic algorithms. Computational results demonstrate that the genetic algorithm performs well for small-scale instances, while the $ NEH $ (Nawaz-Enscore-Ham) algorithm achieves better performance for large-scale instances.

References

[1]	T. Wu, R. Q. Chen, Heuristic algorithm of scheduling model for cold coils annealing, 2006 6th World Congress on Intelligent Control and Automation, (2006), 7263–7266. https://doi.org/10.1109/WCICA.2006.1713398
[2]	Y. Lu, F. Teng, Z. Feng, Scheduling jobs with truncated exponential sum-of-logarithm-processing-times based and position-based learning effects, Asia-Pac J. Oper. Res., 32 (2015), 1–17. https://doi.org/10.1142/S0217595915500268 doi: 10.1142/S0217595915500268
[3]	X. Zhang, Y. Wang, S. Bai, Single-machine group scheduling problems with deteriorating and learning effect, Int. J. Syst. Sci., 47 (2016), 2402–2410. https://doi.org/10.1080/00207721.2014.998739 doi: 10.1080/00207721.2014.998739
[4]	Z. Jiang, F. Chen, X. Zhang, Single-machine scheduling with times-based and job-dependent learning effect, J. Oper. Res. Soc., 68 (2017), 809–815. https://doi.org/10.1057/jors.2016.40 doi: 10.1057/jors.2016.40
[5]	N. Yin, Single machine due window assignment resource allocation scheduling with job-dependent learning effect, J. Appl. Math. Comput., 56 (2018), 715–725. https://doi.org/10.1007/s12190-017-1091-6 doi: 10.1007/s12190-017-1091-6
[6]	A. Azzouz, M. Ennigrou, L. Ben Said, Scheduling problems under learning effects: classification and cartography, Int. J. Prod. Res., 56 (2018), 1642–1661. https://doi.org/10.1080/00207543.2017.1355576 doi: 10.1080/00207543.2017.1355576
[7]	C. Wu, W. Lin, X. Zhang, I. Chung, T. Yang, K. Lai, Tardiness minimisation for a customer order scheduling problem with sum-of-processing-time-based learning effect, J. Oper. Res. Soc., 70 (2019), 487–501. https://doi.org/10.1080/01605682.2018.1447249 doi: 10.1080/01605682.2018.1447249
[8]	J. Wang, M. Gao, J. Wang, L. Liu, H. He, Scheduling with a position-weighted learning effect and job release dates, Eng. Optim., 52 (2020), 1475–1493. https://doi.org/10.1080/0305215X.2019.1664498 doi: 10.1080/0305215X.2019.1664498
[9]	S. Zhao, Scheduling jobs with general truncated learning effects including proportional setup times, Comput. Appl. Math., 41 (2022), 146. https://doi.org/10.1007/s40314-022-01851-0 doi: 10.1007/s40314-022-01851-0
[10]	R. Ma, L. Zhang, Y. Zhang, A best possible algorithm for an online scheduling problem with position-based learning effect, J. Ind. Manag. Optim., 18 (2022), 3989–4010. https://doi.org/10.3934/jimo.2021144 doi: 10.3934/jimo.2021144
[11]	Y. Jiang, Z. Zhang, X. Song, Y. Yin, Seru scheduling problems with multiple due-windows assignment and learning effect, J. Syst. Sci. Syst. Eng., 31 (2022), 480–511. https://doi.org/10.1007/s11518-022-5534-8 doi: 10.1007/s11518-022-5534-8
[12]	D. Deliktas, Self-adaptive memetic algorithms for multi-objective single machine learning-effect scheduling problems with release times, Flex. Serv. Manuf. J., 34 (2022), 748–784. https://doi.org/10.1007/s10696-021-09434-7 doi: 10.1007/s10696-021-09434-7
[13]	N. Ren, J. Wang, E. Wang, Research on delivery times scheduling with truncated learning effects, Comput. Appl. Math., 42 (2023), 243. https://doi.org/10.1007/s40314-023-02379-7 doi: 10.1007/s40314-023-02379-7
[14]	Y. Luo, Stochastic single machine scheduling with time-dependent deterioration or position-dependent learning effect, Optim. Lett., 17 (2023), 1811–1832. https://doi.org/10.1007/s11590-022-01955-w doi: 10.1007/s11590-022-01955-w
[15]	J. Wang, D. Lv, J. Xu, P. Ji, F. Li, Bicriterion scheduling with truncated learning effects and convex controllable processing times, Int. Trans. Oper. Res., 28 (2021), 1573–1593. https://doi.org/10.1111/itor.12888 doi: 10.1111/itor.12888
[16]	B. Mor, D. Mor, N. Shani, D. Shapira, Single machine scheduling with generalized due-dates, learning effect, and job-rejection, J. Appl. Math. Comput., 70 (2024), 6063–6083. https://doi.org/10.1007/s12190-024-02198-x doi: 10.1007/s12190-024-02198-x
[17]	W. Liu, X. Wang, L. Li, W. Dai, Due-window assignment scheduling with job-rejection, truncated learning effects and setup times, J. Ind. Manag. Optim., 20 (2024), 313–324. https://doi.org/10.3934/jimo.2023079 doi: 10.3934/jimo.2023079
[18]	J. Gao, J. Zou, Y. Zhang, Single-machine scheduling with a deteriorating maintenance activity and DeJong's learning effect, Int. J. Found. Comput. Sci., 36 (2025), 635–648. https://doi.org/10.1142/S0129054122460030 doi: 10.1142/S0129054122460030
[19]	Y. Zhang, X. Sun, T. Liu, J. Wang, X. Geng, Single-machine scheduling simultaneous consideration of resource allocations and exponential time-dependent learning effects, J. Oper. Res. Soc., 76 (2025), 528–540. https://doi.org/10.1080/01605682.2024.2371527 doi: 10.1080/01605682.2024.2371527
[20]	B. Cheng, Y. Wang, M. Zhou, X. Zhu, Integrated scheduling of batch production and intermediate delivery with batch-position-based learning effect, Asia-Pac. J. Oper. Res., 42 (2025), 2550003. https://doi.org/10.1142/S0217595925500034 doi: 10.1142/S0217595925500034
[21]	L. Wang, Due-window assignment scheduling problems with position-dependent weights, truncated learning effects and past-sequence-dependent setup-times, Symmetry, 18 (2026), 396. https://doi.org/10.3390/sym18030396 doi: 10.3390/sym18030396
[22]	H. Song, J. Yang, J. Wang, Study on multiple due-windows assignment scheduling with learning and deteriorating effects, Asia-Pac. J. Oper. Res., (2026), 2650001. https://doi.org/10.1142/S0217595926500016
[23]	B. Cheng, W. Bao, J. Gao, Optimising batch operations under energy constraint with truncated position-based learning effect and ageing effect, J. Oper. Res. Soc., (2026), 1–16. https://doi.org/10.1080/01605682.2026.2621244
[24]	D. Shabtay, D. Oron, Proportionate flow-shop scheduling with rejection, J. Oper. Res. Soc., 67 (2016), 752–769. https://doi.org/10.1057/jors.2015.95 doi: 10.1057/jors.2015.95
[25]	N. Zhao, S. Ye, K. Li, S. Chen, Effective iterated greedy algorithm for flow-shop scheduling problems with time lags, Chin. J. Mech. Eng., 30 (2017), 652–662. https://doi.org/10.1007/s10033-017-0108-2 doi: 10.1007/s10033-017-0108-2
[26]	S. Sheikh, G. M. Komaki, V. Kayvanfar, E. Teymourian, Multi-stage assembly flow shop with setup time and release time, Oper. Res. Perspect., 6 (2019), 100111. https://doi.org/10.1016/j.orp.2019.100111 doi: 10.1016/j.orp.2019.100111
[27]	M. Al-Behadili, D. Ouelhadj, D. Jones, Multi-objective biased randomised iterated greedy for robust permutation flow shop scheduling problem under disturbances, J. Oper. Res. Soc., 71 (2020), 1847–1859. https://doi.org/10.1080/01605682.2019.1630330 doi: 10.1080/01605682.2019.1630330
[28]	J. Wang, D. Lv, C. Wan, Proportionate flow shop scheduling with job-dependent due windows and position-dependent weights, Asia-Pac. J. Oper. Res., 42 (2025), 2450011. https://doi.org/10.1142/S0217595924500118 doi: 10.1142/S0217595924500118
[29]	R. Jin, W. Tong, Y. Xu, J. Dong, Two-stage flexible flow shop scheduling in GPU systems, J. Oper. Res. Soc., 77 (2026), 793–804. https://doi.org/10.1080/01605682.2025.2504435 doi: 10.1080/01605682.2025.2504435
[30]	C. Wu, J. Chen, W. Lin, K. Lai, D. Bai, S. Lai, A two-stage three-machine assembly scheduling flowshop problem with both two-agent and learning phenomenon, Comput. Ind. Eng., 130 (2019), 485–499. https://doi.org/10.1016/j.cie.2019.02.047 doi: 10.1016/j.cie.2019.02.047
[31]	X. Sun, X. Geng, F. Liu, Flow shop scheduling with general position weighted learning effects to minimise total weighted completion time, J. Oper. Res. Soc., 72 (2021), 2674–2689. https://doi.org/10.1080/01605682.2020.1806746 doi: 10.1080/01605682.2020.1806746
[32]	D. Lv, J. Wang, Considering the peak power consumption problem with learning and deterioration effect in flow shop scheduling, Comput. Ind. Eng., 197 (2024), 110599. https://doi.org/10.1016/j.cie.2024.110599 doi: 10.1016/j.cie.2024.110599
[33]	M. Li, D. Lv, L. Zhang, J. Wang, Permutation flow shop scheduling with makespan objective and truncated learning effects, J. Appl. Math. Comput., 70 (2024), 2907–2939. https://doi.org/10.1007/s12190-024-02080-w doi: 10.1007/s12190-024-02080-w
[34]	Y. A. Paredes-Astudillo, V. Botta-Genoulaz, J. R. Montoya-Torres, Impact of learning effect modelling in flowshop scheduling with makespan minimisation based on the Nawaz-Enscore-Ham algorithm, Int. J. Prod. Res., 62 (2024), 1999–2014. https://doi.org/10.1080/00207543.2023.2204967 doi: 10.1080/00207543.2023.2204967
[35]	D. Lv, J. Wang, Research on two-machine flow shop scheduling problem with release dates and truncated learning effects, Eng. Optim., 57 (2025), 1828–1848. https://doi.org/10.1080/0305215X.2024.2372633 doi: 10.1080/0305215X.2024.2372633
[36]	K. Zhang, J. Wang, Y. Lu, On flowshop scheduling with the DeJong's learning effect, Asia-Pac. J. Oper. Res., (2026). https://doi.org/10.1142/S0217595926500296
[37]	M. S. Nagano, H. H. Miyata, Review and classification of constructive heuristics mechanisms for no-wait flow shop problem, Int. J. Adv. Manuf. Technol., 86 (2016), 2161–2174. https://doi.org/10.1007/s00170-015-8209-5 doi: 10.1007/s00170-015-8209-5
[38]	H. Singh, J. S. Oberoi, D. Singh, Multi-objective permutation and non-permutation flow shop scheduling problems with no-wait: a systematic literature review, RAIRO Oper. Res., 55 (2021), 27–50. https://doi.org/10.1051/ro/2020055 doi: 10.1051/ro/2020055
[39]	D. M. Utama, S. Z. Umamy, C. N. Al-Imron, No-Wait Flow Shop scheduling problem: a systematic literature review and bibliometric analysis, RAIRO Oper. Res., 58 (2024), 1281–1313. https://doi.org/10.1051/ro/2024008 doi: 10.1051/ro/2024008
[40]	H. Samarghandi, M. Behroozi, On the exact solution of the no-wait flow shop problem with due date constraints, Comput. Oper. Res., 81 (2017), 141–159. https://doi.org/10.1016/j.cor.2016.12.013 doi: 10.1016/j.cor.2016.12.013
[41]	H. Ye, W. Li, A. Abedini, B. Nault, An effective and efficient heuristic for no-wait flow shop production to minimize total completion time, Comput. Ind. Eng., 108 (2017), 57–69. https://doi.org/10.1016/j.cie.2017.04.002 doi: 10.1016/j.cie.2017.04.002
[42]	C. Koulamas, G. J. Kyparisis, The no-wait flow shop with rejection, Int. J. Prod. Res., 59 (2021), 1852–1859. https://doi.org/10.1080/00207543.2020.1727042 doi: 10.1080/00207543.2020.1727042
[43]	Y. Li, C. Zheng, X. Pei, Multi-search mechanism-improved differential evolution algorithm for the no-wait flow shop scheduling problem, Appl. Soft Comput., 175 (2025), 113094. https://doi.org/10.1016/j.asoc.2025.113094 doi: 10.1016/j.asoc.2025.113094
[44]	Y. Liu, Z. Feng, Two-machine no-wait flowshop scheduling with learning effect and convex resource-dependent processing times, Comput. Ind. Eng., 75 (2014), 170–175. https://doi.org/10.1016/j.cie.2014.06.017 doi: 10.1016/j.cie.2014.06.017
[45]	F. Gao, M. Liu, J. Wang, Y. Lu, No-wait two-machine permutation flow shop scheduling problem with learning effect, common due date and controllable job processing times, Int. J. Prod. Res., 56 (2018), 2361–2369. https://doi.org/10.1080/00207543.2017.1371353 doi: 10.1080/00207543.2017.1371353
[46]	W. Liu, C. Jiang, Flow shop resource allocation scheduling with due date assignment, learning effect and position-dependent weights, Asia-Pac. J. Oper. Res., 37 (2020), 2050014. https://doi.org/10.1142/S0217595920500141 doi: 10.1142/S0217595920500141
[47]	D. Lv, J. Wang, Study on resource-dependent no-wait flow shop scheduling with different due-window assignment and learning effects, Asia-Pac. J. Oper. Res., 38 (2021), 2150008. https://doi.org/10.1142/S0217595921500081 doi: 10.1142/S0217595921500081
[48]	Y. Sun, D. Lv, X. Huang, Properties for due window assignment scheduling on a two-machine no-wait proportionate flow shop with learning effects and resource allocation, J. Oper. Res. Soc., 77 (2026), 599–615. https://doi.org/10.1080/01605682.2025.2492817 doi: 10.1080/01605682.2025.2492817
[49]	J. Gu, J. Wang, Minimizing total completion time in no-wait flow shop scheduling with learning effects and group technology, J. Oper. Res. Soc., (2026), 1–22. https://doi.org/10.1080/01605682.2026.2721567
[50]	T. C. E. Cheng, P. Lai, C. Wu, W. Lee, Single-machine scheduling with sum-of-logarithm-processing-times-based learning considerations, Inf. Sci., 197 (2009), 3127–3135. https://doi.org/10.1016/j.ins.2009.05.002 doi: 10.1016/j.ins.2009.05.002
[51]	D. Biskup, A state-of-the-art review on scheduling with learning effects, Eur. J. Oper. Res., 188 (2008), 315–329. https://doi.org/10.1016/j.ejor.2007.05.040 doi: 10.1016/j.ejor.2007.05.040
[52]	P. C. Gilmore, R. E. Gomory, Sequencing a one state-variable machine: A solvable case of the traveling salesman problem, Oper. Res., 12 (1964), 655–679. https://doi.org/10.1287/opre.12.5.655 doi: 10.1287/opre.12.5.655
[53]	S. S. Reddi, C. V. Ramamoorthy, On the flow-shop sequencing problem with no wait in process, J. Oper. Res. Soc., 23 (1972), 323–331. https://doi.org/10.1057/jors.1972.52 doi: 10.1057/jors.1972.52
[54]	M. Nawaz, E. E. Enscore Jr, 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
[55]	I. H. Osman, C. N. Potts, Simulated annealing for permutation flow-shop scheduling, Omega, 17 (1989), 551–557. https://doi.org/10.1016/0305-0483(89)90059-5 doi: 10.1016/0305-0483(89)90059-5
[56]	L. Zhang, M. Li, L. Lin, Study on controllable processing time and minmax group scheduling with common due-window assignment, Symmetry, 18 (2026), 358. https://doi.org/10.3390/sym18020358 doi: 10.3390/sym18020358
[57]	Z. Sun, D. Lv, P. Ji, J. Wang, Minimizing total completion time scheduling problem with ready times and linear deterioration functions of processing times, J. Appl. Math. Comput., 72 (2026), 42. https://doi.org/10.1007/s12190-025-02694-8 doi: 10.1007/s12190-025-02694-8
[58]	Z. Wang, Optimal scheduling of flow shop based on genetic algorithm, J. Adv. Manuf. Syst., 21 (2022), 111–123. https://doi.org/10.1142/S021968672150044X doi: 10.1142/S021968672150044X
[59]	O. A. Arik, Genetic algorithm application for permutation flow shop scheduling problems, Gazi Univ. J. Sci., 35 (2022), 92–111. https://doi.org/10.35378/gujs.682388 doi: 10.35378/gujs.682388
[60]	M. S. Umam, M. Mustafid, S. Suryono, A hybrid genetic algorithm and tabu search for minimizing makespan in flow shop scheduling problem, J. King Saud Univ. Comput. Inf. Sci., 34 (2022), 7459–7467. https://doi.org/10.1016/j.jksuci.2021.08.025 doi: 10.1016/j.jksuci.2021.08.025
[61]	N. Yin, M. Gao, Single-machine group scheduling with general linear deterioration and truncated learning effects, Comput. Appl. Math., 43 (2024), 386. https://doi.org/10.1007/s40314-024-02881-6 doi: 10.1007/s40314-024-02881-6
[62]	D. Lv, J. Wang, Single-machine group technology scheduling with resource allocation and slack due window assignment including minmax criterion, J. Oper. Res. Soc., 76 (2025), 1696–1712. https://doi.org/10.1080/01605682.2024.2430351 doi: 10.1080/01605682.2024.2430351
[63]	N. Yin, H. He, Y. Zhao, Y. Chang, N. Wang, Integrating group setup time deterioration effects and job processing time learning effects with group technology in single-machine green scheduling, Axioms, 14 (2025), 480. https://doi.org/10.3390/axioms14070480 doi: 10.3390/axioms14070480
[64]	L. Zhang, J. Wang, Resource allocation and minmax scheduling under group technology and different due-window assignments, Axioms, 14 (2025), 827. https://doi.org/10.3390/axioms14110827 doi: 10.3390/axioms14110827
[65]	L. Zhang, N. Yin, Study on single-machine group scheduling with convex resource allocations and different due-date assignments, Bull. Malays. Math. Sci. Soc., 49 (2026), 33. https://doi.org/10.1007/s40840-025-02031-z doi: 10.1007/s40840-025-02031-z
[66]	R. Mao, Y. Wang, D. Lv, J. Wang, Y. Lu, Delivery times scheduling with deterioration effects in due window assignment environments, Mathematics, 11 (2023), 3983. https://doi.org/10.3390/math11183983 doi: 10.3390/math11183983
[67]	X. Sun, T. Liu, X. Geng, Y. Hu, J. Xu, Optimization of scheduling problems with deterioration effects and an optional maintenance activity, J. Sched., 26 (2023), 251–266. https://doi.org/10.1007/s10951-022-00756-4 doi: 10.1007/s10951-022-00756-4
[68]	F. Kong, C. Miao, Y. Huo, J. Song, Y. Zhang, Single-machine scheduling with step-deteriorating jobs and rejection, J. Oper. Res. Soc. China, 12 (2024), 1088–1102. https://doi.org/10.1007/s40305-023-00481-5 doi: 10.1007/s40305-023-00481-5
[69]	Q. Kong, C. Wei, J. Wang, Minmax delivery completion time scheduling with delivery times and deteriorating jobs, Comput. Appl. Math., 45 (2026), 276. https://doi.org/10.1007/s40314-026-03684-7 doi: 10.1007/s40314-026-03684-7
[70]	B. Choi, E. Kim, J. Lee, Scheduling step-deteriorating jobs on a single machine with multiple critical dates, J. Oper. Res. Soc., 76 (2025), 1553–1563. https://doi.org/10.1080/01605682.2024.2419979 doi: 10.1080/01605682.2024.2419979
[71]	L. Zhang, J. Wang, P. Ji, Group parallel-batching scheduling with position-dependent learning and time-dependent deterioration effects, Comput. Appl. Math., 46 (2027), 45. https://doi.org/10.1007/s40314-026-03899-8 doi: 10.1007/s40314-026-03899-8
[72]	J. Qian, Z. Guo, Common due window assignment and single machine scheduling with delivery time, resource allocation, and job-dependent learning effect, J. Appl. Math. Comput., 70 (2024), 4441–4471. https://doi.org/10.1007/s12190-024-02090-8 doi: 10.1007/s12190-024-02090-8
[73]	J. Wang, Y. Wang, C. Wan, D. Lv, L. Zhang, Controllable processing time scheduling with total weighted completion time objective and deteriorating jobs, Asia-Pac. J. Oper. Res., 41 (2024), 2350026. https://doi.org/10.1142/S0217595923500264 doi: 10.1142/S0217595923500264
[74]	X. Wang, W. Liu, Single machine group scheduling jobs with resource allocations subject to unrestricted due date assignments, J. Appl. Math. Comput., 70 (2024), 6283–6308. https://doi.org/10.1007/s12190-024-02216-y doi: 10.1007/s12190-024-02216-y
[75]	S. Kovalev, I. Chalamon, A. Becuwe, Single machine scheduling with resource constraints: Equivalence to two-machine flow-shop scheduling for regular objectives, J. Oper. Res. Soc., 75 (2024), 1343–1346. https://doi.org/10.1080/01605682.2023.2244529 doi: 10.1080/01605682.2023.2244529
[76]	Y. Lu, M. Li, A unified analysis for single-machine scheduling with resource allocations, learning and deteriorating effects simultaneously, Comput. Appl. Math., 45 (2026), 388. https://doi.org/10.1007/s40314-026-03784-4 doi: 10.1007/s40314-026-03784-4

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)