基于柔性資源約束的前攝性項(xiàng)目調(diào)度優(yōu)化研究

馬 詠，何正文，鄭維博

(1.西安交通大學(xué)管理學(xué)院，陜西 西安 710049；2.過程控制與效率工程教育部重點(diǎn)實(shí)驗(yàn)室(西安交通大學(xué))，陜西 西安 710049)

1 引言

現(xiàn)有的項(xiàng)目調(diào)度問題研究很多是在確定型環(huán)境下進(jìn)行的。然而現(xiàn)實(shí)中，大多數(shù)項(xiàng)目的執(zhí)行會受到不同程度不確定因素的干擾[1]，若是在制定進(jìn)度計劃的過程中不將這一特點(diǎn)進(jìn)行考慮，那么在項(xiàng)目的執(zhí)行過程中進(jìn)度計劃可能會因?yàn)槭艿讲淮_定因素的影響而需不斷的調(diào)整，使其失去有效性進(jìn)而導(dǎo)致項(xiàng)目不能順利實(shí)施[2]。而如果資源具備柔性，即資源具備活動實(shí)施所需的多種技能，則可以增加制定進(jìn)度計劃時的靈活性，進(jìn)而獲得一個魯棒性更大的進(jìn)度計劃。因此，如何利用柔性資源制定能在不確定環(huán)境中穩(wěn)定執(zhí)行的進(jìn)度計劃就顯得十分重要。

項(xiàng)目進(jìn)度計劃的魯棒性是指在內(nèi)外部環(huán)境因素干擾的情況下，進(jìn)度計劃能不受影響與保持其穩(wěn)定執(zhí)行的能力。對于處在不確定環(huán)境中的項(xiàng)目而言，魯棒性較高的進(jìn)度計劃可以幫助其抵御內(nèi)外部不確定因素帶來的擾動，確保項(xiàng)目目標(biāo)的穩(wěn)定實(shí)現(xiàn)。為了得到應(yīng)對活動工期擾動而不需要重大調(diào)整的穩(wěn)定基準(zhǔn)計劃，Herroelen和Leus[3]開發(fā)了幾種啟發(fā)式算法并對算法進(jìn)行了評價。Van de vonder等[4]研究了解魯棒性和質(zhì)量魯棒性之間的權(quán)衡關(guān)系，并對時間緩沖在項(xiàng)目中的使用方式進(jìn)行了分析。Al-Fawzan和Haouari[5]考慮了在制定進(jìn)度計劃時同時兼顧魯棒性和工期的問題。Lambrechts等[6]為生成能抵御由資源可用量變化帶來的擾動的穩(wěn)定基準(zhǔn)計劃，設(shè)計了一種禁忌搜索算法。Hazr等[7]研究了魯棒離散時間成本均衡問題，并提出了幾種度量進(jìn)度計劃魯棒性的方式。壽涌毅和王偉[8]將RCPSP(Resource Constrained Project Scheduling Problem)向不確定方向進(jìn)行了拓展，構(gòu)建了問題的魯棒優(yōu)化模型，并針對模型設(shè)計了遺傳算法。何正文等[9]對活動工期具有隨機(jī)性、以魯棒性為目標(biāo)的資源約束項(xiàng)目調(diào)度問題進(jìn)行了研究，在受到項(xiàng)目工期和可更新資源限制的情況下對活動開始時間進(jìn)行安排，以得到具有最大魯棒性的進(jìn)度計劃。崔南方等[10]對不確定環(huán)境下的Max-npv項(xiàng)目魯棒性調(diào)度問題進(jìn)行了研究。王建軍等[11]為解決并行機(jī)環(huán)境下工件加工時間可控情況中機(jī)器隨機(jī)發(fā)生故障而使初始調(diào)度方案性能下降的問題，以最小化機(jī)器故障造成的期望成本為目標(biāo)，提出了內(nèi)外兩層嵌套式魯棒調(diào)度策略。陶莎等[12]等研究了帶有不確定項(xiàng)目收益交互和資源交互作用的項(xiàng)目組合選擇問題，并構(gòu)建了魯棒性可調(diào)節(jié)的魯棒優(yōu)化模型。Chakrabortty等[13]根據(jù)不確定性的特征提出了6種啟發(fā)式方法將不確定活動工期轉(zhuǎn)化為魯棒優(yōu)化模型中確定性的約束，并對問題進(jìn)行求解。Bruni等[14]針對活動工期不確定情況下的資源約束項(xiàng)目調(diào)度問題構(gòu)建了可調(diào)整的魯棒優(yōu)化模型，并用一種分解方法求解問題。崔南方和梁洋洋[15]為構(gòu)建具有較大魯棒性的項(xiàng)目進(jìn)度計劃，將魯棒性資源分配和時間緩沖插入兩種策略進(jìn)行結(jié)合，設(shè)計了一種兩階段集成優(yōu)化算法。

在經(jīng)典的RCPSP中，一種資源被認(rèn)定為只能具備一種能力，即提供一種技能。然而在現(xiàn)實(shí)中很多情形下，一種可使用的資源往往能夠表現(xiàn)出多種能力，尤其是涉及到人力資源或工業(yè)機(jī)器人的情況。工業(yè)機(jī)器人是綜合機(jī)械、電子、控制、計算機(jī)、傳感器、人工智能等多種學(xué)科的先進(jìn)技術(shù)于一體的復(fù)雜智能機(jī)器[16]。工業(yè)機(jī)器人能夠借助編程操作來處理各種零件、材料和工具，以執(zhí)行各種任務(wù)，具有可編程的輸出能力。多技能的人員也可根據(jù)所具備的能力用于執(zhí)行不同的任務(wù)。資源柔性的增加產(chǎn)生了多技能資源約束項(xiàng)目調(diào)度問題MSRCPSP(Multi-Skill Resource Constrained Project Scheduling Problem)，目前國內(nèi)外已有學(xué)者對其進(jìn)行了研究。Li和Womer[17]考慮了多技能人力資源約束項(xiàng)目調(diào)度問題，研究在滿足工期約束的情況下最小化人力資源使用所帶來的成本。黃敏鎂和羅榮桂[18]針對柔性資源約束下的產(chǎn)品開發(fā)項(xiàng)目調(diào)度問題進(jìn)行了分析，提出改進(jìn)的遺傳算法并運(yùn)用最大流理論求解出每項(xiàng)任務(wù)的柔性資源分配方案。王一帆等[19]提出了一種兩階段優(yōu)化算法用于解決多技能人力資源約束的項(xiàng)目調(diào)度問題。Correia和Saldanha-da-Gama[20]研究了在MSRCPSP中資源固定成本和可變成本帶來的影響。Almeida等[21]提出一種基于并行調(diào)度機(jī)制的啟發(fā)式算法，通過給資源賦予權(quán)重和對活動進(jìn)行分組兩個策略將啟發(fā)式算法運(yùn)用于MSRCPSP的求解。李明和徐哲[22]考慮了項(xiàng)目多技能人力資源調(diào)度與指派問題，針對該問題提出了一種優(yōu)化方法并通過算例實(shí)驗(yàn)驗(yàn)證了方法的有效性。任逸飛和陸志強(qiáng)[23]以最小化資源投入成本為目標(biāo)，研究了大型工業(yè)品移動裝配過程中的多技能人力資源投入項(xiàng)目調(diào)度問題。陳蓉等[24]對存在人員隨機(jī)離職環(huán)境下的新產(chǎn)品研發(fā)項(xiàng)目組合多技能人員調(diào)度問題進(jìn)行了分析和研究。Myszkowski等[25]設(shè)計了一種混合微分進(jìn)化貪婪算法來求解MSRCPSP。Wang Ling和Zheng Xiaolong[26]對同時考慮工期和成本最小化的MSRCPSP進(jìn)行了研究，并提出了一種知識導(dǎo)向的多目標(biāo)果蠅優(yōu)化算法。

資源柔性的考慮使得RCPSP變得更加復(fù)雜和符合實(shí)際。與此同時，柔性資源可以實(shí)現(xiàn)資源間的相互替代，并且允許項(xiàng)目在制定進(jìn)度計劃時有更多的選擇，以此應(yīng)對由活動工期變化帶來的不確定性，提高項(xiàng)目的抗干擾能力與執(zhí)行效率?；谝陨享?xiàng)目調(diào)度理論和研究現(xiàn)狀，以及考慮不確定因素帶來的擾動終將反映在活動工期的變化上，本文研究具有隨機(jī)活動工期的柔性資源約束下的前攝性項(xiàng)目調(diào)度優(yōu)化問題，即在柔性資源及項(xiàng)目計劃工期的約束下，通過對項(xiàng)目各活動的開始時間進(jìn)行安排以得到具有最大魯棒性的進(jìn)度計劃。

2 問題界定

在本文中使用AoN(Activity-on-Node)網(wǎng)絡(luò)對項(xiàng)目進(jìn)行表示。若該項(xiàng)目有N個實(shí)活動，則在網(wǎng)絡(luò)的表述中需添加兩個虛活動：活動0和活動N+1，分別表示項(xiàng)目的開始和結(jié)束。在不確定環(huán)境中，非虛活動n(n=1,2,…,N)的工期是一個隨機(jī)變量，用μ(dn)和σ(dn)來表示其均值與標(biāo)準(zhǔn)差。虛活動0和N+1工期都為0。因?yàn)楦骰顒庸て谑遣淮_定的，所以項(xiàng)目實(shí)際工期是一個隨機(jī)變量。項(xiàng)目計劃工期D在項(xiàng)目實(shí)施的過程中可能會被突破，但在制定項(xiàng)目進(jìn)度計劃的時候必須將工期約束加以考慮及遵守。

在根據(jù)已知活動工期均值μ(dn)所制定的進(jìn)度計劃中，第n個活動的開始時間為sn。然而在進(jìn)度計劃的執(zhí)行過程中，各活動的實(shí)際工期可能會偏離均值，從而導(dǎo)致各活動不能按照所制定的進(jìn)度計劃中的開始時間實(shí)施，破壞了進(jìn)度計劃的穩(wěn)定性。對于這種情況，可采取給活動留出適當(dāng)時間緩沖的措施來減輕或吸收由于活動工期變化帶來的擾動，阻止擾動在整個進(jìn)度計劃上的傳播。因此，本文在活動n(n=1,2,…,N)的計劃完成時間后設(shè)置一定時間緩沖Bn，借此提高進(jìn)度計劃抵抗工期擾動的能力。在已知sn的前提下，Bn可按照下式計算:

Bn=minm∈Un{sm}-[sn+μ(dn)]n=1,2,…,N

其中，Un為活動n的所有緊后活動的集合。在為每個活動設(shè)置Bn的時間緩沖后，只要活動的實(shí)際工期超過該活動均值工期的幅度不大于Bn，那么活動n工期發(fā)生的變化就不會對后續(xù)進(jìn)度計劃的執(zhí)行產(chǎn)生影響，其緊后活動m也可以按照進(jìn)度計劃中的開始時間sm實(shí)施。

基于上述的討論，可以知道項(xiàng)目進(jìn)度計劃的魯棒性取決于給各活動制定的開始時間，而活動開始時間又受制于各種資源在項(xiàng)目開始前技能的選擇。因此，本文所研究的問題有兩組決策變量：

n=0,1,…,N+1;t=0,1,…,D

k=1,2,…,K;l=1,2,…,L

為了后文表達(dá)需要，進(jìn)一步定義如下兩個決策向量：

Y=(t:ynt=1,n=0,1,…,N+1)

注意，在這里需要指出的是由于資源的使用是不可分割的，當(dāng)?shù)趉種資源選擇使用第l種技能時，該資源全體都只能用于提供第l種技能。至此，本文研究的問題可以界定為：在滿足柔性資源可用量Rk以及項(xiàng)目計劃工期D約束的條件下，利用已知的資源技能選擇與活動工期參數(shù)(包括均值μ(dn)和標(biāo)準(zhǔn)差σ(dn))來確定各活動的開始時間sn，最終實(shí)現(xiàn)項(xiàng)目進(jìn)度計劃魯棒值Robu的最大化目標(biāo)。

3 模型構(gòu)建

在對研究問題完成界定及說明的基礎(chǔ)上，構(gòu)建所研究問題的優(yōu)化模型，具體表述如下：

MaxRobu

(1)

(2)

m∈Unt=0,1,…,D

(3)

(4)

(5)

l=1,2,…,LT=0,1,…,D-1

(6)

n=0,1,…,N+1;t=0,1,…,D

k=1,2,…,K;l=1,2,…,L

(7)

其中，ST為在T時刻正在進(jìn)行的活動集合，En與Ln分別表示活動n最早開始時間與最晚開始時間。

在上述的優(yōu)化模型中，式(1)為目標(biāo)函數(shù)式，要求最大化進(jìn)度計劃的魯棒值Robu；式(2)指在活動開始時間窗內(nèi)為其確定一個開始時間；式(3)為活動之間的優(yōu)先關(guān)系約束，用于保證緊后活動m的開始時間sm不能早于其緊前活動n的計劃完成時間；式(4)為計劃工期約束，即虛結(jié)束活動N+1的計劃開始時間不能超過項(xiàng)目計劃工期D；式(5)保證對于每種資源，只選擇一種技能進(jìn)行使用；式(6)為可更新資源技能約束，保證在項(xiàng)目實(shí)施過程中的任意一個時刻T，所有正在進(jìn)行的活動對第l種技能的需求總量不超過資源對該技能的總供給量；式(7)為變量的定義域約束。上述模型中，柔性資源可以通過變換技能的選擇來使技能的供應(yīng)和項(xiàng)目的需求更好的進(jìn)行匹配，使得資源能得到更好的利用，并提高制定進(jìn)度計劃時活動開始時間調(diào)整的自由度。在滿足資源和工期約束的情況下，通過對各活動開始時間的不斷調(diào)整，各活動會被分配到與其權(quán)重系數(shù)匹配的時間緩沖，進(jìn)而得到擁有最大魯棒性的進(jìn)度計劃。

4 算法設(shè)計

RCPSP已被證明為NP-hard問題[27]。本文所研究的問題為具有隨機(jī)活動工期的柔性資源約束下的前攝性項(xiàng)目調(diào)度問題，是RCPSP向不確定方向的一種擴(kuò)展。因此，本文所研究的問題也必然為一個NP-hard問題。對于NP-hard問題，因其復(fù)雜性較高和求解的難度大，在項(xiàng)目調(diào)度問題的研究中一般采用啟發(fā)式算法進(jìn)行求解，包括禁忌搜索算法[5-6,9]和遺傳算法[8,11,18,23-24,28-29]等。本文選擇使用禁忌搜索算法對問題進(jìn)行求解，具體設(shè)計如下。

4.1 算法設(shè)計思路

鑒于研究問題的特性，算法總體分為內(nèi)外兩層嵌套搜索。外層搜索是對資源技能分配方案的滿意解搜索，內(nèi)層搜索是在給定的資源技能分配方案前提下對于項(xiàng)目進(jìn)度計劃滿意解的搜索。對于每種資源技能分配方案，運(yùn)用禁忌搜索算法求得相應(yīng)的進(jìn)度計劃滿意解，然后繼續(xù)進(jìn)行資源技能分配方案的禁忌搜索迭代，兩者交互進(jìn)行，直到達(dá)到算法的終止條件，最終目的是為了尋找到使目標(biāo)函數(shù)值最優(yōu)的資源技能分配方案與項(xiàng)目進(jìn)度計劃的滿意組合。

內(nèi)外兩層搜索的具體執(zhí)行步驟如圖1和圖2所示，其中AL為活動優(yōu)先次序列表，SL為工期增量列表。

圖2 內(nèi)層搜索流程圖

4.2 內(nèi)層搜索算法設(shè)計

在給定資源技能分配方案的情況下，所研究的問題轉(zhuǎn)化成資源約束項(xiàng)目調(diào)度問題。設(shè)計禁忌搜索啟發(fā)式算法對其進(jìn)行求解。

4.2.1 解的表示及初始可行解構(gòu)造

解的表示:內(nèi)層搜索是對活動開始時間安排滿意解的搜索?；顒娱_始時間安排若直接使用活動開始時間進(jìn)行解的表示，需要多次進(jìn)行活動優(yōu)先關(guān)系與資源技能關(guān)系的判斷，增加了計算的復(fù)雜性。因此，在本研究中，用具有滿足活動優(yōu)先關(guān)系的活動次序列表AL與活動工期增量列表SL結(jié)合來表示解。

活動次序列表AL：該列表{p0,p1,…,pN+1}由N個實(shí)活動和兩個虛活動的序號組成。在制定進(jìn)度計劃時，活動被安排的先后次序取決于該活動對應(yīng)序號在列表中的位置。這里需要注意的是pi所對應(yīng)的活動可能不是活動i，列表中的活動只需滿足優(yōu)先關(guān)系即可。

活動工期增量列表SL：該列表{w0,w1,…,wN+1}由N+2個值組成，每個值表示所對應(yīng)活動添加的工期增量。與活動次序列表不同的是，在該列表中值wi對應(yīng)活動i。

基于已知的AL和SL組合，生成進(jìn)度計劃的具體過程如下：首先，在SL定義的基礎(chǔ)上，令μ(di)′=μ(di)+wi，將μ(di)′作為活動i新的工期；其次，按照AL中所定義的活動優(yōu)先次序，基于μ(di)′利用串行進(jìn)度生成機(jī)制SSGS(serial schedule generation scheme)可以將一個活動次序列表AL轉(zhuǎn)換為一個可行的項(xiàng)目進(jìn)度計劃。

初始可行解構(gòu)造:步驟1按照活動序號從小到大的順序排列，得到一個滿足活動間優(yōu)先關(guān)系的活動次序列表ALinit。

步驟2為每個活動在指定區(qū)間內(nèi)隨機(jī)生成工期增量，并由這些工期增量構(gòu)成工期增量列表SLinit。

步驟3基于活動次序列表ALinit與工期增量列表SLinit，在滿足資源技能約束的前提下，利用串行進(jìn)度生成機(jī)制SSGS生成一個活動開始時間安排。

步驟4檢查是否滿足項(xiàng)目工期約束，如果滿足約束條件，則將該活動開始時間安排作為初始解；否則，返回步驟2并繼續(xù)生成可行活動開始時間安排的操作。

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

當(dāng)前可行解ALcurr、SLcurr的鄰點(diǎn)ALneig、SLneig可由如下算子得到：

活動交換算子：在活動優(yōu)先關(guān)系的約束下，隨機(jī)選擇ALcurr上的兩個活動并交換活動位置，得到一個新的活動次序列表ALneig。將SLcurr直接記為SLneig。然后基于SLneig和ALneig，利用SSGS生成新的活動開始時間安排。檢查是否滿足項(xiàng)目工期約束，如果滿足約束條件，則將SLneig和ALneig作為一可行鄰點(diǎn)；否則，重新開始生成可行鄰點(diǎn)的操作。

工期增量算子：將ALcurr直接記為ALneig。在SLcurr中，隨機(jī)選擇一個活動的工期增量，將該值隨機(jī)地變化一個單位，得到一個新的工期增量列表SLneig。然后基于ALneig和SLneig，利用SSGS生成新的活動開始時間安排。檢查是否滿足項(xiàng)目工期約束，如果滿足約束條件，則將SLneig和ALneig作為一可行鄰點(diǎn)；否則，重新開始生成可行鄰點(diǎn)的操作。

4.2.3 禁忌對象

活動交換禁忌TLA：活動交換的禁忌表達(dá)式為(Apv,v)。其中，Apv表示pv所對應(yīng)的活動，v表示活動Apv在交換前列表中的位置。例如，活動次序列表中位置2上的活動3和位置5上的活動4進(jìn)行交換，則禁忌對象為(3,2)和(4,5)。

工期增量禁忌TLS：工期增量的禁忌表達(dá)式為(Ai,wi)。其中，Ai表示工期增量發(fā)生變化的活動i，wi表示該活動變化前的增量值。如活動3的工期增量為1，變化后為2，則在工期增量迭代中的禁忌對象為 (3,1)。

4.2.4 算法搜索過程

算法的具體搜索步驟如下：

步驟1構(gòu)造初始可行解ALinit、SLinit并計算其魯棒值Robuinit；設(shè)置算法停止條件：搜索Nummax個可行解;初始化TLA和TLS；初始化計數(shù)器Num=0；解的初始化：ALcurr=ALbest=ALinit，SLcurr=SLbest=SLinit，Robucurr=Robubest=Robuinit。

步驟2從兩個算子中隨機(jī)地選擇一個，生成一個可行鄰點(diǎn)ALneig、SLneig，計算其對應(yīng)魯棒值Robuneig。判斷生成鄰點(diǎn)的移動是否在TLA或TLS中，若在TLA或TLS中，轉(zhuǎn)步驟4；否則，轉(zhuǎn)步驟3。

步驟3 將鄰點(diǎn)解作為新的當(dāng)前解：ALcurr=ALneig，SLcurr=SLneig,Robucurr=Robuneig；令Num=Num+1，更新禁忌列表。若Robuneig>Robubest，進(jìn)一步令A(yù)Lbest=ALneig，SLbest=SLneig,Robubest=Robuneig,轉(zhuǎn)步驟5。

步驟4 若Robuneig>Robubest，激活生成該鄰點(diǎn)的禁忌狀態(tài)，并對解進(jìn)行更新：ALcurr=ALbest=ALneig，SLcurr=SLbest=SLneig，Robucurr=Robubest=Robuneig，令Num=Num+1，更新禁忌列表，轉(zhuǎn)步驟5；否則，轉(zhuǎn)步驟2。

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

步驟6輸出當(dāng)前最好解，即ALbest、SLbest和Robubest。

本文中，設(shè)計兩個禁忌列表TLA和TLS，分別對應(yīng)活動次序列表AL和工期增量列表SL。在搜索過程中，禁忌列表按照“先進(jìn)先出”原則進(jìn)行管理。禁忌列表的長度通過實(shí)驗(yàn)法確定。

4.3 外層搜索算法設(shè)計

4.3.1 解的表示及初始可行解構(gòu)造

解的表示:資源技能分配方案由所有資源的技能決策向量組成：X=(Xk;k=1,2,…K)。

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

在本文的研究中，每種資源只能選擇使用一種技能，為了滿足所有的技能需求，可用資源種類數(shù)K必須不小于項(xiàng)目所需技能種類數(shù)L。根據(jù)K與L的大小關(guān)系，鄰點(diǎn)生成方式分別如下：

K=L：隨機(jī)選擇兩種資源，對這兩種資源所選擇的技能進(jìn)行變化，得到新的資源技能分配方案，判斷所得資源技能分配方案能否生成可行進(jìn)度計劃，如能生成可行進(jìn)度計劃則得到可行鄰點(diǎn)Xneig；否則，重新開始生成可行鄰點(diǎn)的操作。

K>L：隨機(jī)選擇一種資源，對其當(dāng)前選擇的技能進(jìn)行變化，得到新的資源技能分配方案，判斷所得資源技能分配方案能否生成可行進(jìn)度計劃，如能生成可行進(jìn)度計劃則得到可行鄰點(diǎn)Xneig；否則，重新開始生成可行鄰點(diǎn)的操作。

4.3.3 禁忌對象

資源技能變換禁忌表達(dá)式為(R,La,Lb)。其中，R表示變換技能的資源，La表示變換后的技能，Lb表示變換前的技能。根據(jù)鄰點(diǎn)生成方式分為兩種情形。

K=L：對于兩種所選擇的資源1和資源2，資源1選擇的技能由技能1變?yōu)榧寄?，資源2選擇的技能由技能2變?yōu)榧寄?，則禁忌對象為(1,2,1)和(2,1,2)。

K>L：當(dāng)前技能分配方案中，資源1選擇技能2，對其選擇的技能進(jìn)行變換，變換后選擇技能3，則禁忌對象為(1,3,2)。

4.3.4 算法改進(jìn)措施

改進(jìn)措施1：當(dāng)K=L時，對生成新的資源技能分配方案過程中變化技能的兩種資源進(jìn)行以下判斷：①兩種資源是否有相同的技能數(shù)且至少有兩種相同技能。②兩種資源變化前后的兩種技能是否為雙方都具備的技能。如果滿足以上兩個條件，生成新的進(jìn)度計劃，并判斷是否滿足約束條件；否則，重新選擇兩種資源生成資源技能分配方案并繼續(xù)上述操作，直到得到可行計劃為止。

改進(jìn)措施2：當(dāng)K>L時，對生成新的資源技能分配方案過程中選擇的資源進(jìn)行以下判斷：①是否有其它資源與所選資源提供相同的技能。②該資源是否至少具備兩種技能。如果滿足以上兩個條件，生成新的進(jìn)度計劃，并判斷是否滿足約束條件；否則，重新選擇一種資源繼續(xù)上述操作，直到得到可行計劃為止。

4.3.5 算法搜索過程

算法的具體搜索步驟如下：

步驟1將初始可行解Xinit作為參數(shù)輸入到內(nèi)層搜索中，將所得到的滿意解ALbest、SLbest和Robubest作為外層搜索的ALinit、SLinit和Robuinit；設(shè)置算法停止條件：搜索Nummax個可行解;初始化禁忌列表；初始化計數(shù)器Num=0；資源技能分配方案的初始化：Xcurr=X*=Xinit；外層搜索解的初始化：AL*=ALinit，SL*=SLinit，Robu*=Robuinit。

步驟2如果K=L(K>L),在生成一個可行鄰點(diǎn)Xneig的過程中使用改進(jìn)措施1(改進(jìn)措施2)，將Xneig輸入到內(nèi)層搜索中得到對應(yīng)的ALneig、SLneig和Robuneig。判斷生成鄰點(diǎn)Xneig的移動是否在禁忌列表中，若是轉(zhuǎn)步驟4；否則，轉(zhuǎn)步驟3。

步驟3將鄰點(diǎn)解作為新的當(dāng)前解：Xcurr=Xneig；令Num=Num+1，更新禁忌列表。若Robuneig>Robu*，進(jìn)一步令A(yù)L*=ALneig，SL*=SLneig,Robu*=Robuneig,轉(zhuǎn)步驟5。

步驟4若Robuneig>Robu*，激活生成該鄰點(diǎn)的禁忌狀態(tài)，并對解進(jìn)行更新：Xcurr=X*=Xneig，AL*=ALneig，SL*=SLneig，Robu*=Robuneig，令Num=Num+1，更新禁忌列表，轉(zhuǎn)步驟5；否則，轉(zhuǎn)步驟2。

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

步驟6輸出當(dāng)前最好解，即X*、AL*、SL*和Robu*。

5 實(shí)際案例

5.1 項(xiàng)目背景與數(shù)據(jù)提煉

ZSY西南二期軟件開發(fā)項(xiàng)目是SST公司為ZSY西南銷售分公司開發(fā)的管理信息系統(tǒng)。該軟件開發(fā)項(xiàng)目旨在項(xiàng)目實(shí)施前，在分析項(xiàng)目活動開始時間延遲所產(chǎn)生損失的基礎(chǔ)上制定出魯棒性高的項(xiàng)目進(jìn)度計劃，以保證項(xiàng)目在內(nèi)外部條件發(fā)生變化時所受的擾動最小。項(xiàng)目從2008年6月1日開始，計劃于2008年12月30日完工，項(xiàng)目工期為150天。

該項(xiàng)目在實(shí)施過程中需要用到三類人力資源：需求人員、開發(fā)人員與實(shí)施人員?，F(xiàn)有的人力資源有需求人員、開發(fā)人員、實(shí)施人員以及市場人員，可用量分別為4、8、7和4。需求人員主要負(fù)責(zé)系統(tǒng)需求的調(diào)研和分析；開發(fā)人員主要負(fù)責(zé)系統(tǒng)架構(gòu)設(shè)計、組件設(shè)計以及程序的編寫和調(diào)試等；實(shí)施人員主要負(fù)責(zé)對用戶實(shí)施系統(tǒng)進(jìn)行教育以及咨詢和技術(shù)服務(wù)等。在SST公司中，各類人員分別具有多種技能。需求人員和實(shí)施人員同屬于軟件業(yè)務(wù)部，能相互承擔(dān)對方的工作。開發(fā)人員除了能完成自身工作外，還能勝任需求人員和實(shí)施人員的工作。市場人員在完成與客戶建立聯(lián)系和合同管理等本職工作后，還能協(xié)助需求人員或?qū)嵤┤藛T共同完成任務(wù)。

隨著公司業(yè)務(wù)范圍的拓寬，西安SST有限責(zé)任公司經(jīng)常會有多個項(xiàng)目同時進(jìn)行的情況發(fā)生。每多進(jìn)行一個項(xiàng)目，就要在當(dāng)前人力資源分配的基礎(chǔ)上進(jìn)行調(diào)整，這會使其他正在進(jìn)行項(xiàng)目的人力資源可用量發(fā)生變動，人力資源不足會使活動的工期變長，進(jìn)而導(dǎo)致進(jìn)度計劃頻繁的調(diào)整，活動無法按時開始和完成，甚至項(xiàng)目實(shí)際完工時間會超過項(xiàng)目截止工期，給公司帶來損失。多技能的人力資源使得不同種類資源間的相互替代成為可能，一種資源可在另一種資源短缺時派上用場。同時，具有多技能的人力資源能夠在制定進(jìn)度計劃時提供更大的靈活性，可以提高資源的利用效率和實(shí)現(xiàn)進(jìn)度計劃魯棒性最大化。

該項(xiàng)目共有33個活動組成，需3種技能。項(xiàng)目AoN網(wǎng)絡(luò)圖見圖3，其中活動0和活動32分別為虛的開始和結(jié)束活動，其余為實(shí)活動。各活動的相關(guān)參數(shù)見表1，其中各活動的標(biāo)準(zhǔn)差是根據(jù)歷史數(shù)據(jù)和實(shí)際情況估算得到的。

圖3 ZSY西南二期軟件開發(fā)項(xiàng)目網(wǎng)絡(luò)圖

表1 算例活動的相關(guān)參數(shù)

5.2 計算結(jié)果

5.2.1 不考慮資源柔性時的技能分配方案

在資源無柔性的情況下，四種人力資源都只具備一種技能，參與項(xiàng)目的有需求人員、開發(fā)人員和實(shí)施人員，市場人員不會參與到項(xiàng)目中。參與項(xiàng)目的三種人力資源的技能向量分別為(1,0,0)、(0,1,0)和(0,0,1)。利用本文提出的禁忌搜索算法，可求得該項(xiàng)目的滿意進(jìn)度計劃如下：Y=(0,0,5,6,8,41,9,14,22,38,41,43,48,53,70,53,53,110,114,77,96,101,118,91,96,103,133,70,101,121,143,146,150);Robu=3.76;X=((1,0,0),(0,1,0),(0,0,1))。

由所求得的滿意解可知，項(xiàng)目實(shí)際完工時間為149天，進(jìn)度計劃的魯棒值為3.76，技能分配方案為((1,0,0),(0,1,0),(0,0,1))，即由需求人員提供第一種技能L1，開發(fā)人員提供第二種技能L2，實(shí)施人員提供第三種技能L3。

5.2.2 考慮資源柔性時的技能分配方案

根據(jù)上文對人力資源的描述，一種人力資源可能具備多種技能，具體技能分布情況如表2所示。

表2 資源技能分布情況

由表2可知，只有開發(fā)人員具備技能L2，而技能L1和技能L3所有人力資源都具備。為了研究各種人力資源技能擁有情況對進(jìn)度計劃魯棒性的影響，可在表2的基礎(chǔ)上對資源技能分布進(jìn)行進(jìn)一步的細(xì)分。因?yàn)榧寄躄2為開發(fā)人員獨(dú)有，只能由開發(fā)人員提供技能L2，所以在進(jìn)一步分析時默認(rèn)開發(fā)人員只具備技能L2。具體細(xì)分情況如下：

1)需求人員具備技能L1和L3，實(shí)施人員具備技能L3，市場人員具備技能L1。

2)需求人員具備技能L1和L3，實(shí)施人員具備技能L3，市場人員具備技能L3。

3)需求人員具備技能L1和L3，實(shí)施人員具備技能L3，市場人員具備技能L1和L3。

4)需求人員具備技能L1，實(shí)施人員具備技能L1和L3，市場人員具備技能L1。

5)需求人員具備技能L1，實(shí)施人員具備技能L1和L3，市場人員具備技能L3。

6)需求人員具備技能L1，實(shí)施人員具備技能L1和L3，市場人員具備技能L1和L3。

7)需求人員和實(shí)施人員具備技能L1和L3，市場人員不具備上述技能。

8)需求人員和實(shí)施人員具備技能L1和L3，市場人員具備技能L1。

9)需求人員和實(shí)施人員具備技能L1和L3，市場人員具備技能L3。

10)需求人員、實(shí)施人員和市場人員都具備技能L1和L3。

上述10種組合情況對應(yīng)的資源技能向量及求得的滿意解如表3所示。

表3 各組合技能向量及滿意解

根據(jù)上表中各種組合的魯棒值可知，相比資源無柔性情況下的進(jìn)度計劃而言，資源具有柔性后安排得到的進(jìn)度計劃魯棒值有了大幅提高，最大值為7.42，進(jìn)度計劃如下：Y=(0,0,5,7,9,10,10,15,24,37,40,47,52,54,69,54,54,127,131,78,87,98,116,85,90,96,112,69,96,116,137,140,150);Robu=7.42;X=((1,0,0),(0,1,0),(0,0,1),(1,0,0))。

其中，組合1和組合2、組合4和組合5、組合8和組合9這三組組合的對比都表明市場人員具備技能L1較技能L3而言能給進(jìn)度計劃魯棒性帶來更大的提升；組合3、組合6和組合10中市場人員同時具備技能L1和技能L3，而所得滿意解的資源技能分配方案中市場人員都用于提供技能L1，進(jìn)一步表明市場人員用于提供技能L1是更好的選擇；組合7是無市場人員參與的情況，同組合8、組合9和組合10對比可知，市場人員的參與能得到一個魯棒性更大的進(jìn)度計劃。產(chǎn)生以上結(jié)果的原因是：市場人員的參與增加了技能的可用量，提高了活動開始時間調(diào)整的靈活性，總緩沖時間增加的同時能將緩沖時間更合理地進(jìn)行分配，進(jìn)而提高進(jìn)度計劃魯棒性，而在項(xiàng)目中技能L1的可用量相對技能L3是匱乏的，因此市場人員用于提供技能L1會給進(jìn)度計劃魯棒性帶來更大的提升。從滿意解的資源技能分配方案可知，最優(yōu)的資源技能分配情況為：需求人員、開發(fā)人員和實(shí)施人員分別用于提供技能L1、技能L2和技能L3，市場人員用于提供技能L1。

通過對比以上兩種情況下資源技能分配方案的結(jié)果可以知道，SST公司的市場人員具備技能L1使得ZSY西南二期軟件開發(fā)項(xiàng)目實(shí)際完工時間由149天縮短為143天，進(jìn)度計劃的魯棒值由3.76提高到7.42，增幅達(dá)97.34%。這表明在不確定環(huán)境中，資源柔性的增加能縮短項(xiàng)目工期進(jìn)而幫助項(xiàng)目制定一個魯棒性更高的進(jìn)度計劃，提高項(xiàng)目抵御不確定因素干擾的能力。

5.3 關(guān)鍵參數(shù)的敏感性分析

由本文所構(gòu)建的優(yōu)化模型可以知道，項(xiàng)目進(jìn)度計劃的魯棒性受一些關(guān)鍵參數(shù)的影響，主要有項(xiàng)目工期D、資源可用量Rk和資源柔性。在假定其它因素不變的情況下，單一因素變化對項(xiàng)目進(jìn)度計劃魯棒性的影響如圖4所示(初始資源技能分配方案為((1,0,0), (0,1,0), (0,0,1), (0,0,1)))。需要指出的是資源可用量的增加為四種資源可用量在原有基礎(chǔ)上同步增加，資源柔性的提高體現(xiàn)在四種資源具備的技能數(shù)同步增加。

圖4 進(jìn)度計劃魯棒性隨關(guān)鍵參數(shù)變化曲線

各參數(shù)的變化情況具體解釋如下:

隨著項(xiàng)目工期的延長，進(jìn)度計劃的魯棒性近似的呈線性增加。因?yàn)轫?xiàng)目工期的延長會使項(xiàng)目網(wǎng)絡(luò)中所有路徑上的時間緩沖均同步增加，進(jìn)度計劃擁有的總緩沖變大，進(jìn)而使得計劃的魯棒性提高。

隨著資源可用量的增加，進(jìn)度計劃的魯棒性雖在增加，但有減緩的趨勢。因?yàn)橘Y源可用量的增加允許活動開始時間能以更大的自由度進(jìn)行調(diào)整，總時間緩沖增加的同時能將緩沖更合理地分配在活動上，進(jìn)度計劃魯棒性提高。但當(dāng)資源可用量增加到一定程度時，受項(xiàng)目網(wǎng)絡(luò)的約束，活動開始時間調(diào)整的靈活性被限制，計劃魯棒性的上升速度減緩。

隨著資源具備的技能數(shù)越多，資源的柔性就越大，進(jìn)度計劃魯棒性也不斷增加。因?yàn)橘Y源具備柔性后有更多的技能選擇，可以根據(jù)項(xiàng)目的網(wǎng)絡(luò)結(jié)構(gòu)和活動對技能的需求量來對應(yīng)的提供技能，在提高技能利用率的同時縮短了項(xiàng)目工期，給項(xiàng)目留出了更多的緩沖時間在活動中進(jìn)行分配，進(jìn)而提高進(jìn)度計劃魯棒性。

6 結(jié)語

本文研究了具有隨機(jī)活動工期的柔性資源約束下的前攝性項(xiàng)目調(diào)度優(yōu)化問題。在文中，首先對問題進(jìn)行界定，將柔性資源定義為具備多種技能但在項(xiàng)目實(shí)施前只能選擇一種技能且不可分割使用的可更新資源，采用給活動添加時間緩沖的方式提高進(jìn)度計劃魯棒性并定義了度量進(jìn)度計劃魯棒性的方式。研究目標(biāo)是在滿足柔性資源和項(xiàng)目計劃工期約束的條件下，借助對活動開始時間合理地進(jìn)行安排進(jìn)而得到擁有最大魯棒性的進(jìn)度計劃。隨后，構(gòu)建了研究問題的優(yōu)化模型，并根據(jù)問題NP-hard屬性和模型特點(diǎn)設(shè)計了問題求解的雙層嵌套禁忌搜索啟發(fā)式算法，通過內(nèi)外兩層搜索交互迭代求得滿意解。最后通過一個實(shí)際案例對研究問題進(jìn)行了說明，并分析了項(xiàng)目工期、資源可用量、資源柔性等關(guān)鍵參數(shù)分別對項(xiàng)目進(jìn)度計劃魯棒性的影響。研究結(jié)果表明：相對于資源無柔性情況下的項(xiàng)目進(jìn)度計劃而言，資源具備柔性后安排得到的項(xiàng)目進(jìn)度計劃的魯棒性更高，提高了項(xiàng)目的抗干擾能力，保證項(xiàng)目穩(wěn)定執(zhí)行；項(xiàng)目進(jìn)度計劃魯棒性隨著項(xiàng)目工期的延長、資源可用量的增加或資源柔性的提高而上升。本文的研究將柔性資源約束項(xiàng)目調(diào)度問題向魯棒性方向進(jìn)行了擴(kuò)展，對在不確定環(huán)境中如何制定項(xiàng)目進(jìn)度計劃可給予決策支持。