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

Parallel scheduling on three machines under a grade of service provision

考虑带服务等级的三台平行机排序问题.预先赋予每台机器和每个任务一个服务等级(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.