优先序约束的排序问题：基于最大匹配的近似算法

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

摘要/Abstract

摘要：

本文研究具有加工次序约束的单位工件开放作业和流水作业排序问题，目标函数为极小化工件最大完工时间。工件之间的加工次序约束关系可以用一个被称为优先图的有向无圈图来刻画。当机器数作为输入时，两类问题在一般优先图上都是强NP-困难的，而在入树的优先图上都是可解的。我们利用工件之间的许可对数获得了问题的新下界，并基于许可工件之间的最大匹配设计近似算法，其中匹配的许可工件对均能同时在不同机器上加工。对于一般优先图的开放作业问题和脊柱型优先图的流水作业问题，我们在理论上证明了算法的近似比为$2-\frac 2m$，其中$m$是机器数目。

关键词: 工件序, 开放作业, 流水作业, 最大匹配, 近似算法

Abstract:

We investigate the problem to schedule a set of precedence constrained jobs of unit size on an open-shop or on a flow-shop to minimize the makespan. The precedence constraints among the jobs are presented as a directed acyclic graph called the precedence graph. When the number of machines in the shop is part of the input, both problems are strongly NP-hard on general precedence graphs, but were proven polynomial-time solvable for some special precedence graphs such as intrees. In this paper, we characterize improved lower bounds on the minimum makespan in terms of the number of agreeable pairings among certain jobs and propose approximation algorithms based on a maximum matching among these jobs, so that every agreeable pair of jobs can be processed on different machines simultaneously. For open-shop with an arbitrary precedence graph and for flow-shop with a spine precedence graph, both achieved approximation ratios are $2 - \frac 2m$, where $m$ is the number of machines in the shop.

Key words: job precedence, open-shop, flow-shop, maximum matching, approximation algorithm

中图分类号:

O221.7

张安, 陈永, 陈光亭, 陈占文, 舒巧君, 林国辉. 优先序约束的排序问题：基于最大匹配的近似算法[J]. 运筹学学报, 2022, 26(3): 57-74.

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.

图/表 6

Table 1

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

参考文献 24

1	Pinedo M . Scheduling: Theory, Algorithm and Systems (5th Ed.)[M]. New York: Springer, 2016.
2	Graham R L . Bounds for certain multiprocessing anomalies[J]. Bell Labs Technical Journal, 1966, 45, 1563- 1581. doi: 10.1002/j.1538-7305.1966.tb01709.x
3	Graham R L , Lawler E L , Lenstra J K , et al. Optimization and approximation in deterministic sequencing and scheduling: A survey[J]. Annuals of Discrete Mathematics, 1979, 5, 287- 326.
4	Lam S , Sethi R . Worst case analysis of two scheduling algorithms[J]. SIAM Journal on Computing, 1977, 6, 518- 536. doi: 10.1137/0206037
5	Braschi B , Trystram D . A new insight into the Coffman-Graham algorithm[J]. SIAM Journal on Computing, 1994, 23, 662- 669. doi: 10.1137/S0097539790181889
6	Gangal D , Ranade A . Precedence constrained scheduling in $(2 - \frac {7}{3p+1}) \cdot$optimal[J]. Journal of Computer and System Sciences, 2008, 74, 1139- 1146. doi: 10.1016/j.jcss.2008.04.001
7	Bansal N, Khot S. Optimal long code test with one free bit[C]//Proceedings of FOCS 2009, 2009: 453-462.
8	Svensson O. Conditional hardness of precedence constrained scheduling on identical machines[C]//Proceedings of STOC 2010, 2010: 745-754.
9	Garey M R , Johnson D S . Computers and Intractability: A Guide to the Theory of NP-Completeness[M].
10	Schuurman P , Woeginger G J . Polynomial time approximation algorithms for machine scheduling: Ten open problems[J]. Journal of Scheduling, 1999, 2, 103- 213.
11	Levey E, Rothvoss T. A (1 + $\varepsilon$)-approximation for makespan scheduling with precedence constraints using LP hierarchies[C]//Proceedings of SODA 2016, 2016: 168-177.
12	Prot D , Bellenguez-Morinea O . A survey on how the structure of precedence constraints may change the complexity class of scheduling problems[J]. Journal of Scheduling, 2018, 21, 3- 16. doi: 10.1007/s10951-017-0519-z
13	Leung J Y T , Vornberger O , Witthoff J D . On some variants of the bandwidth minimization problem[J]. SIAM Journal on Computing, 1984, 13, 650- 667. doi: 10.1137/0213040
14	Timkovsky V G . Identical parallel machines vs. chains in scheduling complexity[J]. European Journal of Operational Research, 2003, 149, 355- 376. doi: 10.1016/S0377-2217(02)00767-1
15	Brucker P , Jurisch B , Jurisch M Z . Open shop problems with unit time operations[J]. Operations Research, 1993, 37, 59- 73.
16	Bruno J , Jones Ⅲ J W , So K . Deterministic scheduling with pipelined processors[J]. IEEE Transactions on Computers, 1980, 29, 308- 316.
17	Bräsel H , Kluge D , Werner F . A polynomial algorithm for the $[n/m/0, t_ij=1, { \rm{tree}} /C_{\max}]$ open shop problem[J]. European Journal of Operational Research, 1994, 72, 125- 134. doi: 10.1016/0377-2217(94)90335-2
18	Brucker P , Knust S . Complexity results for single-machine problems with positive finish-start time-lags[J]. Computing, 1999, 63, 299- 316. doi: 10.1007/s006070050036
19	Chen Y , Goebel R , Lin G , et al. Open-shop scheduling for unit jobs under precedence constraints[J]. Theoretical Computer Science, 2020, 803, 144- 151. doi: 10.1016/j.tcs.2019.09.046
20	Tanaev V S , Sotskov Y N , Strusevich V A . Scheduling Theory: Multi-Stage Systems[M]. Netherlands: Springer, 1994.
21	Hopcroft J E , Karp R M . An $n^{\frac 52}$ algorithm for maximum matchings in bipartite graphs[J]. SIAM Journal on Computing, 1973, 2, 225- 231. doi: 10.1137/0202019
22	Karzanov A V . O nakhozhdenii maksimal'nogo potoka v setyakh spetsial'nogo vida i nekotorykh prilozheniyakh (in Russian; title translation: On finding maximum flows in networks with special structure and some applications)[J]. Matematicheskie Voprosy Upravleniya Proizvodstvom, 1973, 5, 81- 94.
23	Madry A. Navigating central path with electrical flows: From flows to matchings, and back[C]//Proceedings of FOCS 2013, 2013: 253-262.
24	Potts C N , Shmoys D B , Williamson D P . Permutation vs. non-permutation flow shop schedules[J]. Operations Research Letters, 1991, 10, 281- 284. doi: 10.1016/0167-6377(91)90014-G

Problem		Complexity	Approximation
$ P \mid prec \mid C_{\max} $		NP-hard^[2]	$ 2 - \frac 1m $^[2]
$ P \mid prec, p_j = 1 \mid C_{\max} $		NP-hard to $ 2 $-approx^[8]	$ 2 - \frac 2m $^{[4, 5]}
$ P \mid prec \mid C_{\max} $, $ m {\geqslant} 4 $		NP-hard	$ 2 - \frac 7{3m+1} $^[6]
	$ m {\geqslant} 3 $	NP-hard open^[9]
$ Pm \mid prec, p_j = 1 \mid C_{\max} $	$ m {\geqslant} 4 $	PTAS open^[10]
	$ m {\geqslant} 4 $	Not APX-hard^[11]
$ O \mid prec, p_{ij} = 1\mid C_{\max} $		Strongly NP-hard^{[13, 14]}	$ 2 - \frac 2m $ (^[19] and this paper)
$ F \mid prec, p_{ij} = 1\mid C_{\max} $		Strongly NP-hard^{[13, 14]}
$ F \mid spine, p_{ij} = 1\mid C_{\max} $		NP-hard open	$ 2 - \frac 2m $ (this paper)
$ O/F \mid intree/outtree, p_{ij} = 1\mid C_{\max} $		P^{[16, 17]}
$ O/F \mid intree, p_{ij} = 1\mid L_{\max} $		P^{[15, 16]}
$ O/F \mid outtree, p_{ij} = 1\mid L_{\max} $		Strongly NP-hard^{[14, 18]}
$ Om/Fm \mid prec, p_{ij} = 1 \mid C_{\max} $, $ m {\geqslant} 3 $		NP-hard open
$ O2/F2 \mid prec, p_{ij} = 1 \mid L_{\max} $		P^{[15, 16]}

[1]	王冬, 李刚刚, 罗文昌. 工件具有任意尺寸的混合分批平行机排序问题的近似算法[J]. 运筹学学报, 2022, 26(3): 133-142.
[2]	袁藩, 徐大川, 张冬梅. k-均值问题的差分隐私算法综述[J]. 运筹学学报, 2022, 26(3): 1-16.
[3]	毕春燕, 万龙, 罗文昌. 工件有到达时间及可拒绝下的同类平行机排序问题的近似算法[J]. 运筹学学报, 2022, 26(2): 73-82.
[4]	李建平, 蔡力健, 李陈筠然, 潘鹏翔. 限制性多源点偏心距增广问题[J]. 运筹学学报, 2022, 26(1): 60-68.
[5]	陈婳, 张国川. 经典一维装箱问题近似算法的研究进展[J]. 运筹学学报, 2022, 26(1): 69-84.
[6]	刘文杰, 张冬梅, 张鹏, 邹娟. 带惩罚μ-相似Bregman散度k-均值问题的初始化算法[J]. 运筹学学报, 2022, 26(1): 99-112.
[7]	剧嘉琛, 刘茜, 张昭, 周洋. 带惩罚的相同容量k-均值问题的局部搜索算法[J]. 运筹学学报, 2022, 26(1): 113-124.
[8]	李小玮, 成夏炎, 李荣珩. 带有线性惩罚的鲁棒k-种产品设施选址问题的近似算法[J]. 运筹学学报, 2021, 25(4): 31-44.
[9]	包晓光, 路超, 黄冬梅, 余炜. 混合图上最小-最大圈覆盖问题的近似算法[J]. 运筹学学报, 2021, 25(1): 107-113.
[10]	任建峰, 田晓云. 带有异常点的平方度量设施选址问题[J]. 运筹学学报, 2021, 25(1): 114-122.
[11]	赵聪聪, 方丹丹, 李荣珩. 具有学习效应的两台机上最优混合流水作业算法[J]. 运筹学学报, 2020, 24(2): 42-60.
[12]	张玉忠. 工件可拒绝排序问题综述[J]. 运筹学学报, 2020, 24(2): 111-130.
[13]	刘晓霞, 余山杉, 罗文昌. 工作有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法[J]. 运筹学学报, 2020, 24(1): 131-139.
[14]	王翼展, 张安, 陈永, 陈光亭. 堆取料机调度问题的一个近似算法[J]. 运筹学学报, 2020, 24(1): 147-154.
[15]	张国川, 陈林. 负载均衡问题[J]. 运筹学学报, 2019, 23(3): 1-14.