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

作     者：张安 陈永 陈光亭 陈占文 舒巧君 林国辉 ZHANG An;CHEN Yong;CHEN Guangting;CHEN Zhanwen;SHU Qiaojun;LIN Guohui

作者机构：杭州电子科技大学数学系浙江杭州310018 浙江水利水电学院浙江杭州310018 阿尔伯塔大学计算科学系阿尔伯塔埃德蒙顿T6G 2E8 

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

出 版 物：《运筹学学报》 (Operations Research Transactions)

年 卷 期：2022年第26卷第3期

页      码：57-74页

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

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

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 07[理学] 070105[070105] 0701[理学-数学类] 

核心收录：

D　O　I：10.15960/j.cnki.issn.1007-6093.2022.03.005

馆 藏 号：203113541...