Search Advanced

Journal of Industrial and Management Optimization

2026, Volume 22, Issue 4: 1609-1628. doi: 10.3934/jimo.2026059
Previous Article Next Article
Research article

Algorithms for a 2-stage hybrid flow shop scheduling problem with two classes of jobs

  • 1.
    Division of Business Administration & Accounting, Kangwon National University Kangwondaehak-gil, Chuncheon-si, Gangwon-do 24341, Republic of Korea
  • 2.
    Division of Business Administration & Accounting, Kongju National University 56, Gongjudaehak-ro, Gongju-si, Chungcheongnam-do 32588, Republic of Korea
  • Published: 09 March 2026

  • 90B35, 90C59, 90C29

  • This study addresses the complex 2-stage hybrid flow shop (HFS) scheduling problem, which involves urgent and normal jobs in a multi-agent context. The goal is to simultaneously minimize the makespan for normal jobs and the total tardiness for urgent jobs. Our proposed approaches include a Mixed-Integer Programming (MIP) model, list scheduling algorithms (MEDD, MEDD2), constructive algorithms (MNEH, MN-NEH, MFL, MN-MFL), and a simulated annealing (SA) metaheuristic to find practical solutions. Extensive experiments, using randomly generated instances which reflect real manufacturing environments, validate the algorithms' performance. The SA algorithm consistently exhibits a superior and robust performance across all scenarios, finding solutions remarkably close to the optimal. Additionally, MFL and MN-MFL show noteworthy efficiencies and stable performances, indicating their potential for practical applications in rapid decision-making environments.

    Citation: Ju-Yong Lee, BongJoo Jeong. Algorithms for a 2-stage hybrid flow shop scheduling problem with two classes of jobs[J]. Journal of Industrial and Management Optimization, 2026, 22(4): 1609-1628. doi: 10.3934/jimo.2026059

    Related Papers:

  • This study addresses the complex 2-stage hybrid flow shop (HFS) scheduling problem, which involves urgent and normal jobs in a multi-agent context. The goal is to simultaneously minimize the makespan for normal jobs and the total tardiness for urgent jobs. Our proposed approaches include a Mixed-Integer Programming (MIP) model, list scheduling algorithms (MEDD, MEDD2), constructive algorithms (MNEH, MN-NEH, MFL, MN-MFL), and a simulated annealing (SA) metaheuristic to find practical solutions. Extensive experiments, using randomly generated instances which reflect real manufacturing environments, validate the algorithms' performance. The SA algorithm consistently exhibits a superior and robust performance across all scenarios, finding solutions remarkably close to the optimal. Additionally, MFL and MN-MFL show noteworthy efficiencies and stable performances, indicating their potential for practical applications in rapid decision-making environments.



    加载中


    [1] J. S. Neufeld, S. Schulz, U. Buscher, A systematic review of multi-objective hybrid flow shop scheduling, Eur. J. Oper. Res., 309 (2023), 1–23. https://doi.org/10.1016/j.ejor.2022.08.009 doi: 10.1016/j.ejor.2022.08.009
    [2] B. J. Jeong, S. O. Shim, Heuristic algorithms for two-machine re-entrant flowshop scheduling problem with jobs of two classes, J. Adv. Mech. Des. Syst. Manuf., 11 (2017), JAMDSM0062. https://doi.org/10.1299/jamdsm.2017jamdsm0062 doi: 10.1299/jamdsm.2017jamdsm0062
    [3] T. Kis, E. Pesch, A review of exact solution methods for the non-preemptive multiprocessor flowshop problem, Eur. J. Oper. Res., 164 (2005), 592–608. https://doi.org/10.1016/j.ejor.2003.12.026 doi: 10.1016/j.ejor.2003.12.026
    [4] J. Liang, P. Wang, L. Guo, B. Qu, C. Yue, K. Yu, et al., Multi-objective flow shop scheduling with limited buffers using hybrid self-adaptive differential evolution, Memetic Comput., 11 (2019), 407–422. https://doi.org/10.1007/s12293-019-00290-5 doi: 10.1007/s12293-019-00290-5
    [5] V. Anjana, R. Sridharan, P. N. Ram Kumar, Metaheuristics for solving a multi-objective flow shop scheduling problem with sequence-dependent setup times, J. Sched., 23 (2020), 49–69. https://doi.org/10.1007/s10951-019-00610-0 doi: 10.1007/s10951-019-00610-0
    [6] A. P. Rifai, S. T. W. Mara, A. Sudiarso, Multi-objective distributed reentrant permutation flow shop scheduling with sequence-dependent setup time, Expert Syst. Appl., 183 (2021), 115339. https://doi.org/10.1016/j.eswa.2021.115339 doi: 10.1016/j.eswa.2021.115339
    [7] Y. Han, J. Li, H. Sang, Y. Liu, K. Gao, Q. Pan, Discrete evolutionary multi-objective optimization for energy-efficient blocking flow shop scheduling with setup time, Appl. Soft Comput., 93 (2020), 106343. https://doi.org/10.1016/j.asoc.2020.106343 doi: 10.1016/j.asoc.2020.106343
    [8] C. Lu, L. Gao, J. Yi, X. Li, Energy-efficient scheduling of distributed flow shop with heterogeneous factories: A real-world case from automobile industry in China, IEEE Trans. Ind. Inform., 17 (2021), 6687–6696. https://doi.org/10.1109/TII.2020.3043734 doi: 10.1109/TII.2020.3043734
    [9] B. Zhang, Q. Pan, L. Gao, X. Li, L. Meng, K. Peng, A multiobjective evolutionary algorithm based on decomposition for hybrid flowshop green scheduling problem, Comput. Ind. Eng., 136 (2019), 325–344. https://doi.org/10.1016/j.cie.2019.07.036 doi: 10.1016/j.cie.2019.07.036
    [10] B. G. Yılmaz, Ö. F. Yılmaz, F. B. Yeni, Comparison of lot streaming division methodologies for multi-objective hybrid flowshop scheduling problem by considering limited waiting time, J. Ind. Manag. Optim., 20 (2024), 3373–3414. https://doi.org/10.3934/jimo.2024058 doi: 10.3934/jimo.2024058
    [11] X. Liu, X. Chen, Y. Zhao, X. Liu, C. C. Wu, W. C. Lin, A multi-objective flexible flow shop scheduling problem with an improved NSGA-Ⅱ algorithm, J. Ind. Manag. Optim., 21 (2025), 4041–4062. https://doi.org/10.3934/jimo.2025042 doi: 10.3934/jimo.2025042
    [12] Z. H. Jia, T. Wu, H. Zhang, C. Liu, K. Li, An energy-efficient scheduling approach for a two-stage hybrid flow shop with parallel batch machines, Eur. J. Oper. Res., 328 (2026), 762–784. https://doi.org/10.1016/j.ejor.2025.07.055 doi: 10.1016/j.ejor.2025.07.055
    [13] Q. Peng, K. Gao, Y. Fu, J. Li, H. F. Rahman, Integrating meta-heuristics and Q-learning for solving hybrid flow shop scheduling and rescheduling problems with reentrant, J. Ind. Manag. Optim., 21 (2025), 6023–6043. https://doi.org/10.3934/jimo.2025121 doi: 10.3934/jimo.2025121
    [14] M. Rauf, Z. Guan, S. Sarfraz, J. Mumtaz, S. Almaiman, E. Shehab, et al., Multi-criteria inventory classification based on multi-criteria decision-making (Mcdm) technique, In: Advances in Manufacturing Technology, 8 (2018), 343–348. https://doi.org/10.3233/978-1-61499-902-7-343
    [15] M. Rauf, Z. Guan, S. Sarfraz, J. Mumtaz, E. Shehab, M. Jahanzaib, et al., A smart algorithm for multi-criteria optimization of model sequencing problem in assembly lines, Robot. Comput. Integr. Manuf., 61 (2020), 101844. https://doi.org/10.1016/j.rcim.2019.101844 doi: 10.1016/j.rcim.2019.101844
    [16] A. Agnetis, P. B. Mirchandani, D. Pacciarelli, A. Pacifici, Scheduling problems with two competing agents, Oper. Res., 52 (2004), 229–242. https://doi.org/10.1287/opre.1030.0092 doi: 10.1287/opre.1030.0092
    [17] K. R. Baker, J. Cole Smith, A multiple-criterion model for machine scheduling, J. Sched., 6 (2003), 7–16. https://doi.org/10.1023/A:1022231419049 doi: 10.1023/A:1022231419049
    [18] C. T. Ng, T. C. E. Cheng, J. J. Yuan, A note on the complexity of the problem of two-agent scheduling on a single machine, J. Combin. Optim., 12 (2006), 387–394. https://doi.org/10.1007/s10878-006-9001-0 doi: 10.1007/s10878-006-9001-0
    [19] J. Y. T. Leung, M. Pinedo, G. Wan, Competitive two-agent scheduling and its applications, Oper. Res., 58 (2010), 458–469. https://doi.org/10.1287/opre.1090.0744 doi: 10.1287/opre.1090.0744
    [20] T. C. E. Cheng, C. T. Ng, J. J. Yuan, Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs, Theor. Comput. Sci., 362 (2006), 273–281. https://doi.org/10.1016/j.tcs.2006.07.011 doi: 10.1016/j.tcs.2006.07.011
    [21] T. C. E. Cheng, C. T. Ng, J. J. Yuan, Multi-agent scheduling on a single machine with max-form criteria, Eur. J. Oper. Res., 188 (2008), 603–609. https://doi.org/10.1016/j.ejor.2007.04.040 doi: 10.1016/j.ejor.2007.04.040
    [22] P. Liu, L. Tang, Two-agent scheduling with linear deteriorating jobs on a single machine, In: Lecture Notes in Computer Science, Heidelberg: Springer Berlin Heidelberg, 2008. https://doi.org/10.1007/978-3-540-69733-6_63
    [23] W. C. Lee, Y. H. Chung, Z. R. Huang, A single-machine bi-criterion scheduling problem with two agents, Appl. Math. Comput., 219 (2013), 10831–10841. https://doi.org/10.1016/j.amc.2013.05.025 doi: 10.1016/j.amc.2013.05.025
    [24] L. Wan, J. Yuan, L. Wei, Pareto optimization scheduling with two competing agents to minimize the number of tardy jobs and the maximum cost, Appl. Math. Comput., 273 (2016), 912–923. https://doi.org/10.1016/j.amc.2015.10.059 doi: 10.1016/j.amc.2015.10.059
    [25] W.-C. Lee, S.-K. Chen, C.-C. Wu, Branch-and-bound and simulated annealing algorithms for a two-agent scheduling problem, Expert Syst. Appl., 37 (2010), 6594–6601. https://doi.org/10.1016/j.eswa.2010.02.125 doi: 10.1016/j.eswa.2010.02.125
    [26] W. C. Lee, S. K. Chen, C. W. Chen, C. C. Wu, A two-machine flowshop problem with two agents, Comput. Oper. Res., 38 (2011), 98–104. https://doi.org/10.1016/j.cor.2010.04.002 doi: 10.1016/j.cor.2010.04.002
    [27] B. Mor, G. Mosheiov, Polynomial time solutions for scheduling problems on a proportionate flowshop with two competing agents, J. Oper. Res. Soc., 65 (2014), 151–157. https://doi.org/10.1057/jors.2013.9 doi: 10.1057/jors.2013.9
    [28] B. J. Jeong, Y. D. Kim, S. O. Shim, Algorithms for a two-machine flowshop problem with jobs of two classes, Int. Trans. Oper. Res., 27 (2020), 3123–3143. https://doi.org/10.1111/itor.12530 doi: 10.1111/itor.12530
    [29] B. J. Jeong, J. H. Han, J. Y. Lee, Metaheuristics for a flow shop scheduling problem with urgent jobs and limited waiting times, Algorithms, 14 (2021), 323. https://doi.org/10.3390/a14110323 doi: 10.3390/a14110323
    [30] D. Lei, X. Guo, A shuffled frog-leaping algorithm for hybrid flow shop scheduling with two agents, Expert Syst. Appl., 42 (2015), 9333–9339. https://doi.org/10.1016/j.eswa.2015.08.025 doi: 10.1016/j.eswa.2015.08.025
    [31] D. Lei, Two-phase neighborhood search algorithm for two-agent hybrid flow shop scheduling problem, Appl. Soft Comput., 34 (2015), 721–727. https://doi.org/10.1016/j.asoc.2015.05.027 doi: 10.1016/j.asoc.2015.05.027
    [32] J. Y. Bang, B. J. Jeong, A branch-and-bound algorithm to minimize total tardiness in a two-machine flowshop problem with different release time, J. Adv. Mech. Des. Syst. Manuf., 13 (2019), JAMDSM0080. https://doi.org/10.1299/jamdsm.2019jamdsm0080 doi: 10.1299/jamdsm.2019jamdsm0080
    [33] 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
    [34] R. Puka, J. Duda, A. Stawowy, I. Skalna, N-NEH algorithm for solving permutation flow shop problems, Comput. Oper. Res., 132 (2021), 105296. https://doi.org/10.1016/j.cor.2021.105296 doi: 10.1016/j.cor.2021.105296
    [35] J. M. Framinan, R. Leisten, An efficient constructive heuristic for flowtime minimisation in permutation flow shops, Omega, 31 (2003), 311–317. https://doi.org/10.1016/S0305-0483(03)00047-1 doi: 10.1016/S0305-0483(03)00047-1
    [36] L. Ding, Z. Guan, D. Luo, M. Rauf, W. Fang, An adaptive search algorithm for multiplicity dynamic flexible job shop scheduling with new order arrivals, Symmetry, 16 (2024), 641. https://doi.org/10.3390/sym16060641 doi: 10.3390/sym16060641
    [37] Y. Chen, J. Zhang, M. Rauf, J. Mumtaz, S. Huang, Dynamic scheduling of hybrid flow shop problem with uncertain process time and flexible maintenance using NeuroEvolution of Augmenting Topologies, IET Collab. Intell. Manuf., 6 (2024), e12119. https://doi.org/10.1049/cim2.12119 doi: 10.1049/cim2.12119
  • 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)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索
Journal of Industrial and Management Optimization
1.6 3.3

Metrics

Article views(278) PDF downloads(12) Cited by(0)

Preview PDF
Download XML
Export Citation
Article outline

Figures and Tables

Tables(6)

Other Articles By Authors

Related pages

Tools

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog