摘要
对有两个服务等级的平行机排序问题的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
