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

李佳媛， 何正文

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

?

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

李佳媛， 何正文

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

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

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

0 引言

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

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

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

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

1 問(wèn)題界定

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

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

2 模型構(gòu)建

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

(1)

(2)

(3)

(4)

(5)

(6)

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

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

3 算法設(shè)計(jì)

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

采用活動(dòng)優(yōu)先次序列表表示問(wèn)題的可行解，鄰點(diǎn)生成操作簡(jiǎn)便易行；

所有生成的鄰點(diǎn)中選擇目標(biāo)值較高的鄰點(diǎn)進(jìn)行移動(dòng)，移動(dòng)方向具有較強(qiáng)的確定性；

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

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

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

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

問(wèn)題的可行解用如下兩個(gè)列表表示：

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

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

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

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

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

3.2 鄰點(diǎn)生成機(jī)理

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

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

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

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

3.3 移動(dòng)定義

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

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

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

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

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

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

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

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

3.5 搜索步驟

步驟1 輸入初始可行解MLini、ALini，及其對(duì)應(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 從兩個(gè)算子中隨機(jī)地選擇一個(gè)，生成當(dāng)前解的鄰點(diǎn)MLnei、ALnei，對(duì)應(yīng)的目標(biāo)函數(shù)值記為Πnei。判斷生成該鄰點(diǎn)的移動(dòng)是否位于禁忌列表中，若是轉(zhuǎn)步驟4；若否轉(zhuǎn)步驟3。

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

步驟4 判斷Πnei<Πopt是否成立。若成立則激活生成該鄰點(diǎn)移動(dòng)的禁忌狀態(tài)，將當(dāng)前解及當(dāng)前最好解同時(shí)更新為鄰點(diǎn)解：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 算法測(cè)試

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

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

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

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

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

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

5 結(jié)論

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

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

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

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

[1] 龐南生,孟俊姣.多目標(biāo)資源受限項(xiàng)目魯棒調(diào)度研究[J].運(yùn)籌與管理,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)急救援動(dòng)態(tài)調(diào)度優(yōu)化: 以KX井噴事故為例[J].運(yùn)籌與管理,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

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

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

C935;F224.33

A

1007-3221(2015)06- 0044- 07

10.12005/orms.2015.0194