有两个服务等级的平行机排序问题  

Parallel machine scheduling problem with two GoS levels

作　　者：周萍[1] 蒋义伟[2] 何勇[3] 

机构地区：[1]浙江商业职业技术学院基础部,浙江杭州310053 [2]浙江理工大学理学院,浙江杭州310018 [3]浙江大学数学系,浙江杭州310027

出　　处：《高校应用数学学报（A辑）》2007年第3期275-284,共10页Applied Mathematics A Journal of Chinese Universities(Ser.A)

基　　金：浙江省自然科学基金(Y605316)

摘　　要：对有两个服务等级的平行机排序问题的m台机情形,证明了修正的MF算法的最坏情况界不超过4/3＋（1/2）^k,其中k是算法中预先给定的迭代次数.而已有的算法仅为2-1/m-1,从而大大改进了已有文献中的结果.For m parallel machines scheduling with two grade of service （GoS） levels, it is shown that the worst-case ratio of the modified MF algorithm is at most 4/3 ＋ （1/2）^k , where k is the desired number of iteration, which improves greatly the known result 2-1/m-1

关 键 词：平行机排序 服务等级 近似算法 最坏情况界 

分 类 号：O223[理学—运筹学与控制论]