典型文献
优先序约束的排序问题:基于最大匹配的近似算法
文献摘要：
本文研究具有加工次序约束的单位工件开放作业和流水作业排序问题,目标函数为极小化工件最大完工时间.工件之间的加工次序约束关系可以用一个被称为优先图的有向无圈图来刻画.当机器数作为输入时,两类问题在一般优先图上都是强NP-困难的,而在入树的优先图上都是可解的.我们利用工件之间的许可对数获得了问题的新下界,并基于许可工件之间的最大匹配设计近似算法,其中匹配的许可工件对均能同时在不同机器上加工.对于一般优先图的开放作业问题和脊柱型优先图的流水作业问题,我们在理论上证明了算法的近似比为2 2-m,其中m是机器数目.
文献关键词：
工件序;开放作业;流水作业;最大匹配;近似算法
中图分类号：
作者姓名：
张安;陈永;陈光亭;陈占文;舒巧君;林国辉
作者机构：
杭州电子科技大学数学系,浙江杭州310018;浙江水利水电学院,浙江杭州310018;阿尔伯塔大学计算科学系,阿尔伯塔埃德蒙顿T6G 2E8
文献出处：
引用格式：
[1]张安;陈永;陈光亭;陈占文;舒巧君;林国辉-.优先序约束的排序问题:基于最大匹配的近似算法)[J].运筹学学报,2022(03):57-74
A类：
有向无圈图
B类：
优先序,最大匹配,近似算法,有加,次序,开放作业,流水作业排序问题,极小化,最大完工时间,约束关系,NP,下界,匹配设计,作业问题,脊柱,上证,近似比,工件序
AB值：
0.300353
相似文献
机标中图分类号，由域田数据科技根据网络公开资料自动分析生成，仅供学习研究参考。
