二部许可图下{2;3}问题的近似算法  

An Approximation Algorithm for Parallel Machine Scheduling with Bipartite Agreement Graph

作　　者：王佳音 张亮 张安[1] 陈永[1] 陈光亭 WANG Jiayin;ZHANG Liang;ZHANG An;CHEN Yong;CHEN Guangting(School of Sciences,Hangzhou Dianzi University,Hangzhou Zhejiang 310018;Zhejiang University of Water Resources and Electic Power,Hangzhou Zhejiang,310018)

机构地区：[1]杭州电子科技大学理学院,浙江杭州310018 [2]浙江水利水电学院,浙江杭州310018

出　　处：《杭州电子科技大学学报（自然科学版）》2023年第5期78-83,共6页Journal of Hangzhou Dianzi University：Natural Sciences

基　　金：国家自然科学基金资助项目(11771114,11971139);浙江省自然科学基金(LY21A010014)。

摘　　要：研究了二部许可图下的两台平行机排序问题,针对加工时间仅取2,3且目标函数为最小化最大完工时间这一特殊情形,设计了基于匹配方法的近似算法,证明了算法的最坏情况界为5/4。This paper studies scheduling with bipartite agreement graph on two parallel machines.For a special variant of the makespan minimization problem where the processing time equals either 2 or 3,we design a matching-based approximation algorithm,and show that its worst case ratio is 5/4.

关 键 词：平行机排序 许可图 匹配 近似算法 最坏情况界 

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