項目魯棒調(diào)度資源分配方案優(yōu)化算法研究

葉博童

摘 要：由于活動間的資源爭搶會使調(diào)度計劃在執(zhí)行過程中失效，因此合理的資源分配方案對于調(diào)度計劃至關(guān)重要?；诂F(xiàn)有研究成果提出了SCAS（Superior Chain Allocation Scheme）算法，在資源分配時優(yōu)先選擇優(yōu)質(zhì)資源鏈為重要活動提供資源，同時盡可能減少附加約束數(shù)量，保證資源按時傳遞給重要活動，降低資源沖突對進(jìn)度計劃魯棒性的影響。

關(guān)鍵詞：魯棒調(diào)度；資源分配；優(yōu)化算法

中圖分類號：TB 文獻(xiàn)標(biāo)識碼：A doi：10.19311/j.cnki.16723198.2019.32.099

0 引言

在項目調(diào)度過程中，由于施工環(huán)境等各種變化可能使實際執(zhí)行情況與預(yù)期計劃發(fā)生偏離，造成項目成本過高和延期完工，所以在計劃階段需要制定具有較高魯棒性的項目調(diào)度計劃來指導(dǎo)實際工作。

自從Artigues等首次提出資源流網(wǎng)絡(luò)的概念，并將其引入到項目調(diào)度研究后，很多學(xué)者都對資源約束項目調(diào)度問題進(jìn)行了深入的研究。Leus R等基于資源流網(wǎng)絡(luò)設(shè)計了一個動態(tài)資源分配模型。Artigues等通過隨機選擇活動對進(jìn)行資源分配得到可行的資源流網(wǎng)絡(luò)。雖然該算法較為簡單，但在資源分配時隨機性較大。Policella等在資源分配過程中提出了鏈的概念，通過為活動分配一定數(shù)量的鏈來完成資源配置。Nalan等通過估計活動的邊際效用來確定資源分配的順序，但是這種算法的計算時間較長，不利于大規(guī)模項目的求解。

考慮到現(xiàn)有研究中的不足，本文提出了SCAS算法，SCAS算法以資源鏈的方式進(jìn)行資源分配，并定義優(yōu)質(zhì)資源鏈和活動位置系數(shù)，通過位置系數(shù)來判斷活動的重要程度，優(yōu)先分配優(yōu)質(zhì)資源鏈為重要活動提供資源，盡可能保證了項目調(diào)度按計劃進(jìn)行。同時，在分配時充分利用優(yōu)先關(guān)系傳遞資源，減少附加約束數(shù)量，得到了魯棒性最好的資源分配方案。

1 問題描述與數(shù)學(xué)模型

1.1 問題描述

本文采用單代號網(wǎng)絡(luò)圖描述項目，項目網(wǎng)絡(luò)圖G（N，A）由節(jié)點活動1到節(jié)點活動n一共n個活動組成，N表示節(jié)點集，A表示邏輯關(guān)系約束形成的弧集?；顒觠（j=0，1，…，n）的開始時間為sj，活動工期為dj，第kk∈K種資源的初始需求量為rjk，第k種資源的資源限量為Rk。fijk表示活動i傳遞給活動j第k種資源的資源量，并生成資源約束（i，j）。

1.2 問題提出

在項目實施過程中，各種環(huán)境因素的影響最終會導(dǎo)致項目活動不能按計劃執(zhí)行。本文將活動的實際開始時間與預(yù)期開始時間進(jìn)行比較，以各活動的時間差值與相應(yīng)權(quán)重的乘積來衡量計劃的魯棒性，目標(biāo)函數(shù)是懲罰成本最小化，min∑j∈NωjE（sj-sj）。

2 SCAS算法

資源分配產(chǎn)生的附加約束會影響活動間的依賴性，降低方案的松弛性。本文將資源以資源鏈的方式進(jìn)行分配，通過識別對項目影響較大的活動并優(yōu)先滿足其資源要求，盡可能降低重要活動因資源延遲對項目整體調(diào)度的影響，提高調(diào)度計劃魯棒性。

2.1 算法原理

本算法按階段一次性分配資源。在資源分配時，通過活動在項目調(diào)度中的位置判斷活動被延誤的可能性，當(dāng)活動的實現(xiàn)路徑較復(fù)雜且前項活動較多時，活動被延誤的可能性較大，因此，優(yōu)先分配延誤可能性較大的活動。在選擇資源鏈時，優(yōu)先選擇緊前活動占用的資源鏈為其提供資源，若資源需求未被滿足時，區(qū)分優(yōu)質(zhì)資源鏈，選擇優(yōu)質(zhì)資源鏈占有量較多的優(yōu)質(zhì)活動為其提供資源，降低附加約束對活動的不利影響。

2.2 鏈?zhǔn)秸{(diào)度

Policella用一組資源鏈表示資源，通過選擇資源鏈為活動提供資源。而鏈?zhǔn)秸{(diào)度在選擇資源鏈時只考慮了優(yōu)先關(guān)系，忽略了資源鏈間的差異。當(dāng)資源鏈流經(jīng)活動數(shù)較多時，因其他活動延誤造成資源鏈占用時間過長的可能性越大，資源鏈按時流入后序活動的可能性越小。本文將資源鏈根據(jù)其流經(jīng)活動數(shù)進(jìn)行比較，并將流經(jīng)的活動數(shù)少的資源鏈稱為優(yōu)質(zhì)資源鏈。

2.3 階段路徑圖

在一個調(diào)度計劃中，各個活動對整個調(diào)度計劃的影響是不同的。假設(shè)每條路線阻塞的概率是一樣的，那么活動前向約束數(shù)量越少，延遲的幾率會減少。同理，整個項目的約束數(shù)量越少，項目的延期幾率就會越少。因此，在進(jìn)行資源分配時應(yīng)優(yōu)先分配延誤可能性較大的活動。為了描述活動實現(xiàn)的難度，本文通過識別活動的實現(xiàn)路徑圖計算活動的位置系數(shù)，以此判斷活動延誤可能性大小。

階段路徑圖描述了實現(xiàn)該活動所需進(jìn)行的全部過程，由開始節(jié)點到該活動節(jié)點之間所有需要經(jīng)歷的活動節(jié)點和路線組成。本文定義位置系數(shù)為前向活動數(shù)（所有實現(xiàn)路徑上的活動總數(shù)）與路徑條數(shù)的乘積。

2.4 算法步驟

本算法按階段一次性分配資源，首先將活動按照開始時間排序生成活動順序表，以活動開始時間為階段

開始點。在每個階段生成前向活動表和后向活動表，后向活動按照位置系數(shù)由大到小排序，按順序?qū)笙蚧顒臃峙滟Y源鏈。分配時優(yōu)先選擇有邏輯關(guān)系的緊前活動占用的優(yōu)質(zhì)資源鏈提供資源；若仍不能滿足資源需求，根據(jù)附加約束數(shù)最少的原則，優(yōu)先選擇資源鏈占用量不少于需求量的前向活動提供資源，若符合條件的前向活動不止一個，選擇優(yōu)質(zhì)資源鏈較多的活動提供資源，以降低其他活動的延遲對后向活動產(chǎn)生影響的概率。

2.5 算例結(jié)果

本文算法采用MATLAB 2014a實現(xiàn)，根據(jù)圖1所示的項目算例，本文算法生成的資源分配方案如圖2所示。以第三階段為例，初始后向活動排序表為（6，7，5，8），初始前項活動順序表為（1，4，2，3）。為活動6選擇資源鏈時，因為活動2和活動4是活動6的緊前活動，而活動2占用的優(yōu)質(zhì)資源鏈較多，所以選擇活動2的第1～4條資源鏈和活動4的第5條資源鏈為活動6提供資源；活動5無緊前活動，優(yōu)先選擇優(yōu)質(zhì)資源鏈較多的活動1提供第13、14條資源鏈。本算法生成的資源分配方案中附加約束僅為2條。本算法在資源分配中考慮了最小化資源分配對項目調(diào)度的影響，有效提高了項目調(diào)度計劃的魯棒性。

3 結(jié)語

由于資源在活動間傳遞可能使活動間依賴關(guān)系變得更加復(fù)雜，從而降低項目調(diào)度計劃的魯棒性，因此，合理的資源分配方案對項目按時完成有重要的影響。本文在生成資源分配方案的過程中充分考慮資源分配對活動的影響，提出了SCAS算法，通過階段重要活動的識別及優(yōu)質(zhì)資源鏈的分配，實現(xiàn)了局部最優(yōu)分配，保證關(guān)鍵活動按計劃進(jìn)行，繼而提高了項目調(diào)度計劃的魯棒性。

參考文獻(xiàn)

[1]Artigues C，Roubellat F.A polynomial activity insertion algorithm in a multiresource schedule with cumulative constraints and multiple modes[J].European Journal of Operational Research，2000，127（2）：297316.

[2]Leus R，Herroelen W.The complexity of machine scheduling for stability with a single disrupted job.Operations Research Letters，2005，33（1）：151156.

[3]張沙清，陳新度，陳慶新.基于優(yōu)化資源流約束的模具多項目反應(yīng)調(diào)度算法[J].系統(tǒng)工程理論與實踐，2011，31（8）：15711580.

[4]Policella N.Solve-and-Robustify Synthesizing Partial Order Schedules by Chaining[J].Journal of Scheduling，2009，12（3）：299314.

[5]Nalan Gülpnar，Ethem anakoglu，Juergen Branke.Heuristics for the stochastic dynamic task-resource allocation problem with retry opportunities[J].European Journal of Operational Research，2017，23（8）：3441.

[6]Hazir¨ O，Haouari M，Erel E.Robust scheduling and robustness measures for the discrete time/cost trade-off problem[J].European Journal of Operational Research，2010，207（2）：633643.