馬 詠，何正文，鄭維博

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

1 引言

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

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

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

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

2 問(wèn)題界定

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

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

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

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

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

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

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

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

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

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

3 模型構(gòu)建

在對(duì)研究問(wèn)題完成界定及說(shuō)明的基礎(chǔ)上，構(gòu)建所研究問(wèn)題的優(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時(shí)刻正在進(jìn)行的活動(dòng)集合，En與Ln分別表示活動(dòng)n最早開(kāi)始時(shí)間與最晚開(kāi)始時(shí)間。

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

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

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

4.1 算法設(shè)計(jì)思路

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.2.3 禁忌對(duì)象

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

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

4.2.4 算法搜索過(guò)程

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

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

步驟2從兩個(gè)算子中隨機(jī)地選擇一個(gè)，生成一個(gè)可行鄰點(diǎn)ALneig、SLneig，計(jì)算其對(duì)應(yīng)魯棒值Robuneig。判斷生成鄰點(diǎn)的移動(dòng)是否在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)，并對(duì)解進(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è)計(jì)兩個(gè)禁忌列表TLA和TLS，分別對(duì)應(yīng)活動(dòng)次序列表AL和工期增量列表SL。在搜索過(guò)程中，禁忌列表按照“先進(jìn)先出”原則進(jìn)行管理。禁忌列表的長(zhǎng)度通過(guò)實(shí)驗(yàn)法確定。

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

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

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

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

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

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

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

4.3.3 禁忌對(duì)象

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

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

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

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

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

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

4.3.5 算法搜索過(guò)程

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

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

步驟2如果K=L(K>L),在生成一個(gè)可行鄰點(diǎn)Xneig的過(guò)程中使用改進(jìn)措施1(改進(jìn)措施2)，將Xneig輸入到內(nèi)層搜索中得到對(duì)應(yīng)的ALneig、SLneig和Robuneig。判斷生成鄰點(diǎn)Xneig的移動(dòng)是否在禁忌列表中，若是轉(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)，并對(duì)解進(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西南二期軟件開(kāi)發(fā)項(xiàng)目是SST公司為ZSY西南銷(xiāo)售分公司開(kāi)發(fā)的管理信息系統(tǒng)。該軟件開(kāi)發(fā)項(xiàng)目旨在項(xiàng)目實(shí)施前，在分析項(xiàng)目活動(dòng)開(kāi)始時(shí)間延遲所產(chǎn)生損失的基礎(chǔ)上制定出魯棒性高的項(xiàng)目進(jìn)度計(jì)劃，以保證項(xiàng)目在內(nèi)外部條件發(fā)生變化時(shí)所受的擾動(dòng)最小。項(xiàng)目從2008年6月1日開(kāi)始，計(jì)劃于2008年12月30日完工，項(xiàng)目工期為150天。

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

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

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

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

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

5.2 計(jì)算結(jié)果

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

在資源無(wú)柔性的情況下，四種人力資源都只具備一種技能，參與項(xiàng)目的有需求人員、開(kāi)發(fā)人員和實(shí)施人員，市場(chǎng)人員不會(huì)參與到項(xiàng)目中。參與項(xiàng)目的三種人力資源的技能向量分別為(1,0,0)、(0,1,0)和(0,0,1)。利用本文提出的禁忌搜索算法，可求得該項(xiàng)目的滿意進(jìn)度計(jì)劃如下：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í)際完工時(shí)間為149天，進(jìn)度計(jì)劃的魯棒值為3.76，技能分配方案為((1,0,0),(0,1,0),(0,0,1))，即由需求人員提供第一種技能L1，開(kāi)發(fā)人員提供第二種技能L2，實(shí)施人員提供第三種技能L3。

5.2.2 考慮資源柔性時(shí)的技能分配方案

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

表2 資源技能分布情況

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

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

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

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

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

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

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

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

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

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

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

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

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

根據(jù)上表中各種組合的魯棒值可知，相比資源無(wú)柔性情況下的進(jìn)度計(jì)劃而言，資源具有柔性后安排得到的進(jìn)度計(jì)劃魯棒值有了大幅提高，最大值為7.42，進(jìn)度計(jì)劃如下：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這三組組合的對(duì)比都表明市場(chǎng)人員具備技能L1較技能L3而言能給進(jìn)度計(jì)劃魯棒性帶來(lái)更大的提升；組合3、組合6和組合10中市場(chǎng)人員同時(shí)具備技能L1和技能L3，而所得滿意解的資源技能分配方案中市場(chǎng)人員都用于提供技能L1，進(jìn)一步表明市場(chǎng)人員用于提供技能L1是更好的選擇；組合7是無(wú)市場(chǎng)人員參與的情況，同組合8、組合9和組合10對(duì)比可知，市場(chǎng)人員的參與能得到一個(gè)魯棒性更大的進(jìn)度計(jì)劃。產(chǎn)生以上結(jié)果的原因是：市場(chǎng)人員的參與增加了技能的可用量，提高了活動(dòng)開(kāi)始時(shí)間調(diào)整的靈活性，總緩沖時(shí)間增加的同時(shí)能將緩沖時(shí)間更合理地進(jìn)行分配，進(jìn)而提高進(jìn)度計(jì)劃魯棒性，而在項(xiàng)目中技能L1的可用量相對(duì)技能L3是匱乏的，因此市場(chǎng)人員用于提供技能L1會(huì)給進(jìn)度計(jì)劃魯棒性帶來(lái)更大的提升。從滿意解的資源技能分配方案可知，最優(yōu)的資源技能分配情況為：需求人員、開(kāi)發(fā)人員和實(shí)施人員分別用于提供技能L1、技能L2和技能L3，市場(chǎng)人員用于提供技能L1。

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

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

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

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

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

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

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

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

6 結(jié)語(yǔ)

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