頂點覆蓋約束下的同類機排序算法研究

嵇雯蕙 陳智斌

(昆明理工大學理學院,昆明,650000)

1 引言

經典的平行機排序問題(Parallel Machine Scheduling)是著名的NP-hard 問題.同類機作為同速機的推廣,其排序問題顯然也是NP-hard 的.近幾十年來,關于排序問題,不管是離線還是半在線或在線版本,學者們都做了大量的研究工作[1,2,3].經典的平行機問題存在多項式時間近似方案[4],當機器數固定時,甚至存在完全多項式近似方案[5].2012 年,Wang 等[6]提出了平行機排序與頂點覆蓋的組合問題(Combination of parallel machine scheduling and vertex cover).而一個頂點覆蓋(Vertex Cover)指的是無向圖的一個頂點子集,使得圖中的任意一條邊都至少存在一個頂點屬于該子集.為求解平行機排序與頂點覆蓋的組合問題,Wang 等基于local ratio 算法[7]和LPT(Longest Processing Time first)算法[8]給出了近似比為的算法.同年,Hong 等[9]在Wang 的基礎上,提出了改進算法,當機器數為2 或者3 時,將近似比縮減至.相比排序問題,頂點覆蓋問題雖然同為NP-hard,但它不存在小于1.36 的近似比,除非P=NP[10].

本文考慮如下的頂點覆蓋約束下的同類機排序問題.給定m臺機器M={M1,···,Mm}和n個工件J={J1,···,Jn},其中機器Mj的速度為sj(j=1,···,m),不失一般性,可設s1≤··· ≤sm? 工件Ji的加工時間為pi(i=1,···,n),工件Ji在機器Mj上的負載為(i=1,···,n,j=1,···,m).在這些工件之間,存在著一些“關系”,我們用一個無向圖G=(V,E)來描述這些關系,圖中n個頂點分別代表n個工件,圖中的一條邊表示該邊的端點所對應的兩個工件之間存在關系,對于圖中的每個頂點v ∈V,都有一個非負權重w(v)代表相應工件的加工時間.我們的目標是將一部分工件分配到m臺機器上,使得這些工件所對應的頂點集合構成G的一個頂點覆蓋,同時使得最大完工時間(makespan)最小.針對該問題,我們首先采用分層算法選擇頂點覆蓋,然后結合同類機排序算法設計近似算法進行求解.當所有機器的速度都相差不大時,我們發現該算法具有較好的近似比.

2 頂點覆蓋問題

給定一個無向圖G=(V,E),且對于圖中的每個頂點v ∈V,都有一個非負權重w(v).若存在C ?V,且對任意(u,v)∈E都有u ∈C或v ∈C,則稱C為圖G的一個頂點覆蓋.頂點覆蓋問題的目標是找到圖G的一個頂點覆蓋C,使得C中的頂點權重之和最小.

不難知道,采用原始對偶法(primal-dual)[11]或局部比值法(local ratio)[7],可以得到頂點覆蓋問題的2-近似算法.1985 年,Bar-Yehuda 等[7]提出了一種基于局部比值法的-近似算法.此后,局部比值法被廣泛應用于組合最優化問題中,并且該方法本身已發展為近似算法的一個統一框架[12].

下面,我們先介紹有關圖的一些概念.

定義1([13]) 給定一個無向圖G=(V,E),我們稱G中與頂點v相關聯的邊的數目degG(v)為該頂點v的度.

定義2([14]) 給定一個無向圖G=(V,E),且對于圖中的每個頂點v ∈V,都有一個非負權重w(v).若存在常數c ＞0,使得對任意頂點v,都有w(v)=c·degG(v),則稱頂點權重為度加權重,w為度加權重函數.

定義3([14]) 給定一個無向圖G=(V,E),且對于圖中的每個頂點v ∈V,都有一個非負權重w(v).若存在函數t(v),使得對任意頂點v,都有t(v)=c·degG(v),則稱w′(v)=w(v)-t(v)為頂點的剩余權重,w′為剩余權重函數.

針對頂點覆蓋問題,我們利用分層算法進行求解,策略如下.

第一輪開始:

令G0=G.

1.搜索G0的頂點,若G0中存在度為零的頂點,則將這些頂點放入集合D0并從G0中刪除這些頂點.

2.計算集合VD0中每個頂點v的剩余權重,計算過程如下:

(1)令c=min

(2)計算頂點的度加權重t(v)=c·degG(v)?

(3)根據度加權重計算頂點的剩余權重w′(v)=w(v)-t(v).

3.再次搜索頂點,若存在剩余權重為零的頂點,則將這些頂點放入集合C0.

第一輪結束.

當圖G所有頂點的度均為零時,算法終止? 否則繼續考慮由V(D0∪C0)導出的子圖G1,在G1上重復第一輪的相關步驟.最后C=C0∪C1∪···∪Ck-1就是我們選擇的頂點覆蓋,而VC=D=D0∪D1∪···∪Dk是未被選擇的頂點集合,其中k是算法從開始到結束的總輪數(k ＜n).

根據以上策略設計的分層算法具體描述如下.

在分析分層算法的近似比之前,我們先看一個引理.

引理1([14]) 給定一個無向圖G=(V,E),對于圖中的每個頂點v ∈V,都有一個非負權重w(v).若w為度加權重函數,則≤2OPT,其中OPT 表示頂點覆蓋問題的最優頂點覆蓋的總權重.

引理1 表明:在分層算法中,即使選擇覆蓋圖G=(V,E)中的所有頂點,得到的頂點覆蓋的總權重仍在最優頂點覆蓋的總權重的兩倍之內.由此引理,我們有以下定理.

定理1分層算法對于求解頂點覆蓋問題的近似比至多為2.

證明根據分層算法,輸入一個無向圖G=(V,E),且對于圖中的每個頂點v ∈V,都有一個非負權重w(v),算法結束時輸出一個頂點集合C.設C*是圖G的最小頂點覆蓋.

首先,證明頂點集合C是圖G的一個頂點覆蓋.假設C不是G的頂點覆蓋,則至少存在一條邊未被覆蓋,不妨設這條邊為(u,v).不難發現,與該邊關聯的兩個頂點均屬于獨立集D,這與degG(u)≥1（或degG(v)≥1）矛盾,從而頂點集合C為圖G的一個頂點覆蓋.

其次,證明頂點覆蓋C中所有頂點的權重之和≤2OPT.對頂點集合V中的任意一個頂點v,有以下兩種可能情形.

3 頂點覆蓋約束下的同類機排序問題

3.1 LSPT 算法

對于經典的平行機排序問題,1969 年,Graham 首次提出了著名的LPT 算法[8].我們知道LPT算法是針對同速機提出的,當所有機器速度互不相同時,我們采用類似的思想,給出求解同類機排序問題的LSPT(Longest Scheduling Processing Time first)算法.

對于頂點覆蓋約束下的同類機排序問題,即使找到頂點覆蓋問題的最優頂點覆蓋C*,然后將C*中的工件放到m臺同類機上加工,得到的最大完工時間也未必是最優的.因此,為了得到一個相對滿意的近似解,我們將這兩個問題以及相應的算法進行結合,即通過替換策略將分層算法和LSPT 算法結合起來,給出求解該問題的一個近似算法,簡記為LLSPT(Layering-Longest Scheduling Processing Time first)算法.

3.2 LLSPT 算法

下面給出LLSPT 算法.

4 LLSPT 算法的復雜度與近似比

4.1 復雜度

由LLSPT 算法知,第4 步的循環最多n次,算法的計算量主要集中在分層算法與LSPT 算法上,而前者的最大計算量為O(kn)，其中k是分層算法的循環次數(k ＜n),因此,整個算法的計算復雜度為O(n2(k+logn+m)).

4.2 近似比

定理2存在常數,使得LLSPT 算法為ρ-近似的,其中.

定理證畢.