Abstract: The load balancing problem with hierarchical constraints is a special case of the unrelated parallel machine scheduling problem. When the objective is to minimize the l_p norm of the machine load vector, by exploiting the combinatorial properties of the considered problem and the convexity of objective function, this paper designs an all norm 2-approximation algorithm, which is combinatorial. When the number of machines and norm are fixed, this paper constructs an auxiliary instance, and analyzes the relationship of optimal values of original instance and auxiliary instance. Then, this paper uses the dynamic algorithm to find an optimal solution to the auxiliary instance and construct a corresponding solution to the original instance, whose objective value is very close to the optimal value. These results improve previous best results on time complexity.

Key words: load balancing, approximation algorithms, all norm

摘要： 具有等级约束的负载均衡问题是不同类平行机排序问题的一个特殊情形。当目标函数为最小化机器负载向量的l_p范数时，通过分析该问题的组合性质，利用目标函数的凸性得到了一个全范数2-近似的组合算法；当机器数为常数时，在固定l_p范数下，构造一个辅助实例，分析输入实例和辅助实例的最优值之间的关系，利用动态规划算法求出辅助实例的最优解，进一步得到输入实例的一个近似解，其目标函数值与最优值无限接近。这些均在算法的时间复杂性方面改进了之前的结果。

关键词: 负载均衡, 近似算法, 全范数