嵇雯蕙 陳智斌

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

1 引言

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

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

2 頂點(diǎn)覆蓋問題

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

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

下面,我們先介紹有關(guān)圖的一些概念.

定義1([13]) 給定一個(gè)無向圖G=(V,E),我們稱G中與頂點(diǎn)v相關(guān)聯(lián)的邊的數(shù)目degG(v)為該頂點(diǎn)v的度.

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

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

針對(duì)頂點(diǎn)覆蓋問題,我們利用分層算法進(jìn)行求解,策略如下.

第一輪開始:

令G0=G.

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

2.計(jì)算集合VD0中每個(gè)頂點(diǎn)v的剩余權(quán)重,計(jì)算過程如下:

(1)令c=min

(2)計(jì)算頂點(diǎn)的度加權(quán)重t(v)=c·degG(v)?

(3)根據(jù)度加權(quán)重計(jì)算頂點(diǎn)的剩余權(quán)重w′(v)=w(v)-t(v).

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

第一輪結(jié)束.

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

根據(jù)以上策略設(shè)計(jì)的分層算法具體描述如下.

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

引理1([14]) 給定一個(gè)無向圖G=(V,E),對(duì)于圖中的每個(gè)頂點(diǎn)v ∈V,都有一個(gè)非負(fù)權(quán)重w(v).若w為度加權(quán)重函數(shù),則≤2OPT,其中OPT 表示頂點(diǎn)覆蓋問題的最優(yōu)頂點(diǎn)覆蓋的總權(quán)重.

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

定理1分層算法對(duì)于求解頂點(diǎn)覆蓋問題的近似比至多為2.

證明根據(jù)分層算法,輸入一個(gè)無向圖G=(V,E),且對(duì)于圖中的每個(gè)頂點(diǎn)v ∈V,都有一個(gè)非負(fù)權(quán)重w(v),算法結(jié)束時(shí)輸出一個(gè)頂點(diǎn)集合C.設(shè)C*是圖G的最小頂點(diǎn)覆蓋.

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

其次,證明頂點(diǎn)覆蓋C中所有頂點(diǎn)的權(quán)重之和≤2OPT.對(duì)頂點(diǎn)集合V中的任意一個(gè)頂點(diǎn)v,有以下兩種可能情形.

3 頂點(diǎn)覆蓋約束下的同類機(jī)排序問題

3.1 LSPT 算法

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

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

3.2 LLSPT 算法

下面給出LLSPT 算法.

4 LLSPT 算法的復(fù)雜度與近似比

4.1 復(fù)雜度

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

4.2 近似比

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

定理證畢.