基于資源隨機中斷的反應性多模式項目調度優化

李佳媛， 何正文

(西安交通大學 管理學院，陜西 西安 710049)

?

基于資源隨機中斷的反應性多模式項目調度優化

李佳媛， 何正文

(西安交通大學 管理學院，陜西 西安 710049)

資源中斷是項目實施過程中一種常見現象，它會導致項目進度計劃的變更并引起額外的成本。本文研究資源隨機中斷下的項目調度問題，目標是對基準進度計劃進行合理的調整，以最小化由此所造成的額外成本。作者首先對研究問題進行界定，隨后構建問題的優化模型。針對模型的NP-hard屬性，設計禁忌搜索啟發式算法。最后以基準列表算法和隨機生成算法為參照，在隨機生成的標準算例集合上對算法進行測試，得到如下結論：在可接受的計算時間范圍內，禁忌搜索獲得的滿意解質量明顯高于其他兩種啟發式算法；算法的平均計算時間隨著項目活動數的增加而增加，隨著網絡復雜度、資源強度或資源中斷次數的增加而減小；滿意解的平均目標函數值，隨著項目活動數或網絡復雜度的增加而增加，隨著資源中斷次數的增加而減小，與資源強度無明顯關系。

反應性項目調度；優化模型；禁忌搜索；資源隨機中斷

0 引言

由于內外部諸多不可預見因素的干擾，現實中的絕大多數項目在執行過程中都不可避免地會發生變更[1]。項目的變更無疑會引起進度計劃的調整、資源配置的改變，進而影響項目的平穩實施并由此產生額外成本。

在項目執行過程中，如何基于實際情況對基準進度計劃進行調整，在理論上被稱為反應性項目調度問題(Reactive Project Scheduling Problem)[2]。關于該問題，目前已有學者開始進行研究：Vonder等[3]對已有的多種前攝性調度和反應性調度算法進行了對比測試，找到了計算效果較好的算法組合。Vonder等[4]還提出了多種最小化實際與計劃進度偏差的反應性調度啟發式算法。Deblaere等[5]設計了針對活動工期不確定的反應性調度啟發式算法，并推導出了相應的進度計劃穩定性下界。Lambrechts等[6]設計了單模式下針對資源中斷的多種計劃生成策略與反應性調度策略并進行了測試。Deblaere等[7]開發了將活動開始時間延后與執行模式改變同步進行的反應性調度精確算法與啟發式算法，并對精確算法、啟發式算法及多種算法結合的情況進行了測試分析。任世科等[8]研究了突發事件應急救援的動態調度優化問題，構建了相應的動態調度優化模型，并設計了禁忌搜索啟發式算法。然而，必須指出的是，當前對該問題的研究尚處于起步階段，亟待進一步的深入和擴展。

值得注意的是，在造成項目變更的各種因素中，資源問題是最為突出的因素之一。其中，在項目實施過程中一個經常遇到的問題，便是項目資源的隨機中斷[9][10]。資源隨機中斷是指由于各種干擾因素的作用，導致項目資源在某一隨機時段上的不可使用。顯然，當資源隨機中斷發生時，項目管理者將不得不對基準進度計劃，包括各活動的執行模式和開始時間進行調整。本文正是基于上述理論和現實背景，研究資源隨機中斷下的反應性項目調度問題。即研究如何基于資源中斷對基準進度計劃進行調整，以使得由此產生的額外總成本最小化。

在論文的后續部分，作者首先對所研究問題進行界定。隨后，構建基于資源隨機中斷的反應性多模式項目調度優化模型。針對問題的NP-hard屬性，設計禁忌搜索啟發式算法。在隨機生成的標準算例集合上對算法進行測試分析。最后，總結全文并給出研究結論。

1 問題界定

本文采用基于活動(Activity-based)的研究方法，將項目表示成AoN (Activity-on-Node)網絡，其中，節點代表活動，箭線代表活動之間的邏輯關系。現假定某一項目包含有N個活動，出于網絡表述的需要，額外添加兩個虛活動：活動0和活動N+1，前者表示項目的開始，后者表示項目的結束。項目的執行需要K種可更新資源，第k(k=1, 2,…,K)種資源的可用量為aK。活動i(i=0, 1,…,N+1)具有Mi種執行模式，以模式m(m=1, 2,…,Mi)執行時的工期為dim，對第k種資源的需求量為rikm。注意，虛活動0和N+1在任何執行模式下的工期及對資源的需求量均為0。

顯然，在對項目進度計劃進行調整時，應對BT中各活動的開始時間進行審慎的權衡和分析，以使得由此所引起的總損失Π最小化。

2 模型構建

根據上述對研究問題的界定，可構建基于資源隨機中斷的反應性多模式項目調度優化模型如下所述：

(1)

(2)

(3)

(4)

(5)

(6)

上述優化模型為一整數規劃優化模型。目標函數式(1)最小化由于項目進度計劃反應性調整而引起的總損失Π。約束條件式(2)為每個T時刻未完成的活動重新確定一種執行模式；式(3)將T時刻已經完成的活動的開始時間定義為基準開始時間；式(4)確保在對活動開始時間和執行模式進行調整時，活動之間的優先關系得到滿足；式(5)為可更新資源約束，確保T時刻及其后每個時刻正在進行的活動對資源的總需求量不超過資源的可用量；式(6)為決策變量的定義域約束。

上述優化模型可視為經典的確定型資源約束項目調度問題(resource-constrained project scheduling problems)[11]，向資源隨機中斷的不確定條件下的一種擴展，屬于活動具有多種執行模式的資源約束反應性項目調度問題[12]。不失一般性，令模型中的Mi=1(i=0, 1,…,N+1)，則本文所研究問題即可簡化為一個單模式的資源約束反應性項目調度問題。也就是說，前者可視為后者在活動具有多種執行模式下的一般化形式，而后者則可視為前者在活動僅具有一種執行模式下的一個特例。由于單模式資源約束反應性項目調度問題已被Leus和Herroelen[13]證明為一NP-hard問題，所以，本文所研究問題也必然為一NP-hard問題。

3 算法設計

鑒于本文所研究問題的NP-hard屬性，采用啟發式算法求解該問題。已有相關研究[12,14]表明，禁忌搜索算法具有較優的計算效果，且該種算法已被眾多學者[5～8]應用于反應性調度問題的求解中，因此本文也采用禁忌搜索對問題進行求解。本文所設計的禁忌搜索啟發式算法具有如下特點：

采用活動優先次序列表表示問題的可行解，鄰點生成操作簡便易行；

所有生成的鄰點中選擇目標值較高的鄰點進行移動，移動方向具有較強的確定性；

用禁忌列表對新近搜索過的移動進行禁止，避免陷入局部最優并減少重復搜索；

終止條件綜合考慮搜索次數和無改進迭代次數，在保證解的質量的同時可減少無效搜索時間。

下面首先介紹算法的初始可行解構造、鄰點生成機理、移動定義，然后給出禁忌列表、算法終止條件及具體的搜索步驟。

3.1 解的表示及初始解構造

問題的可行解用如下兩個列表表示：

活動執行模式列表ML：該列表中的元素與集合BT中的活動一一對應，并按活動的編號次序排列，元素的取值定義了相應活動的執行模式。

活動優先次序列表AL：該列表定義了集合BT中活動在安排開始時間時的優先次序，即在不違反活動之間邏輯關系的前提下，排在該列表前面的活動優先考慮安排。給定一個AL，利用SSGS(serial schedule generation scheme)[15]，可以生成一個唯一的滿足資源約束的活動開始時間安排ST。

問題的初始可行解按下述步驟構造：

步驟1 隨機地為BT中的每個活動選定一種執行模式，由此得到一個初始活動執行模式列表MLini。

步驟2 對于BT中的活動，在不違反活動之間邏輯關系的前提下，按照ωi取值從大到小進行排列，由此獲得一個初始活動優先次序列表ALini。

3.2 鄰點生成機理

當前可行解MLcur、ALcur的鄰點MLnei、ALnei由如下算子生成：

執行模式改變算子MC：在MLcur上選擇一個元素，將其取值改變成另外一個可行的取值，從而將其所代表活動的執行模式從當前模式轉變為另一種模式，由此得到當前解的一個鄰點(注意，在此過程中ALcur保持不變)。按照上述處理方式，MLcur上被選擇的元素取值可以改變為任何其他可行的取值，而且，對于MLcur上的所有其他元素，均可做同樣的處理。經過上述操作，可以獲得當前可行解的一個鄰點集合，在該集合中每個鄰點的ML列表上，僅有一個元素的取值與當前解不同。

活動位置交換算子AS：在ALcur上選擇兩個元素，在不違反優先關系的前提下交換它們的位置，從而將當前可行解轉變為它的一個鄰點(注意，在此過程中MLcur保持不變)。按照上述處理方式，ALcur上任何兩個無邏輯關系的元素均可做同樣的處理，由此可獲得當前可行解的一個鄰點集合，在該集合中每個鄰點的AL列表上，僅有兩個元素的位置與當前解不同。

從上述算子生成的鄰點集合中，選擇最好的解(即目標函數值最小的解)作為當前可行解的鄰點MLnei、ALnei。

3.3 移動定義

對應于生成鄰點操作所使用的不同算子，相應的移動定義如下：

MC移動：用一個三元向量——(在MLcur上所選元素的位置，該元素的初始值，該元素的新值)。舉例說明，如果MLcur上位置8的元素取值由2變成了1，那么MC移動表示為(8,2,1)，其含義是位置8上元素所對應活動的執行模式由2變成了1。該移動的逆向移動表示為(8,2)并被同時加入到禁忌列表中，以避免位置8上的元素取值重新變回2。

AS移動：用一個二元向量——(在ALcur上所選的第1個元素的取值，在ALcur上所選的第2個元素的取值)表示。舉例說明，如果ALcur上取值為5的元素與取值為7的元素互換位置，則AS移動表示為(5,7)，其含義是取值為5的元素的優先次序與取值為7的元素的優先次序被互相交換。該移動的逆向移動表示為(7,5)并被同時加入到禁忌列表中，以避免取值為7的元素和取值為5的元素重新換回原來的位置。

3.4 禁忌列表及算法終止條件

禁忌列表的長度設置為[0.5NBT](其中，NBT為集合BT中活動的總數)，采用“先進先出FIFO(First-in-First-out)”的原則進行管理：每當鄰點生成算子形成一個移動時，該移動的逆向移動從底部加入到禁忌列表中，與此同時，最早進入列表的逆向移動從頂部移出列表，列表中其余逆向移動向上遞進一位。所有位于禁忌列表中的逆向移動都是被禁止的，但當一個被禁止的逆向移動能夠生成比當前最好解還要好的鄰點時，它的禁忌狀態可依據激活準則被解除，即將其從禁忌列表中刪除，其下所有逆向移動向上遞進一位，同時將該逆向移動加入到禁忌列表的底部。

在算法運行過程中，當下述兩個終止條件有一個滿足時，算法便停止搜索并將保存的當前最好解輸出為滿意解：

當搜索的鄰點數Num達到Numstop，Numstop在本研究中設定為[100NBT]；

算法的無改進迭代次數NNum達到NNumstop，且當前所有搜索對象均被禁忌，又不可激活，NNumstop在本研究中設定為[10NBT]。

3.5 搜索步驟

步驟1 輸入初始可行解MLini、ALini，及其對應的目標值Πini。初始化禁忌列表，定義終止條件Numstop和NNumstop，令Num=0，NNum=0。將當前解及當前最好解賦值為初始解：MLcur=MLopt=MLini，ALcur=ALopt=ALini，Πcur=Πopt=Πini。

步驟2 從兩個算子中隨機地選擇一個，生成當前解的鄰點MLnei、ALnei，對應的目標函數值記為Πnei。判斷生成該鄰點的移動是否位于禁忌列表中，若是轉步驟4；若否轉步驟3。

步驟3 將當前解更新為鄰點解：MLcur=MLnei，ALcur=ALnei，Πcur=Πnei。令Num=Num+1，更新禁忌列表。若Πnei<Πopt，進一步將當前最好解也更新為鄰點解：MLopt=MLnei，ALopt=ALnei，Πopt=Πnei，令NNum=0。轉步驟5。

步驟4 判斷Πnei<Πopt是否成立。若成立則激活生成該鄰點移動的禁忌狀態，將當前解及當前最好解同時更新為鄰點解：MLcur=MLopt=MLnei，ALcur=ALopt=ALnei，Πcur=Πopt=Πnei，令Num=Num+1，NNum=0，更新禁忌列表，轉步驟5；否則，令NNum=NNum+1，轉步驟6。

步驟5 判斷Num≥Numstop是否成立。若成立轉步驟7；否則，轉步驟2。

步驟6 判斷NNum≥NNumstop是否成立。若成立轉步驟7；否則，轉步驟2。

步驟7 輸出當前最好解，即MLopt、ALopt、Πopt。

4 算法測試

為測試本文所設計的禁忌搜索啟發式算法，用基準列表(活動優先次序列表按基準進度開始時間從小到大排列，活動模式與基準進度一致)和隨機生成RG(random generation，即隨機產生規定數目的可行解，從中選出最好解作為問題的滿意解)兩種啟發式算法作為對比參照。隨機生成的終止條件與禁忌搜索相同，即當探測可行解的總數達到Numstop時停止搜索。算法測試在ProGen[16]隨機生成的標準算例上進行，算例的參數設置見表1。其中，按全因子實驗設置的參數有4個：項目非虛活動數N、網絡復雜度NC(network complexity，表示每個節點上無冗余的活動數平均值)、可更新資源強度RRS(renewable resource strength)和資源中斷次數Numdis。其中，參數N和NC取值為3種，RRS和Numdis取值為4種，每種參數組合下生成的算例數為10個，由此得到3×3×4×4×10=1440個算例。以項目總工期最短為目標搜索得到的滿意解作為項目的基準進度計劃。算法績效用如下四個指標進行評價：平均計算時間Timave、最大計算時間Timmax、平均目標函數值Пave和最大目標函數值Пmax。注意，在項目執行過程中，資源隨機中斷的發生有可能不止一次。當這種情況出現時，用多次資源中斷算法運行結果的平均值作為相應的評價指標。上述三種算法均采用Visual C++6.0編程，在CPU為1.60GHz，內存為1.00GB的個人計算機上運行。

算法的測試結果如表2所示。由表2可見，對于全部算例，從獲得的滿意解質量看，禁忌搜索的Пave和Пmax比基準列表的相應指標分別低21.3%和10.2%，比隨機生成的分別低50.6%和48.1%；從算法的運行時間看，由于基準列表算法沒有搜索過程，因此Timave和Timmax近似為0；隨機生成算法在搜索過程中不需要禁忌和判斷，因此Timave和Timmax比禁忌搜索的低82.8%和93.1%。上述結果表明，在滿意解質量方面，禁忌搜索最好，基準列表次之，隨機生成最差；在計算時間方面，基準列表最好，隨機生成次之，禁忌搜索最差。但是，算法的最長運行時間不超過4.3秒，所以，可以認為：在可接受的計算時間范圍內，禁忌搜索啟發式算法能夠獲得質量較高的滿意解，與其他兩種啟發式算法相比，該算法是求解本文所研究問題的較好算法。

上述結果驗證了本文所設計的禁忌搜索啟發式算法的特點。首先，由于上述三種算法均采用優先次序列表生成活動的開始時間，因此搜索速度均較快。如果采用其他方式(如開始時間窗)搜索開始時間，禁忌搜索中AS算子的搜索范圍將會大大擴大，必然會導致搜索時間的增加。其次，與基準列表算法和隨機搜索算法相比，禁忌搜索的滿意解質量最高，這與算法搜索時總是向目標值較高的鄰點移動，保證了移動方向具有較強的確定性有關。而且，采用禁忌列表可使得搜索不局限在已經得到的最好解上，從而有效避免了陷入局部最優并減少了重復搜索，這也進一步提高了算法的搜索效率。最后，與一般禁忌搜索算法通常將搜索次數設定為終止條件不同，本文所設計的禁忌搜索算法同時考慮了無改進迭代次數，由此減少了無效的搜索時間，從而使得算法獲得較為理想的計算結果。

表2 算法的測試結果

從關鍵參數對運算時間Timave和滿意解質量Пave的影響看，當算例規模N增大時，算法的Timmax和Пave單調上升。這是因為隨著算例規模的增大，每次資源中斷時需要調整的活動數隨之增加，導致算法的計算時間變長，同時因活動開始時間延遲而引起的損失增加。當網絡復雜度NC增大時，算法的Timave單調下降，Пave單調上升。造成這一結果的原因是：網絡復雜度增加后，活動間的邏輯關系變復雜，一個活動延遲將影響更多的后續活動，所以資源中斷造成的損失值增加，同時由于活動間優先關系變復雜，搜索的可行解變少，因而計算時間變短。當資源中斷次數Numdis增大時，算法的Timmax和Пave單調下降。這主要是因為隨著資源中斷次數的增加，在給定項目規模的條件下，平均每次中斷需要調整的活動數下降，所以，算法的計算時間變短，每次資源中斷的平均額外總成本下降。

可更新資源強度RRS對計算結果的影響較為復雜。當RRS增大時，算法的Timave單調下降，而Пave卻呈現隨機波動的現象。這一結果分析如下：資源強度增大意味著活動安排時受到的資源約束放松，這使得在生成鄰點的操作中資源約束更容易得到滿足，因此計算時間也相應縮短。當資源約束放松時，滿意解通常應該有所改善，但本文的測試結果卻未支持這一結論。這是因為本文所采用的基準進度計劃是以項目總工期最短為目標搜索得到的滿意解，因此資源強度越大，基準進度計劃越接近最優解，這樣，當資源中斷發生時，調整后的進度計劃與基準計劃的偏離便可能越顯著；相反，當資源強度較小時，基準進度計劃可能是一個距離最優解較遠的滿意解，這使得它反而對資源中斷所造成的影響不是很敏感，亦即調整后的進度計劃與基準計劃偏離可能會較小。

5 結論

本文研究了基于資源隨機中斷的反應性多模式項目調度問題。作者首先對研究問題進行界定，目標是當資源中斷發生時，在可更新資源約束下，合理安排活動的執行模式和開始時間，以最小化資源中斷所造成的損失。在此基礎上構建了問題的優化模型，并針對其NP-hard屬性和特點設計禁忌搜索啟發式算法。最后以基準列表算法和隨機生成算法為參照，在隨機生成的標準算例集合上對算法進行了比較測試，分析了項目活動數、網絡復雜度、資源強度和資源中斷次數等關鍵參數對計算結果的影響，得到如下結論：

在可接受的計算時間范圍內，禁忌搜索啟發式算法獲得的滿意解質量明顯高于其他兩種啟發式算法，是求解本文所研究問題的較好算法；

算法的平均計算時間，隨著項目活動數的增加而增加，隨著網絡復雜度、資源強度或資源中斷次數的增加而減小；

滿意解平均目標函數值，隨著項目活動數或網絡復雜度的增加而增加，隨著資源中斷次數的增加而減小，與資源強度無明顯關系。

[1] 龐南生,孟俊姣.多目標資源受限項目魯棒調度研究[J].運籌與管理,2012,21(3):27-32.

[2] Herroelen W, Leus R. Project scheduling under uncertainty: survey and research potentials[J]. European Journal of Operational Research, 2005, 165(2): 289-306.

[3] Vonder S V D, Demeulemeester E, Herroelen W. A classification of predictive-reactive project scheduling procedures[J]. Journal of Scheduling, 2007, 10: 195-207.

[4] Vonder S V D, Ballestin F, Demeulemeester E, Herroelen W. Heuristic procedures for reactive project scheduling[J]. Computers & Industrial Engineering, 2007, 52: 11-28.

[5] Deblaere F, Demeulemeester E, Herroelen W, Vonder S V D. Robust resource allocation decisions in resource-constrained projects[J]. Decision Sciences, 2007, 38(1): 5-34.

[6] Lambrechts O, Demeulemeester E, Herroelen W. Proactive and reactive strategies for resource-constrained project scheduling with uncertain resource availabilities[J]. Journal of Scheduling, 2008, 11: 121-136.

[7] Deblaere F, Demeulemeester E, Herroelen W. Reactive scheduling in the multi-mode RCPSP[J]. Computers & Operations Research, 2011, 38: 63-74.

[8] 任世科,袁治平,徐渝.突發事件應急救援動態調度優化: 以KX井噴事故為例[J].運籌與管理,2012,21(3):1-7.

[9] Mehta S, Uzsoy R. Predictive scheduling of a job shop subject to breakdowns[J]. IEEE Transactions on Robotics and Automation, 1998, 14: 365-378.

[10] Mehta S, Uzsoy R. Predictive scheduling of a single machine subject to breakdowns[J]. International Journal of Computer Integrated Manufacturing, 1999, 12: 15-38.

[11] Blazewicz J, Lenstra J K, Rinnooy K A H G. Scheduling subject to resource constraints: classification and complexity[J]. Discrete Applied Mathematics, 1983, 5: 11-24.

[12] Herroelen W, Leus R. Robust and reactive project scheduling: a review and classification of procedures[J] International Journal of Production Research, 2004, 42(8): 1599-1620.

[13] Leus R, Herroelen W. The complexity of machine scheduling for stability with a single disrupted job[J]. Operations Research Letters, 2005, 33(2): 151-156.

[14] Ouelhadj D, Petrovic S. A survey of dynamic scheduling in manufacturing systems[J]. Journal of Scheduling, 2009, 12: 417- 431.

[15] Kolisch R. Serial and parallel resource-constrained project scheduling methods revisited: theory and computation[J]. European Journal of Operational Research, 1996, 90(2): 320-333.

[16] Kolisch R, Sprecher A. PSPLIB-aproject scheduling problem library[J]. European Journal of Operational Research, 1996, 96(1): 205-216.

Optimization of Reactive Multi-mode Project Scheduling Based on Stochastic Breakdown of Resources

LI Jia-yuan, HE Zheng-wen

(SchoolofManagement，Xi’anJiaotongUniversity,Xi’an710049,China)

Resource breakdown occurs frequently during the implementation of projects. It may lead to the changes of project schedule and generate additional expenses. This paper involves the project scheduling problem under resource breakdown, where the objective is to adjust the baseline schedule reasonably so as to minimize the incurred additional expenses. The problem is identified at first and the optimization model is constructed accordingly. For the NP-hardness of the problem, a tabu search heuristic algorithm is developed. Finally, given the baseline list algorithm and the random generation algorithm as comparison, we test the tabu search algorithm on a set of standard instances generated randomly. The conclusions are drawn as follows. First, within the acceptable computation time, the quality of the desirable solutions obtained by the tabu search heuristic algorithm is significantly better than those obtained by other two heuristic algorithms. Second, the average computation time increases with the activity number, but decreases with the network complexity, the renewable resource strength, and the number of resource breakdown, respectively. Third, the mean of objective function value also climbs with the activity number and drops with the network complexity and the number of resource breakdown, but it seems that there is no significance influence on the renewable resource strength.

reactive project scheduling; optimization model; tabu search; stochastic resource breakdown

2012- 08-12

國家自然科學基金資助項目(70971105、71371150)；新世紀優秀人才支持計劃資助項目(NCET-13- 0460)

李佳媛(1987-),女，青海西寧人，碩士研究生，研究方向：項目管理及優化。

C935;F224.33

A

1007-3221(2015)06- 0044- 07

10.12005/orms.2015.0194