本文研究了加工工件的机器集具有嵌套型限制下的混合分批平行机排序问题。具体来说, 给定一个待加工的工件集需在多台平行批处理机中的一台进行加工,每个工件有它的加工时间和可加工它的机器集,这些机器集之间满足嵌套型加工限制; 每台机器可以同时加工多个工件,称为一个批次, 只要批内工件总个数不超过其容量即可;一个批次的加工时间等于该批中工件的最大加工时间与总加工时间的加权和;目标函数是极小化最大完工时间。该问题包含经典的平行机排序问题为其特殊情形, 为强NP-困难的。对此设计了一个性能比为 $\left({2 + \alpha} \right)$ 的近似算法,其中$\alpha$ 为给定的权重参数, 满足$0\leq\alpha\leq 1$。
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$.
[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.
北大中文核心期刊