In this paper, we addressed a scheduling challenge in a two-stage, three-machine flow-shop assembly problem with step learning. In this setting, each job had a machine-specific learning date, after which its processing time was reduced if processing began on or after that date. Our goal was to devise a schedule that minimized the makespan for the given jobs. This problem was categorized as NP-hard, as it could be reduced to a similar problem without learning dates. To address this issue, we formulated a mixed-integer programming model and developed two lemmas along with a lower bound, which were incorporated into a branch-and-bound algorithm to achieve an optimal solution. Additionally, we proposed two heuristics derived from the Johnson rule, including enhanced versions utilizing a swapping scheme. We also applied these Johnson-based heuristics in an iterated greedy algorithm, a population-based genetic algorithm, and simulated annealing algorithm to effectively approximate the solutions. Finally, we performed numerical experiments to assess the efficacy of all the proposed methods.
Citation: Chin-Chia Wu, Juin-Han Chen, Xin-Gong Zhang, Chao-Chung Kang, Ching-Yuan Huang, Jian-You Xu, Jatinder N.D. Gupta. Two-stage three-machine assembly flowshop scheduling with step learning: exact and metaheuristic approaches[J]. Journal of Industrial and Management Optimization, 2026, 22(12): 6475-6502. doi: 10.3934/jimo.2026217
In this paper, we addressed a scheduling challenge in a two-stage, three-machine flow-shop assembly problem with step learning. In this setting, each job had a machine-specific learning date, after which its processing time was reduced if processing began on or after that date. Our goal was to devise a schedule that minimized the makespan for the given jobs. This problem was categorized as NP-hard, as it could be reduced to a similar problem without learning dates. To address this issue, we formulated a mixed-integer programming model and developed two lemmas along with a lower bound, which were incorporated into a branch-and-bound algorithm to achieve an optimal solution. Additionally, we proposed two heuristics derived from the Johnson rule, including enhanced versions utilizing a swapping scheme. We also applied these Johnson-based heuristics in an iterated greedy algorithm, a population-based genetic algorithm, and simulated annealing algorithm to effectively approximate the solutions. Finally, we performed numerical experiments to assess the efficacy of all the proposed methods.
| [1] |
D. Biskup, Single-machine scheduling with learning considerations, Eur. J. Oper. Res. , 115 (1999), 173–178. https://doi.org/10.1016/S0377-2217(98)00246-X doi: 10.1016/S0377-2217(98)00246-X
|
| [2] |
C. Koulamas, G. J. Kyparisis, Single-machine and two-machine flowshop scheduling with general learning functions, Eur. J. Oper. Res. , 178 (2007), 402–407. https://doi.org/10.1016/j.ejor.2006.01.030 doi: 10.1016/j.ejor.2006.01.030
|
| [3] |
W. H. Kuo, D. L. Yang, Minimizing the total completion time in a single-machine scheduling problem with a time-dependent learning effect, Eur. J. Oper. Res. , 174 (2006), 1184–1190. https://doi.org/10.1016/j.ejor.2005.03.020 doi: 10.1016/j.ejor.2005.03.020
|
| [4] |
T. C. E. Cheng, G. Wang, Single machine scheduling with learning effect considerations, Ann. Oper. Res. , 98 (2000), 273–290. https://doi.org/10.1023/A:1019216726076 doi: 10.1023/A:1019216726076
|
| [5] |
J. B. Wang, Single-machine scheduling problems with the effects of learning and deterioration, Omega, 35 (2007), 397–402. https://doi.org/10.1016/j.omega.2005.07.008 doi: 10.1016/j.omega.2005.07.008
|
| [6] |
Y. Yin, D. Xu, K. Sun, H. Li, Some scheduling problems with general position-dependent and time-dependent learning effects, Inf. Sci. , 179 (2009), 2416–2425. https://doi.org/10.1016/j.ins.2009.02.015 doi: 10.1016/j.ins.2009.02.015
|
| [7] |
J. B. Wang, J. J. Wang, Single machine scheduling with sum-of-logarithm-processing-times based and position-based learning effects, Optim. Lett. , 8 (2014), 971–982. https://doi.org/10.1007/s11590-012-0494-4 doi: 10.1007/s11590-012-0494-4
|
| [8] |
Y. P. Niu, L. Wan, J. B. Wang, A note on scheduling jobs with extended sum-of-processing-times-based and position-based learning effect, Asia-Pac. J. Oper. Res. , 32 (2015), 1550001. https://doi.org/10.1142/S0217595915500013 doi: 10.1142/S0217595915500013
|
| [9] |
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
|
| [10] |
D. Biskup, A state-of-the-art review on scheduling with learning effect, 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
|
| [11] |
A. Janiak, T. Krysiak, R. Trela, Scheduling problems with learning and ageing effects: a survey, Decis. Mak. Manuf. Serv. , 5 (2011), 19–36. https://doi.org/10.7494/dmms.2011.5.1.19 doi: 10.7494/dmms.2011.5.1.19
|
| [12] |
C. C. Wu, J. Y. Chen, W. C. Lin, K. Lai, S. C. Liu, P. W. Yu, A two-stage three-machine assembly flow shop scheduling with learning consideration to minimize the flowtime by six hybrids of particle swarm optimization, Swarm Evol. Comput. , 41 (2018), 97–110. https://doi.org/10.1016/j.swevo.2018.01.012 doi: 10.1016/j.swevo.2018.01.012
|
| [13] |
W. C. Lin, Minimizing the makespan for two-stage three-machine assembly flow shop problem with the sum-of-processing-time based learning effect, Discrete Dyn. Nat. Soc. , 2018 (2018), 8170294. https://doi.org/10.1155/2018/8170294 doi: 10.1155/2018/8170294
|
| [14] |
Y. Zou, D. J. Wang, W. C. Lin, J. Y. Chen, P. W. Yu, W. H. Wu, et al., Two-stage three-machine assembly scheduling problem with sum-of-processing-times based learning effect, Soft Comput. , 24 (2020), 5445–5462. https://doi.org/10.1007/s00500-019-04301-y doi: 10.1007/s00500-019-04301-y
|
| [15] |
A. Azzouz, P. A. Pan, P. H. Hsu, W. C. Lin, S. C. Liu, L. Ben Said, et al., A two-stage three-machine assembly scheduling problem with a truncation position-based learning effect, Soft Comput. , 24 (2020), 10515–10531. https://doi.org/10.1007/s00500-019-04561-8 doi: 10.1007/s00500-019-04561-8
|
| [16] |
C. C. Wu, X. Zhang, A. Ameni, W. L. Shen, S. R. Cheng, P. H. Hsu, et al., Metaheuristics for two-stage flow-shop assembly problem with a truncation learning function, Eng. Optim. , 53 (2021), 843–866. https://doi.org/10.1080/0305215X.2020.1757089 doi: 10.1080/0305215X.2020.1757089
|
| [17] |
J. Wang, D. Lei, J. Cai, An adaptive artificial bee colony with reinforcement learning for distributed three-stage assembly scheduling with maintenance, Appl. Soft Comput. , 117 (2022), 108371. https://doi.org/10.1016/j.asoc.2021.108371 doi: 10.1016/j.asoc.2021.108371
|
| [18] |
M. Rostami, A. Yousefzadeh, A gamified teaching-learning based optimization algorithm for a three-echelon supply chain scheduling problem in a two-stage assembly flow shop environment, Appl. Soft Comput. , 146 (2023), 110598. https://doi.org/10.1016/j.asoc.2023.110598 doi: 10.1016/j.asoc.2023.110598
|
| [19] |
W. Lin, J. Chen, Deep reinforcement learning for dynamic scheduling of two-stage assembly flowshop, in: Advances in Swarm Intelligence, Springer, (2021), 248–258. https://doi.org/10.1007/978-3-030-78811-7_25 10.1007/978-3-030-78811-7_25 |
| [20] |
K. C. Ying, S. W. Lin, K. F. Chen, Minimising makespan in distributed assembly hybrid flowshop scheduling problems, Int. J. Prod. Res. , 63 (2025), 1674–1691. https://doi.org/10.1080/00207543.2024.2383781 doi: 10.1080/00207543.2024.2383781
|
| [21] |
E. S. Kim, D. Oron, Minimizing total completion time on a single machine with step improving jobs, J. Oper. Res. Soc. , 66 (2015), 1481–1490. https://doi.org/10.1057/jors.2014.91 doi: 10.1057/jors.2014.91
|
| [22] |
J. Y. Xu, W. C. Lin, Y. W. Chang, Y. H. Chung, J. H. Chen, C. C. Wu, A two-machine learning-date flowshop scheduling problem with heuristics and population-based GA to minimize the makespan, Mathematics, 11 (2023), 4060. https://doi.org/10.3390/math11194060 doi: 10.3390/math11194060
|
| [23] |
M. Atsmony, B. Mor, G. Mosheiov, Single machine scheduling with step-learning, J. Sched. , 27 (2024), 227–237. https://doi.org/10.1007/s10951-022-00763-5 doi: 10.1007/s10951-022-00763-5
|
| [24] |
J. Song, C. Miao, F. Kong, Scheduling with step learning and job rejection, Oper. Res. Int. J. , 25 (2025), 6. https://doi.org/10.1007/s12351-024-00887-w doi: 10.1007/s12351-024-00887-w
|
| [25] |
J. Phosavanh, D. Oron, Minimizing total weighted late work with step-learning on a single machine, Discrete Appl. Math. , 391 (2026), 277–293. https://doi.org/10.1016/j.dam.2026.04.045 doi: 10.1016/j.dam.2026.04.045
|
| [26] |
Y. Jiang, H. Lin, J. Dong, T. C. E. Cheng, M. Ji, Single-machine scheduling with learning dates, Eur. J. Oper. Res., (2026). https://doi.org/10.1016/j.ejor.2026.08.033 10.1016/j.ejor.2026.08.033 |
| [27] |
M. Kong, Y. Zhang, J. Xu, W. Wang, S. Lu, A. M. Fathollahi-Fard, A green scheduling model for two-stage photo-etching and acid-etching collaboration in semiconductor manufacturing, J. Ind. Inf. Integr. , 41 (2024), 100655. https://doi.org/10.1016/j.jii.2024.100655 doi: 10.1016/j.jii.2024.100655
|
| [28] |
H. Kazemi, M. Nourelfath, A. M. Fathollahi-Fard, M. Gendreau, Integrated two-stage multi-factory assembly scheduling with maintenance considerations, Int. J. Prod. Res. , 63 (2025), 2133–2149. https://doi.org/10.1080/00207543.2024.2396512 doi: 10.1080/00207543.2024.2396512
|
| [29] |
S. Lu, X. Zhang, M. Kong, A. M. Fathollahi-Fard, Two-stage hybrid flow shop scheduling with sequence-dependent setup times in semiconductor manufacturing: a customized variable neighborhood search, Ann. Oper. Res., (2025). https://doi.org/10.1007/s10479-025-06541-8 10.1007/s10479-025-06541-8 |
| [30] |
D. Y. Lv, J. B. 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
|
| [31] |
K. F. Zhang, J. F. Zhang, J. B. Wang, Single-machine linear resource-dependent consumption scheduling with DeJong's time-dependent learning effect, J. Ind. Manag. Optim. , 22 (2026), 4422–4448. https://doi.org/10.3934/jimo.2026154 doi: 10.3934/jimo.2026154
|
| [32] |
J. M. Gu, J. B. Wang, Minimising total completion time in no-wait flow shop scheduling with learning effects and group technology, J. Oper. Res. Soc., (2026). https://doi.org/10.1080/01605682.2026.2721567 10.1080/01605682.2026.2721567 |
| [33] |
J. M. Gu, L. Lin, J. B. Wang, The no-wait flow shop problem with makespan objective and learning effects, J. Ind. Manag. Optim. , 22 (2026), 5275–5307. https://doi.org/10.3934/jimo.2026182 doi: 10.3934/jimo.2026182
|
| [34] |
Y. Y. Lu, M. H. 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
|
| [35] |
D. Y. Lv, Y. B. Wu, Single-machine just-in-time scheduling problem with learning/deterioration effects and past-sequence-dependent delivery times, J. Oper. Res. Soc., (2026). https://doi.org/10.1080/01605682.2026.2731156 10.1080/01605682.2026.2731156 |
| [36] |
L. Y. 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
|
| [37] |
L. H. Zhang, J. B. 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
|
| [38] |
R. L. Graham, E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: a survey, Ann. Discrete Math. , 5 (1979), 287–326. https://doi.org/10.1016/S0167-5060(08)70356-X doi: 10.1016/S0167-5060(08)70356-X
|
| [39] |
C. Y. Lee, T. C. E. Cheng, B. M. T. Lin, Minimizing the makespan in the 3-machine assembly-type flowshop scheduling problem, Manage. Sci. , 39 (1993), 616–625. https://doi.org/10.1287/mnsc.39.5.616 doi: 10.1287/mnsc.39.5.616
|
| [40] |
S. K. Iyer, B. S. Saxena, Improved memetic genetic algorithm for the permutation flowshop scheduling problem, Comput. Oper. Res. , 31 (2004), 593–606. https://doi.org/10.1016/S0305-0548(03)00016-9 doi: 10.1016/S0305-0548(03)00016-9
|
| [41] |
I. Ribas, R. Companys, X. Tort-Martorell, An iterated greedy algorithm for the flowshop scheduling problem with blocking, Omega, 39 (2011), 293–301. https://doi.org/10.1016/j.omega.2010.07.007 doi: 10.1016/j.omega.2010.07.007
|
| [42] |
R. Ruiz, T. Stützle, An iterated greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives, Eur. J. Oper. Res. , 187 (2008), 1143–1159. https://doi.org/10.1016/j.ejor.2006.07.029 doi: 10.1016/j.ejor.2006.07.029
|
| [43] |
M. Shehab, M. A. Abu-Hashem, M. K. Y. Shambour, A. I. Alsalibi, O. A. Alomari, J. N. D. Gupta, et al., A comprehensive review of bat inspired algorithm: variants, applications, and hybridization, Arch. Comput. Methods Eng. , 30 (2023), 765–797. https://doi.org/10.1007/s11831-022-09817-5 doi: 10.1007/s11831-022-09817-5
|
| [44] |
F. Xiong, K. Xing, Meta-heuristics for the distributed two-stage assembly scheduling problem with bi-criteria of makespan and mean completion time, Int. J. Prod. Res. , 52 (2014), 2743–2766. https://doi.org/10.1080/00207543.2014.884290 doi: 10.1080/00207543.2014.884290
|
| [45] |
Y. Z. Li, Q. K. Pan, J. Q. Li, L. Gao, M. F. Tasgetiren, An adaptive iterated greedy algorithm for distributed mixed no-idle permutation flowshop scheduling problems, Swarm Evol. Comput. , 63 (2021), 100874. https://doi.org/10.1016/j.swevo.2021.100874 doi: 10.1016/j.swevo.2021.100874
|
| [46] |
H. Li, X. Li, L. Gao, An iterated greedy algorithm with acceleration of job allocation probability for distributed heterogeneous permutation flowshop scheduling problem, Swarm Evol. Comput. , 88 (2024), 101580. https://doi.org/10.1016/j.swevo.2024.101580 doi: 10.1016/j.swevo.2024.101580
|
| [47] |
Q. Y. Li, Q. K. Pan, L. Gao, H. Y. Sang, X. X. Zhang, W. M. Li, The constrained permutation flowshop problem: an effective two-stage iterated greedy algorithm to minimize weighted tardiness, Swarm Evol. Comput. , 91 (2024), 101696. https://doi.org/10.1016/j.swevo.2024.101696 doi: 10.1016/j.swevo.2024.101696
|
| [48] |
Z. Shao, W. Shao, D. Pi, Effective heuristics and metaheuristics for the distributed fuzzy blocking flow-shop scheduling problem, Swarm Evol. Comput. , 59 (2020), 100747. https://doi.org/10.1016/j.swevo.2020.100747 doi: 10.1016/j.swevo.2020.100747
|
Flowchart of the simulated annealing algorithm
Flowchart of the heuristic-based genetic algorithm
Flowchart of the iterated greedy algorithm
Exploring the values of parameters used in SA, GA, and IG (small job size)
Exploring the values of parameters used in SA, GA, and IG (large job size)
Box of distribution of AEP for eight proposed algorithms
Box plot of distribution of RPDs for eight proposed algorithms
Box plot of CPU times (in sec.) for eight algorithms at a large job case