項目魯棒調度資源分配方案優化算法研究

葉博童

摘 要：由于活動間的資源爭搶會使調度計劃在執行過程中失效，因此合理的資源分配方案對于調度計劃至關重要。基于現有研究成果提出了SCAS（Superior Chain Allocation Scheme）算法，在資源分配時優先選擇優質資源鏈為重要活動提供資源，同時盡可能減少附加約束數量，保證資源按時傳遞給重要活動，降低資源沖突對進度計劃魯棒性的影響。

關鍵詞：魯棒調度；資源分配；優化算法

中圖分類號：TB 文獻標識碼：A doi：10.19311/j.cnki.16723198.2019.32.099

0 引言

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

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

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

1 問題描述與數學模型

1.1 問題描述

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

1.2 問題提出

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

2 SCAS算法

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

2.1 算法原理

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

2.2 鏈式調度

Policella用一組資源鏈表示資源，通過選擇資源鏈為活動提供資源。而鏈式調度在選擇資源鏈時只考慮了優先關系，忽略了資源鏈間的差異。當資源鏈流經活動數較多時，因其他活動延誤造成資源鏈占用時間過長的可能性越大，資源鏈按時流入后序活動的可能性越小。本文將資源鏈根據其流經活動數進行比較，并將流經的活動數少的資源鏈稱為優質資源鏈。

2.3 階段路徑圖

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

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

2.4 算法步驟

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

開始點。在每個階段生成前向活動表和后向活動表，后向活動按照位置系數由大到小排序，按順序對后向活動分配資源鏈。分配時優先選擇有邏輯關系的緊前活動占用的優質資源鏈提供資源；若仍不能滿足資源需求，根據附加約束數最少的原則，優先選擇資源鏈占用量不少于需求量的前向活動提供資源，若符合條件的前向活動不止一個，選擇優質資源鏈較多的活動提供資源，以降低其他活動的延遲對后向活動產生影響的概率。

2.5 算例結果

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

3 結語

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

參考文獻

[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]張沙清，陳新度，陳慶新.基于優化資源流約束的模具多項目反應調度算法[J].系統工程理論與實踐，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.