翟治年,劉關(guān)俊,盧亞輝,向 堅(jiān),吳茗蔚,豐明坤

(1.浙江科技學(xué)院 信息與電子工程學(xué)院,浙江 杭州 310023;2.同濟(jì)大學(xué) 計(jì)算機(jī)科學(xué)系,上海 201804;3.深圳大學(xué) 計(jì)算機(jī)與軟件學(xué)院,廣東 深圳 518060)

0 引言

工作流可滿足性(Workflow Satisfiability,WS)[1-2]是一種保守(conservative)約束可滿足問題(Constraint Satisfaction Problem,CSP)[3-4],其基本設(shè)置是求授權(quán)約束下任一可行資源分配(或確定其無解),稱為WS決策。在工作流執(zhí)行資源日益云/服務(wù)化趨勢(shì)下,資源配比(資源數(shù)n與任務(wù)數(shù)k之比)顯著增大,成為WS相對(duì)其他CSP的主要特征,并給WS求解技術(shù)帶來了獨(dú)特挑戰(zhàn),要求其實(shí)現(xiàn)固定參數(shù)k的多項(xiàng)式時(shí)間復(fù)雜度[1,5-7]。另一方面,WS決策側(cè)重于安全策略性質(zhì)的驗(yàn)證,不足以指導(dǎo)最終的資源分配。在WS無解時(shí),為消除沖突,使業(yè)務(wù)得以運(yùn)轉(zhuǎn),可以通過CSP值化[8-9]將部分約束柔性化,并最小化有關(guān)風(fēng)險(xiǎn)(也有研究通過調(diào)整授權(quán)來消除沖突,并最小化有關(guān)代價(jià)[10])。而當(dāng)WS有解,特別是可行解很多時(shí),更有必要從其他角度優(yōu)選,特別是根據(jù)某些柔性約束,選出違反風(fēng)險(xiǎn)最小者。柔性約束導(dǎo)致的尋優(yōu)需求對(duì)WS求解技術(shù)提出了進(jìn)一步考驗(yàn),要求其在枚舉設(shè)置下,快速求解“欠約束”實(shí)例。上述兩個(gè)方面的需求共同引出了本文的研究主題,下面展開進(jìn)行分析。

首先,高資源配比將造成變量取值范圍的膨脹,放大潛在的值對(duì)稱因素。但保守CSP的打破值對(duì)稱求解受到變量值域不統(tǒng)一的嚴(yán)重限制,在群等價(jià)樹[11]、值可交換性[12]、逐片值可交換性[13]等相關(guān)研究中,均未得到很好解決,給人們?cè)斐闪碎L(zhǎng)期困擾。2014年,COHEN[14]面向常見的資源獨(dú)立CSP,提出了資源分配模式概念,為完全值對(duì)稱因素的分離打破準(zhǔn)備了重要工具[15],并由此提出一種模式動(dòng)態(tài)規(guī)劃(Pattern Dynamic Programming,PDP)算法。PDP借助模式等價(jià)性來壓縮緩存,但模式數(shù)量仍為超指數(shù)級(jí),將造成極大空間開銷,且該算法的設(shè)計(jì)需要反復(fù)搬移緩存內(nèi)容,進(jìn)一步制約了其時(shí)間性能。隨后,文獻(xiàn)[16]通過約束預(yù)處理、約束傳播、資源動(dòng)態(tài)排序和消除無用值對(duì)PDP進(jìn)行了優(yōu)化,但不能從根本上克服前述缺陷。2015年,KARAPETYAN[17]建立了模式空間上的回溯搜索技術(shù),首次實(shí)現(xiàn)了多項(xiàng)式空間的WS固定參數(shù)求解。普通回溯的搜索樹已體現(xiàn)了變量值域(即各任務(wù)的授權(quán)資源集)因素,在節(jié)點(diǎn)處只須檢查或傳播約束[3]。而模式回溯要在搜索節(jié)點(diǎn)處計(jì)算指派(二分)圖及其(從左到右完備)匹配,以驗(yàn)證授權(quán)。指派圖需要系統(tǒng)計(jì)算,每個(gè)塊鄰域耗費(fèi)O(kn)時(shí)間,成為模式回溯的性能瓶頸。2019年,KARAPETYAN[7]在匹配等價(jià)前提下,將全指派約簡(jiǎn)為k指派,利用搜索上下文加速指派及匹配計(jì)算,得到增量模式回溯(Incremental Pattern Backtracking,IPB)法,其性能顯著超過了包括CP-SAT(近幾年Minizinc約束規(guī)劃挑戰(zhàn)賽的冠軍求解器)和文獻(xiàn)[16]PDP在內(nèi)的多種代表性方法[7],將模式技術(shù)研究推向了高峰[18-21]?，F(xiàn)有IPB可對(duì)資源分配或其模式進(jìn)行決策、枚舉或計(jì)數(shù)[22],但缺乏面向?qū)?yōu)場(chǎng)景的性能研究。另一方面,柔性約束違反風(fēng)險(xiǎn)是可行解尋優(yōu)的重要標(biāo)準(zhǔn),其建?？蚣茉贑SP領(lǐng)域已有研究[8-9],但相關(guān)算法難以應(yīng)對(duì)WS的高資源配比壓力。2015年,CRAMPTON[23]建模了柔性資源獨(dú)立約束的違反程度,表明其僅由模式確定,由此提出了值工作流可滿足性(Valued WS,VWS)問題及其模式分支限界(Pattern Branch Bounding,PBB)算法。2017年,CRAMPTON[24]針對(duì)多個(gè)柔性目標(biāo)的度量值難以歸一化的情況,提出了雙目標(biāo)VWS及其PBB算法?，F(xiàn)有PBB均借鑒模式回溯法,以深度優(yōu)先的模式枚舉搜索為基礎(chǔ),但不支持剛性的約束和授權(quán)。

若剛性和柔性資源獨(dú)立約束并存,且授權(quán)為剛性,需要對(duì)可行資源分配進(jìn)行尋優(yōu),則IPB的模式枚舉能力提供了直接的解決方案:根據(jù)柔性約束可快速計(jì)算模式的風(fēng)險(xiǎn)值[23],通過模式枚舉找出風(fēng)險(xiǎn)最小可行模式,利用其搜索驗(yàn)證時(shí)的指派圖匹配信息,轉(zhuǎn)化為可行解即可。因其在僅與k有關(guān)的模式空間上搜索,并在模式層面進(jìn)行解的優(yōu)選,故具有固定k的參數(shù)化性能。若進(jìn)一步引入目標(biāo)剪枝能力,還可望達(dá)到更好的性能。

然而,現(xiàn)有IPB研究主要關(guān)注WS決策設(shè)置,并用相變實(shí)例集進(jìn)行測(cè)試。相變是從“欠約束”到“過約束”的臨界狀態(tài),將導(dǎo)致可行解極少而難以搜到,或剛好無解而難以剪枝,為決策設(shè)置提供了測(cè)試壓力。但模式枚舉的情況非常不同。特別是“欠約束”(通過擴(kuò)大授權(quán)或降低約束而脫離相變點(diǎn))的實(shí)例,可能有大量可行模式,均位于完全搜索樹葉端,將共同拉近剪枝搜索樹與完全樹的差距。由于可行模式大量分布于葉端,找到其中一個(gè)很快,但枚舉它們要遍歷整個(gè)剪枝樹,將非常緩慢。本文實(shí)驗(yàn)表明:IPB對(duì)“欠約束”實(shí)例的模式枚舉性能很弱,且隨著“欠約束”程度增大快速下降。從應(yīng)用角度看,相變實(shí)例的出現(xiàn)條件過于苛刻,大多數(shù)WS有解實(shí)例都位于“欠約束”區(qū),而“欠約束”程度越高,可行解越多,對(duì)枚舉尋優(yōu)性能要求越高。而對(duì)無解WS,也須盡量將問題調(diào)整到“欠約束”狀態(tài),并進(jìn)行解的尋優(yōu)?？偟膩碚f,枚舉設(shè)置下“欠約束”實(shí)例的求解性能是業(yè)務(wù)運(yùn)轉(zhuǎn)和優(yōu)化的重要保障,而現(xiàn)有IPB對(duì)此存在明顯不足。

本文對(duì)基于IPB的模式枚舉框架進(jìn)行研究,并將問題設(shè)置簡(jiǎn)化為模式枚舉計(jì)數(shù)(通過模式枚舉完成模式計(jì)數(shù))。主要貢獻(xiàn)在于:通過挖掘模式授權(quán)驗(yàn)證中指派與匹配兩個(gè)環(huán)節(jié)的關(guān)系,提出了新的指派圖約簡(jiǎn)理論與技術(shù);將其用于現(xiàn)有IPB的兩種實(shí)現(xiàn),均明顯提升了模式枚舉計(jì)數(shù)性能,特別是對(duì)高授權(quán)比例的“欠約束”情形,提升效果更為顯著;在相變實(shí)例集上,其模式枚舉計(jì)數(shù)性能也有所提高,故也有益于WS的決策/模式?jīng)Q策求解(至少無解情形下如此)。

1 引例

本章對(duì)文獻(xiàn)[1]給出的采購(gòu)工作流進(jìn)行調(diào)整,以說明剛性和柔性資源獨(dú)立性約束并存時(shí),對(duì)WS可行解的尋優(yōu)需求。該工作流包括創(chuàng)建訂購(gòu)t1、同意訂購(gòu)t2、收貨簽字t3、創(chuàng)建支付t4、收貨副簽t5、同意支付t6共6個(gè)任務(wù),其執(zhí)行關(guān)系為t1-t2-(t3-t5,t4)-t6,這里用—連接順序任務(wù),用()列出并行任務(wù)。該工作流有一定資源集,在它與任務(wù)集之間存在一定的剛性授權(quán)關(guān)系。在t1和t2、t3和t5、t4和t6三對(duì)任務(wù)之間,分別存在剛性互斥約束,以保證創(chuàng)建與同意或簽字與副簽職責(zé)的分離;在t1和t3之間存在柔性綁定約束,表示最好由訂購(gòu)者收貨,當(dāng)資源分配模式P為t1和t3分配相同資源時(shí),違反度為0,否則為1;而在t1和t4之間存在柔性互斥約束,表示盡量避免由訂購(gòu)者創(chuàng)建支付,當(dāng)模式P為t1和t4分配不同資源時(shí),違反度為0,否則為1。根據(jù)兩條柔性約束的重要程度,為相應(yīng)違反度賦予不同權(quán)重,可得到關(guān)于P的目標(biāo)函數(shù)。

上述剛性授權(quán)和剛性互斥約束共同確定了一個(gè)WS問題。但為了實(shí)現(xiàn)目標(biāo)函數(shù)的最小化,需要對(duì)該問題進(jìn)行模式枚舉求解。

2 預(yù)備知識(shí)

約束的資源獨(dú)立性,是指當(dāng)計(jì)劃π滿足約束x∈X時(shí)(約束及其滿足的定義與約束類型有關(guān)),任取U上的置換φ,計(jì)劃φ°π也滿足x。根據(jù)該性質(zhì),將可通過模式抽象,簡(jiǎn)化計(jì)劃的約束滿足性驗(yàn)證。例如某模式相應(yīng)的多個(gè)計(jì)劃是否違反互斥約束x=(s,t),由s和t在該模式中是否同塊即可判斷,無須對(duì)每個(gè)計(jì)劃分別驗(yàn)證。稱模式P是合格的,當(dāng)且僅當(dāng)任何符合該模式的計(jì)劃合格;又稱模式P是授權(quán)的,當(dāng)且僅當(dāng)存在相應(yīng)的計(jì)劃授權(quán)。稱授權(quán)且合格的模式為有效模式,而有效的全模式為可行模式。WS決策/枚舉/計(jì)數(shù)設(shè)置分別求任一可行計(jì)劃(或確定其不存在)/所有可行計(jì)劃/可行計(jì)劃的數(shù)量。這些設(shè)置可有模式化版,即模式?jīng)Q策/模式枚舉/模式計(jì)數(shù)分別求任一可行模式/所有可行模式/所有可行模式的數(shù)量。引言所述的模式枚舉計(jì)數(shù)要求通過枚舉方式統(tǒng)計(jì)可行模式數(shù)量,本質(zhì)上是模式枚舉設(shè)置。

上述模式授權(quán)性,等價(jià)于模式的全指派圖存在左完備匹配。該圖定義為:

定義1給定模式Q,其全指派圖B=B(Q)是以Q為左側(cè)頂點(diǎn)集(每個(gè)左頂是Q作為劃分的一個(gè)塊),U為右側(cè)頂點(diǎn)集的二分圖,且塊b∈Q在B中的鄰域NB(b)=∩{U(t)|t∈b}。同時(shí),將該鄰域稱為塊b的全(指派)鄰域。

該圖的左完備匹配可為Q中每個(gè)塊分配不同的資源,從而將模式轉(zhuǎn)化為一個(gè)相應(yīng)的計(jì)劃。只要模式是授權(quán)的,該計(jì)劃就是授權(quán)的。

利用模式之間的關(guān)系組織樹形模式空間,并進(jìn)行回溯搜索,可求解WS的各種問題設(shè)置及其模式化版本。模式回溯壓縮了搜索范圍,有助于化解高資源配比的性能壓力,而代價(jià)是在搜索結(jié)點(diǎn)處增加了模式授權(quán)驗(yàn)證,包括計(jì)算模式指派圖,再求其左完備匹配兩個(gè)環(huán)節(jié)[17]。

文獻(xiàn)[7]進(jìn)一步建立了模式回溯的增量化框架:在每個(gè)節(jié)點(diǎn)處,相對(duì)于父節(jié)點(diǎn)只有一個(gè)新塊,即包含當(dāng)前任務(wù)的塊(可能是當(dāng)前任務(wù)單獨(dú)成塊,或?qū)⑵浼尤敫腹?jié)點(diǎn)的某塊而得),只須計(jì)算該塊的指派鄰域,即可將父節(jié)點(diǎn)指派圖更新為該節(jié)點(diǎn)的指派圖,稱為增量指派;而在父指派圖的匹配中,將當(dāng)前任務(wù)所加入塊原有的匹配邊(若當(dāng)前任務(wù)單獨(dú)成塊,則之前為空塊,無匹配邊)取消,然后以其為初始匹配,進(jìn)行一次匹配增廣,即得該節(jié)點(diǎn)指派圖的左完備匹配,稱為增量匹配。

對(duì)于全指派圖,計(jì)算新塊鄰域需要O(kn)的時(shí)間,特別是求一個(gè)鄰點(diǎn)也需要O(kn)的時(shí)間,在高資源配比(n/k)條件下,計(jì)算塊指派的全鄰域會(huì)嚴(yán)重拖慢搜索進(jìn)度。為降低增量指派的計(jì)算代價(jià),文獻(xiàn)[7]建立了k指派圖的概念:

定義2設(shè)模式Q的全指派圖B=B(Q),稱其生成子圖K為Q的k指派圖,當(dāng)且僅當(dāng)任取b∈Q,若|NB(b)|

該圖在|NB(b)|≥k時(shí)對(duì)塊b的鄰域?qū)嵤┘s簡(jiǎn),降低指派計(jì)算目標(biāo)和負(fù)擔(dān),且不影響授權(quán)匹配:

定理1給定模式Q,設(shè)其指派圖B=B(Q),而其k指派圖K∈K(Q),則B存在左完備匹配當(dāng)且僅當(dāng)K存在左完備匹配。

約簡(jiǎn)指派計(jì)算目標(biāo)之后,文獻(xiàn)[7]對(duì)計(jì)算出的塊鄰域進(jìn)行緩存,以減少重復(fù)計(jì)算,而在其提供的IPB實(shí)現(xiàn)中,還使用了位運(yùn)算來加速鄰點(diǎn)計(jì)算。文獻(xiàn)[21]為塊指派鄰點(diǎn)的計(jì)算引入了邊界收縮加速,以克服IPB從整個(gè)U中連續(xù)查找鄰點(diǎn)的缺陷。

文獻(xiàn)[7]的IPB針對(duì)WS決策設(shè)置描述,但很容易修改用于模式?jīng)Q策,而文獻(xiàn)[22]進(jìn)一步給出了基于IPB近似求解WS計(jì)數(shù)設(shè)置的方法,容易修改用于模式枚舉計(jì)數(shù)。因后者不統(tǒng)計(jì)可行模式相應(yīng)的計(jì)劃數(shù),不存在遺漏可行計(jì)劃的問題,故可采用k指派圖代替該文獻(xiàn)使用的全指派圖。須注意的是,該文獻(xiàn)對(duì)約束圖做了連通分解預(yù)處理,以控制問題規(guī)模,加快總體求解,但其不能簡(jiǎn)單遷移到模式枚舉/計(jì)數(shù)。不妨設(shè)有兩個(gè)連通分支,分別取相應(yīng)分問題的一個(gè)可行計(jì)劃,組合即得總問題的一個(gè)可行計(jì)劃(由于無跨連通片的約束,故組合不會(huì)導(dǎo)致約束違反,而在兩個(gè)分計(jì)劃中,每個(gè)變量的取值必然滿足其值域要求)。反過來,將后者分解到兩個(gè)連通片上,即可還原之前的兩個(gè)分計(jì)劃。于是約束分解不影響計(jì)劃的枚舉/計(jì)數(shù)。然而,在模式枚舉/計(jì)數(shù)設(shè)置下,從兩個(gè)連通片各自取一個(gè)分可行模式,其組合出的總可行模式未必唯一確定。具體有哪些結(jié)果,還依賴于每個(gè)分模式包含哪些可行計(jì)劃。為了保證模式枚舉/計(jì)數(shù)的正確性,應(yīng)當(dāng)取消約束分解。

3 約簡(jiǎn)增量模式回溯法

本文將定義一種結(jié)構(gòu)優(yōu)化的簡(jiǎn)指派圖(定義3),進(jìn)一步削減指派計(jì)算目標(biāo),并證明該圖的左完備匹配存在性等價(jià)于全指派圖(定理2)以及k指派圖。簡(jiǎn)指派圖的塊鄰域大小與指派圖整體結(jié)構(gòu)(體現(xiàn)在定義3中的|Q|和|∪Q|項(xiàng))耦合,不利于增量計(jì)算(父子結(jié)點(diǎn)對(duì)簡(jiǎn)指派鄰域的定義標(biāo)準(zhǔn)不同,影響子結(jié)點(diǎn)處的重用)。本文將通過證明有關(guān)的算法不變式(引理1和定理3),表明在IPB模式計(jì)數(shù)的搜索上下文中,可以增量方式計(jì)算簡(jiǎn)指派圖。下面先給出有關(guān)概念:

定義3設(shè)模式Q的全指派圖B=B(Q),稱其生成子圖R為Q的簡(jiǎn)指派圖,當(dāng)且僅當(dāng)任取b∈Q,若|NB(b)|<|Q|+k-|∪Q|,則NR(b)=NB(b),否則|Q|+k-|∪Q|≤|NR(b)|≤k。易知Q的簡(jiǎn)指派圖不唯一,將它們的集合記為R(Q)。

簡(jiǎn)指派圖可代替全/k指派圖,作為授權(quán)匹配的基礎(chǔ)。其依據(jù)在于:

定理2給定模式Q,設(shè)B=B(Q)為其全指派圖,R∈R(Q)為其簡(jiǎn)指派圖,則B存在左完備匹配當(dāng)且僅當(dāng)R存在左完備匹配。

證明由于R是B的生成子圖,充分性顯然。下面只證必要性。

由二分圖匹配的Hall定理,要證R有左完備匹配,只須證任取Q′?Q,|∪{NR(d)|d∈Q′}|≥|Q′|。而任取Q′?Q,分兩種情況:

(1)存在b∈Q′,|NB(b)|≥|Q|+k-|∪Q|。由定義3知,|NR(b)|≥|Q|+k-|∪Q|,又恒有|∪Q|≤k,故有|∪{NR(d)|d∈Q′}|≥|NR(b)|≥|Q|≥|Q′|。

(2) 任取b∈Q′,均有|NB(b)|<|Q|+k-|∪Q|。由定義3可知任取b∈Q′,NR(b)=NB(b),而由B有左完備匹配可知|∪{NB(d)|d∈Q′}|≥|Q′|,從而也有|∪{NR(d)|d∈Q′}|≥|Q′|。

綜合上可知,R必存在左完備匹配。

證畢。

給定模式Q中的塊,求每個(gè)指派鄰點(diǎn)都要驗(yàn)證若干候選資源,最壞情況下須遍歷整個(gè)U,且對(duì)每個(gè)候選,都要驗(yàn)證其與塊中O(k)個(gè)任務(wù)的授權(quán),故鄰點(diǎn)指派過程具有O(kn)代價(jià)。全指派塊鄰域的規(guī)模達(dá)到O(n),計(jì)算代價(jià)很高。k指派和簡(jiǎn)指派可分別對(duì)規(guī)模超過k和|Q|+k-|∪Q|的塊鄰域?qū)嵤┘s簡(jiǎn),而后者的約簡(jiǎn)條件更低。又因?yàn)閗≥|NR(b)|,所以其約簡(jiǎn)結(jié)果也可能更小。

本文的改進(jìn)IPB將對(duì)搜索到的每個(gè)模式節(jié)點(diǎn),以增量化方式計(jì)算唯一的簡(jiǎn)指派圖,其核心思路是:對(duì)模式空間中的結(jié)點(diǎn)Q,設(shè)其唯一的新塊(包含當(dāng)前任務(wù)的塊)為bQ,而任取非新塊b,必然屬于Q的父結(jié)點(diǎn)模式P,此時(shí)有:

|Q|+k-|∪Q|≤|P|+k-|∪P|。

(1)

注意子模式比父模式多含1個(gè)新任務(wù),故總有|∪Q|=|∪P|+1,但|P|≤|Q|≤|P|+1,即子模式所含劃分塊數(shù)未必加1。于是任取塊b∈P∩Q,P簡(jiǎn)指派圖對(duì)全指派鄰域NB(b)在較高起點(diǎn)進(jìn)行較小幅度的約簡(jiǎn),所得b鄰域一定滿足Q簡(jiǎn)指派圖的要求。只要b鄰域在P處符合要求,到Q處可不加改動(dòng)。從而在節(jié)點(diǎn)Q處,只須計(jì)算新塊bQ的簡(jiǎn)指派鄰域(這表明簡(jiǎn)指派圖可以增量方式計(jì)算)。特別地,若|NB(bQ)|≥|Q|+k-|∪Q|,根據(jù)定義3,計(jì)算|Q|+k-|∪Q|個(gè)鄰點(diǎn)即可作為NR(bQ),否則取NR(bQ)=NB(bQ)。下面分兩種情況,對(duì)簡(jiǎn)指派與k指派圖的約簡(jiǎn)能力進(jìn)行比較:

(1)|NB(bQ)|<|Q|+k-|∪Q|時(shí),有|NB(bQ)|

(2) 否則,即在|NB(bQ)|≥|Q|+k-|∪Q|條件下,簡(jiǎn)指派將實(shí)施約簡(jiǎn),取|NR(bQ)|=|Q|+k-|∪Q|。但本條件下不一定有|NB(bQ)|≥k,即未必滿足k指派的約簡(jiǎn)條件。綜合這一差異,可給出本條件下簡(jiǎn)指派較k指派減少計(jì)算的鄰點(diǎn)數(shù)量:

min{|∪Q|-|Q|+|NB(bQ)|-k,|∪Q|-|Q|}。

(2)

易知,式(2)必為非負(fù)值,其第一項(xiàng)對(duì)應(yīng)本文實(shí)施約簡(jiǎn)而k指派未實(shí)施的情況,第二項(xiàng)對(duì)應(yīng)兩者都實(shí)施的情況。在第一種情況下|NB(bQ)|

綜合上述條件可知,若用簡(jiǎn)指派代替k指派,則IPB主要的增量指派代價(jià)不增加,且簡(jiǎn)指派圖規(guī)模不超過k指派圖,可以保持增量匹配的時(shí)間復(fù)雜度,故其在性能上至少是安全的,不會(huì)招致明顯損失。

其中條件(2)使得簡(jiǎn)指派真正發(fā)揮作用,并較k指派產(chǎn)生優(yōu)勢(shì)。單獨(dú)考查一個(gè)搜索結(jié)點(diǎn)Q,可知|NB(bQ)|或|∪Q|-|Q|越大,該條件越容易滿足。而滿足后,簡(jiǎn)指派將產(chǎn)生式(2)描述的優(yōu)勢(shì)。當(dāng)|∪Q|-|Q|越大時(shí),式(2)中min操作所比較的兩項(xiàng)都越大,其比較結(jié)果也越大。當(dāng)|NB(bQ)|

以上考查了簡(jiǎn)指派優(yōu)勢(shì)在模式剪枝樹中的分布情況,以便分析其整體效果。由于本文關(guān)心“欠約束”實(shí)例上的性能,而進(jìn)入該狀態(tài)有提高授權(quán)比例、提高資源配比(本文工作以高資源配比為前提,但其程度存在進(jìn)一步差別)和降低約束密度3種基本手段。在后文實(shí)驗(yàn)部分,將分別改變這些參數(shù),對(duì)簡(jiǎn)指派的改進(jìn)效果進(jìn)行測(cè)試和分析。

接下來面向WS模式枚舉計(jì)數(shù)設(shè)置給出本文的約簡(jiǎn)增量模式回溯算法。

算法1RIPB(P,&R,M,&S,&U,&A,&X)。

輸入:S,U,A和X描述一個(gè)WS問題;P是一個(gè)可行模式;&表示其后的參數(shù)為傳址引用;R為P的簡(jiǎn)指派圖,本文靈活使用該記號(hào),也將其視為從P中塊到其簡(jiǎn)指派鄰域的映射,即R(b)表示P中第b塊的簡(jiǎn)指派鄰域;M是R的左完備匹配,本文靈活使用該記號(hào),也將其視為從P中塊到其匹配資源(未匹配時(shí)為nil)的映射,還用其表示P中所有塊的匹配資源的集合,尚未匹配時(shí)為?;X為約束集,本文靈活使用該記號(hào),也將其視為從任務(wù)到其參與的約束子集的映射,即任務(wù)s參與的約束子集可表示為X(s);

輸出:對(duì)問題(S,U,A,X),可由P擴(kuò)展得到的可行模式數(shù)量;

輸出不變式:返回時(shí)R與輸入時(shí)相同。

1 cnt←0;//子問題可行模式的數(shù)量,初始化

2 if(|∪P|=k){//P為全模式,擴(kuò)展過程終止

3 cnt←1;//擴(kuò)展于P的可行模式數(shù)為1

4 }else{

5 s←SelectLeftTask(P,S);//按排序規(guī)則取一剩余任務(wù)

6 for(1≤b≤|P|+1){//b依次標(biāo)識(shí)P中各塊和空塊

7 Pb←(P-)∪{b∪{s}};//s進(jìn)入b后塊標(biāo)識(shí)不變

8 if(!Satisfy(Pb,s,X))continue;

9 bak←R(b);//備份新塊的鄰域

10 R(b)←?;//準(zhǔn)備計(jì)算新塊的鄰域

11 for(u∈∩{U(t)|t∈b}){//用b表示塊本身

12 R(b)←R(b)∪{u};

13 if(|R(b)|=|Pb|+k-|∪Pb|) break;

14 }//不變式:此時(shí)R為Pb的簡(jiǎn)指派圖

15 if(|b|=1)//s進(jìn)入空塊形成,此時(shí)M(b)=nil

16 M′←Augment(R,M,b);//R上從b增廣M

17 else//|b|>1,M(b)≠nil

18 M′←Augment(R,M-{(b,M(b))},b);

19 if(M′(b)≠nil){//授權(quán)匹配成功

20 c←RIPB(Pb,R,M′,S,U,A,X);;

21 cnt←cnt+c;//按加法原理匯總

22 }

23 R(b)←bak;//恢復(fù)至P的簡(jiǎn)指派圖

24 }//for

25}//if-else

26 return cnt;

算法1第2行檢查模式P的完整性,若完整,且按輸入要求也是可行模式,則由第3行計(jì)數(shù)為1,由第26行返回結(jié)果;若P不完整,第7行對(duì)其進(jìn)行擴(kuò)展,得到子節(jié)點(diǎn)Pb,第8行對(duì)Pb進(jìn)行約束驗(yàn)證,只須驗(yàn)證s所參與的約束子集X(s),第10～18行對(duì)其進(jìn)行授權(quán)驗(yàn)證,其中第10～14行為增量指派環(huán)節(jié),15～18行為增量匹配環(huán)節(jié)。當(dāng)兩種驗(yàn)證通過后,第20行深度優(yōu)先搜索下一節(jié)點(diǎn)。若第8行約束驗(yàn)證失敗,恢復(fù)塊b進(jìn)而恢復(fù)模式P,切換到兄弟節(jié)點(diǎn)繼續(xù)搜索。若授權(quán)驗(yàn)證失敗,由第23行恢復(fù)第9行備份的R(b),再由第6行循環(huán)控制切換到兄弟節(jié)點(diǎn)。每個(gè)兄弟Pb的根子樹搜索完成后返回計(jì)數(shù)結(jié)果c,第21行將c累加到父節(jié)點(diǎn)P的計(jì)數(shù)器cnt中,當(dāng)各Pb根子樹搜索完成后,cnt就是P根子樹的可行模式數(shù)量,由第26行返回。注意,若沒有Pb通過驗(yàn)證,則cnt保持第1行賦的0值,由26行返回,表明P根子樹不含可行模式。

如下給出了算法1模式計(jì)數(shù)框架的基本特性:

引理1算法1的輸出不變式成立,即對(duì)符合要求的輸入,該算法結(jié)束時(shí)的R等于輸入時(shí)的R。

證明|∪P|作歸納:

(1)基始。當(dāng)|∪P|=k時(shí),算法進(jìn)入第3行的if分支,然后從第26行返回,R顯然不變。

(2)歸納步驟。假設(shè)當(dāng)|∪P|=h+1(0≤h<|S|)時(shí)結(jié)論成立,要證|∪P|=h時(shí)也成立。此時(shí),因h

綜合基始與歸納步驟,命題得證。

證畢。

算法1的指派約簡(jiǎn)不影響授權(quán)驗(yàn)證,有結(jié)論:

定理3算法1第14行的不變式成立,即該行結(jié)束時(shí)的R為Pb的簡(jiǎn)指派圖。

證明由于|∪P|=|S|時(shí)不經(jīng)過第14行,只須考慮|∪P|<|S|的情況,又分兩種情況:

(1) 當(dāng)P≠?時(shí),同時(shí)輸入的R∈R(P)(算法1的輸入要求),要證第14行處R∈R(Pb)。設(shè)全指派圖B=B(P),B′=B(Pb)。這里b是模式Pb相對(duì)P的唯一新塊(注意Pb中的塊b包含第5行選擇的s,而P中的塊無論是否標(biāo)識(shí)為b,均不含s)。任取Pb中(相對(duì)于P)的非新塊d,由定義1可知NB′(d)=NB(d)=∩{U(t)|t∈d}。由引理1的結(jié)論及類似其歸納步驟的分析,第6行控制的每次循環(huán)都處理與輸入時(shí)相同的R和P,故第10行面臨的R∈R(P),即R為P的簡(jiǎn)指派圖。由定義3可知R(d)?NB(d)(R為B生成子圖),而且:①當(dāng)|NB(d)|≥|P|+k-|∪P|時(shí),|P|+k-|∪P|≤|R(d)|≤k。那么由NB′(d)=NB(d)也必有R(d)?NB′(d),再由式(1)有|P|+k-|∪P|≥|Pb|+k-|∪Pb|,從而必有|NB′(d)|≥|Pb|+k-|∪Pb|,|Pb|+k-|∪Pb|≤|R(d)|≤k。② 當(dāng)|NB(d)|<|P|+k-|∪P|時(shí),R(d)=NB(d)。則若|NB′(d)|<|Pb|+k-|∪Pb|,由|NB(d)|=|NB′(d)|<|Pb|+k-|∪Pb|≤|P|+k-|∪P|,可得R(d)=NB(d)進(jìn)而R(d)=NB′(d)。綜合①和②可知,R(d)也必滿足Pb簡(jiǎn)指派圖的要求。再由d作為非新塊的任意性,只要第10～14行按Pb簡(jiǎn)指派圖的定義對(duì)新塊鄰域R(b)進(jìn)行更新,即可保證R∈R(Pb)。具體來說,由于Pb的全指派圖是B′,更新應(yīng)使R(b)?NB′(b),且當(dāng)|∩{U(t)|t∈b}|=|NB′(b)|≥|Pb|+k-|∪Pb|時(shí),應(yīng)使|Pb|+k-|∪Pb|≤|R(b)|≤k,否則,應(yīng)使R(b)=NB′(b),這正是該段代碼所做的。因此,第14行結(jié)束后,R∈R(Pb)。

(2) 當(dāng)P=?時(shí),只能有Pb={{s}},其中{s}是標(biāo)識(shí)為b的塊。由定義1,全指派圖B′=B(Pb)右側(cè)為U,而左側(cè)只有一個(gè)塊b,其鄰域?yàn)镹B′(b)=U(s)。若|NB′(b)|≥|Pb|+k-|∪Pb|=k,由第10～14行代碼,易知其結(jié)束后R(b)?U(b)=U(s),且|Pb|+k-|∪Pb|=k=|R(b)|,而若|NB′(b)|<|Pb|+k-|∪Pb|=k,該段代碼也使得R(b)=NB′(b),滿足Pb簡(jiǎn)指派圖的定義,故其結(jié)束后R∈R(Pb)。

證畢。

算法1中增量指派和增量匹配的時(shí)間復(fù)雜度分別是O(kn)和O(k2)。第8行的資源獨(dú)立約束驗(yàn)證通?？梢栽贠(k)或O(k2)時(shí)間內(nèi)完成。故算法1總時(shí)間復(fù)雜度為O(Bk(kn+k2)),其中超指數(shù)函數(shù)Bk是第k貝爾數(shù),等于k集合的劃分?jǐn)?shù),即S的全模式數(shù)量。

算法1的空間占用主要是問題實(shí)例的授權(quán)、約束信息以及求解時(shí)所用指派圖結(jié)構(gòu),分別占用O(kn)、O(k2)和O(k2)空間,故總的空間復(fù)雜度為O(k2+kn)。

4 實(shí)驗(yàn)研究

本章將簡(jiǎn)指派用于IPB模式枚舉計(jì)數(shù)的兩種實(shí)現(xiàn),以驗(yàn)證其改進(jìn)效果。首先用C++復(fù)現(xiàn)了IPB,并改造為模式計(jì)數(shù)算法,記為IPB21。IPB有公開的C#源代碼(http://researchdata.essex.ac.uk/114)。本文也將其轉(zhuǎn)換為C++,經(jīng)程序優(yōu)化后(在Windows平臺(tái)上測(cè)試,其性能通常優(yōu)于C#版本),改造為模式計(jì)數(shù)算法,記為IPB19。將上述兩種實(shí)現(xiàn)所用k指派改為簡(jiǎn)指派,分別得到RIPB21和RIPB19。實(shí)驗(yàn)涉及的幾種資源獨(dú)立約束很容易快速驗(yàn)證。4種算法均采用文獻(xiàn)[7](增強(qiáng)約束剪枝)的變量排序規(guī)則。而為突出指派圖結(jié)構(gòu)和指派計(jì)算方法所致性能差異,未使用塊指派鄰域緩存技術(shù)。其中21版和19版分別使用文獻(xiàn)[21]的邊界收縮方案和位運(yùn)算來加速指派計(jì)算。另外,兩者分別采用深度和廣度優(yōu)先方式進(jìn)行匹配增廣。最后,將根據(jù)19和21版本中較小的改進(jìn)幅度來報(bào)告本文方法的優(yōu)勢(shì)。

此外,目前尚無基于通用求解器進(jìn)行模式枚舉的工作,作為一條可能的途徑,其建模問題還有待研究。文獻(xiàn)[16]的PDP決策算法系統(tǒng)化構(gòu)造并緩存已找到的所有模式,很容易修改用于模式計(jì)數(shù)。本文復(fù)現(xiàn)了該算法,驗(yàn)證了其決策版本的性能水平,但其計(jì)數(shù)版本對(duì)后文兩個(gè)實(shí)驗(yàn)中各自規(guī)模最小的一批實(shí)例,仍無法按時(shí)解出,故未納入正式對(duì)比。

本文的實(shí)驗(yàn)環(huán)境為:主頻4 GHz/睿頻4.6 GHz的Intel Core i3-9350kf CPU(未超頻)、8 G RAM、CentOS 8、GNU C++(-O3優(yōu)化)、GMP6.2大整數(shù)庫(kù)。對(duì)每個(gè)實(shí)例的執(zhí)行時(shí)間,以30分鐘為上限。

表1 4種算法的時(shí)間(s)和空間(KB)代價(jià)

將IPB19與IPB21比較。由表1,在兩者均完全解出的前5組實(shí)例上,后者的時(shí)間性能高達(dá)前者的1.66～3.45倍。這主要源于以下兩個(gè)因素:

(1) IPB19的實(shí)現(xiàn)存在一個(gè)性能缺陷:若某個(gè)模式節(jié)點(diǎn)P所有驗(yàn)證通過,則深入到以P為根的子樹,當(dāng)根子樹搜索完成回溯到P時(shí),為恢復(fù)P的指派圖,重復(fù)計(jì)算了P處新塊(P相對(duì)于其父結(jié)點(diǎn)的唯一新塊)的鄰域。在前述公開的C#源代碼(IPB決策版本)中,該缺陷體現(xiàn)為:初次搜索某節(jié)點(diǎn)P時(shí),若其新塊中含多個(gè)任務(wù),調(diào)用AddStepsToNode()更新指派圖,而回溯到P時(shí),需要維護(hù)指派圖結(jié)構(gòu),為此調(diào)用RemoveStepsFromNode()。這兩個(gè)函數(shù)均調(diào)用ComputeIncidenceList()計(jì)算塊鄰域,并在該函數(shù)內(nèi),通過局部變量短暫備份了塊鄰域,以便匹配失敗后恢復(fù),但缺乏穩(wěn)定可持續(xù)的備份,造成了回溯時(shí)的重復(fù)計(jì)算。該實(shí)現(xiàn)的塊鄰域緩存機(jī)制有助于緩解相關(guān)影響,但寫入緩存后進(jìn)入子樹搜索,若期間緩存到達(dá)容量上限而清空,則回溯時(shí)無法從緩存中查出,無法保證消除重復(fù)計(jì)算。本文實(shí)驗(yàn)中關(guān)閉緩存以對(duì)比不同指派圖及計(jì)算方法的原始性能差距,會(huì)使上述缺陷充分暴露。為分析其影響,本文針對(duì)其進(jìn)行優(yōu)化得到IPB19opt,在前5組實(shí)例上再次進(jìn)行測(cè)試,所得平均時(shí)間依次為4.77155、15.5722、1.04655、85.24735和830.7432s。由此重新計(jì)算IPB21的性能優(yōu)勢(shì),將分別下降到1.33、1.16、2.39、1.63和1.21倍,仍比較顯著。這表明除了IPB19的自身缺陷,還存在IPB21與IPB19的特性差異,共同導(dǎo)致了IPB21在本實(shí)驗(yàn)中的優(yōu)勢(shì)。

(2) IPB21和IPB19的主要差異在于任務(wù)塊指派鄰域的計(jì)算加速方式。IPB19在整個(gè)資源集U上搜索鄰點(diǎn),但借助位運(yùn)算快速驗(yàn)證每個(gè)候選資源(預(yù)先為每個(gè)資源計(jì)算授權(quán)任務(wù)集,用64位圖表示,而任務(wù)塊也有位圖表示,可借助位運(yùn)算判斷前者是否包含了后者),其實(shí)際代價(jià)為常數(shù),不妨設(shè)為1次操作。但塊越大,其鄰點(diǎn)在U中的分布越稀疏,為找到一個(gè)而驗(yàn)證的候選越多。本實(shí)例集互斥約束密度很低,使得剪枝模式樹邊緣更接近完全樹葉端,有利于增大近葉節(jié)點(diǎn)處新塊的大小(從根到葉的每個(gè)結(jié)點(diǎn)引入一個(gè)新任務(wù),但多數(shù)時(shí)候是將其加入舊塊,故所得新塊趨于變大),這對(duì)IPB19的性能不利。而IPB21的邊界收縮加速方案利用任務(wù)授權(quán)資源之間的空隙(以及兩側(cè)的邊緣)來縮小搜索范圍,但其可能將一個(gè)候選資源與塊中每個(gè)任務(wù)進(jìn)行一次授權(quán)關(guān)系判斷,每次判斷需要常數(shù)時(shí)間,故候選驗(yàn)證代價(jià)與塊大小有關(guān)。設(shè)給定塊大小為x,驗(yàn)證一個(gè)候選的平均代價(jià)是x/y次操作(1≤y≤x,任務(wù)授權(quán)比例越高時(shí),塊授權(quán)資源越稠密,y越趨于1),若塊中存在授權(quán)資源稀疏的任務(wù),可使每個(gè)鄰點(diǎn)的搜索范圍縮小z倍,則只要yz>x,IPB21便會(huì)優(yōu)于IPB19。降低授權(quán)比例可增大z值和y值,將有利于提高IPB21與IPB19的性能比。若固定授權(quán)比例及相應(yīng)的z和y值,則當(dāng)約束密度降低導(dǎo)致x增大時(shí),IPB19搜索一個(gè)鄰點(diǎn)的范圍將指數(shù)級(jí)擴(kuò)張,而IPB21驗(yàn)證每個(gè)候選的代價(jià)只是線性增大,故IPB21與IPB19的性能比也會(huì)提高,而且速度很快。為排除因素(1)的作用,觀察前述IPB21與IPB19opt的比較結(jié)果,可知IPB21處于優(yōu)勢(shì),這與本實(shí)例集的低約束密度有關(guān)。進(jìn)而,IPB21的最大/小優(yōu)勢(shì)分別出現(xiàn)在第3/2組實(shí)例上,分別與其授權(quán)比例較低/高有關(guān)。盡管第5組實(shí)例的授權(quán)比例高于第2組,對(duì)IPB21優(yōu)勢(shì)的抑制作用更強(qiáng),但其資源配比不高,資源數(shù)量較少,影響了要計(jì)算的鄰點(diǎn)數(shù),故未更有效地抑制IPB21的優(yōu)勢(shì)。

由于IPB21和IPB19作為IPB的不同實(shí)現(xiàn)出現(xiàn)了極大性能差異,以上詳細(xì)分析了有關(guān)因素。本文主題在于簡(jiǎn)指派對(duì)k指派的改進(jìn),后文將重點(diǎn)考查RIPB較對(duì)應(yīng)版本IPB的性能提升情況。

現(xiàn)在將IPB21與RIPB21進(jìn)行比較。由表1可知,在兩者均完全解出的前6組實(shí)例上,后者的時(shí)間性能達(dá)到前者的0.97～1.24倍,平均為1.11倍。這表明使用簡(jiǎn)指派圖有效控制了鄰點(diǎn)的計(jì)算數(shù)量,進(jìn)而提高了授權(quán)驗(yàn)證和整體搜索性能。特別地,在第2、5、6組,RIPB21的優(yōu)勢(shì)達(dá)到1.15～1.24倍。這幾組實(shí)例的特點(diǎn)是資源配比和授權(quán)比例都較高。此時(shí),各任務(wù)的授權(quán)資源集較大,任務(wù)塊的全鄰域較大,有利于達(dá)到第3章的實(shí)施條件(2),使簡(jiǎn)指派較k指派出現(xiàn)式(2)描述的優(yōu)勢(shì)。

再將IPB19與RIPB19進(jìn)行比較。由表1,兩者均完全解出了前5組實(shí)例,后者的時(shí)間性能達(dá)到前者的1.14～1.43倍,平均為1.3倍。19版本回溯時(shí)重復(fù)計(jì)算塊鄰域,將導(dǎo)致指派代價(jià)在總驗(yàn)證代價(jià)中所占比例擴(kuò)大(注意回溯時(shí)不必重新驗(yàn)證約束),故使用簡(jiǎn)指派導(dǎo)致的優(yōu)勢(shì)也超過了21版本。

仍對(duì)前述50組四參數(shù),將m取作原來的2倍,然后每組生成2次,得到100個(gè)較高約束密度的實(shí)例,按前述三參數(shù)分10組進(jìn)行測(cè)試,結(jié)果如表2所示。相對(duì)于表1,同一算法在對(duì)應(yīng)實(shí)例組上的時(shí)間性能大大提高,其原因主要是稠密約束有效增強(qiáng)了剪枝,加快了枚舉計(jì)數(shù)搜索。

表2 2倍約束下4種算法的時(shí)間(s)和空間(KB)代價(jià)

將IPB19與IPB21比較。由表2,在兩者均完全解出的前6組實(shí)例上,后者的時(shí)間性能達(dá)到前者的1.64～3.18倍。相對(duì)于表1,第3、4、5組優(yōu)勢(shì)均下降,且3、4組下降較多,只有第2組優(yōu)勢(shì)略有提高。再對(duì)IPB19opt進(jìn)行測(cè)試,在前6組實(shí)例上的平均時(shí)間依次為1.49175、4.51175、2.21755、44.04355、238.53475和412.5632s,相應(yīng)的IPB21優(yōu)勢(shì)為1.32、1.20、2.13、1.30、1.21和1.22倍。相對(duì)于約束倍增前,第1、3、4組優(yōu)勢(shì)均下降,且3、4組下降較多,只有第2組優(yōu)勢(shì)略有提高。與IPB21較IPB19優(yōu)勢(shì)的變化相比,基本同步。這表明IPB21對(duì)IPB19性能優(yōu)勢(shì)在約束倍增后的變化(總體上是下降的)主要不是由IPB19自身缺陷導(dǎo)致的,而與IPB21和IPB19指派計(jì)算方式的差異有關(guān)。在之前的因素(2)中,也已分析過較稀疏約束對(duì)IPB19更不利的原因。

將IPB21與RIPB21比較。由表2,在兩者均完全解出的前6組實(shí)例上,后者的時(shí)間性能達(dá)到前者的0.96～1.21倍,平均1.11倍。再將IPB19與RIPB19比較。由表2,在兩者均完全解出的前6組實(shí)例上,后者的時(shí)間性能達(dá)到前者的1.14～1.40倍,平均為1.26倍?？傮w上,僅約束密度變化時(shí),簡(jiǎn)指派較k指派的優(yōu)勢(shì)略有下降。這是因?yàn)檩^多的約束增強(qiáng)了剪枝,降低了該技術(shù)發(fā)揮優(yōu)勢(shì)的機(jī)會(huì)。

上述倍增前后的約束密度均處于較低水平。實(shí)驗(yàn)2將在較復(fù)雜約束配置下,通過施加充分的互斥約束達(dá)到相變條件,然后減少約束觀察其影響。

表1和表2中,4種算法的空間占用相差很小。它們都使用唯一的指派關(guān)系存儲(chǔ),其內(nèi)容隨著搜索不斷變化,動(dòng)態(tài)部分在堆上分配。表中RIPB和對(duì)應(yīng)IPB的峰值空間完全相同。盡管RIPB使用了更小的簡(jiǎn)指派圖,預(yù)期空間占用會(huì)有所下降,但系統(tǒng)以4KB頁(yè)為單位分配堆空間(表中的空間為平均值,不一定是4KB的整數(shù)倍),每次可能分配較多的頁(yè),除了滿足當(dāng)前申請(qǐng)的需要,還給出較大的預(yù)留,通常可以容納以字節(jié)為單位的指派圖變化。

現(xiàn)在限定k=16,m=18(ω=15),使μ從200以步長(zhǎng)200增加到1000,再分別取AP為L(zhǎng)、M和H,得到15組四參數(shù)配置,每個(gè)配置生成10個(gè)實(shí)例,對(duì)4種算法進(jìn)行測(cè)試,觀察其隨資源配比μ和授權(quán)比例AP增加的變化,結(jié)果如表3所示。

表3 資源增加時(shí)3種算法時(shí)間(s)與空間(MB)代價(jià)

固定AP=L時(shí),隨著μ的增加,每種算法的時(shí)間性能呈現(xiàn)出較強(qiáng)的下降趨勢(shì)。這是因?yàn)棣淘黾訒?huì)增大任務(wù)授權(quán)資源集,有利于塊鄰域的擴(kuò)大,這將使授權(quán)匹配更容易成功,剪枝模式樹規(guī)模相應(yīng)擴(kuò)大,而搜索性能隨之降低。而當(dāng)AP=M和L時(shí),性能下降趨勢(shì)減緩。這是因?yàn)槭跈?quán)比例較高時(shí),較低的資源配比就可使任務(wù)和塊的授權(quán)資源集足夠大,授權(quán)匹配基本可以成功,故繼續(xù)增加資源配比基本不會(huì)導(dǎo)致剪枝樹規(guī)模增大,而只是增加了與n有關(guān)的預(yù)計(jì)算開銷。從另一角度觀察表3的數(shù)據(jù),固定μ=200時(shí),隨著AP的升高,每種算法的性能都在下降。而當(dāng)μ達(dá)到400或600以后,隨著AP的升高,同一算法的性能出現(xiàn)明顯的先下降后上升的變化。先下降仍是由于授權(quán)剪枝削弱導(dǎo)致搜索樹規(guī)模增大,后上升是因?yàn)榧糁湟?guī)?；静蛔?而同樣任務(wù)塊的授權(quán)資源在U中密度增大,只要檢查更少的候選就可找到足夠的鄰點(diǎn),導(dǎo)致了塊指派鄰域計(jì)算代價(jià)下降。

統(tǒng)計(jì)表3的數(shù)據(jù),在μ=200的3組實(shí)例上:RIPB21(較IPB21)的提升倍數(shù)為0.97～1.17,平均為1.04;RIPB19(較IPB19)的提升倍數(shù)為1.05～1.36,平均為1.17。在μ=600的3組實(shí)例上:RIPB21的提升倍數(shù)為0.97～1.20,平均為1.11;RIPB19的提升倍數(shù)為1.18～1.41,平均為1.31。在μ=1000的3組實(shí)例上:RIPB21的提升倍數(shù)為0.97～1.29,平均為1.16;RIPB19的提升倍數(shù)為1.28～1.56,平均為1.40。隨著資源配比以步長(zhǎng)4增加,簡(jiǎn)指派的平均優(yōu)勢(shì)在21版本上從1.04增加到1.11再增加到1.16;在19版本上從1.17增加到1.31又增加到1.40。

在AP=L的5組實(shí)例上:RIPB21(較IPB21)的提升倍數(shù)為0.967～0.973,平均為0.971;RIPB19(較IPB19)的提升倍數(shù)為1.05～1.28,平均為1.17。在AP=M的5組實(shí)例上:RIPB21的提升倍數(shù)為0.98～1.29,平均為1.13;RIPB19的提升倍數(shù)為1.11～1.56,平均為1.37;兩者的最大提升倍數(shù)1.29和1.56均出現(xiàn)在μ=1 000處。在AP=H的5組實(shí)例上:RIPB21的提升倍數(shù)為1.17～1.22,平均為1.20;RIPB19的提升倍數(shù)為1.349～1.365,平均為1.358。隨著AP增加,簡(jiǎn)指派的平均優(yōu)勢(shì)在21版本上從0.97增加到1.13再增加到1.20;在19版本上從1.17增加到1.37又下降到1.36。

下面對(duì)上述性能變化的原因進(jìn)行分析。大體上,資源配比或授權(quán)比例越大,任務(wù)授權(quán)資源越多,節(jié)點(diǎn)Q新塊bQ的全鄰域NB(bQ)越大,越有利于條件(2)的滿足,使簡(jiǎn)指派較k指派的優(yōu)勢(shì)擴(kuò)大。不過,AP從M到L時(shí),RIPB19的優(yōu)勢(shì)出現(xiàn)了下降。這是μ=1 000時(shí),AP從M到L時(shí),簡(jiǎn)指派優(yōu)勢(shì)顯著下降導(dǎo)致的。其原因在于,μ=1 000和AP=M時(shí),NB(bQ)已足夠大,使得簡(jiǎn)指派的實(shí)施已經(jīng)很充分,繼續(xù)提高授權(quán)比例作用不大。特別地,提高授權(quán)比例仍將增加鄰點(diǎn)在U中的密度,使得搜索更少的資源就可完成指派鄰域計(jì)算,且其對(duì)19版本特別有利(因其候選驗(yàn)證代價(jià)為常數(shù),指派效率主要取決于搜索范圍)。這就會(huì)相應(yīng)降低指派代價(jià)在整體驗(yàn)證中的比例,以及簡(jiǎn)指派的優(yōu)勢(shì)。

表3的空間數(shù)據(jù)表明,授權(quán)比例的增大對(duì)4種算法的峰值空間占用幾乎沒有影響,而資源配比增大使其有微弱增長(zhǎng)。這是因?yàn)楹笳唢@著增大了資源總數(shù),使以字節(jié)為單位的實(shí)例和索引數(shù)據(jù)規(guī)模明顯增大,導(dǎo)致系統(tǒng)分配了更多的4KB頁(yè)面。RIPB和對(duì)應(yīng)IPB的空間占用都相同,其原因類似于之前的分析。

實(shí)驗(yàn)2文獻(xiàn)[7]配置at-most-r和at-least-r兩種全局約束(分別要求p≥3個(gè)任務(wù)至多/至少由3個(gè)不同資源執(zhí)行,而p稱為約束的元數(shù))和(2元)互斥約束,研究了相變實(shí)例的生成,并公開了有關(guān)實(shí)例集(http://researchdata.essex.ac.uk/114)。其生成規(guī)則簡(jiǎn)介如下:將每個(gè)資源隨機(jī)授權(quán)給[1,0.5k]個(gè)任務(wù),相應(yīng)的授權(quán)比例α%約為1/4;分別固定μ%=10和100,讓k從18開始增長(zhǎng);對(duì)每個(gè)k,分別生成k個(gè)5元塊at-most-3和at-least-3約束,以及導(dǎo)致實(shí)例難度相變的特定數(shù)量互斥約束,得到1個(gè)實(shí)例,如此重復(fù)100次,得1組實(shí)例。本實(shí)驗(yàn)只對(duì)每個(gè)算法完全解出的實(shí)例組進(jìn)行統(tǒng)計(jì),并對(duì)每組100個(gè)實(shí)例的性能結(jié)果取均值。

先用上述相變實(shí)例集測(cè)試4種算法,μ%=10和μ%=100的時(shí)間結(jié)果分別如圖1和圖2所示。由于k的變化導(dǎo)致最小和最大執(zhí)行時(shí)間相差很大,本實(shí)驗(yàn)繪圖均采用了對(duì)數(shù)縱坐標(biāo)。其中IPB19較IPB21更有優(yōu)勢(shì),這與實(shí)驗(yàn)1的情況相反。由于IPB19本身尚且存在性能缺陷,該優(yōu)勢(shì)必然源于IPB19和IPB21指派計(jì)算方式的差異。實(shí)驗(yàn)1中已分析表明,給定授權(quán)比例,則降低約束密度(特別是互斥約束密度)有利于提高IPB21與IPB19的性能比。此處兩個(gè)相變實(shí)例集在固定1/4授權(quán)比例等條件下,通過增加互斥約束來到達(dá)“欠約束”到“過約束”的臨界點(diǎn),將快速抑制塊大小,迅速降低IPB21與IPB19的性能比,使后者占據(jù)優(yōu)勢(shì)。對(duì)于μ%=100設(shè)置下各算法按時(shí)解出的實(shí)例組,每種算法的平均峰值空間均在19M左右。而在μ%=100的解出實(shí)例組上:當(dāng)k從18增至43時(shí),21版本的峰值空間從19M+增至22M+;當(dāng)k從18增至43時(shí),19版本的峰值空間從18M+增至77M+,且當(dāng)k=43時(shí),增至177M+。μ%=100時(shí)空間占用的增加較為明顯,主要是問題實(shí)例和一些預(yù)計(jì)算索引的規(guī)模與n相關(guān),增長(zhǎng)更快。特別是19版本,在n>k2時(shí),對(duì)指派圖中的塊鄰域使用了耗空間的散列存儲(chǔ)。

統(tǒng)計(jì)圖1的原始數(shù)據(jù)可知:在4種算法共同解出的31組實(shí)例上,RIPB21的時(shí)間性能達(dá)到IPB21的1.03～1.08倍,且隨k的增加呈微弱增大趨勢(shì),平均1.06倍,而RIPB19的時(shí)間性能達(dá)到IPB19的1.08～1.17倍,且隨k的增加呈一定增大趨勢(shì),平均1.15倍。本實(shí)例子集n/k=10而授權(quán)比例約1/4,故當(dāng)k=18～48時(shí),新塊大小|bQ|最大為4～5(當(dāng)塊增大時(shí),塊鄰點(diǎn)數(shù)首次不足1)。而相應(yīng)的相變點(diǎn)(互斥約束數(shù)量)為27～82(見該子集的e50值表),故k=18和48時(shí),5元塊bQ的互斥約束剪枝概率約為0.84和0.52,相應(yīng)的Q較難進(jìn)入授權(quán)驗(yàn)證。當(dāng)k增加時(shí),剪枝樹規(guī)模擴(kuò)大和搜索結(jié)點(diǎn)數(shù)增多,只是導(dǎo)致小的新塊更頻繁出現(xiàn)。對(duì)|bQ|=3,當(dāng)k=18～48時(shí),|NB(bQ)|約為2.8～7.5,但|∪Q|-|Q|很難達(dá)到16～41,導(dǎo)致條件(2)很難成立,|bQ|=4時(shí)更是如此。故RIPB主要在|bQ|≤2時(shí)可能取得優(yōu)勢(shì),其整體優(yōu)勢(shì)也很受限。|bQ|=1時(shí),|NB(bQ)|≥k,簡(jiǎn)指派達(dá)到充分優(yōu)勢(shì)|∪Q|-|Q|,當(dāng)k增加導(dǎo)致剪枝樹規(guī)模擴(kuò)大時(shí),|bQ|=1可發(fā)生在更深的結(jié)點(diǎn)處,相應(yīng)的|∪Q|-|Q|會(huì)有所擴(kuò)大,有利于簡(jiǎn)指派整體優(yōu)勢(shì)的擴(kuò)大。在19版本上,簡(jiǎn)指派方法導(dǎo)致了更大的平均性能提升,其優(yōu)勢(shì)隨k增大的趨勢(shì)也更強(qiáng),主要是因?yàn)樵摪姹净厮輹r(shí)重新計(jì)算指派,擴(kuò)大了指派代價(jià)在整體驗(yàn)證中的比例。

統(tǒng)計(jì)圖2的原始數(shù)據(jù)可知:在共同解出的26組實(shí)例上,RIPB21的時(shí)間性能達(dá)到IPB21的1.13～1.24倍,最大倍數(shù)出現(xiàn)在k=21處,此后有一定下降趨勢(shì),最小倍數(shù)出現(xiàn)在k=42處,平均1.18倍;在共同解出的29組實(shí)例上,RIPB19的時(shí)間性能達(dá)到IPB19的1.15～1.35倍,最大倍數(shù)出現(xiàn)在k=21處,此后有下降趨勢(shì),最小倍數(shù)出現(xiàn)在k=46處,平均1.25倍。RIPB的優(yōu)勢(shì)較圖1明顯擴(kuò)大,但其在k增加時(shí),主要呈下降趨勢(shì)。本實(shí)例集n/k=100而授權(quán)比例為1/4,當(dāng)k=18～45時(shí),|bQ|最大為6～7。但其相變點(diǎn)為39～125(見該子集的e50值表),故k=18和45時(shí),5元塊bQ的互斥約束剪枝概率為0.93和0.72,故進(jìn)入授權(quán)驗(yàn)證的bQ較圖1更小一些。對(duì)|bQ|=4,當(dāng)k=18～45時(shí),|NB(bQ)|約為7.0～17.6,難以滿足條件(2)。對(duì)|bQ|≤3,當(dāng)k=18～45時(shí),|NB(bQ)|至少為28～70,均超過k而使簡(jiǎn)指派有充分優(yōu)勢(shì),使其整體優(yōu)勢(shì)較圖1明顯擴(kuò)大。但是圖2的剪枝樹達(dá)到更大規(guī)模,但進(jìn)入授權(quán)驗(yàn)證的bQ反而小于圖1,意味著搜索節(jié)點(diǎn)中有更高比例的剪枝節(jié)點(diǎn)。這不利于RIPB的整體優(yōu)勢(shì)(因約束剪枝不進(jìn)入指派,授權(quán)剪枝的|NB(bQ)|通常非常小,簡(jiǎn)指派在剪枝處基本沒有優(yōu)勢(shì)),只是圖2大量剪枝由快速的約束驗(yàn)證導(dǎo)致,其負(fù)面作用有限。而當(dāng)k增大導(dǎo)致剪枝樹擴(kuò)張時(shí),這種負(fù)面作用將隨之變得顯著,不利于RIPB整體優(yōu)勢(shì)幅度的保持。簡(jiǎn)指派在19版本上的性能提升仍然更大,原因也與之前類似。相對(duì)于圖1的情況,隨著資源配比的擴(kuò)大(但增加了互斥約束以保持相變),RIPB的性能優(yōu)勢(shì)明顯擴(kuò)大。對(duì)其原因,將與下面擴(kuò)大授權(quán)的情形一起分析。

對(duì)μ%=10的情形,將授權(quán)方式分別改為每個(gè)資源[1,0.75k]和[1,k]個(gè)任務(wù),相應(yīng)的授權(quán)比例α%≈0.375和0.5分別是原來的1.5倍和2倍,保持其他參數(shù)不變,按前述方式生成實(shí)例集,對(duì)4種算法進(jìn)行測(cè)試。α%≈0.375時(shí)的結(jié)果如圖3所示,α%≈0.5時(shí)的結(jié)果如圖4所示。4種算法的性能均明顯下降,這是因?yàn)閿U(kuò)大授權(quán)比例造成實(shí)例,進(jìn)入“欠約束”狀態(tài),模式剪枝樹顯著擴(kuò)大,模式枚舉搜索代價(jià)相應(yīng)提高。每種算法對(duì)上述各解出實(shí)例組的平均峰值空間均在19M左右,與之前相近。這是因?yàn)閿U(kuò)大授權(quán)對(duì)實(shí)例和預(yù)計(jì)算索引的規(guī)模影響不大。

統(tǒng)計(jì)圖3原始數(shù)據(jù)可知:在共同解出的20組實(shí)例上,RIPB21的時(shí)間性能達(dá)到IPB21的1.11～1.24倍,隨k呈增長(zhǎng)趨勢(shì),平均1.16倍;在共同解出的20組實(shí)例上,RIPB19的時(shí)間性能達(dá)到IPB19的1.19～1.48倍,隨k呈增長(zhǎng)趨勢(shì),平均1.26倍。統(tǒng)計(jì)圖4原始數(shù)據(jù)可知:在共同解出的18組實(shí)例上,RIPB21的時(shí)間性能達(dá)到IPB21的1.45～2.10倍,隨k呈增長(zhǎng)趨勢(shì),平均1.76倍;在共同解出的17組實(shí)例上,RIPB19的時(shí)間性能達(dá)到IPB19的1.34～2.01倍,隨k呈增長(zhǎng)趨勢(shì),平均1.61倍。相對(duì)圖1的情況,圖3和圖4中RIPB的優(yōu)勢(shì)明顯擴(kuò)大,其原因相似,這里僅分析圖4的情況。該子集的授權(quán)比例為1/2,當(dāng)k=18～35時(shí),|bQ|最大為8～9。但是其相變點(diǎn)(注意授權(quán)比例增大時(shí),原有約束不變)為27～62,故k=18和35時(shí),5元bQ的互斥約束剪枝概率約為0.84和0.65,較難進(jìn)入授權(quán)驗(yàn)證。而當(dāng)|bQ|≤3時(shí),必有|NB(bQ)|≥k,簡(jiǎn)指派均有充分優(yōu)勢(shì),故其整體優(yōu)勢(shì)較圖1明顯擴(kuò)大。同時(shí)由于k增大時(shí),簡(jiǎn)指派優(yōu)勢(shì)不充分的|bQ|=4節(jié)點(diǎn)比例提高有限,簡(jiǎn)指派的優(yōu)勢(shì)也將隨k增大而明顯增長(zhǎng)。2倍授權(quán)時(shí),簡(jiǎn)指派在21版本上取得了更大優(yōu)勢(shì),這是因?yàn)樵搶?shí)例集資源配比和授權(quán)比例都較大,任務(wù)和塊的授權(quán)資源密度很高,對(duì)19版本的指派計(jì)算方式非常有利。這使得在19版本中,盡管存在重復(fù)指派缺陷,但指派代價(jià)占總驗(yàn)證代價(jià)的比例仍然低于21版本,從而簡(jiǎn)指派的改進(jìn)效果相對(duì)難以凸顯。

增大授權(quán)比例明顯擴(kuò)大了簡(jiǎn)指派方法的優(yōu)勢(shì),而有關(guān)原因在實(shí)驗(yàn)1中已進(jìn)行過分析。但這里2倍授權(quán)比例就導(dǎo)致了較10倍資源配比更大的優(yōu)勢(shì),原因在于:

(1) 增大資源配比提升了資源總數(shù),在固定的授權(quán)比例下,各任務(wù)的授權(quán)資源將更為分散。此時(shí)雖然每個(gè)任務(wù)的授權(quán)資源集擴(kuò)大了,但其交集的擴(kuò)大幅度會(huì)受到抑制,|NB(bQ)|只是按資源配比的增大倍數(shù)擴(kuò)大。而增大授權(quán)比例時(shí),資源數(shù)量不變,不僅每個(gè)任務(wù)的授權(quán)資源集擴(kuò)大,而且其交集的擴(kuò)大幅度會(huì)增強(qiáng),|NB(bQ)|按授權(quán)比例增大倍數(shù)的|bQ|次冪擴(kuò)大,會(huì)使更多節(jié)點(diǎn)達(dá)到簡(jiǎn)指派的實(shí)施條件。

(2)μ%=100的相變實(shí)例集在增大資源配比時(shí),也增加了約束數(shù)量。后者導(dǎo)致剪枝模式空間不會(huì)明顯擴(kuò)大,抑制了較大|∪Q|-|Q|值的增多。而由圖2和圖4相關(guān)分析可知,該值對(duì)簡(jiǎn)指派的優(yōu)勢(shì)程度起很大作用。而增大授權(quán)比例讓實(shí)例進(jìn)入“欠約束”狀態(tài),剪枝模式樹邊緣更逼近完全樹葉端,導(dǎo)致更多較大的|∪Q|-|Q|值,從而簡(jiǎn)指派的作用效果也隨之提升。

現(xiàn)在對(duì)μ%=10的情形,將約束數(shù)量減少為原來的0.75和0.5倍,保持其他參數(shù)不變,按前述方式生成實(shí)例集,對(duì)4種算法進(jìn)行測(cè)試。0.75倍約束時(shí)的結(jié)果如圖5所示,0.5倍約束的結(jié)果如圖6所示。每種算法對(duì)上述各解出實(shí)例組的平均峰值空間均在19M左右,與之前相近。這是因?yàn)闇p少約束對(duì)實(shí)例和預(yù)計(jì)算索引的規(guī)模影響也不大。

統(tǒng)計(jì)圖5原始數(shù)據(jù)可知:在共同解出的19組實(shí)例上,RIPB21的時(shí)間性能達(dá)到IPB21的1.03～1.13倍,平均1.09倍;在共同解出的18組實(shí)例上,RIPB19的時(shí)間性能達(dá)到IPB19的1.16～1.36倍,平均1.25倍。相對(duì)圖1的情況,RIPB的優(yōu)勢(shì)有一定擴(kuò)大。這主要是因?yàn)闇p少約束使實(shí)例偏離相變點(diǎn),進(jìn)入“欠約束”狀態(tài),使更多簡(jiǎn)指派有潛在優(yōu)勢(shì)的搜索結(jié)點(diǎn)Q(位于原來的剪枝邊緣或其下方)進(jìn)入了授權(quán)匹配驗(yàn)證。這些節(jié)點(diǎn)Q位置較深,其|bQ|必須很小,才能使|NB(bQ)|取滿足條件(2)的值。而深度越大,這樣的結(jié)點(diǎn)相對(duì)越少,故RIPB的優(yōu)勢(shì)較圖1提高不多。

由統(tǒng)計(jì)圖6原始數(shù)據(jù)可知:在共同解出的8組實(shí)例上,RIPB21的時(shí)間性能達(dá)到IPB21的1.06～1.12倍,平均1.09倍;在共同解出的8組實(shí)例上,RIPB19的時(shí)間性能達(dá)到IPB19的1.31～1.39倍,平均1.35倍。而在圖5的前8組實(shí)例上,RIPB21的時(shí)間性能只是達(dá)到IPB21的1.03～1.10倍,平均1.07倍。可見,隨著約束進(jìn)一步減少,RIPB的優(yōu)勢(shì)仍有微弱擴(kuò)大,其原因仍類似于圖5相關(guān)分析。0.5倍約束的影響明顯弱于2倍授權(quán)比例,這是因?yàn)閱渭兘档图s束對(duì)簡(jiǎn)指派優(yōu)勢(shì)的影響比較局限,特別是不能增大NB(bQ)的值。

5 結(jié)束語(yǔ)

本文面向云/服務(wù)化資源環(huán)境和WS可行解尋優(yōu)場(chǎng)景,研究資源獨(dú)立WS在模式枚舉計(jì)數(shù)設(shè)置下的求解技術(shù)。對(duì)此類WS的最高效求解途徑IPB進(jìn)行改進(jìn),建立了簡(jiǎn)指派優(yōu)化技術(shù)。將本文方法應(yīng)用于IPB的兩種實(shí)現(xiàn)(包括原始C#實(shí)現(xiàn)的移植版本),在兩個(gè)隨機(jī)實(shí)例集上進(jìn)行實(shí)驗(yàn),結(jié)果表明:

(1)為最大化可滿足決策難度而生成的相變實(shí)例集對(duì)IPB并非最難的,而在偏離相變區(qū)的“欠約束”實(shí)例集上,該方法的性能急劇下降。這表明模式枚舉設(shè)置的求解難度有著顯著的特點(diǎn),給現(xiàn)有最好的技術(shù)路線帶來了新的挑戰(zhàn)。

(2)通過降低約束密度,或提高資源配比,特別是通過增大授權(quán)比例的方式進(jìn)入“欠約束”狀態(tài)后,本文方法較IPB有明顯的優(yōu)勢(shì)。另外在相變實(shí)例集上,本文的方法也有一定優(yōu)勢(shì)。

下一步將結(jié)合增量模式回溯法研究的新進(jìn)展,繼續(xù)優(yōu)化模式枚舉/計(jì)數(shù)的性能,并尋求在非資源獨(dú)立約束條件下的擴(kuò)展。