This paper investigates the parallel scheduling problem with a new feature that service requests from various customers who are entitled to many different grades of service (GOS) levels. Hence each job and machine are labelled with the 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 makespan. This problem is proposed by HWANG et al. Recently. For this problem, we present an algorithm, based on techniques from 'bin-packing', with3-2+(1-2)R for any m≥ 3, where k is the desired number of iteration, which improves theknown result 2-m-1-1.%考虑一般情况下带服务等级的同速机排序问题.预先赋予每台机器和每个任务一个服务等级( grade of service)标号.每个任务只能被某台服务等级不高于该任务服务等级的机器加工.目标是最小化最大机器完工时间.这个问题最初由HWANG等提出并研究,HWANG等给出了一个最坏情况界为2-1/m-1的算法.本文给出了求解这个问题的算法.并证明算法的最坏情况界不超过3/2+(1/2)k,其中k是算法中预先给定的迭代次数.
展开▼
