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的所有任務記為J?B。

證明 令(S1,?S2,?…,?Sm)表示實例I的一個最優解，這里Si表示分配給機器Mi的任務集。顯然：

這里不等式右端第一項是因為Si?JB中的每一個任務Jj在實例?中相應的任務?均滿足 p?j≤(1+δ)pj；第二項是因為

對任意給定的p，由范數的三角不等式和式（7）（8）知，可行解(S?1,?S?2,?…,?S?m)的目標函數值

引理4實例I存在一個可行解(S1,?S2,?…,?Sm)，其目標函數值至多為

下面構造實例I的一個可行解(S1,?S2,?…,?Sm)，這里Si表示分配給機器Mi的任務集。對i=1,2,…,m，將每一個任務所對應的實例I中的任務Jj分配給機器 Mi。對i=1,2,…,m，令表示中大小為δAL的任務的大小之和，按等級從小到大的順序將中盡可能多的（但大小之和不超過s?i+δAL）剩余的任務分配給機器Mi，直至全部分完。容易驗證，此種分配任務的方法可行，從而得到I的一個可行解(S1,?S2,?…,?Sm)，并且這里不等式右端第一項是因為S?i∩J?B中的每一個任務J?j相應的實例I中的任務Jj均滿足 pj≤p?j；第二項是因為分配給機器Mi的大小不超過δAL的任務的大小之和不超過

對任意給定的p，由范數的三角不等式和式（6）（9）（10）知，可行解(S1,?S2,?…,?Sm)的目標函數值

下面給出問題Pm||GoSlp的一個多項式時間算法。

步驟1對任意給定的實例I，按前述方法構造相應的實例I?，不妨設實例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