许可图约束下带释放时间的两机排序算法  

An algorithm for two machine scheduling with release times under bipartite agreement graph constraints

作　　者：童昕 张亮 张安[1] 陈永[1] 陈光亭 TONG Xin;ZHANG Liang;ZHANG An;CHEN Yong;CHEN Guangting(School of Sciences,Hangzhou Dianzi University,Hangzhou Zhejiang 310018,China;School of Information Engineering,Zhejiang University of Water Resources and Electric Power,Hangzhou Zhejiang 310018,China)

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

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

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

摘　　要：研究一类许可图约束下的2台平行机排序问题,目标是最小化时间表长。针对许可图为二部图,在加工时间为1的工件仅在0时刻释放而加工时间为2的工件在0时刻或r时刻释放的强NP-难情形下,设计了基于最大权匹配方法的近似算法,证明了算法的最坏情况界为3/2。We consider two-parallel machine scheduling under agreement graph constraints. The objective is to minimize the makespan. For the strong NP-hard case where the graph is bipartite, all unit jobs arrive at time 0, and jobs with processing time 2 arrive at either time 0 or timer r, we design an approximation algorithm based on the maximum weighted matching method, and show that its worst case ratio is 3/2.

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

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