English

运筹学学报 >

2022 , Vol. 26 >Issue 3: 57 - 74

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2022.03.005

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

展开
  • 1. 杭州电子科技大学数学系, 浙江杭州 310018
    2. 浙江水利水电学院, 浙江杭州 310018
    3. 阿尔伯塔大学计算科学系, 阿尔伯塔埃德蒙顿 T6G 2E8

收稿日期: 2022-01-08

  网络出版日期: 2022-09-07

收起

Maximum matching based approximation algorithms for precedence constrained scheduling problems

Expand
  • 1. Department of Mathematics, Hangzhou Dianzi University. Zhejiang, Hangzhou 310018, China
    2. Zhejiang University of Water Resources and Electric Power. Zhejiang, Hangzhou 310018, China
    3. Department of Computing Science, University of Alberta. Edmonton, T6G 2E8 Alberta, Canada
LIN Guohui, E-mail: guohui@ualberta.ca

Received date: 2022-01-08

  Online published: 2022-09-07

Fold

摘要

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

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

本文引用格式

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

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

参考文献

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.
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.
5 Braschi B , Trystram D . A new insight into the Coffman-Graham algorithm[J]. SIAM Journal on Computing, 1994, 23, 662- 669.
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.
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.
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.
14 Timkovsky V G . Identical parallel machines vs. chains in scheduling complexity[J]. European Journal of Operational Research, 2003, 149, 355- 376.
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.
18 Brucker P , Knust S . Complexity results for single-machine problems with positive finish-start time-lags[J]. Computing, 1999, 63, 299- 316.
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.
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.
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.
Options
文章导航

/

〈 〉