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(n4)-time algorithm.
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
.
DOI: 10.1007/s40305-024-00545-0
[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)
