李佳媛， 何正文

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

?

基于資源隨機中斷的反應(yīng)性多模式項目調(diào)度優(yōu)化

李佳媛， 何正文

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

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

反應(yīng)性項目調(diào)度；優(yōu)化模型；禁忌搜索；資源隨機中斷

0 引言

由于內(nèi)外部諸多不可預(yù)見因素的干擾，現(xiàn)實中的絕大多數(shù)項目在執(zhí)行過程中都不可避免地會發(fā)生變更[1]。項目的變更無疑會引起進度計劃的調(diào)整、資源配置的改變，進而影響項目的平穩(wěn)實施并由此產(chǎn)生額外成本。

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

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

在論文的后續(xù)部分，作者首先對所研究問題進行界定。隨后，構(gòu)建基于資源隨機中斷的反應(yīng)性多模式項目調(diào)度優(yōu)化模型。針對問題的NP-hard屬性，設(shè)計禁忌搜索啟發(fā)式算法。在隨機生成的標(biāo)準(zhǔn)算例集合上對算法進行測試分析。最后，總結(jié)全文并給出研究結(jié)論。

1 問題界定

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

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

2 模型構(gòu)建

根據(jù)上述對研究問題的界定，可構(gòu)建基于資源隨機中斷的反應(yīng)性多模式項目調(diào)度優(yōu)化模型如下所述：

(1)

(2)

(3)

(4)

(5)

(6)

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

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

3 算法設(shè)計

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

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

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

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

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

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

3.1 解的表示及初始解構(gòu)造

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

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

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

問題的初始可行解按下述步驟構(gòu)造：

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

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

3.2 鄰點生成機理

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

執(zhí)行模式改變算子MC：在MLcur上選擇一個元素，將其取值改變成另外一個可行的取值，從而將其所代表活動的執(zhí)行模式從當(dāng)前模式轉(zhuǎn)變?yōu)榱硪环N模式，由此得到當(dāng)前解的一個鄰點(注意，在此過程中ALcur保持不變)。按照上述處理方式，MLcur上被選擇的元素取值可以改變?yōu)槿魏纹渌尚械娜≈担?，對于MLcur上的所有其他元素，均可做同樣的處理。經(jīng)過上述操作，可以獲得當(dāng)前可行解的一個鄰點集合，在該集合中每個鄰點的ML列表上，僅有一個元素的取值與當(dāng)前解不同。

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

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

3.3 移動定義

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

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

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

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

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

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

當(dāng)搜索的鄰點數(shù)Num達到Numstop，Numstop在本研究中設(shè)定為[100NBT]；

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

3.5 搜索步驟

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

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

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

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

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

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

步驟7 輸出當(dāng)前最好解，即MLopt、ALopt、Πopt。

4 算法測試

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

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

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

表2 算法的測試結(jié)果

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

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

5 結(jié)論

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

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

算法的平均計算時間，隨著項目活動數(shù)的增加而增加，隨著網(wǎng)絡(luò)復(fù)雜度、資源強度或資源中斷次數(shù)的增加而減??；

滿意解平均目標(biāo)函數(shù)值，隨著項目活動數(shù)或網(wǎng)絡(luò)復(fù)雜度的增加而增加，隨著資源中斷次數(shù)的增加而減小，與資源強度無明顯關(guān)系。

[1] 龐南生,孟俊姣.多目標(biāo)資源受限項目魯棒調(diào)度研究[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] 任世科,袁治平,徐渝.突發(fā)事件應(yīng)急救援動態(tài)調(diào)度優(yōu)化: 以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

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

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

C935;F224.33

A

1007-3221(2015)06- 0044- 07

10.12005/orms.2015.0194