施應(yīng)玲 宿慧芳 龐南生

(華北電力大學(xué)經(jīng)濟(jì)與管理學(xué)院，北京 102206)

1 概述

項(xiàng)目調(diào)度問(wèn)題是項(xiàng)目管理領(lǐng)域的重要問(wèn)題，研究目標(biāo)是通過(guò)合理安排活動(dòng)開(kāi)始時(shí)間，使得成本或者工期等目標(biāo)值最優(yōu)化。

Leus,Herroelen設(shè)計(jì)了資源流網(wǎng)絡(luò)模型，并采用分支定界法解決了該問(wèn)題[1,2]。Artigues等提出了一個(gè)按活動(dòng)分配資源的資源流網(wǎng)絡(luò)算法，該算法優(yōu)點(diǎn)是計(jì)算簡(jiǎn)單，但生成的附加約束較多[3]。Policella等通過(guò)在基準(zhǔn)計(jì)劃中生成偏序調(diào)度計(jì)劃，提出了通過(guò)對(duì)活動(dòng)分配鏈從而生成資源流網(wǎng)絡(luò)的算法[4,5]。Deblaere等提出了資源流網(wǎng)絡(luò)優(yōu)化算法MABO[6]。通過(guò)對(duì)比分析結(jié)果表明MABO算法構(gòu)建的調(diào)度計(jì)劃魯棒性較強(qiáng)，但算法的準(zhǔn)確性不髙，會(huì)造成多資源分配方案的存在[7]。李佳媛等定義了三組0-1決策變量，構(gòu)建了基于資源緩沖的多模式項(xiàng)目調(diào)度優(yōu)化模型[8]。

本文提出了新的資源流網(wǎng)絡(luò)的生成算法，首先利用禁忌搜索算法得到基準(zhǔn)計(jì)劃，然后在原有的網(wǎng)絡(luò)計(jì)劃的基礎(chǔ)上添加不可避免的弧，在各活動(dòng)之間形成一個(gè)擴(kuò)大的優(yōu)先關(guān)系；按照一定順序排列接受資源的活動(dòng)；利用優(yōu)先規(guī)則為提供資源的活動(dòng)進(jìn)行排序，遍歷所有活動(dòng)，滿(mǎn)足其資源需求，最終形成可行的資源流網(wǎng)絡(luò)，并與現(xiàn)有算法進(jìn)行比較，分析其有效性。

2 資源優(yōu)化問(wèn)題提出

2.1 資源流概念

Artigues等將資源流網(wǎng)絡(luò)概念應(yīng)用到魯棒調(diào)度問(wèn)題中，在原有邏輯約束的基礎(chǔ)上附加資源約束，形成資源流網(wǎng)絡(luò)，在此基礎(chǔ)上對(duì)活動(dòng)進(jìn)行資源分配，有效避免活動(dòng)間的資源沖突，為解決執(zhí)行過(guò)程中的資源沖突提供了新的思路。

基于資源流網(wǎng)絡(luò)生成魯棒性調(diào)度方案的優(yōu)勢(shì)在于，調(diào)整不確定性因素時(shí)可以避免再發(fā)生新的資源沖突；而其劣勢(shì)在于新增的資源約束會(huì)使活動(dòng)間的制約關(guān)系增大，意味著前向活動(dòng)的拖延會(huì)給更多的活動(dòng)帶來(lái)不利影響，即降低調(diào)度方案的魯棒性。因此，為生成一個(gè)穩(wěn)定性較好的魯棒性計(jì)劃，就應(yīng)當(dāng)選擇對(duì)魯棒性影響較小的資源流網(wǎng)絡(luò)。

2.2 問(wèn)題分析與模型構(gòu)建

資源流網(wǎng)絡(luò)的生成，是在需要的活動(dòng)對(duì)(i,j)之間添加資源約束，建立先后關(guān)系，減小發(fā)生資源沖突的可能性。當(dāng)所有的活動(dòng)資源達(dá)到平衡之后，得到一個(gè)可行的資源流網(wǎng)絡(luò)。

以基準(zhǔn)計(jì)劃為基礎(chǔ)構(gòu)建資源流網(wǎng)絡(luò)，在活動(dòng)對(duì)之間附加資源約束將會(huì)增加活動(dòng)間相互制約，降低計(jì)劃的魯棒性，可建立以下優(yōu)化模型：

(1)

s.t.

(2)

(3)

f(i,j,k)∈{0,1,2,…},?i,j∈N;?k∈K

(4)

表1 參數(shù)含義

3 NSM資源分配算法

本文提出的NSM算法原理如下：先計(jì)算項(xiàng)目中的不可避免資源弧，然后將活動(dòng)按照開(kāi)始時(shí)間升序排列來(lái)獲取資源，同一時(shí)刻開(kāi)始的活動(dòng)按照“穩(wěn)定性成本貢獻(xiàn)值”的降序排列，從而得到LRA列表；當(dāng)為列表LRA中的活動(dòng)j分配資源時(shí)，可提供資源的活動(dòng)被分為兩類(lèi)：優(yōu)先資源集和非優(yōu)先資源集，當(dāng)優(yōu)先資源集中的資源不足以滿(mǎn)足活動(dòng)j的資源需求時(shí)，再由非優(yōu)先資源集中的活動(dòng)提供資源；當(dāng)可提供資源的活動(dòng)不止一個(gè)時(shí)，將活動(dòng)按照“后向子網(wǎng)絡(luò)復(fù)雜度”升序排列依次為活動(dòng)j提供資源。遍歷所有活動(dòng)，直到資源流網(wǎng)絡(luò)達(dá)到平衡。

3.1 資源分配變量計(jì)算

3.1.1不可避免的弧

“不可避免弧”是指在某給定計(jì)劃中，因各時(shí)段資源分配平衡的原因而必須在此活動(dòng)對(duì)之間附加的資源約束。對(duì)于?i∈N,?j∈N,且在基線(xiàn)調(diào)度計(jì)劃中，活動(dòng)i在活動(dòng)j開(kāi)始之前就已經(jīng)完成，即si+di≤sj，則判斷(i,j)∈AU的充要條件是：

(i,j)∈AU?

其中,Psj為在活動(dòng)j開(kāi)始時(shí)間正在進(jìn)行的活動(dòng)的集合，即活動(dòng)l的開(kāi)始時(shí)間與結(jié)束時(shí)間滿(mǎn)足sl

3.1.2穩(wěn)定性成本貢獻(xiàn)值

“穩(wěn)定性成本貢獻(xiàn)值”的計(jì)算方法如下：對(duì)于每個(gè)活動(dòng)j，通過(guò)仿真計(jì)算其開(kāi)始時(shí)間的平均延誤量δj；為了分析不同的活動(dòng)對(duì)其后向活動(dòng)的影響程度，本算法統(tǒng)一假設(shè)活動(dòng)j的實(shí)際開(kāi)始時(shí)間與計(jì)劃開(kāi)始時(shí)間相比為sj′=sj+δj，且工期延誤為dj′=1.2×dj，計(jì)算此時(shí)由于活動(dòng)j的拖延所導(dǎo)致的所有后向活動(dòng)開(kāi)始時(shí)間延誤值的加權(quán)之和Cj：

其中，Sj為活動(dòng)j的所有后向活動(dòng)(包括直接緊后活動(dòng)以及間接緊后活動(dòng))的集合，因此“穩(wěn)定性成本貢獻(xiàn)值”越大的活動(dòng)對(duì)網(wǎng)絡(luò)穩(wěn)定性的影響越大。

3.1.3優(yōu)先資源集

定義集合Pj為可以為活動(dòng)j提供資源的所有活動(dòng)的集合，該集合滿(mǎn)足以下條件：

(i,j)∈Pj?si+di≤sj,allocik>0,i∈N,j∈N。

其中,allocik為活動(dòng)i可以提供的第k種資源的數(shù)量。但是在集合Pj中選擇哪個(gè)活動(dòng)為活動(dòng)j優(yōu)先提供資源也直接影響著計(jì)劃的魯棒性。在這里，本文將集合Pj劃分為優(yōu)先資源集PAj和非優(yōu)先資源集PA_nonj。PAj中包含活動(dòng)j的緊前活動(dòng)或由不可避免弧連接的活動(dòng)i，該集合滿(mǎn)足以下條件：

(i,j)∈PAj?(i,j)∈A∪AU,si+di≤sj,allocik>0。

其中，PA_nonj為其他可為活動(dòng)j提供資源的非優(yōu)先活動(dòng)集合，所以當(dāng)集合PA_nonj中的活動(dòng)i為活動(dòng)j提供資源時(shí)，活動(dòng)對(duì)(i,j)之間需添加資源約束。對(duì)每個(gè)活動(dòng)j而言，先由集合PAj中的活動(dòng)為其提供資源，仍無(wú)法滿(mǎn)足其需求時(shí)再由PA_nonj中的活動(dòng)提供。

3.1.4后向子網(wǎng)絡(luò)復(fù)雜度

網(wǎng)絡(luò)復(fù)雜度NC(NetworkComplexity)是指在網(wǎng)絡(luò)中，平均每個(gè)節(jié)點(diǎn)(包括開(kāi)始虛活動(dòng)0和結(jié)束虛活動(dòng)n)上非冗余弧的數(shù)量。本文將NC的概念應(yīng)用到活動(dòng)i的后向子網(wǎng)絡(luò)GS(NS,AS)中，記做SNC：

3.2 NSM算法步驟

初始化：首先利用禁忌搜索算法生成基線(xiàn)調(diào)度計(jì)劃，然后計(jì)算不可避免的弧集AU，將原優(yōu)先關(guān)系擴(kuò)大，生成初始的資源流網(wǎng)絡(luò)。對(duì)任意資源k，虛活動(dòng)0的資源持有量為資源限量ak，即alloc0k=ak。按照LRA列表中的活動(dòng)次序，依次為其執(zhí)行下列步驟，直至所有活動(dòng)的資源需求得到滿(mǎn)足。

Step 1：判斷優(yōu)先資源集PAj中的活動(dòng)的資源持有量是否滿(mǎn)足活動(dòng)j的資源需求，PA_nonj中的活動(dòng)i按照其后向子網(wǎng)絡(luò)復(fù)雜度SNC進(jìn)行升序排列，依次向后傳遞資源。

Step 2：若不足，則由非優(yōu)先資源集PA_nonj中的活動(dòng)為活動(dòng)j提供資源，添加附加資源弧。

對(duì)于?k∈K,由PA_nonj中的活動(dòng)i按照其后向子網(wǎng)絡(luò)復(fù)雜度SNC進(jìn)行升序排列，依次為活動(dòng)j傳遞資源，更新資源流網(wǎng)絡(luò)。

Step 3：為活動(dòng)j分配資源。

按集合PAj以及集合PA_nonj活動(dòng)順序依次將活動(dòng)i的資源持有量分配給活動(dòng)j，直到：allocjk>rjk:

f(i,j,k)=min(allocik,rjk-allocjk),

allocik=allocik-f(i,j,k),

allocjk=allocjk+f(i,j,k)。

4 實(shí)驗(yàn)分析

為說(shuō)明本文提出的基于“穩(wěn)定性成本貢獻(xiàn)值”與“后向子網(wǎng)絡(luò)復(fù)雜度”的資源分配算法的可行性和合理性，本文將本算法與Artigues算法，Basic Chaining和MaxCC算法等進(jìn)行了實(shí)驗(yàn)比較分析。

為分析各算法在不同的項(xiàng)目規(guī)模條件下的表現(xiàn)性能，在實(shí)驗(yàn)中，選取了J10，J30，J50三組項(xiàng)目數(shù)據(jù)，每組包含200個(gè)項(xiàng)目實(shí)例仿真1 000次進(jìn)行實(shí)驗(yàn)比較分析，所有的實(shí)驗(yàn)數(shù)據(jù)均由生成器ProGen生成。

為評(píng)價(jià)不同算法所生成的資源分配方案對(duì)魯棒性的影響，本文選取指標(biāo)：項(xiàng)目穩(wěn)定性成本SC和項(xiàng)目附加約束數(shù)NPC，兩者的值越小，表示魯棒性越好。

表2 實(shí)驗(yàn)結(jié)果對(duì)比

從表2可以看出：對(duì)于SC,NPC兩個(gè)指標(biāo)，與其他三種算法相比較，本文算法NSM都有明顯下降，且隨著項(xiàng)目規(guī)模的增大這種趨勢(shì)越來(lái)越明顯，說(shuō)明利用該算法產(chǎn)生的資源流網(wǎng)絡(luò)在穩(wěn)定性成本和附加約束上都能保證計(jì)劃有一定魯棒性，在這樣的資源流網(wǎng)絡(luò)上進(jìn)行魯棒調(diào)度，能夠有效提高調(diào)度計(jì)劃對(duì)實(shí)際操作的指導(dǎo)性，做好統(tǒng)籌安排，減少損失。

5 結(jié)語(yǔ)

本文針對(duì)魯棒性資源分配提出了基于“穩(wěn)定性成本貢獻(xiàn)值”與“后向子網(wǎng)絡(luò)復(fù)雜度”的NSM資源流網(wǎng)絡(luò)生成算法，在接受資源和分配資源的活動(dòng)優(yōu)先順序上設(shè)定規(guī)則，使得資源分配有序進(jìn)行，盡可能減少附加資源約束，并降低計(jì)劃的穩(wěn)定性成本。實(shí)驗(yàn)表明所生成的資源流網(wǎng)絡(luò)能夠有效提升調(diào)度計(jì)劃的“解”魯棒性和“質(zhì)”魯棒性，具有一定現(xiàn)實(shí)指導(dǎo)作用。