具有服务等级的三台平行机排序问题  

Parallel scheduling on three machines under a grade of service provision

作　　者：周萍[1] 蒋义伟[2] 华荣伟[3] 

机构地区：[1]浙江大学数学系,浙江杭州310027 [2]浙江理工大学理学院,浙江杭州310018 [3]浙江医学高等专科学校,浙江杭州310053

出　　处：《浙江大学学报（理学版）》2007年第4期378-383,共6页Journal of Zhejiang University（Science Edition）

基　　金：浙江省自然科学基金资助项目(Y605316)

摘　　要：考虑带服务等级的三台平行机排序问题.预先赋予每台机器和每个任务一个服务等级(grade of service)标号.每个任务只能被某台服务等级不高于该任务服务等级的机器加工.目标是最小化最大机器完工时间.本文给出了求解这个问题的算法.并证明算法的最坏情况界不超过54+12k,其中k是算法中预先给定的迭代次数.已有的算法仅为32.Parallel scheduling problem on three machines with a grade of service provision is introduced. That process service requests from various customers who are entitled to many different grade of service （GoS） levels. Hence, each job and machine are labelled with prespecified GoS levels, and each job can be processed by a particular machine only when the GoS level of the job is not less than that of the machine. The objective is to minimize the aximum machine completion time. For this problem, an algorithm with a worst-case ratio of 5/4＋（1/2）^k is presented, where k is the desired number of iteration, which has improved the known result 3/2.

关 键 词：服务等级 最坏情况界 FFD算法 Multifit算法 

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