本变主要研究具有服务等级的平行机排序问题，预先赋予每个任务和每台机器一个服务等级标号，使得服务等级低的机器既能加工服务等级低的任务，又能加工服务等级高的任务，而服务等级高的机器只能加工服务等级高的任务.目标函数是极小化最大机器完工时间.这类问题最先是由Hwang等提出来的.本文给出了求解这类问题的新算法.从而大大改进了已知文献中的结果2-1/m-1.全文共分为三章. 第一章是绪论部分，主要介绍排序问题相关的一些概念和预备知识. 第二章主要研究了具有两个服务等级的m台平行机排序问题.目标函数是极小化最大的机器完工时间(Cmax).给出了一个修正的MULTIFIT算法，其最坏情况界为4/3+(1/2)к，其中к是预先给定得迭代次数. 第三章主要研究了一般情况下具有服务等级的m台平行机排序问题.目标函数为极小化最大的机器完工时间.给出了一个最坏情况界为3/2+(1/2)к的算法.对m=3的情形给出了一个最坏情况界为5/4+(1/2)к的算法，并证明了这个界是紧的.