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

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

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

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

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

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

1　引言

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

給定機(jī)器集M={M1,?M2,?…,?Mm}和任務(wù)集J= {J1,?J2,?…,?Jn}，任務(wù)Jj在機(jī)器Mi上的處理時(shí)間（或稱大?。?pij，將這n個(gè)任務(wù)分配到m臺(tái)機(jī)器上處理，每個(gè)任務(wù)只能分配一臺(tái)機(jī)器。令Si表示在機(jī)器Mi上處理的任務(wù)集，機(jī)器Mi的負(fù)載定義為在其上加工的所有任務(wù)的大小之和，記為Li=∑j:??Jj∈Sipij。GLB問題要求尋找一種分配方案使得機(jī)器負(fù)載向量L= (L1,?L2,?…,Lm)的lp范數(shù)盡可能達(dá)到最小，即：GLB問題的數(shù)學(xué)規(guī)劃形式如下：

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

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

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

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

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

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

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

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

2　問題描述

給定機(jī)器集M={M1,?M2,?…,?Mm}和任務(wù)集J={J1, ?J2,?…,?Jn}，任務(wù)Jj的處理時(shí)間（或稱大?。?pj。令g(Mi)和g(Jj)分別表示機(jī)器Mi和任務(wù)Jj的等級，不失一般性，假定

g(M1)≤g(M2)≤…≤g(Mm)，g(J1)≤g(J2)≤…≤g(Jn)（1）具有等級約束的GLB問題要求，任務(wù)Jj只能在等級不超過g(Jj)的某臺(tái)機(jī)器處理。令CMj={Mi|g(Mi)≤g(Jj)}表示能加工任務(wù)Jj的機(jī)器集，由假定知：

將n個(gè)任務(wù)分配到m臺(tái)機(jī)器上，令Si表示在機(jī)器Mi上處理的任務(wù)集，機(jī)器Mi的負(fù)載定義為其上所有任務(wù)的加工時(shí)間之和，記為 Li=∑j:?Jj∈Sipij。令向量L=(L1,?L2,?…,?Lm)，lp范數(shù)下具有等級約束的GLB問題的數(shù)學(xué)規(guī)劃形式為：

3　全范數(shù)算法

假定任務(wù)是可分的，即每一個(gè)任務(wù)Jj可以分配在多臺(tái)機(jī)器上處理且大小之和為pj。通過分析此假定下該問題的良好性質(zhì)，可以得到一個(gè)多項(xiàng)式時(shí)間算法，該算法得到的解是任意lp范數(shù)下的最優(yōu)解?；谠撍惴ǎ梢缘玫饺蝿?wù)不可分時(shí)的一個(gè)全范數(shù)2-近似算法。

引理1當(dāng)任務(wù)可分時(shí)，任一個(gè)最優(yōu)解x的負(fù)載向量L=(L1,?L2,?…,?Lm)均滿足：

證明 反證法。假定某個(gè)最優(yōu)解x中存在兩個(gè)機(jī)器Mk和Ml滿足k

方便起見，對任一任務(wù)Jj，定義其機(jī)器指標(biāo)vj為能處理任務(wù) Jj的最大機(jī)器下標(biāo)，即 vj=max}。令J[i]={Jj|vj=i}表示機(jī)器指標(biāo)為i的任務(wù)集。顯然，，且任意兩個(gè)不同的J[i]交集為空，即可將任務(wù)集J劃分成m個(gè)不交的任務(wù)集。對任一任務(wù)集S?J，令 p(S)=∑j:Jj∈Spj表示S中所有任務(wù)的大小之和。按如下方法找到一個(gè)最優(yōu)負(fù)載向量：找到最大的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，令；依此類推，可以得到一個(gè)負(fù)載向量。

引理2當(dāng)任務(wù)可分時(shí)，對所有的lp范數(shù)，任一最優(yōu)解x的負(fù)載向量L與?相同，即對i=1,?2,?…,?m，有Li=?i。

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

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

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

矛盾。因此，引理成立。

定理1當(dāng)任務(wù)可分時(shí)，具有等級約束的GLB問題屬于P類。

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

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

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

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

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

這里OPTp表示lp范數(shù)下的最優(yōu)值，最后一個(gè)不等式是因?yàn)槭莑p范數(shù)下最優(yōu)值的下界。

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

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

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

（2）將任務(wù)集J分成兩個(gè)子集：

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

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

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

這里不等式右端第一項(xiàng)是因?yàn)镾i?JB中的每一個(gè)任務(wù)Jj在實(shí)例?中相應(yīng)的任務(wù)?均滿足 p?j≤(1+δ)pj；第二項(xiàng)是因?yàn)?/p>

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

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

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

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

下面給出問題Pm||GoSlp的一個(gè)多項(xiàng)式時(shí)間算法。

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

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

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

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

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

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

5　結(jié)束語

本文設(shè)計(jì)了lp范數(shù)下具有等級約束的GLB問題的一個(gè)全范數(shù)2-近似算法，未來的研究重點(diǎn)之一是給出該問題的一個(gè)全范數(shù)1.388-近似算法和固定lp范數(shù)下的一個(gè)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.

附中文參考文獻(xiàn)：

[16]林凌.lp范數(shù)下兩臺(tái)同型機(jī)半在線問題的最優(yōu)算法[J].浙江大學(xué)學(xué)報(bào):理學(xué)版,2007,34(2):148-157．

[17]閔嘯,劉靜.l2范數(shù)下兩臺(tái)帶緩沖區(qū)同型機(jī)半在線排序問題的最優(yōu)算法[J].浙江大學(xué)學(xué)報(bào):理學(xué)版,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年于云南大學(xué)數(shù)學(xué)專業(yè)獲得博士學(xué)位，現(xiàn)為云南大學(xué)副教授，主要研究領(lǐng)域?yàn)榻扑惴ǎS機(jī)算法和算法博弈論等。發(fā)表學(xué)術(shù)論文20余篇，主持過兩項(xiàng)國家自然科學(xué)基金項(xiàng)目。

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—），女，云南昆明人，云南大學(xué)數(shù)學(xué)系碩士研究生，主要研究領(lǐng)域?yàn)檫\(yùn)籌學(xué)與控制論，組合最優(yōu)化，算法設(shè)計(jì)，博弈論等。

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年于巴黎南大學(xué)計(jì)算機(jī)科學(xué)專業(yè)獲得博士學(xué)位，現(xiàn)為云南大學(xué)教授、博士生導(dǎo)師，主要研究領(lǐng)域?yàn)榻M合最優(yōu)化，近似算法等。發(fā)表學(xué)術(shù)論文50余篇，主持過5項(xiàng)國家自然科學(xué)基金項(xiàng)目。

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

Received 2015-06,Accepted 2015-08.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2015-09-02,http://www.cnki.net/kcms/detail/11.5602.TP.20150902.1100.002.html

文獻(xiàn)標(biāo)志碼：A

中圖分類號(hào)：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