等级约束下的负载均衡问题是组合优化领域的经典难题之一,其在近十年里得到了广泛的研究。等级约束下的负载均衡问题即把若干个带等级的工件分配给一些带等级的机器加工,工件可以在等级不低于自己的机器上加工,且每个工件只能被一台机器不间断的加工。目标是寻找一种分配方案使得最大机器负载最小化,这里的负载一般定义为工件的加工时间或加工工件所需的各种资源。本文主要研究了等级约束下的负载均衡问题的两类广义形式:多重负载均衡问题和多维负载均衡问题。等级约束下的多重负载均衡问题即给定若干个客户和一些带等级的机器,每个客户提交若干个带等级的工件给这些机器加工,工件可以在等级不低于自己的机器上加工,且每个工件只能被一台机器不间断的加工。目标是寻找一种分配方案使得最大机器负载最小化。对等级约束下的多重负载均衡问题,当机器台数m = 2时,本文设计了一个5/4-近似算法,一个5/3-最优在线算法和一个在所有工件加工时间之和的一半已知的情况下的3/2-最优半在线算法并分析了近似比;当机器台数m ≥ 3时,本文设计了一个2-1/m-1-近似算法并分析了近似比。m-1等级约束下的多维负载均衡问题即把若干个带等级的工件分配给一些带等级的机器加工,此问题中的工件的负载为具有相同维数的向量,工件可以在等级不低于自已的机器上加工。目标是寻找一种分配方案使得最大机器负载分量最小化。对等级约束下的多维负载均衡问题,本文通过把每个向量的分量进行叠加的方法设计了一个2d-近似算法,同时给出了该问题的动态规划形式。当负载向量的维数和机器数都为固定常数时,本文在结合了2d-近似算法和动态规划的基础上设计了一个全多项式时间近似方案。