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

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

Abstract

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

CLC Number:

O221.7

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.

Figures/Tables 6

References 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]	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.
[2]	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.
[3]	Jianping LI, Lijian CAI, Junran LICHEN, Pengxiang PAN. The constrained multi-sources eccentricity augmentation problems [J]. Operations Research Transactions, 2022, 26(1): 60-68.
[4]	Hua CHEN, Guochuan ZHANG. A survey on approximation algorithms for one dimensional bin packing [J]. Operations Research Transactions, 2022, 26(1): 69-84.
[5]	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.
[6]	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.
[7]	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.
[8]	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.
[9]	Jianfeng REN, Xiaoyun TIAN. Squared metric facility location problem with outliers [J]. Operations Research Transactions, 2021, 25(1): 114-122.
[10]	ZHANG Yuzhong. A survey on job scheduling with rejection [J]. Operations Research Transactions, 2020, 24(2): 111-130.
[11]	LIU Xiaoxia, YU Shanshan, LUO Wenchang. Approximation algorithms for single machine parallelbatch scheduling with release dates subject to the number of rejected jobs not exceeding a given threshold [J]. Operations Research Transactions, 2020, 24(1): 131-139.
[12]	WANG Yizhan, ZHANG An, CHEN Yong, CHEN Guangting. An approximation algorithm for reclaimer scheduling [J]. Operations Research Transactions, 2020, 24(1): 147-154.
[13]	ZHANG Guochuan, CHEN Lin. The load balancing problem [J]. Operations Research Transactions, 2019, 23(3): 1-14.
[14]	LIU Yan, LEI Mengxia, HUANG Xiaoxian. Path-transformation graph of maximum matchings [J]. Operations Research Transactions, 2019, 23(2): 104-112.
[15]	JIANG Yanjun, XU Dachuan, ZHANG Dongmei. An approximation algorithm for the squared metric dynamic facility location problem [J]. Operations Research Transactions, 2018, 22(3): 49-58.

Maximum matching based approximation algorithms for precedence constrained scheduling problems

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 6

References 24

Related Articles 15

Recommended Articles

Metrics

Comments