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

Maximum matching based approximation algorithms for precedence constrained scheduling problems

作　　者：张安[1] 陈永[1] 陈光亭 陈占文 舒巧君 林国辉 ZHANG An;CHEN Yong;CHEN Guangting;CHEN Zhanwen;SHU Qiaojun;LIN Guohui(Department of Mathematics,Hangzhou Dianzi University.Zhejiang,Hangzhou 310018,China;Zhejiang University of Water Resources and Electric Power.Zhejiang,Hangzhou 310018,China;Department of Computing Science,University of Alberta.Edmonton,T6G 2E8 Alberta,Canada)

机构地区：[1]杭州电子科技大学数学系,浙江杭州310018 [2]浙江水利水电学院,浙江杭州310018 [3]阿尔伯塔大学计算科学系,阿尔伯塔埃德蒙顿T6G 2E8

出　　处：《运筹学学报》2022年第3期57-74,共18页Operations Research Transactions

基　　金：Zhejiang Provincial Natural Science Foundation(No.LY21A010014);National Natural Science Foundation of China(No.11971139)。

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

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

分 类 号：O221.7[理学—运筹学与控制论]