In this paper, we investigate the mixed batch parallel machine scheduling problem in which a set of jobs should be processed on one of the parallel batch machines with nested processing set restrictions. Each job has its processing time and its machine set for processing with these machine sets satisfying the nested processing set restrictions. Each machine can process a group of jobs as a batch simultaneously, as long as the total number of jobs in this batch does not exceed the capacity of the machine. For a given batch, its processing time is equal to the weighted sum of the maximum processing time and the total processing time of jobs in the batch. The objective function is to minimize the makespan. The problem includes the classic parallel machine scheduling problem as a special case, which is strongly NP-hard. For the studied problem, we derive an approximation algorithm with a performance ratio of $\left({2 + \alpha} \right)$, where $\alpha$ is a given parameter for weight with $0\leq\alpha\leq 1$.
WU Hongyi
,
WANG Dong
,
WAN Long
,
LUO Wenchang
. Approximation algorithm for mixed batch parallel machine scheduling with nested processing set restrictions[J]. Operations Research Transactions, 2026
, 30(1)
: 188
-196
.
DOI: 10.15960/j.cnki.issn.1007-6093.2026.01.013
[1] 唐国春，张峰，罗守成，等.现代排序论[M].上海：上海科学普及出版社，2003.
[2] Leung, J Y T, Li C L. Scheduling with processing set restrictions: A survey [J]. International Journal of Production Economics, 2008, 116(2): 251-262.
[3] Mönch L, Fowler J W, Dauzere-Péres S, et al. A survey of problems, solution techniques, and future challenges in scheduling semiconductor manufacturing operations [J]. Journal of Scheduling, 2011, 14(6): 583-599.
[4] Potts C N, Kovalyov M Y. Scheduling with batching: A review [J]. European Journal of Operational Research, 2000, 120(2): 228-249.
[5] Wang J Q, Fan G Q, Liu Z. Mixed batch scheduling on identical machines [J]. Journal of Scheduling, 2020, 23(4): 487-496.
[6] Graham R L, Lawler E L, Lenstra J K, et al. Optimization and approximation in deterministic sequencing and scheduling: A survey [J]. Annals of Discrete Mathematics, 1979, 5: 236-287.
[7] Lenstra J K, Shmoys D B, Tardos E. Approximation algorithms for scheduling unrelated ′ parallel machines [J]. Mathematical Programming, 1990, 46(1): 259-271.
[8] Ou J, Leung J Y T, Li C L. Scheduling parallel machines with inclusive processing set restrictions [J]. Naval Research Logistics, 2008, 55(4): 328-338.
[9] Hwang H C, Chang S Y, Lee K. Parallel machine scheduling under a grade of service provision [J]. Computers & Operations Research, 2004, 31(12): 2055-2061.
[10] Glass C A, Kellerer H. Parallel machine scheduling with job assignment restrictions [J]. Naval Research Logistics, 2007, 54(3): 250-257.
[11] Huo Y, Leung J Y T. Parallel machine scheduling with nested processing set restrictions [J]. European Journal of Operational Research, 2010, 204(2): 229-236.
[12] Bar-Noy A, Freund A, Naor J. On-line load balancing in a hierarchical server topology [J]. SIAM Journal on Computing, 2001, 31(2): 527-549.
[13] Epstein L, Levin A. Scheduling with processing set restrictions: PTAS results for several variants [J]. International Journal of Production Economics, 2011, 133(2): 586-595.
[14] Li S. Parallel batch scheduling with inclusive processing set restrictions and non-identical capacities to minimize makespan [J]. European Journal of Operational Research, 2017, 260(1): 12-20.
[15] Li S. Parallel batch scheduling with nested processing set restrictions [J]. Theoretical Computer Science, 2017, 689: 117-125.
[16] 王冬，李刚刚，罗文昌.工件具有任意尺寸的混合分批平行机排序问题的近似算法[J].运筹学学报， 2022，26(3)：133-142.
[17] Lee C Y, Uzsoy R, Martin-Vega L A. Efficient algorithms for scheduling semiconductor burn-in operations [J]. Operations Research, 1992, 40(4): 764-775.
[18] Deng X, Feng H, Li G, et al. A PTAS for semiconductor burn-in scheduling [J]. Journal of Combinatorial Optimization, 2005, 9(1): 5-17.
