Research article Special Issues

Two-stage three-machine assembly flowshop scheduling with step learning: exact and metaheuristic approaches

  • Published: 12 November 2026
  • 90B35

  • 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

    Related Papers:

  • 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
  • Reader Comments
  • © 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)

Metrics

Article views(80) PDF downloads(22) Cited by(0)

Article outline

Figures and Tables

Figures(8)  /  Tables(5)

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog