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

作者：张安; 陈永; 陈光亭; 陈占文; 舒巧君; 林国辉^*

来源：运筹学学报, 2022, 26(03): 57-74.

DOI：10.15960/j.cnki.issn.1007-6093.2022.03.005

• 工件序
• 开放作业
• 流水作业
• 最大匹配
• 近似算法

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

• 单位
  浙江水利水电学院; 杭州电子科技大学