排序问题是一类重要的组合最优化问题，在生产计划、计算机控制等领域有着广泛应用，一直是理论界研究热点。对带服务等级的3台平行机排序问题进行研究，每台机器和每个工件都有等级标号，每个工件只能被某台服务等级不高于该工件等级的机器加工，目标是最小化最大机器的完工时间。运用新的算法思想解决离线状态等级约束下的3台机器负载均衡问题。对等级约束为1、2、2的3台平行机给出一个--近似算法；对于等级约束为1、1、2的3台平行机给出一个2-近似算法。
0 引言
排序问题描述如下：若干个工件要在一些机器上进行加工，如何安排机器和工件使某些要求（目标函数）达到最优。一个排序问题可以用三元组α|β|γ来描述，其中α域描述机器环境，β域提供加工特征和约束