摘 要:作為對(duì)裝箱覆蓋問(wèn)題的推廣，提出帶拒絕的裝箱覆蓋問(wèn)題#65377;設(shè)有許多等長(zhǎng)的一維箱子，給定一個(gè)物品集，每個(gè)物品有兩個(gè)參數(shù):長(zhǎng)度和費(fèi)用#65377;物品可以放入箱子也可被拒絕放入箱子，每個(gè)物品只準(zhǔn)放入一只箱子中，每只箱子中的物品容量總和至少為箱子容量，一旦箱子中的物品長(zhǎng)度達(dá)到要求則需啟用新箱#65377;如果物品被放入箱中，則產(chǎn)生費(fèi)用#65377;該問(wèn)題是一個(gè)新的組合優(yōu)化問(wèn)題，在內(nèi)部互聯(lián)網(wǎng)信息管理等問(wèn)題中有著廣泛的應(yīng)用背景#65377;給出一個(gè)求解該問(wèn)題的局內(nèi)近似算法C-FF，分析其最壞情況漸近性能比為1/2，并給出了相應(yīng)的實(shí)驗(yàn)結(jié)果#65377;

關(guān)鍵詞:箱覆蓋問(wèn)題;近似算法;最壞情況漸近性能比;因特網(wǎng)通信;信息管理

中圖分類號(hào):TP393文獻(xiàn)標(biāo)識(shí)碼:A

1 引 言

面對(duì)內(nèi)外眾多客戶對(duì)Web服務(wù)信息的高頻率訪問(wèn)要求，如何有效地對(duì)內(nèi)部網(wǎng)(Intranet) 的分布式信息系統(tǒng)進(jìn)行管理，以達(dá)到低費(fèi)用#65380;高效率的目的，是非常重要的關(guān)鍵技術(shù)#65377;文獻(xiàn)[1]首先提出這類問(wèn)題，進(jìn)行了一定深度的研究#65377;文獻(xiàn)[2]對(duì)此問(wèn)題進(jìn)行了探討#65377;一個(gè)企業(yè)為了有效地降低通信費(fèi)用，往往將被訪問(wèn)頻繁的外部Internet信息塊下載至Intranet內(nèi)部的網(wǎng)絡(luò)服務(wù)器上，使之成為內(nèi)部信息塊#65377;但由于網(wǎng)絡(luò)服務(wù)器本身內(nèi)存的限制及訪問(wèn)該服務(wù)器上的信息的速度的要求，企業(yè)要有選擇地下載Internet外部信息塊#65377;企業(yè)要考慮的是如何使通信費(fèi)用總和最小#65377;

本文將上述問(wèn)題轉(zhuǎn)化成如下定義的優(yōu)化問(wèn)題:如何合理地將互聯(lián)網(wǎng)上的信息分布到所有Web服務(wù)器上，在至少達(dá)到各個(gè)服務(wù)器容量基本額度要求下，使這些信息因被訪問(wèn)而產(chǎn)生的通信費(fèi)用最小?因?yàn)榭梢詫?duì)每個(gè)有用的信息塊定義兩個(gè)參數(shù):信息塊容量，表示其內(nèi)存大小;信息塊費(fèi)用值，表示放在服務(wù)器上產(chǎn)生的費(fèi)用值#65377;從而目標(biāo)變?yōu)檫_(dá)到放在服務(wù)器上的信息塊費(fèi)用值之和最少的服務(wù)器數(shù)最多#65377;該問(wèn)題描述如下:

設(shè)有長(zhǎng)為C的一維箱子，給定n個(gè)物品的序列Ln=<ɑ1，ɑ2，…，ɑn>，物品ɑi(1≤i≤n)的大小為ωi，費(fèi)用值為pi(1≤i≤n)#65377;物品可以放入箱子也可被拒絕放入箱子#65377;每個(gè)物品只準(zhǔn)放入一只箱子中，每只箱子中的物品容量總和至少超過(guò)箱子容量，如果某物品被放入箱中，則產(chǎn)生費(fèi)用pi，怎樣安排物品使箱子中物品總費(fèi)用之和最小同時(shí)容量達(dá)到要求的箱子數(shù)最多#65377;我們稱此問(wèn)題為帶拒絕箱覆蓋問(wèn)題#65377;

注意到如果令每個(gè)物品的費(fèi)用都充分大，大于購(gòu)買服務(wù)器的費(fèi)用，在最優(yōu)解中該物品一定不會(huì)拒絕#65377;帶拒絕箱覆蓋問(wèn)題就變成箱覆蓋問(wèn)題，它是強(qiáng)NP難的^[3]，因此帶拒絕箱覆蓋問(wèn)題也是強(qiáng)NP難的#65377;

計(jì)算技術(shù)與自動(dòng)化2007年6月第26卷第2期楊鼎強(qiáng)等:帶拒絕箱覆蓋問(wèn)題的局內(nèi)算法本文第2節(jié)給出相關(guān)知識(shí);第3節(jié)提出一個(gè)求解帶拒絕箱覆蓋問(wèn)題的局內(nèi)近似算法C-FF算法，然后分析了該算法的性能;第4節(jié)給出了實(shí)驗(yàn)結(jié)果#65377;

2 相關(guān)知識(shí)

箱覆蓋問(wèn)題是:給定n個(gè)物品的序列Ln=<ɑ1，ɑ2，…，ɑn>，物品ɑi(1≤i≤n)的大小為ωi∈(0，1]，要求將這些物品裝入單位容量的箱子B1，B2，…，Bm中，使得每個(gè)箱子中的物品大小之和至少為1，并使所使用的箱子數(shù)目m最大#65377;

箱覆蓋問(wèn)題是組合優(yōu)化領(lǐng)域的基本問(wèn)題，已有很多好的結(jié)果^[4-6]，而對(duì)帶拒絕裝箱覆蓋問(wèn)題，尚未見(jiàn)文獻(xiàn)研究#65377;由于目前NP完全問(wèn)題不存在有效時(shí)間內(nèi)求得精確解的算法，因此設(shè)計(jì)和分析其近似算法是重要的研究?jī)?nèi)容#65377;設(shè)A為一近似算法，A(L)表示算法A對(duì)輸入物品序列L操作所使用的裝箱數(shù)，OPT(L)表示最優(yōu)值#65377;算法A的最壞情況漸近性能比定義為R∞A=limn→∞infL{A(L)/OPT(L)|OPT(L)≥n}#65377;

根據(jù)對(duì)物品信息的依賴程度，近似算法分為局內(nèi)(online)算法和局外(offline)算法#65377;如果在依序處理各輸入物品時(shí)，不知道任何后續(xù)物品信息，并立即給出當(dāng)前物品的裝箱方案，則稱為局內(nèi)算法;而首先得到所有物品信息之后，統(tǒng)一處理所有物品的裝箱方案，則稱為局外算法#65377;

最早研究此類帶拒絕的組合優(yōu)化問(wèn)題是可拒絕并行處理器調(diào)度問(wèn)題，它與本文所討論的問(wèn)題有一定聯(lián)系#65377;該問(wèn)題可描述如下:設(shè)有m個(gè)同型并行處理器(identical multiprocessor)，n類不同尺寸的工件，其罰值也不同，并行處理器可選擇，也可拒絕，要求將最后一個(gè)工件的完工時(shí)間與被拒絕工件的總罰值之和最小#65377;這個(gè)問(wèn)題最早由Bartal等人提出^[7]#65377;他們對(duì)局外和局內(nèi)算法的研究都得到了很好的結(jié)果#65377;Alex和Richar^[8]將此問(wèn)題推廣同型并行處理器(uniform multiprocessor)上的調(diào)度問(wèn)題，對(duì)局外算法的設(shè)計(jì)進(jìn)行了探討#65377;

3 C-FF算 法

帶拒絕箱覆蓋問(wèn)題中，要求每個(gè)箱子中的物品費(fèi)用總和最小，同時(shí)物品尺寸之和盡可能大，因此，可以考慮將達(dá)到要求的費(fèi)用/尺寸比值的物品裝入箱子#65377;一種自然的策略是首先判斷物品是否滿足裝箱的條件，然后在滿足條件的物品使用經(jīng)典裝箱算法#65377;基于此思想，我們提出C-FF(classified-first fit)算法#65377;

為方便計(jì)，將所有信息塊的費(fèi)用除以購(gòu)買新服務(wù)器的費(fèi)用后作為新的費(fèi)用#65377;

根據(jù)物品ɑi的費(fèi)用密度Cpi/ωi，算法中的物品分成兩大類:

C-FF算法主要過(guò)程:

1)物品ɑ1到達(dá)，如果p1<1則拒絕，轉(zhuǎn)步驟2);否則轉(zhuǎn)步驟3)#65377;

2)物品ɑi到達(dá)，設(shè)已到達(dá)物品的總費(fèi)用值為P，如果P+pi<1則拒絕ɑi，否則轉(zhuǎn)步驟3)#65377;

3)自當(dāng)前物品ɑi開(kāi)始，如果該物品屬于M1，則按FF算法將該物品裝入箱子中，當(dāng)箱子中的物品大小至少為C時(shí)則關(guān)閉當(dāng)前箱子;如果該物品屬于M2，則拒絕該物品#65377;

引理1^[2] 對(duì)任意帶拒絕裝箱問(wèn)題實(shí)例I，L=∑i∈M1ωiC+P(M2)是其最優(yōu)解值OPT(I)的下界，即有OPT(I)≥L;且成立L≥12(OPT(I)-1)#65377;這里P(M2)=∑i∈M2pi為M2中物品的總罰值#65377;

定理2 對(duì)于帶拒絕箱覆蓋問(wèn)題的所有實(shí)例L，成立2C-FF(L)≥OPT(L)-1;C-FF算法的最壞情況漸近性能比RC-FF∞=1/2#65377;

證明 如果所有物品的總罰值小于1，則顯然算法C-FF得到問(wèn)題最優(yōu)解#65377;故以下假定所有物品的總罰值至少為1#65377;令L1為算法C-FF按步驟3安排的物品集組成的實(shí)例#65377;由于算法C-FF步驟1～步驟2中被拒絕物品的總罰值不超過(guò)1，且未將任何物品裝箱，所以C-FF(L\\L1)≤1#65377;下面就L1中物品總長(zhǎng)度分兩種情況考慮:

(1) 如果L1中物品總長(zhǎng)度小于C，按M2的定義知，L1中被拒絕物品的總罰值不超過(guò)它們的總長(zhǎng)度除以C#65377;因此總罰值也不超過(guò)1，且未被拒絕的物品總長(zhǎng)度仍小于C，所以C-FF(L1)=0，因此

C-FF(L)=C-FF(L1)+C-FF(L\\L1)≤C-FF(L1)+1=1#65377;

由于OPT(L)≥1，顯然成立C-FF(L)≤OPT(L)，2C-FF(L)≥OPT(L)-1#65377;

(2) 如果L1中物品總長(zhǎng)度至少為C，因?yàn)镃-FF算法中每個(gè)箱子的物品大小之和超過(guò)C但小于2C，我們有2C-FF(L1)+1≥OPT(L1)，因此有2C-FF(L)+1=2C-FF(L1)+2C-FF(L\\L1)+1≥2C-FF(L1)+2≥OPT(L1)+1又據(jù)引理1知OPT(L)≤OPT(L1)+1，因此有2C-FF(L)≥OPT(L)-1#65377;

令ε=12m，用(ɑ，c)表示大小為ɑ#65380;費(fèi)用為c的物品，{ɑ1，ɑ2，…，ɑn}表示把物品序列{ɑ1，ɑ2，…，ɑn}重復(fù)k次所得的物品序列，考慮輸入物品序列:

L={(1-ε，1)，(1-ε2m，1)}2m

則所有物品均屬于M1#65377;使用算法時(shí)每?jī)蓚€(gè)大小為1-ε的物品占用一個(gè)箱子，所以C-FF(L)=m;而若使用最佳策略，所有大小為(1-ε)/2m的物品恰好可以放入一個(gè)箱子中，每個(gè)大小為1-ε的物品也恰好占用一個(gè)箱子，故OPT(L)=2m+1，所以綜上所述，C-FF算法的最壞情況漸近性能比RC-FF∞=1/2#65377;

證畢#65377;

4 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)中分別取物品個(gè)數(shù)n=20，30，50，100，箱子長(zhǎng)度C=100#65377;物品長(zhǎng)度為區(qū)間[1，C]中隨機(jī)產(chǎn)生的整數(shù)，費(fèi)用為區(qū)間[0，2]中隨機(jī)產(chǎn)生的實(shí)數(shù)#65377;對(duì)每一種組合，隨機(jī)產(chǎn)生50個(gè)實(shí)例，對(duì)50個(gè)的性能比取平均值#65377;實(shí)驗(yàn)環(huán)境是CPU1.6G，512M內(nèi)存#65377;

求C-FF算法的平均性能比時(shí)，我們用第2節(jié)給出的最優(yōu)解定界，采用分枝定界法(深探法)求出最優(yōu)解#65377;實(shí)驗(yàn)結(jié)果如圖1所示#65377;

從實(shí)驗(yàn)結(jié)果可以看出，隨著問(wèn)題規(guī)模的擴(kuò)大，近似算法C-FF平均性能比逐步下降#65377;

5 結(jié) 論

本文從互聯(lián)網(wǎng)的信息管理問(wèn)題中提出了一個(gè)新的組合優(yōu)化問(wèn)題——極小化箱子中物品費(fèi)用的帶拒絕箱覆蓋問(wèn)題#65377;本文進(jìn)一步給出了求解帶拒絕裝箱覆蓋問(wèn)題的局內(nèi)近似算法C-FF，證明了該算法最壞情況漸近性能比R∞C-FF為1/2，實(shí)驗(yàn)顯示在平均意義下C-FF的效果相當(dāng)好#65377;設(shè)計(jì)出帶拒絕箱覆蓋問(wèn)題最壞情況漸近性能比更好的局內(nèi)算法，是我們進(jìn)一步研究的課題#65377;

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。