嵌套加工型限制下的混合分批平行机排序问题的近似算法

doi:10.15960/j.cnki.issn.1007-6093.2026.01.013

Abstract

Abstract: 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$.

Key words: mixed batch scheduling, nested processing set, makespan, approximation algorithm

CLC Number:

O221.7

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.

References

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

Approximation algorithm for mixed batch parallel machine scheduling with nested processing set restrictions

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	Yuan YUAN, Yan LAN, Xin HAN. A survey of scheduling with maintenance periods [J]. Operations Research Transactions, 2025, 29(1): 1-18.
[2]	Chengwen JIAO. Online scheduling on a single parallel-batch machine with linear lookahead [J]. Operations Research Transactions, 2024, 28(4): 111-116.
[3]	Jie GAO, Juan ZOU, Yukang SUI, Yuzhong ZHANG. Unrelated parallel-machine scheduling with deteriorating maintenance activities and job rejection [J]. Operations Research Transactions, 2023, 27(3): 137-149.
[4]	An ZHANG, Yong CHEN, Guangting CHEN, Zhanwen CHEN, Qiaojun SHU, Guohui LIN. Maximum matching based approximation algorithms for precedence constrained scheduling problems [J]. Operations Research Transactions, 2022, 26(3): 57-74.
[5]	Dong WANG, Ganggang LI, Wenchang LUO. Approximation algorithm for mixed batch scheduling on identical machines for jobs with arbitrary sizes [J]. Operations Research Transactions, 2022, 26(3): 133-142.
[6]	Chunyan BI, Long WAN, Wenchang LUO. Approximation algorithm for uniform parallel machine scheduling with release dates and job rejection [J]. Operations Research Transactions, 2022, 26(2): 73-82.
[7]	Jianping LI, Lijian CAI, Junran LICHEN, Pengxiang PAN. The constrained multi-sources eccentricity augmentation problems [J]. Operations Research Transactions, 2022, 26(1): 60-68.
[8]	Hua CHEN, Guochuan ZHANG. A survey on approximation algorithms for one dimensional bin packing [J]. Operations Research Transactions, 2022, 26(1): 69-84.
[9]	Wenjie LIU, Dongmei ZHANG, Peng ZHANG, Juan ZOU. The seeding algorithm for $\mu$-similar Bregman divergences $k$-means problem with penalties [J]. Operations Research Transactions, 2022, 26(1): 99-112.
[10]	Jiachen JU, Qian LIU, Zhao ZHANG, Yang ZHOU. A local search analysis for the uniform capacitated $k$-means problem with penalty [J]. Operations Research Transactions, 2022, 26(1): 113-124.
[11]	Libo WANG, Wenhua LI, Dan YU. Online scheduling on single batch machine with variable lookahead interval [J]. Operations Research Transactions, 2022, 26(1): 134-140.
[12]	Xiaowei LI, Xiayan CHENG, Rongheng LI. An approximation algorithm for Robust k-product facility location problem with linear penalties [J]. Operations Research Transactions, 2021, 25(4): 31-44.
[13]	Xiaoguang BAO, Chao LU, Dongmei HUANG, Wei YU. Approximation algorithm for min-max cycle cover problem on a mixed graph [J]. Operations Research Transactions, 2021, 25(1): 107-113.
[14]	Jianfeng REN, Xiaoyun TIAN. Squared metric facility location problem with outliers [J]. Operations Research Transactions, 2021, 25(1): 114-122.
[15]	ZHAO Congcong, FANG Dandan, LI Rongheng. Optimal algorithms for hybrid flow shop schedule on two machines with learning effect [J]. Operations Research Transactions, 2020, 24(2): 42-60.