lp范數(shù)下具有等級約束的負載均衡問題*

李偉東，李陳筠然，李建平云南大學，昆明 650091

lp范數(shù)下具有等級約束的負載均衡問題*

李偉東+，李陳筠然，李建平
云南大學，昆明 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.

摘要：具有等級約束的負載均衡問題是不同類平行機排序問題的一個特殊情形。當目標函數(shù)為最小化機器負載向量的lp范數(shù)時，通過分析該問題的組合性質(zhì)，利用目標函數(shù)的凸性得到了一個全范數(shù)2-近似的組合算法；當機器數(shù)為常數(shù)時，在固定lp范數(shù)下，構(gòu)造一個輔助實例，分析輸入實例和輔助實例的最優(yōu)值之間的關(guān)系，利用動態(tài)規(guī)劃算法求出輔助實例的最優(yōu)解，進一步得到輸入實例的一個近似解，其目標函數(shù)值與最優(yōu)值無限接近。這些均在算法的時間復雜性方面改進了之前的結(jié)果。

關(guān)鍵詞：負載均衡；近似算法；全范數(shù)

1　引言

自20世紀60年代起，以最小化最大機器負載[1-2]為目標的負載均衡問題因其在工業(yè)生產(chǎn)、并行計算和網(wǎng)絡資源分配等領(lǐng)域的廣泛應用，成為理論計算機科學和運籌學等領(lǐng)域研究的重點內(nèi)容之一。注意到，機器的最大負載在數(shù)學上相當于機器負載向量的l∞范數(shù)。由于最小化最大機器負載側(cè)重于刻畫最大機器完工時間，并不適用于描述機器完工時間的平均情況，其廣義形式即最小化機器負載向量的lp范數(shù)成為近十年來的研究熱點之一。方便起見，稱此類問題為廣義的負載均衡問題（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范數(shù)盡可能達到最小，即：GLB問題的數(shù)學規(guī)劃形式如下：

為更好地陳述相關(guān)的研究成果，下面給出理論計算機科學領(lǐng)域內(nèi)與本文相關(guān)的基本定義。

定義1令Π表示一個最小化問題，I表示該問題的任一實例，A表示問題Π的一個多項式時間算法，A(I)和OPT(I)分別表示算法A解實例I所得到的可行解的目標函數(shù)值和最優(yōu)值，則算法A的近似比（又稱最壞情形界）定義為：

定義2對于最小化問題Π，若對任意的實數(shù)ε>0，算法簇Aε都能得到一個(1+ε)-近似解，則稱算法簇Aε是一個多項式時間近似方案（polynomial time approximation scheme，PTAS）。如果算法簇Aε的運行時間還是關(guān)于的多項式函數(shù)，則稱之為全多項式時間近似方案（fully polynomial time approximation scheme，F(xiàn)PTAS）。

對于GLB問題，Awerbuch等人[3]證明了貪婪算法在任意固定lp范數(shù)下的近似比為θ(p)。Azar和Epstein[4]利用凸規(guī)劃和舍入取整技術(shù)給出了固定的lp范數(shù)下的一個2-近似算法；Kumar等人[5]利用一種新的舍入取整技術(shù)給出了固定的lp范數(shù)下的近似比更好的算法，該算法的近似比依賴于p的取值。

當 pij∈{pj,?+∞}(j=1,2,…,n)時，即每個任務只能在某些機器上處理，且處理時間相同時，Azar和Epstein[4]給出了固定的lp范數(shù)下的一個2-1/(2p2p)-近似算法；Azar等人[6]證明了任意固定的lp范數(shù)下，該問題都不存在PTAS，除非P=NP，并給出了一個全范數(shù)2-近似算法，即該算法的輸入解是任意lp范數(shù)下的一個2-近似解。但是，該算法需要求解具有指數(shù)個不等式約束的線性規(guī)劃，時間復雜性較高。

當機器數(shù)m為固定常數(shù)時，Azar和Epstein[4]給出了固定的lp范數(shù)下的GLB問題的一個PTAS。當機器數(shù)m為固定常數(shù)且 pij∈{pj,?+∞}(j=1,2,…,n)時，Azar等人[6]給出了固定的lp范數(shù)下的運行時間為O(nm+1)的一個FPTAS，這里略去了關(guān)于和m的常數(shù)項，因為ε和m是固定常數(shù)。

當 pij=pj(j=1,2,…,n)時，即每個任務在不同機器上的處理時間都相同時，Alon等人[7]給出了固定的lp范數(shù)下的一個PTAS；Chandra和Wong[8]給出了一個全范數(shù)的1.5-近似算法；Azar和Taub[9]給出了一個全范數(shù)的1.388-近似算法，這是目前最好的結(jié)果。關(guān)于在線情形下的GLB問題及其特殊情形的研究結(jié)果可參考文獻[10-17]。

本文考慮GLB問題的一個特殊情形，即具有等級約束的GLB問題。盡管l∞范數(shù)下具有等級約束的GLB問題已有大量的研究成果[18-20]，但是沒有關(guān)于一般的lp范數(shù)下具有等級約束的GLB問題的相關(guān)研究。本文結(jié)構(gòu)如下：第2章給出了該問題的數(shù)學描述；第3章通過分析該問題的組合特性，給出了一個運行時間為O(mn)的全范數(shù)2-近似算法；第4章當機器數(shù)m為固定常數(shù)時，給出了一個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范數(shù)下具有等級約束的GLB問題的數(shù)學規(guī)劃形式為：

3　全范數(shù)算法

假定任務是可分的，即每一個任務Jj可以分配在多臺機器上處理且大小之和為pj。通過分析此假定下該問題的良好性質(zhì)，可以得到一個多項式時間算法，該算法得到的解是任意lp范數(shù)下的最優(yōu)解。基于該算法，可以得到任務不可分時的一個全范數(shù)2-近似算法。

引理1當任務可分時，任一個最優(yōu)解x的負載向量L=(L1,?L2,?…,?Lm)均滿足：

證明 反證法。假定某個最優(yōu)解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中所有任務的大小之和。按如下方法找到一個最優(yōu)負載向量：找到最大的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范數(shù)，任一最優(yōu)解x的負載向量L與?相同，即對i=1,?2,?…,?m，有Li=?i。

證明 反證法。對任一最優(yōu)解x，不失一般性，假定L1≥L2≥…≥Lm。若L≠?，找到最小的機器下標k，使得Lk≠?k。分如下兩種情況討論：

情形1Lk>L?k。由知，存在一個下標最小的機器Ml滿足，這里l>k。由l的最小性知，。由mt的極大性知，在最優(yōu)解x中，至少存在一個滿足機器指標vj>l-1的任務Jj在機器Mi（i≤l-1）上處理，這意味著Jj可以在機器Ml上處理。同引理1的證明類似，可以構(gòu)造一個新的目標函數(shù)值更小的可行解，同x的最優(yōu)性矛盾。

情形2Lk<。找到最小的t，使得k≤。由引理1和?的定義知，。由中的任務只能在前m1+m2+…+mt臺機器上處理，且其大小之和為：

矛盾。因此，引理成立。

定理1當任務可分時，具有等級約束的GLB問題屬于P類。

證明 由引理2知，只需構(gòu)造一個負載向量為L?的可行解即可。對i=1,2,…,m，按下標從小到大的順序，將任務依次分配給機器Mi，直至該機器的負載恰為?i。由前述引理知，此方法能得到負載向量為?的可行解。易知，整個算法的時間復雜性為O(nm)。

當任務不可分時，具有等級約束的GLB問題是文獻[6]中所考慮問題的一種特殊情形，因此存在一個全范數(shù)2-近似算法，即該算法能找到一個可行解，對任意的lp范數(shù)，其目標函數(shù)值都不超過最優(yōu)值的2倍。但是該算法的時間復雜性較高?；诙ɡ?，可以得到。

定理2當任務不可分時，具有等級約束的GLB問題可在?O(mn)時間內(nèi)找到全范數(shù)2-近似解。

證明根據(jù)引理2，對?i=1,2,…,m，按下標從小到大將未分配的任務分配給機器?Mi，直至該機器的負載首次超過?1或所有的任務都被分配，從而得到一個可行解，其負載向量為。對?i=1,2,…,m，令Jji表示最后一個分配給機器?Mi的任務，則由算法的選擇知：

因此，由范數(shù)的三角不等式知：

這里OPTp表示lp范數(shù)下的最優(yōu)值，最后一個不等式是因為是lp范數(shù)下最優(yōu)值的下界。

4　機器數(shù)為常數(shù)的情形

本文考慮給定的lp范數(shù)下機器數(shù)為常數(shù)的情形，將此問題記為。目前該問題存在著一個時間復雜性為O(mn(mn/ε)m)=O(nm+1)的一個FPTAS[6]，這里m、ε是固定常數(shù)。令表示m臺機器的平均負載，m維向量AL=(AL,AL,…,AL)表示平均負載向量。對于給定的 p，令L=(L1,?L2,?…,?Lm)表示對應于最優(yōu)解x的負載向量。由lp范數(shù)的凸性知，x的目標函數(shù)值為：

對于Pm||GoS lp的任一實例I=(J,M;p,g)和給定的ε>0，令δ=ε/3，按如下方式構(gòu)造一個輔助實例

（2）將任務集J分成兩個子集：

（3）對于每一個任務Jj∈JB，相應地構(gòu)造?中的一個任務，滿足：

易知，pj≤p?j≤pj+δ2AL≤(1+δ)pj，這里最后一個不等式是由于JB中任務Jj都滿足 pj>δAL。對應于Jj∈JB的所有任務記為J?B。

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

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

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

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

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

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

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

步驟1對任意給定的實例I，按前述方法構(gòu)造相應的實例I?，不妨設(shè)實例I?中的任務總數(shù)為n?。

步驟2令初始狀態(tài)空間為φ0={(0,0,…,0)}。對j=1,2,…,?，狀態(tài)空間φj可由狀態(tài)空間φj-1按如下方式拓展得到：

這里ei表示第i個坐標為1，其余坐標為0的m維單位向量；集合A和集合B之和A+B={a+b|a∈A,?b∈B}。

步驟3找到φn?中目標函數(shù)值最小的向量，并找到相應的可行解，利用引理4證明中的方法構(gòu)造實例I的一個可行解(S1,?S2,?…,?Sm)，并輸出。

定理3上述算法是問題Pm||GoS lp的一個運行時間為O(n)的FPTAS。

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

5　結(jié)束語

本文設(shè)計了lp范數(shù)下具有等級約束的GLB問題的一個全范數(shù)2-近似算法，未來的研究重點之一是給出該問題的一個全范數(shù)1.388-近似算法和固定lp范數(shù)下的一個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范數(shù)下兩臺同型機半在線問題的最優(yōu)算法[J].浙江大學學報:理學版,2007,34(2):148-157．

[17]閔嘯,劉靜.l2范數(shù)下兩臺帶緩沖區(qū)同型機半在線排序問題的最優(yōu)算法[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年于云南大學數(shù)學專業(yè)獲得博士學位，現(xiàn)為云南大學副教授，主要研究領(lǐng)域為近似算法，隨機算法和算法博弈論等。發(fā)表學術(shù)論文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—），女，云南昆明人，云南大學數(shù)學系碩士研究生，主要研究領(lǐng)域為運籌學與控制論，組合最優(yōu)化，算法設(shè)計，博弈論等。

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年于巴黎南大學計算機科學專業(yè)獲得博士學位，現(xiàn)為云南大學教授、博士生導師，主要研究領(lǐng)域為組合最優(yōu)化，近似算法等。發(fā)表學術(shù)論文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網(wǎng)絡優(yōu)先出版: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