lp范数下具有等级约束的负载均衡问题*

李伟东，李陈筠然，李建平云南大学，昆明 650091

lp范数下具有等级约束的负载均衡问题*

李伟东+，李陈筠然，李建平
云南大学，昆明 650091

LI Weidong,LICHEN Junran,LI Jianping.Load balancing problem with hierarchical constraints in lpnorm. Journal of Frontiers of Computer Science and Technology,2016,10(8):1184-1190.

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

关键词：负载均衡；近似算法；全范数

1　引言

自20世纪60年代起，以最小化最大机器负载[1-2]为目标的负载均衡问题因其在工业生产、并行计算和网络资源分配等领域的广泛应用，成为理论计算机科学和运筹学等领域研究的重点内容之一。注意到，机器的最大负载在数学上相当于机器负载向量的l∞范数。由于最小化最大机器负载侧重于刻画最大机器完工时间，并不适用于描述机器完工时间的平均情况，其广义形式即最小化机器负载向量的lp范数成为近十年来的研究热点之一。方便起见，称此类问题为广义的负载均衡问题（generalized loading balancing problem，GLB），其定义如下：

给定机器集M={M1, M2, …, Mm}和任务集J= {J1, J2, …, Jn}，任务Jj在机器Mi上的处理时间（或称大小）为 pij，将这n个任务分配到m台机器上处理，每个任务只能分配一台机器。令Si表示在机器Mi上处理的任务集，机器Mi的负载定义为在其上加工的所有任务的大小之和，记为Li=∑j:  Jj∈Sipij。GLB问题要求寻找一种分配方案使得机器负载向量L= (L1, L2, …,Lm)的lp范数尽可能达到最小，即：GLB问题的数学规划形式如下：

为更好地陈述相关的研究成果，下面给出理论计算机科学领域内与本文相关的基本定义。

定义1令Π表示一个最小化问题，I表示该问题的任一实例，A表示问题Π的一个多项式时间算法，A(I)和OPT(I)分别表示算法A解实例I所得到的可行解的目标函数值和最优值，则算法A的近似比（又称最坏情形界）定义为：

定义2对于最小化问题Π，若对任意的实数ε>0，算法簇Aε都能得到一个(1+ε)-近似解，则称算法簇Aε是一个多项式时间近似方案（polynomial time approximation scheme，PTAS）。如果算法簇Aε的运行时间还是关于的多项式函数，则称之为全多项式时间近似方案（fully polynomial time approximation scheme，FPTAS）。

对于GLB问题，Awerbuch等人[3]证明了贪婪算法在任意固定lp范数下的近似比为θ(p)。Azar和Epstein[4]利用凸规划和舍入取整技术给出了固定的lp范数下的一个2-近似算法；Kumar等人[5]利用一种新的舍入取整技术给出了固定的lp范数下的近似比更好的算法，该算法的近似比依赖于p的取值。

当 pij∈{pj, +∞}(j=1,2,…,n)时，即每个任务只能在某些机器上处理，且处理时间相同时，Azar和Epstein[4]给出了固定的lp范数下的一个2-1/(2p2p)-近似算法；Azar等人[6]证明了任意固定的lp范数下，该问题都不存在PTAS，除非P=NP，并给出了一个全范数2-近似算法，即该算法的输入解是任意lp范数下的一个2-近似解。但是，该算法需要求解具有指数个不等式约束的线性规划，时间复杂性较高。

当机器数m为固定常数时，Azar和Epstein[4]给出了固定的lp范数下的GLB问题的一个PTAS。当机器数m为固定常数且 pij∈{pj, +∞}(j=1,2,…,n)时，Azar等人[6]给出了固定的lp范数下的运行时间为O(nm+1)的一个FPTAS，这里略去了关于和m的常数项，因为ε和m是固定常数。

当 pij=pj(j=1,2,…,n)时，即每个任务在不同机器上的处理时间都相同时，Alon等人[7]给出了固定的lp范数下的一个PTAS；Chandra和Wong[8]给出了一个全范数的1.5-近似算法；Azar和Taub[9]给出了一个全范数的1.388-近似算法，这是目前最好的结果。关于在线情形下的GLB问题及其特殊情形的研究结果可参考文献[10-17]。

本文考虑GLB问题的一个特殊情形，即具有等级约束的GLB问题。尽管l∞范数下具有等级约束的GLB问题已有大量的研究成果[18-20]，但是没有关于一般的lp范数下具有等级约束的GLB问题的相关研究。本文结构如下：第2章给出了该问题的数学描述；第3章通过分析该问题的组合特性，给出了一个运行时间为O(mn)的全范数2-近似算法；第4章当机器数m为固定常数时，给出了一个O(n)的FPTAS。

2　问题描述

给定机器集M={M1, M2, …, Mm}和任务集J={J1,  J2, …, Jn}，任务Jj的处理时间（或称大小）为 pj。令g(Mi)和g(Jj)分别表示机器Mi和任务Jj的等级，不失一般性，假定

g(M1)≤g(M2)≤…≤g(Mm)，g(J1)≤g(J2)≤…≤g(Jn)（1）具有等级约束的GLB问题要求，任务Jj只能在等级不超过g(Jj)的某台机器处理。令CMj={Mi|g(Mi)≤g(Jj)}表示能加工任务Jj的机器集，由假定知：

将n个任务分配到m台机器上，令Si表示在机器Mi上处理的任务集，机器Mi的负载定义为其上所有任务的加工时间之和，记为 Li=∑j: Jj∈Sipij。令向量L=(L1, L2, …, Lm)，lp范数下具有等级约束的GLB问题的数学规划形式为：

3　全范数算法

假定任务是可分的，即每一个任务Jj可以分配在多台机器上处理且大小之和为pj。通过分析此假定下该问题的良好性质，可以得到一个多项式时间算法，该算法得到的解是任意lp范数下的最优解。基于该算法，可以得到任务不可分时的一个全范数2-近似算法。

引理1当任务可分时，任一个最优解x的负载向量L=(L1, L2, …, Lm)均满足：

证明 反证法。假定某个最优解x中存在两个机器Mk和Ml满足k

方便起见，对任一任务Jj，定义其机器指标vj为能处理任务 Jj的最大机器下标，即 vj=max}。令J[i]={Jj|vj=i}表示机器指标为i的任务集。显然，，且任意两个不同的J[i]交集为空，即可将任务集J划分成m个不交的任务集。对任一任务集S⊆J，令 p(S)=∑j:Jj∈Spj表示S中所有任务的大小之和。按如下方法找到一个最优负载向量：找到最大的m1，使得

再找到最大的m2，使得

按此方法依次找到m3, m4,…,mk，使得=m，且对t=3,4,…,k，mt满足：

由m1, m2,…,mk的定义知：

对 i=1,2,…,m1，令；对i=m1+1,m1+ 2,…,m1+m2，令；依此类推，可以得到一个负载向量。

引理2当任务可分时，对所有的lp范数，任一最优解x的负载向量L与͂相同，即对i=1, 2, …, m，有Li=͂i。

证明 反证法。对任一最优解x，不失一般性，假定L1≥L2≥…≥Lm。若L≠͂，找到最小的机器下标k，使得Lk≠͂k。分如下两种情况讨论：

情形1Lk>L͂k。由知，存在一个下标最小的机器Ml满足，这里l>k。由l的最小性知，。由mt的极大性知，在最优解x中，至少存在一个满足机器指标vj>l-1的任务Jj在机器Mi（i≤l-1）上处理，这意味着Jj可以在机器Ml上处理。同引理1的证明类似，可以构造一个新的目标函数值更小的可行解，同x的最优性矛盾。

情形2Lk<。找到最小的t，使得k≤。由引理1和͂的定义知，。由中的任务只能在前m1+m2+…+mt台机器上处理，且其大小之和为：

矛盾。因此，引理成立。

定理1当任务可分时，具有等级约束的GLB问题属于P类。

证明 由引理2知，只需构造一个负载向量为L͂的可行解即可。对i=1,2,…,m，按下标从小到大的顺序，将任务依次分配给机器Mi，直至该机器的负载恰为͂i。由前述引理知，此方法能得到负载向量为͂的可行解。易知，整个算法的时间复杂性为O(nm)。

当任务不可分时，具有等级约束的GLB问题是文献[6]中所考虑问题的一种特殊情形，因此存在一个全范数2-近似算法，即该算法能找到一个可行解，对任意的lp范数，其目标函数值都不超过最优值的2倍。但是该算法的时间复杂性较高。基于定理1，可以得到。

定理2当任务不可分时，具有等级约束的GLB问题可在 O(mn)时间内找到全范数2-近似解。

证明根据引理2，对 i=1,2,…,m，按下标从小到大将未分配的任务分配给机器 Mi，直至该机器的负载首次超过͂1或所有的任务都被分配，从而得到一个可行解，其负载向量为。对 i=1,2,…,m，令Jji表示最后一个分配给机器 Mi的任务，则由算法的选择知：

因此，由范数的三角不等式知：

这里OPTp表示lp范数下的最优值，最后一个不等式是因为是lp范数下最优值的下界。

4　机器数为常数的情形

本文考虑给定的lp范数下机器数为常数的情形，将此问题记为。目前该问题存在着一个时间复杂性为O(mn(mn/ε)m)=O(nm+1)的一个FPTAS[6]，这里m、ε是固定常数。令表示m台机器的平均负载，m维向量AL=(AL,AL,…,AL)表示平均负载向量。对于给定的 p，令L=(L1, L2, …, Lm)表示对应于最优解x的负载向量。由lp范数的凸性知，x的目标函数值为：

对于Pm||GoS lp的任一实例I=(J,M;p,g)和给定的ε>0，令δ=ε/3，按如下方式构造一个辅助实例

（2）将任务集J分成两个子集：

（3）对于每一个任务Jj∈JB，相应地构造̂中的一个任务，满足：

易知，pj≤p̂j≤pj+δ2AL≤(1+δ)pj，这里最后一个不等式是由于JB中任务Jj都满足 pj>δAL。对应于Jj∈JB的所有任务记为ĴB。

证明 令(S1, S2, …, Sm)表示实例I的一个最优解，这里Si表示分配给机器Mi的任务集。显然：

这里不等式右端第一项是因为Si⋂JB中的每一个任务Jj在实例̂中相应的任务̂均满足 p̂j≤(1+δ)pj；第二项是因为

对任意给定的p，由范数的三角不等式和式（7）（8）知，可行解(Ŝ1, Ŝ2, …, Ŝm)的目标函数值

引理4实例I存在一个可行解(S1, S2, …, Sm)，其目标函数值至多为

下面构造实例I的一个可行解(S1, S2, …, Sm)，这里Si表示分配给机器Mi的任务集。对i=1,2,…,m，将每一个任务所对应的实例I中的任务Jj分配给机器 Mi。对i=1,2,…,m，令表示中大小为δAL的任务的大小之和，按等级从小到大的顺序将中尽可能多的（但大小之和不超过ŝi+δAL）剩余的任务分配给机器Mi，直至全部分完。容易验证，此种分配任务的方法可行，从而得到I的一个可行解(S1, S2, …, Sm)，并且这里不等式右端第一项是因为Ŝi∩ĴB中的每一个任务Ĵj相应的实例I中的任务Jj均满足 pj≤p̂j；第二项是因为分配给机器Mi的大小不超过δAL的任务的大小之和不超过

对任意给定的p，由范数的三角不等式和式（6）（9）（10）知，可行解(S1, S2, …, Sm)的目标函数值

下面给出问题Pm||GoSlp的一个多项式时间算法。

步骤1对任意给定的实例I，按前述方法构造相应的实例Î，不妨设实例Î中的任务总数为n̂。

步骤2令初始状态空间为φ0={(0,0,…,0)}。对j=1,2,…,̂，状态空间φj可由状态空间φj-1按如下方式拓展得到：

这里ei表示第i个坐标为1，其余坐标为0的m维单位向量；集合A和集合B之和A+B={a+b|a∈A, b∈B}。

步骤3找到φn̂中目标函数值最小的向量，并找到相应的可行解，利用引理4证明中的方法构造实例I的一个可行解(S1, S2, …, Sm)，并输出。

定理3上述算法是问题Pm||GoS lp的一个运行时间为O(n)的FPTAS。

这里第三个不等式由式（6）得到，最后一个等式是由于δ=ε/3。

5　结束语

本文设计了lp范数下具有等级约束的GLB问题的一个全范数2-近似算法，未来的研究重点之一是给出该问题的一个全范数1.388-近似算法和固定lp范数下的一个PTAS。

References:

[1]Graham R L.Bounds for certain multiprocessing anomalies[J]. Bell System Technical Journal,1966,45(9):1563-1581.

[2]Lenstra J K,Shmoys D B,Tardos E.Approximation algorithms for scheduling unrelated parallel machines[J].Mathematical Programming,1990,46(3):259-271.

[3]Awerbuch B,Azar Y,Grove E,et al.Load balancing in the lpnorm[C]//Proceedings of the 36th Annual Symposium on Foundations of Computer Science,Milwaukee,USA,Oct 23-25,1995.Piscataway,USA:IEEE,1995:383-391.

[4]Azar Y,Epstein A.Convex programming for scheduling unrelated parallel machines[C]//Proceedings of the 37th Annual ACM Symposium on Theory of Computing,Baltimore,USA, May 22-24,2005.New York,USA:ACM,2005:331-337.

[5]Kumar V S A,Marathe M V,Parthasarathy S,et al.A unified approach to scheduling on unrelated parallel machines[J]. Journal of theACM,2009,56(5):28.

[6]Azar Y,Epstein L,Richter Y,et al.All-norm approximation algorithms[J].Journal ofAlgorithms,2004,52(2):120-133.

[7]Alon N,Azar Y,Woeginger G J,et al.Approximation schemes for scheduling on parallel machines[J].Journal of Scheduling, 1998,1(1):55-66.

[8]Chandra A K,Wong C K.Worst-case analysis of a placement algorithm related to storage allocation[J].SIAM Journal on Computing,1975,4(3):249-263.

[9]Azar Y,Taub S.All-norm approximation for scheduling on identical machines[C]//LNCS 3111:Proceedings of the 2004 Scandinavian Workshop on Algorithm Theory,Humlebaek, Denmark,Jul 8-10,2004.Berlin,Heidelberg:Springer,2004: 298-310.

[10]Avidor A,Azar Y,Sgall J.Ancient and new algorithms for load balancing in the lpnorm[J].Algorithmica,2001,29(3): 422-441.

[11]Azar Y,Epstein A,Epstein L.Load balancing of temporary tasks in the lpnorm[J].Theoretical Computer Science, 2006,361(2/3):314-328.

[12]Du Donglei,Jiang Xiaoyue,Zhang Guochuan.Optimal preemptive online scheduling to minimize lpnorm on two processors[J].Journal of Manufacturing and Management Optimization,2005,1(3):345-351.

[13]Epstein L,Tassa T.Optimal preemptive scheduling for general target functions[J].Journal of Computer and System Sciences,2006,72(1):132-162.

[14]Lin Ling,Tan Zhiyi,He Yong.Deterministic and randomized scheduling problems under the lpnorm on two identical machines[J].Journal of Zhejiang University:Science A, 2005,6(1):20-26.

[15]Shuai Tianping,Du Donglei,Jiang Xiaoyue.On-line preemptive machine scheduling with lpnorm on two uniform machines[J].Journal of Scheduling,2015,18(2):185-194.

[16]Lin Ling.Semi-online scheduling algorithm under the lpnorm on two identical machines[J]．Journal of Zhejiang University:Science Edition,2007,34(2):148-151.

[17]Min Xiao,Liu Jing.Semi on-line scheduling problem on two identical machines with a buffer under the l2norm[J]. JournaI of Zhejiang University:Science Edition,2008,35 (5):511-516.

[18]Hwang H C,Chang S Y,Lee K.Parallel machine scheduling under a grade of service provision[J].Computers&Operations Research,2004,31(12):2055-2061.

[19]Ou Jinwen,Leung J Y T,Li C L.Scheduling parallel machines with inclusive processing set restrictions[J].Naval Research Logistics,2008,55(4):328-338.

[20]Li Weidong,Li Jianping,Zhang Tongquan.Two approximation schemes for scheduling on parallel machines under a grade of service provision[J].Asia Pacific Journal of Operational Research,2012,29(5):1250029.

附中文参考文献：

[16]林凌.lp范数下两台同型机半在线问题的最优算法[J].浙江大学学报:理学版,2007,34(2):148-157．

[17]闵啸,刘静.l2范数下两台带缓冲区同型机半在线排序问题的最优算法[J].浙江大学学报:理学版,2008,35(5): 511-516．

LI Weidong was born in 1981.He received his Ph.D.degree in mathematics from Yunnan University in 2010.Now he is an associate professor at Yunnan University.His research interests include approximation algorithm,randomized algorithm and algorithmic game theory,etc.

李伟东（1981—），男，河南新密人，2010年于云南大学数学专业获得博士学位，现为云南大学副教授，主要研究领域为近似算法，随机算法和算法博弈论等。发表学术论文20余篇，主持过两项国家自然科学基金项目。

LICHEN Junran was born in 1991.She is an M.S.candidate at Department of Mathematics,Yunnan University. Her research interests include operations research and control theory,combinatorial optimization,algorithms design and game theory,etc.

李陈筠然（1991—），女，云南昆明人，云南大学数学系硕士研究生，主要研究领域为运筹学与控制论，组合最优化，算法设计，博弈论等。

LI Jianping was born in 1965.He received the Ph.D.degree in computer science from Universite de Paris-Sud in 1999.Now he is a professor and Ph.D.supervisor at Yunnan University.His research interests include combinatorial optimization and approximation algorithm,etc.

李建平（1965—），男，云南嵩明人，1999年于巴黎南大学计算机科学专业获得博士学位，现为云南大学教授、博士生导师，主要研究领域为组合最优化，近似算法等。发表学术论文50余篇，主持过5项国家自然科学基金项目。

*The National Natural Science Foundation of China under Grant Nos.11301466,11461081,61170222(国家自然科学基金);the Natural Science Foundation of Yunnan Province under Grant No.2014FB114(云南省自然科学基金).

Received 2015-06,Accepted 2015-08.

CNKI网络优先出版:2015-09-02,http://www.cnki.net/kcms/detail/11.5602.TP.20150902.1100.002.html

文献标志码：A

中图分类号：TP301；O223

doi:10.3778/j.issn.1673-9418.1507046

Load Balancing Problem with Hierarchical Constraints in lpNormƽ

LI Weidong+,LICHEN Junran,LI Jianping
Yunnan University,Kunming 650091,China
+Corresponding author:E-mail:weidong@ynu.edu.cn

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 lpnorm 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