The Unbounded Parallel-Batching Bicriteria Scheduling with Two-Component Jobs

doi:10.1007/s40305-024-00545-0

Journal of the Operations Research Society of China ›› 2026, Vol. 14 ›› Issue (2): 547-564.doi: 10.1007/s40305-024-00545-0

收稿日期:2023-08-22 修回日期:2024-03-19 出版日期:2026-06-30 发布日期:2026-07-06
通讯作者: Cheng He E-mail:hech202@163.com
作者简介:Jing Wu,E-mail:wjing02022@163.com;Hao Lin,E-mail:linhao1974@163.com;Yuan Zhang,E-mail:zhangyuan2021@haut.edu.cn;Yan Zhao,E-mail:yanzhao@haut.edu.cn

The Unbounded Parallel-Batching Bicriteria Scheduling with Two-Component Jobs

Cheng He, Jing Wu, Hao Lin, Yuan Zhang, Yan Zhao

School of Science, Henan University of Technology, Zhengzhou 450001, Henan, China

Received:2023-08-22 Revised:2024-03-19 Online:2026-06-30 Published:2026-07-06
Contact: Cheng He E-mail:hech202@163.com
Supported by:
This work was supported by the Natural Science Foundation of Henan province, China (No. 232300421218) and the National Natural Science Foundation of China (No. 12201186) and the Key project of scientific research for overseas students in Henan Province (No. 2020-70) and Innovation Fund project of Henan University of Technology (No. 2020ZKCJ08).

摘要/Abstract

Abstract: This paper studies a bicriteria scheduling problem on a parallel-batching machine to minimizemaximum cost andmakespan simultaneously. Each job has two components: standard component and specific component. Standard components are processed in batches. Specific components are processed individually. The processing order of two components of a job has no constraint. A job is completed only when its two components are completed. For the simultaneous optimization scheduling problem, we design an O(n⁴)-time algorithm.

Key words: Bicriteria scheduling, Two-component, Makespan, Maximum cost, Pareto optimal schedules

中图分类号:

90B35
90C29

. [J]. Journal of the Operations Research Society of China, 2026, 14(2): 547-564.

Cheng He, Jing Wu, Hao Lin, Yuan Zhang, Yan Zhao. The Unbounded Parallel-Batching Bicriteria Scheduling with Two-Component Jobs[J]. Journal of the Operations Research Society of China, 2026, 14(2): 547-564.

[1] Baker, K.R., Smith, J.C.: A multiple-criterion model for machine scheduling. J. Sched. 6, 7–16(2003)
[2] Brucker, P.: Scheduling Algorithms, 3rd edn. Springer, Berlin (2001)
[3] Brucker, P., Gladky, A., Hoogeveen, H., Kovalyov, M.Y., Potts, C.N., Tautenhahn, T., Van De Velde, S.L.: Scheduling a batching machine. J. Sched. 1(1), 31–54(1998)
[4] Geng, Z.C., Yuan, J.J.: A note on unbounded parallel-batch scheduling. Inf. Process. Lett. 115(12), 969–974(2015)
[5] Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discret. Math. 5, 287–326(1979)
[6] He, C., Li, L.: Hierarchical optimization with two maximum costs on an unbounded parallel-batching machine. RAIRO-Oper. Res. 52, 55–60(2018)
[7] He, C., Lin, Y.X., Yuan, J.J.: Bicriteria scheduling on a batching machine to minimize maximum lateness and makespan. Theoret. Comput. Sci. 381(1–3), 234–240(2007)
[8] He, C., Lin, H., Yuan, J.J., Mu, Y.D.: Batching machine scheduling with bicriteria: maximum cost and makespan. Asia-Pacific J. Oper. Res. 31(04), 1–10(2014)
[9] He, C., Wu, J., Xu, J.L., Wang, J.L.: An improved algorithm on unbounded parallel-batching scheduling to minimize maximum cost and makespan. RAIRO-Oper. Res. 57, 731–741(2023)
[10] Hoogeveen, H.: Multicriteria scheduling. Eur. J. Oper. Res. 167(3), 592–623(2005)
[11] Hoogeveen, J.A.: Single-machine scheduling to minimize a function of two or three maximum cost criteria. J. Algorithms. 21(2), 415–433(1996)
[12] Li, S.G., Geng, Z.C.: Bicriteria scheduling on an unbounded parallel-batch machine for minimizing makespan and maximum cost. Inf. Process. Lett. 180, 106343(2023)
[13] T’kindt, V., Billaut, J.-C.: Multicriteria scheduling problems: a survey. RAIRO-Oper. Res. 35(2), 143–163(2001)

相关文章 15

[1]	. [J]. Journal of the Operations Research Society of China, 2026, 14(2): 489-501.
[2]	. [J]. Journal of the Operations Research Society of China, 2026, 14(2): 653-670.
[3]	. [J]. Journal of the Operations Research Society of China, 2026, 14(1): 129-148.
[4]	. [J]. Journal of the Operations Research Society of China, 2025, 13(4): 1157-1180.
[5]	. [J]. Journal of the Operations Research Society of China, 2025, 13(2): 590-602.
[6]	. [J]. Journal of the Operations Research Society of China, 2025, 13(2): 603-615.
[7]	. [J]. Journal of the Operations Research Society of China, 2024, 12(4): 1088-1102.
[8]	. [J]. Journal of the Operations Research Society of China, 2024, 12(4): 1126-1138.
[9]	. [J]. Journal of the Operations Research Society of China, 2024, 12(3): 681-693.
[10]	. [J]. Journal of the Operations Research Society of China, 2024, 12(2): 341-350.
[11]	. [J]. Journal of the Operations Research Society of China, 2023, 11(3): 693-706.
[12]	. [J]. Journal of the Operations Research Society of China, 2022, 10(1): 113-131.
[13]	. [J]. Journal of the Operations Research Society of China, 2021, 9(4): 909-914.
[14]	. [J]. Journal of the Operations Research Society of China, 2021, 9(2): 359-373.
[15]	. [J]. Journal of the Operations Research Society of China, 2021, 9(1): 63-77.

The Unbounded Parallel-Batching Bicriteria Scheduling with Two-Component Jobs

PDF

可视化

摘要/Abstract

引用本文

使用本文

相关文章 15

编辑推荐

Metrics

本文评价