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

Previous Articles Next Articles

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

CLC Number:

90B35
90C29

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.

TrendMD

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.jorsc.shu.edu.cn/EN/10.1007/s40305-024-00545-0

https://www.jorsc.shu.edu.cn/EN/Y2026/V14/I2/547

References

[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)

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 4

Recommended Articles

Metrics

Comments

[1]	Cheng He, Hao Lin, Li Li. Unbounded Serial-Batching Scheduling on Hierarchical Optimization [J]. Journal of the Operations Research Society of China, 2021, 9(4): 909-914.
[2]	Imen Hamdi, Mohamed Fadhel Tekaya. A Genetic Algorithm to Minimize the Makespan in a Two-Machine Cross-Docking Flow Shop Problem [J]. Journal of the Operations Research Society of China, 2020, 8(3): 457-476.
[3]	Jin-Jiang Yuan, Li-Li Ren, Ji Tian, Ru-Yan Fu. Online Scheduling on Two Uniform Unbounded Parallel-Batch Machines to Minimize Makespan [J]. Journal of the Operations Research Society of China, 2019, 7(2): 303-319.
[4]	Yuan Gao · Jin-Jiang Yuan. Pareto Minimizing Total Completion Time and Maximum Cost with Positional Due Indices [J]. Journal of the Operations Research Society of China, 2015, 3(3): 381-.