摘要
对有两个服务等级的平行机排序问题的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
出处
《高校应用数学学报(A辑)》
CSCD
北大核心
2007年第3期275-284,共10页
Applied Mathematics A Journal of Chinese Universities(Ser.A)
基金
浙江省自然科学基金(Y605316)
关键词
平行机排序
服务等级
近似算法
最坏情况界
parallel machine scheduling
grade of service
approximation algorithm
worst-case ratio