李 雪， 何正文， 王能民

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

0 引言

項(xiàng)目調(diào)度問(wèn)題(project scheduling problem，簡(jiǎn)稱PSP)研究從時(shí)間和資源等條件上合理安排調(diào)度項(xiàng)目的活動(dòng)，在資源最優(yōu)利用的同時(shí)實(shí)現(xiàn)既定目標(biāo)的最優(yōu)化[1]。在實(shí)際項(xiàng)目調(diào)度中，工期和成本[2]與項(xiàng)目的交付及收益息息相關(guān)，是項(xiàng)目管理者普遍關(guān)注的重要指標(biāo)，并且二者之間存在制約關(guān)系。此外，在現(xiàn)實(shí)情況中，進(jìn)度計(jì)劃常常受到一些不可控因素的干擾，如返工、機(jī)器故障等，從而導(dǎo)致項(xiàng)目無(wú)法按期交付。因此，在制定項(xiàng)目計(jì)劃階段考慮時(shí)間/費(fèi)用之間權(quán)衡的同時(shí)，將這類不確定因素納入其中是至關(guān)重要的[3]。項(xiàng)目計(jì)劃的時(shí)間、費(fèi)用和抗干擾能力在給定的資源、工期和預(yù)算等條件下是相互關(guān)聯(lián)、相互影響的，單一指標(biāo)的優(yōu)化可能會(huì)導(dǎo)致其他指標(biāo)的劣化，無(wú)法有效指導(dǎo)項(xiàng)目管理實(shí)踐。在項(xiàng)目調(diào)度中同時(shí)優(yōu)化上述三方面指標(biāo)，可以使得經(jīng)過(guò)多方權(quán)衡制定出的進(jìn)度計(jì)劃不但工期短、費(fèi)用低，還具有更強(qiáng)的抗干擾能力。

由于項(xiàng)目管理在根本上是具有多目標(biāo)屬性的，項(xiàng)目調(diào)度中多目標(biāo)權(quán)衡的相關(guān)問(wèn)題吸引了大量國(guó)內(nèi)外學(xué)者的關(guān)注。項(xiàng)目管理中，通過(guò)增加額外費(fèi)用來(lái)加速項(xiàng)目執(zhí)行過(guò)程中的某些活動(dòng)，以達(dá)到縮短項(xiàng)目工期的目的，就是項(xiàng)目調(diào)度中經(jīng)典的雙目標(biāo)問(wèn)題——時(shí)間/費(fèi)用權(quán)衡問(wèn)題(time/cost trade-off problem，簡(jiǎn)稱TCTP)。Demeulemeester和Vanhoucke[4]研究了確定性環(huán)境下的離散時(shí)間/費(fèi)用權(quán)衡問(wèn)題，并采用精確算法求解。Deckro等[5]使用非線性函數(shù)描述時(shí)間與費(fèi)用的關(guān)系，研究連續(xù)的時(shí)間/費(fèi)用權(quán)衡問(wèn)題。Erenguc等[6]研究多模式條件下的資源約束型時(shí)間/費(fèi)用權(quán)衡問(wèn)題，采用分支定界算法求解并進(jìn)行算例測(cè)試驗(yàn)證方法的有效性。Hazlr ?等[7]以最小化完工時(shí)間為目標(biāo)，使用基于分解策略的精確算法求解大型項(xiàng)目的離散時(shí)間/費(fèi)用權(quán)衡問(wèn)題。

確定性環(huán)境下的項(xiàng)目調(diào)度研究成果豐碩，近年來(lái)，不確定環(huán)境下的相關(guān)研究也得到了廣泛的探索。Van De Vonder等[8]研究了資源約束下質(zhì)量魯棒性(工期)與解的魯棒性(穩(wěn)定性)之間的權(quán)衡。其中，魯棒性是指當(dāng)系統(tǒng)存在不確定影響因素時(shí)，仍然能夠保持正常工作的特性，即系統(tǒng)所具有的抵抗不確定性干擾的能力[9]。Ke等[10]構(gòu)建了隨機(jī)環(huán)境下的時(shí)間/費(fèi)用權(quán)衡模型，運(yùn)用混合智能優(yōu)化算法求解。何正文等[11]探討了隨機(jī)活動(dòng)工期下的魯棒性最大化問(wèn)題，對(duì)比了三種啟發(fā)式算法的滿意解質(zhì)量。龐南生和孟俊姣[12]創(chuàng)建項(xiàng)目魯棒調(diào)度生成機(jī)制，構(gòu)建工期最小化和魯棒性最大化的雙目標(biāo)優(yōu)化模型，并采用啟發(fā)式算法求解。壽涌毅和王偉[13]使用遺傳算法求解活動(dòng)工期不確定的魯棒調(diào)度優(yōu)化問(wèn)題，有效應(yīng)對(duì)了活動(dòng)工期不確定所產(chǎn)生的隨機(jī)差異。何立華和孔云霄[14]考慮活動(dòng)的延期風(fēng)險(xiǎn)，構(gòu)建以加權(quán)時(shí)差最大化為目標(biāo)的魯棒優(yōu)化模型，然后使用改進(jìn)的啟發(fā)式算法求解。Herroelen和Leus[15]構(gòu)建了在特定工程環(huán)境下生成基準(zhǔn)進(jìn)度計(jì)劃的數(shù)學(xué)模型，利用期望實(shí)際進(jìn)度與計(jì)劃進(jìn)度偏差的加權(quán)和作為穩(wěn)定性的衡量指標(biāo)。此外，王杜鵑等[16]研究了單機(jī)環(huán)境下的多目標(biāo)優(yōu)化問(wèn)題，從Pareto優(yōu)化角度求解，改進(jìn)經(jīng)典的NSGA-II，提升算法求解效率。劉士新和宋健海[17]將模糊多目標(biāo)資源約束調(diào)度問(wèn)題轉(zhuǎn)化為單目標(biāo)組合優(yōu)化問(wèn)題，采用遺傳局域搜索算法求解獲得有效解集。

基于以上事實(shí)，本文研究不確定環(huán)境下基于時(shí)間、費(fèi)用及魯棒性權(quán)衡的多目標(biāo)項(xiàng)目調(diào)度優(yōu)化問(wèn)題，在可更新資源(renewable resource)的約束下，以工期、魯棒值和成本為優(yōu)化目標(biāo)確定項(xiàng)目各活動(dòng)的開(kāi)始時(shí)間，制定進(jìn)度方案。在本文的后續(xù)部分，首先界定研究問(wèn)題并定義相關(guān)變量，構(gòu)建問(wèn)題的多目標(biāo)優(yōu)化模型，將模型分解成三個(gè)子模型分析目標(biāo)間的權(quán)衡關(guān)系；然后設(shè)計(jì)非劣排序遺傳算法，提出三種針對(duì)性的優(yōu)化策略，形成優(yōu)化改進(jìn)的非劣排序遺傳算法；隨后進(jìn)行算法測(cè)試和參數(shù)的敏感性分析；接下來(lái)求解一個(gè)項(xiàng)目實(shí)例，得到非劣解集，并且變換資源組合對(duì)結(jié)果進(jìn)行敏感性分析；最后總結(jié)全文并給出研究結(jié)論。

1 模型構(gòu)建

1.1 問(wèn)題界定

本文使用AoN(activity-on-node)網(wǎng)絡(luò)G=(N,A)表示項(xiàng)目，其中N為節(jié)點(diǎn)集合，N={0,1,…,n,n+1}，A為有向弧的集合；節(jié)點(diǎn)表示活動(dòng)，有向弧表示活動(dòng)間的邏輯關(guān)系。為了表示方便，活動(dòng)0和活動(dòng)n+1均是人為添加的虛擬活動(dòng)，分別表示項(xiàng)目的開(kāi)始和結(jié)束，持續(xù)時(shí)間為零且不占用任何資源，活動(dòng)一旦開(kāi)始便立即結(jié)束。項(xiàng)目實(shí)施需要K種可更新資源，單位時(shí)間內(nèi)第k(k=1,2,…,K) 種資源的可用量為Rk。活動(dòng)i(i=0,1,…,n+1)的持續(xù)時(shí)間為di，活動(dòng)i執(zhí)行時(shí)對(duì)第k種資源的需求量為rik，活動(dòng)i延遲單位時(shí)間所造成的成本損失為wi。第k種資源在單位時(shí)間內(nèi)的單位占用成本為ck，項(xiàng)目最大工期為D。假設(shè)項(xiàng)目從零時(shí)刻開(kāi)始執(zhí)行，所有活動(dòng)不能中斷，且活動(dòng)只能在給定的資源和時(shí)間條件下進(jìn)行。

在項(xiàng)目實(shí)施過(guò)程中，項(xiàng)目工期是業(yè)主和承包商共同關(guān)心的一個(gè)重要指標(biāo)。前面定義了各個(gè)活動(dòng)的開(kāi)始時(shí)間si，以及持續(xù)時(shí)間為零的虛擬結(jié)束活動(dòng)n+1。由此，項(xiàng)目工期目標(biāo)函數(shù)可以用虛擬結(jié)束活動(dòng)的開(kāi)始時(shí)間表示，即：T=sn+1。

項(xiàng)目工期T、項(xiàng)目魯棒值Robu和項(xiàng)目成本C的表示式之間存在制約關(guān)系：Δi與項(xiàng)目工期密切相關(guān)，工期越寬松，活動(dòng)之間就可以添加更多的自由時(shí)差，Δi也就越大；與此同時(shí)，項(xiàng)目魯棒值Robu和項(xiàng)目成本C的表示式中均含有Δi，自由時(shí)差的變化直接影響魯棒值和成本。自由時(shí)差由決策變量si計(jì)算得到，決策變量發(fā)生變化時(shí)，各目標(biāo)值也隨之變化。工期較寬松時(shí)，自由時(shí)差也較大，魯棒值和成本就相對(duì)較大；而工期相對(duì)緊張時(shí)，自由時(shí)差則會(huì)較小，魯棒值和成本也相對(duì)較小。本文中，我們考慮多個(gè)目標(biāo)間的相互影響然后進(jìn)行權(quán)衡優(yōu)化，從而獲得問(wèn)題的滿意解。

綜上，本文的研究問(wèn)題可以界定為，在給定條件下確定各活動(dòng)開(kāi)始時(shí)間si，以T最小化、Robu最大化且C最小化為目標(biāo)，同時(shí)優(yōu)化項(xiàng)目的工期、魯棒值和成本三個(gè)指標(biāo)。

1.2 優(yōu)化模型

根據(jù)1.1中對(duì)研究問(wèn)題的界定，以工期最小化、魯棒值最大化、成本最小化為目標(biāo)，以資源、優(yōu)先關(guān)系為約束條件，構(gòu)建基于時(shí)間、費(fèi)用及魯棒性權(quán)衡的多目標(biāo)項(xiàng)目調(diào)度優(yōu)化模型，表述如下：

minT=sn+1

(1)

(2)

(3)

(4)

si+di≤sj,j∈Succi;i=0,1,…,n

(5)

(6)

si為非負(fù)整數(shù),i=0,1,…,n+1

(7)

其中，Vt為t時(shí)刻正在執(zhí)行的活動(dòng)的集合。

上述多目標(biāo)優(yōu)化模型中共包含三個(gè)目標(biāo)函數(shù)，兩個(gè)約束條件，活動(dòng)的開(kāi)始時(shí)間si為決策變量。目標(biāo)函數(shù)式(1)表示工期最小化，虛擬結(jié)束活動(dòng)n+1的開(kāi)始時(shí)間sn+1等于項(xiàng)目工期T。目標(biāo)函數(shù)式(2)表示魯棒值最大化，這里使用項(xiàng)目中各活動(dòng)的自由時(shí)差加權(quán)和表示整個(gè)項(xiàng)目的魯棒值。目標(biāo)函數(shù)式(3)表示成本最小化，用項(xiàng)目實(shí)施過(guò)程中所占用資源的總費(fèi)用作為項(xiàng)目成本。式(4)表示資源約束，保證項(xiàng)目執(zhí)行過(guò)程中各類資源的使用量不超過(guò)相應(yīng)資源的可用量。式(5)表示活動(dòng)間的優(yōu)先關(guān)系約束，保證當(dāng)前活動(dòng)結(jié)束后其緊后活動(dòng)再開(kāi)始執(zhí)行。式(6)是用活動(dòng)開(kāi)始時(shí)間求自由時(shí)差的計(jì)算式。式(7)則為決策變量si的定義域。在多目標(biāo)優(yōu)化模型中，確定各活動(dòng)的開(kāi)始時(shí)間si就形成一個(gè)進(jìn)度計(jì)劃方案，每一進(jìn)度計(jì)劃方案對(duì)應(yīng)確定的工期、魯棒值和成本，改變決策變量可以使得目標(biāo)函數(shù)值發(fā)生變化，然后通過(guò)目標(biāo)值的比較、權(quán)衡和選擇就可以達(dá)到多目標(biāo)優(yōu)化的目的，獲得工期短、魯棒值大且成本低的進(jìn)度方案。

1.3 基于模型分解的三目標(biāo)權(quán)衡關(guān)系分析

為了進(jìn)一步研究1.2中構(gòu)建的多目標(biāo)優(yōu)化模型，將原優(yōu)化模型分解為如下三個(gè)子模型進(jìn)行深入分析討論：工期約束下的魯棒值和成本的權(quán)衡，魯棒值約束下的工期和成本的權(quán)衡，以及成本約束下的工期和魯棒值的權(quán)衡。將原多目標(biāo)優(yōu)化模型分解為三個(gè)雙目標(biāo)子模型，目的是深入分析目標(biāo)間的權(quán)衡關(guān)系，尋找優(yōu)化多目標(biāo)問(wèn)題求解過(guò)程的有效方法。

1.3.1 工期約束下的魯棒值和成本的權(quán)衡

將多目標(biāo)項(xiàng)目調(diào)度優(yōu)化模型中的工期函數(shù)轉(zhuǎn)化為約束條件，就形成了工期約束下的魯棒值和成本的權(quán)衡子模型，表述如下:

其中D*表示給定的最大工期。

該子模型中已將工期函數(shù)轉(zhuǎn)化為不等式作為約束條件，在給定的工期約束下對(duì)魯棒值和成本進(jìn)行權(quán)衡優(yōu)化。觀察子模型中的兩個(gè)目標(biāo)函數(shù)可以發(fā)現(xiàn)，魯棒值和成本中都包含以開(kāi)始時(shí)間si計(jì)算得到的自由時(shí)差Δi，改變決策變量能夠使得活動(dòng)的自由時(shí)差Δi發(fā)生變化。保持式(3)的成本值不增加，在權(quán)衡過(guò)程中，最大化魯棒值就是尋找CIWi和Δi的最佳搭配，也就是將自由時(shí)差優(yōu)先分配給CIW值大的活動(dòng)以增加項(xiàng)目整體的魯棒性。但是當(dāng)改變CIWi和Δi的搭配已經(jīng)無(wú)法得到更大的魯棒值時(shí)，就需要增加Δi來(lái)進(jìn)一步增大魯棒值，而觀察成本目標(biāo)函數(shù)可以發(fā)現(xiàn)，此時(shí)的成本必然會(huì)隨之增加。也就是說(shuō)，在一定限度內(nèi)，權(quán)衡可以在保持成本值不劣化的情況下優(yōu)化魯棒值，但是超過(guò)限度后提高魯棒值會(huì)使得成本上升，權(quán)衡就要在魯棒值和成本之間進(jìn)行取舍。保持式(2)的魯棒值不降低，最小化成本就是尋找(ck×rik)和(di+Δi)的最佳搭配，也就是將自由時(shí)差優(yōu)先分配給占用資源成本小的活動(dòng)，從而降低項(xiàng)目成本。同樣地，當(dāng)二者搭配無(wú)法得到更低的成本時(shí)，就需要降低以減小成本，但是同時(shí)會(huì)導(dǎo)致魯棒值的降低，過(guò)度的縮減成本是要以降低魯棒值為代價(jià)的，此時(shí)的權(quán)衡需要在魯棒值和成本之間進(jìn)行取舍。

從上述分析可以發(fā)現(xiàn)，魯棒值和成本兩個(gè)目標(biāo)的優(yōu)化需要進(jìn)行權(quán)衡取舍：在一定范圍內(nèi)，提高項(xiàng)目魯棒值會(huì)造成成本的上升，降低項(xiàng)目成本會(huì)導(dǎo)致魯棒值的降低。在決策變量變化的過(guò)程中，尋找兩目標(biāo)值的均衡點(diǎn)，可以達(dá)到對(duì)二者的權(quán)衡優(yōu)化。

1.3.2 魯棒值約束下的工期和成本的權(quán)衡

在項(xiàng)目調(diào)度中，工期和成本是兩個(gè)重要的優(yōu)化目標(biāo)，時(shí)間/費(fèi)用權(quán)衡問(wèn)題優(yōu)化的目標(biāo)是實(shí)現(xiàn)二者的均衡。魯棒值約束下的工期和成本的權(quán)衡子模型表述如下：

minT=sn+1

(1)

(3)

(9)

式(4)、(5)、(6)、(7)

其中Robu*表示給定的魯棒值下界。

將原優(yōu)化模型中的魯棒值函數(shù)轉(zhuǎn)化為約束條件，就得到了如上所示的魯棒值約束下的時(shí)間/費(fèi)用權(quán)衡優(yōu)化模型。在該子模型中，同時(shí)最小化工期和成本兩個(gè)目標(biāo)，進(jìn)行時(shí)間/費(fèi)用的權(quán)衡。模型中，工期T與自由時(shí)差Δi直接相關(guān)，工期較大時(shí)，活動(dòng)之間的空余時(shí)間會(huì)增加，自由時(shí)差Δi也更大，資源占用量增多從而使得成本增加，反之工期較小時(shí)則成本降低。由以上分析可見(jiàn)，工期和成本是同增同降的關(guān)系，該子問(wèn)題優(yōu)化的目標(biāo)是在滿足約束條件的基礎(chǔ)上實(shí)現(xiàn)二者的共同優(yōu)化。

1.3.3 成本約束下的工期和魯棒值的權(quán)衡

將原優(yōu)化模型中的成本函數(shù)作為約束條件，就可以得到成本約束下的工期和魯棒值的權(quán)衡子模型，表述如下:

minT=sn+1

(1)

(2)

(10)

式(4)、(5)、(6)、(7)

其中C*表示給定的成本值上界。

該子模型是在滿足成本約束的條件下，最小化項(xiàng)目工期、最大化項(xiàng)目魯棒值。保持式(1)的工期不增大，在權(quán)衡過(guò)程中，尋找CIWi和Δi的最佳搭配以增加項(xiàng)目整體的魯棒性。但是當(dāng)改變CIWi和Δi的搭配無(wú)法再得到更大的魯棒值時(shí)，就需要增加Δi來(lái)增大魯棒值，這時(shí)會(huì)導(dǎo)致項(xiàng)目工期延長(zhǎng)，權(quán)衡需要在工期和魯棒值之間進(jìn)行取舍。也就是說(shuō)，在一定限度內(nèi)，可以在保持工期不延長(zhǎng)的情況下優(yōu)化魯棒值，但是超過(guò)限度后提高魯棒值會(huì)使得工期延長(zhǎng)。再者，工期較寬松時(shí)，有利于更好地安排自由時(shí)差，使項(xiàng)目具有更大的魯棒值。由此可知，工期目標(biāo)和魯棒值目標(biāo)在權(quán)衡過(guò)程中同樣需要取舍，在決策變量變化過(guò)程中尋找二者的均衡點(diǎn)，可以實(shí)現(xiàn)工期和魯棒值的權(quán)衡優(yōu)化。

這里我們將多目標(biāo)優(yōu)化模型分解為三個(gè)雙目標(biāo)子模型，分別分析了三個(gè)目標(biāo)間的權(quán)衡關(guān)系?；谝陨戏治鼋Y(jié)果，進(jìn)行多目標(biāo)優(yōu)化時(shí)將問(wèn)題轉(zhuǎn)化為三個(gè)子模型，分別進(jìn)行優(yōu)化獲得結(jié)果后反饋給多目標(biāo)模型，有助于加快算法的收斂速度、提高滿意解的生成效率。

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

在模型分析時(shí)，將多目標(biāo)優(yōu)化模型轉(zhuǎn)化為時(shí)間/費(fèi)用權(quán)衡問(wèn)題子模型，已有研究證實(shí)時(shí)間/費(fèi)用權(quán)衡問(wèn)題是一類NP-hard問(wèn)題[19]，所以本文研究的多目標(biāo)權(quán)衡優(yōu)化問(wèn)題是一個(gè)NP-hard問(wèn)題?？紤]研究問(wèn)題的這一特性，應(yīng)用智能優(yōu)化算法求解多目標(biāo)優(yōu)化模型。首先給出求解該問(wèn)題的遺傳算法流程，然后針對(duì)研究問(wèn)題設(shè)計(jì)兩種優(yōu)化策略，分別是選擇性復(fù)制時(shí)的精英保留策略以及基于子模型權(quán)衡關(guān)系的優(yōu)化策略，將兩種策略與遺傳算法有效結(jié)合，以此加速算法的收斂過(guò)程、提高運(yùn)算效率，形成優(yōu)化改進(jìn)的非劣排序遺傳算法NSGA-Ⅱ(non-dominated sorting genetic algorithm Ⅱ)。

2.1 算法流程

考慮研究問(wèn)題的特點(diǎn)，采用遺傳算法求解多目標(biāo)優(yōu)化模型，算法流程框架如圖1所示。

圖1 算法流程圖

接下來(lái)對(duì)流程圖中所示遺傳算法的關(guān)鍵環(huán)節(jié)進(jìn)行具體介紹。

1)解的表示

在算法中，一條染色體由活動(dòng)的有序列表和自由時(shí)差列表組成。活動(dòng)有序列表是對(duì)項(xiàng)目中各活動(dòng)按照優(yōu)先關(guān)系順序排列而得，使用SSGS(serial schedule generation scheme)方法可以將其轉(zhuǎn)換為一個(gè)可行的項(xiàng)目進(jìn)度計(jì)劃，同時(shí)保證活動(dòng)的排列滿足項(xiàng)目網(wǎng)絡(luò)關(guān)系。自由時(shí)差列表指出為有序列表中的哪些活動(dòng)添加自由時(shí)差以及自由時(shí)差值為多少。由此可見(jiàn)，活動(dòng)有序列表及自由時(shí)差列表共同決定項(xiàng)目各活動(dòng)的開(kāi)工時(shí)間。

2)適應(yīng)度的計(jì)算

由于研究的是多目標(biāo)問(wèn)題，無(wú)法直接將目標(biāo)函數(shù)值轉(zhuǎn)化為個(gè)體的適應(yīng)度。這里采用非劣排序方法(后文2.2將進(jìn)行詳細(xì)介紹)，判斷個(gè)體的優(yōu)劣，將當(dāng)代種群的所有個(gè)體按照優(yōu)劣依次排序，排序越靠前，適應(yīng)度也就越大，越有機(jī)會(huì)遺傳進(jìn)入下一代而被保留下來(lái)。

3)交叉操作

在交叉操作時(shí)，為了保證交叉后得到的個(gè)體仍然滿足項(xiàng)目網(wǎng)絡(luò)關(guān)系，采用一種適用于遺傳算法的MUCOX(multi-component uniform order-based crossover)交叉算子實(shí)施交叉操作。該方法主要應(yīng)用于項(xiàng)目調(diào)度問(wèn)題的相關(guān)計(jì)算中，在針對(duì)存在優(yōu)先關(guān)系約束的染色體進(jìn)行交叉操作時(shí)，會(huì)同時(shí)考慮活動(dòng)之間的優(yōu)先關(guān)系，保證交叉后的染色體滿足父代的優(yōu)先關(guān)系要求。

4)變異操作

遺傳算法的染色體包含兩組基因：活動(dòng)有序列表和活動(dòng)的自由時(shí)差列表。在交叉操作中已經(jīng)對(duì)活動(dòng)的順序進(jìn)行了調(diào)整，而且活動(dòng)的變異意味著要調(diào)整有序列表中的活動(dòng)順序，這樣容易破壞活動(dòng)間的優(yōu)先關(guān)系，失敗率較高。所以，此處對(duì)自由時(shí)差列表進(jìn)行變異操作，即隨機(jī)選取某個(gè)活動(dòng)，將其自由時(shí)差隨機(jī)增大或減小，從而獲得變異個(gè)體。

5)子代種群的生成

在生成新一代種群時(shí)，主要運(yùn)用四種操作：選擇性復(fù)制、交叉、變異以及基于子模型權(quán)衡關(guān)系的優(yōu)化操作(后文2.4將進(jìn)行詳細(xì)介紹)。以上四種操作分別形成一定數(shù)量的個(gè)體，共同形成新一代種群。

2.2 非劣排序

在求解多目標(biāo)問(wèn)題的遺傳算法中，如何計(jì)算個(gè)體的適應(yīng)度、判斷可行解的優(yōu)劣是一個(gè)難點(diǎn)，本文在計(jì)算適應(yīng)度時(shí)采用非劣排序的方法。對(duì)于隨機(jī)選取的兩個(gè)染色體，使用如下步驟判斷二者的優(yōu)劣：

步驟1比較兩個(gè)體S1和S2對(duì)應(yīng)可行解的工期、魯棒值和成本，工期短、 魯棒值大、成本低的個(gè)體更為優(yōu)秀。若個(gè)體S1(或個(gè)體S2)的工期短、魯棒值大而且成本低(至少有一個(gè)目標(biāo)函數(shù)值不相等)，則個(gè)體S1(或個(gè)體S2)支配個(gè)體S2(或個(gè)體S1)，個(gè)體S1(或個(gè)體S2)排序在前。其他情況則轉(zhuǎn)步驟2。

步驟2當(dāng)比較三個(gè)目標(biāo)函數(shù)值無(wú)法判斷兩個(gè)體的優(yōu)劣時(shí)，即個(gè)體S1(或個(gè)體S2)既有目標(biāo)函數(shù)值優(yōu)于個(gè)體S2(或個(gè)體S1)又有目標(biāo)函數(shù)值劣于個(gè)體S2(或個(gè)體S1)，兩個(gè)個(gè)體不存在支配關(guān)系。這時(shí)采用比較擁擠度的方法進(jìn)行選優(yōu)排序。首先對(duì)種群中的個(gè)體按照三個(gè)目標(biāo)值分別進(jìn)行排序，每個(gè)個(gè)體的單一目標(biāo)值的擁擠度就可以表示為與其排序相鄰的兩個(gè)個(gè)體相應(yīng)目標(biāo)值之差，再將三個(gè)目標(biāo)值的擁擠度經(jīng)過(guò)歸一化處理累加起來(lái)就得到了該個(gè)體的擁擠度。擁擠度大的個(gè)體，周圍個(gè)體分布較為稀疏，為了增加種群的多樣性，這里約定擁擠度越大，個(gè)體越優(yōu)秀。通過(guò)比較兩個(gè)體的擁擠度可以判斷不存在支配關(guān)系的個(gè)體S1和S2的優(yōu)劣，擁擠度大的個(gè)體排序在前。

為了進(jìn)一步說(shuō)明非劣排序的方法，表1給出了一個(gè)含有五個(gè)個(gè)體的種群。在對(duì)個(gè)體S1和S2排序時(shí)，首先對(duì)比二者的三個(gè)目標(biāo)值。相對(duì)于個(gè)體S2，個(gè)體S1的工期短、魯棒值大而且成本低，由此可以判斷出個(gè)體S1支配個(gè)體S2，個(gè)體S1排序位于個(gè)體S2之前。在對(duì)個(gè)體S1和S3排序時(shí)，同樣先對(duì)比二者的三個(gè)目標(biāo)值，發(fā)現(xiàn)相對(duì)于個(gè)體S3，個(gè)體S1的工期雖然短，但是魯棒值小而且成本高，二者不存在支配關(guān)系，無(wú)法直接判斷優(yōu)劣，需要計(jì)算兩個(gè)體的擁擠度。使用步驟2中的方法計(jì)算可以得到個(gè)體S1和個(gè)體S3的擁擠度分別為1.475(30/50+400/800+3000/8000)、1.275(20/50+400/800+3000/8000)，個(gè)體S1的擁擠度更大，排序位于個(gè)體S3之前。

表1 非劣排序示例

2.3 精英保留策略

在進(jìn)行選擇性復(fù)制操作時(shí)，采用精英保留策略。已有模擬計(jì)算說(shuō)明了如果將種群個(gè)體全部替換會(huì)使得當(dāng)前最優(yōu)解發(fā)生遺失，所以應(yīng)該強(qiáng)制當(dāng)前最優(yōu)解遺傳到下一代。具體操作步驟如下：

步驟1計(jì)算當(dāng)代種群個(gè)體的工期、魯棒值和成本，然后依據(jù)2.2中的非劣排序方法確定支配關(guān)系、計(jì)算擁擠度，判斷個(gè)體間的優(yōu)劣并進(jìn)行排序。

步驟2按照步驟1中的優(yōu)劣次序，選擇種群中排序靠前的部分個(gè)體作為“精英”直接進(jìn)入下一代。

采用精英保留策略使得當(dāng)代種群中的優(yōu)良個(gè)體直接遺傳進(jìn)入下一代，可以保證在每代之間最優(yōu)秀的個(gè)體都可以被保留下來(lái)，確保遺傳算法隨著遺傳代數(shù)的增加會(huì)一直收斂逐漸靠近最優(yōu)解。

2.4 基于子模型權(quán)衡關(guān)系的優(yōu)化策略

在完成選擇性復(fù)制、交叉和變異等操作后，為了進(jìn)一步優(yōu)化求解過(guò)程，采用基于子模型權(quán)衡關(guān)系的優(yōu)化操作。在子模型權(quán)衡關(guān)系的分析過(guò)程中，將多目標(biāo)調(diào)度優(yōu)化模型分解成了三個(gè)子模型。這里給出基于子模型權(quán)衡關(guān)系進(jìn)行優(yōu)化的步驟：

步驟1計(jì)算當(dāng)代所有個(gè)體的工期、魯棒值和成本。

步驟2對(duì)于工期最小的個(gè)體，將當(dāng)前工期值作為上界，使用1.3.1中給出的子模型進(jìn)行魯棒值和成本的權(quán)衡優(yōu)化，然后將優(yōu)化后的個(gè)體放入子代種群中。

步驟3對(duì)于魯棒值最大的個(gè)體，將當(dāng)前魯棒值作為下界，使用1.3.2中給出的子模型進(jìn)行工期和成本的雙目標(biāo)優(yōu)化，然后將優(yōu)化后的個(gè)體放入子代種群中。

步驟4對(duì)于成本最低的個(gè)體，將當(dāng)前成本值作為上界，使用1.3.3中給出的模型進(jìn)行工期和魯棒值的權(quán)衡優(yōu)化，然后將優(yōu)化后的個(gè)體放入子代種群中。

基于子模型權(quán)衡關(guān)系的優(yōu)化策略在遺傳算法中用于生成子代個(gè)體，即在算法流程中變異操作之后進(jìn)行，生成一定數(shù)量的子模型優(yōu)化個(gè)體放入子代、作為子代種群的一部分。

3 算法測(cè)試

為了驗(yàn)證本文所采用的精英保留策略和基于子模型權(quán)衡關(guān)系的優(yōu)化策略對(duì)于算法性能的改善效果，設(shè)計(jì)三個(gè)版本的算法進(jìn)行測(cè)試，分別是非劣排序遺傳算法NSGA-Ⅱ，基于子模型優(yōu)化策略的NSGA-Ⅱ，基于子模型優(yōu)化策略、無(wú)精英保留策略的NSGA-Ⅱ，將三個(gè)版本的算法分別記為V1、V2和V3。在測(cè)試中，為了使算法具有同樣的比較基準(zhǔn)，為三個(gè)算法設(shè)置相同的終止條件。每個(gè)版本算法運(yùn)行到指定迭代次數(shù)Itermax時(shí)終止，輸出當(dāng)前的非劣解集。

在生成算例時(shí)，按照表2設(shè)置參數(shù)，并采用ProGen[20]生成標(biāo)準(zhǔn)算例。表中“算例的非虛活動(dòng)數(shù)N”、“項(xiàng)目截止日期D”和“資源可用量Rk”是要進(jìn)行全因素試驗(yàn)的關(guān)鍵參數(shù)，將其設(shè)定幾個(gè)水平以分析參數(shù)變化時(shí)對(duì)計(jì)算結(jié)果的影響。參數(shù)N有4個(gè)水平，參數(shù)D和Rk分別有3個(gè)水平，每種組合下生成10個(gè)算例，共獲得10×4×3×3=360個(gè)算例。表2中其它參數(shù)按照項(xiàng)目調(diào)度構(gòu)造慣例設(shè)定。

表2 ProGen的參數(shù)設(shè)置

對(duì)于算法求解得到的非劣解集所形成的近似Pareto前沿，可以通過(guò)計(jì)算其收斂度指標(biāo)和分布性指標(biāo)判斷優(yōu)劣。為此，我們首先將NSGA-Ⅱ運(yùn)行若干代，將所有代際的非劣解集合并，保留其中的非劣解就形成了一個(gè)Pareto前沿參考解集P*。

計(jì)算第G代的收斂度值時(shí)，首先計(jì)算非劣解集中的點(diǎn)到參考解集間的歐幾里得距離:

(11)

然后分別計(jì)算第G代非劣解集中各點(diǎn)的歐幾里得距離，并取均值，再除以初始種群對(duì)應(yīng)非劣解集的歐幾里得距離均值進(jìn)行歸一化處理，以便于不同算例間的結(jié)果具有可比性。這樣就計(jì)算得到了第G代非劣解集的收斂度值。收斂度值越接近0，就代表非劣解集越接近參考解集，算法的計(jì)算效果越好。

對(duì)于分布性指標(biāo)，首先選取工期和成本組成的平面，將平面內(nèi)的可行域范圍劃分成若干個(gè)小網(wǎng)格，對(duì)于一個(gè)網(wǎng)格若有非劣解位于其中，該網(wǎng)格即被占據(jù)，否則未被占據(jù)。接下來(lái)，統(tǒng)計(jì)第G代非劣解集所占據(jù)的網(wǎng)格數(shù)，再除以參考解集所占據(jù)的網(wǎng)格數(shù)進(jìn)行歸一化處理，就獲得了第G代非劣解集的分布性值。分布性值越接近1，就表示非劣解集在近似Pareto前沿上分布越均勻，算法的計(jì)算效果越好。

為了評(píng)價(jià)算法的績(jī)效，對(duì)比不同版本算法的優(yōu)劣，定義如下三個(gè)指標(biāo)：

·AT(s)：算法的平均計(jì)算時(shí)間；

·AC：算法的平均收斂度值；

·AD：算法的平均分布性值。

算法采用VC++編譯器編程，在CPU主頻為1.6GHz、內(nèi)存為1.73GB的個(gè)人計(jì)算機(jī)上運(yùn)行。取ρD=1.8、ρk=1.0對(duì)三個(gè)版本的算法進(jìn)行測(cè)試，結(jié)果見(jiàn)表3。對(duì)比三個(gè)版本算法，從解的質(zhì)量上看，算法V2的收斂度值A(chǔ)C絕大多數(shù)都小于算法V1的收斂度值A(chǔ)C，算法V2的分布性值A(chǔ)D絕大多數(shù)都大于算法V1的分布性值A(chǔ)D，說(shuō)明基于子模型權(quán)衡關(guān)系的優(yōu)化策略可以提升算法的收斂度和近似Pareto前沿的分布效果，但在項(xiàng)目活動(dòng)較多、網(wǎng)絡(luò)較為復(fù)雜時(shí)表現(xiàn)不夠理想。算法V2的收斂度值A(chǔ)C均小于算法V1的收斂度值A(chǔ)C，算法V2的分布性值A(chǔ)D均大于算法V1的分布性值A(chǔ)D，說(shuō)明精英保留策略能夠顯著提升算法收斂度和近似Pareto前沿的分布效果。從運(yùn)算速度上看，三個(gè)版本算法的平均計(jì)算時(shí)間相差較小，說(shuō)明增加兩個(gè)策略后算法性能得到提升，運(yùn)算速度卻并未下降。

在最大截止工期取三個(gè)水平時(shí)(ρD=1.6，1.8，2.0)和資源取三個(gè)水平時(shí)(ρk=1.0，1.2，1.4)分別測(cè)試算法V2，進(jìn)行敏感性分析，結(jié)果如表4、表5所示。表中ADmin、ACmin和ARmax分別為各活動(dòng)數(shù)下算例的平均最小工期、平均最小成本和平均最大魯棒值。

表4中，在最大截止工期的三個(gè)水平下，ADmin、ACmin和ARmax無(wú)明顯差距，說(shuō)明項(xiàng)目工期、項(xiàng)目成本和項(xiàng)目魯棒值對(duì)最大截止工期不敏感。

表4 最大截止工期敏感性分析

表5 資源敏感性分析

表5中，在資源的三個(gè)水平下，ADmin隨著資源的增加而變小，而ACmin和ARmax在不同資源水平下無(wú)明顯差距，說(shuō)明項(xiàng)目工期對(duì)資源變化十分敏感，增加資源投入能夠縮短項(xiàng)目工期，但是隨著資源投入的增多，縮短工期的效果會(huì)變差。項(xiàng)目成本和項(xiàng)目魯棒值對(duì)于資源變化不敏感。

4 項(xiàng)目實(shí)例

4.1 項(xiàng)目背景及數(shù)據(jù)

LG住宅樓工程項(xiàng)目位于咸陽(yáng)市高新開(kāi)發(fā)區(qū)內(nèi)，是咸陽(yáng)力高地產(chǎn)·咸陽(yáng)中華西路城市綜合體西地塊三期建設(shè)項(xiàng)目，占地面積40余畝，建筑總面積達(dá)11萬(wàn)余平方米。項(xiàng)目合同工期為650日歷天，于2015年4月開(kāi)始建設(shè)。圖2為該項(xiàng)目的AoN網(wǎng)絡(luò)圖，共包含30個(gè)活動(dòng)，其中活動(dòng)0為虛擬初始活動(dòng)，活動(dòng)29為虛擬結(jié)束活動(dòng)。

圖2 項(xiàng)目網(wǎng)絡(luò)圖

項(xiàng)目每日可安排工作的操作工人共有355人，管理人員共有80人。各個(gè)活動(dòng)的執(zhí)行持續(xù)時(shí)間、資源需求量以及依據(jù)經(jīng)驗(yàn)確定各活動(dòng)的權(quán)重值等項(xiàng)目活動(dòng)數(shù)據(jù)見(jiàn)表6。

4.2 進(jìn)度計(jì)劃安排

表6 LG項(xiàng)目活動(dòng)數(shù)據(jù)

應(yīng)用多目標(biāo)模型和非劣排序遺傳算法求解上述實(shí)例的調(diào)度優(yōu)化問(wèn)題。將帶有兩種策略的非劣排序遺傳算法NSGA-II在CPU主頻為1.6GHz、內(nèi)存為1.73GB的個(gè)人計(jì)算機(jī)上運(yùn)行，實(shí)現(xiàn)上述算法，運(yùn)算過(guò)程中交叉概率取0.4，變異概率取0.1。根據(jù)表6輸入LG住宅樓工程項(xiàng)目活動(dòng)數(shù)據(jù)進(jìn)行求解，經(jīng)過(guò)計(jì)算獲得指定迭代次數(shù)下的非支配解集，匯總項(xiàng)目各進(jìn)度方案的工期、魯棒值和成本數(shù)據(jù)結(jié)果見(jiàn)表7。

表7中程序運(yùn)行得到了13個(gè)指定迭代次數(shù)下的非支配解。觀察表格可以發(fā)現(xiàn)，每個(gè)進(jìn)度方案所對(duì)應(yīng)的三個(gè)目標(biāo)值各有優(yōu)劣。方案3、方案13的工期最短，為423天，但是魯棒值較小；方案2的魯棒值最大，為6029，但是工期和成本都最大；方案3的成本最小，約為1004萬(wàn)元，但是魯棒值也最小。觀察可得，沒(méi)有一個(gè)進(jìn)度方案的三個(gè)目標(biāo)值都優(yōu)于(至少有一個(gè)目標(biāo)值不相等)其他方案，均為非支配解，決策者可以根據(jù)自己的需要和傾向性在非支配解中進(jìn)行權(quán)衡、決策，選擇滿足自身要求的進(jìn)度方案。

表7 進(jìn)度方案計(jì)算結(jié)果

4.3 近似帕累托前沿曲面

為了更加直觀地觀察非支配解中工期、魯棒值和成本三個(gè)目標(biāo)的權(quán)衡關(guān)系，根據(jù)表7中的數(shù)據(jù)擬合出帕累托前沿的三維曲面如圖3所示。

圖3 帕累托前沿三維曲面

圖3中標(biāo)記點(diǎn)為表7中各進(jìn)度方案所對(duì)應(yīng)的點(diǎn)，它們共同形成了近似帕累托前沿，將其擬合成三維曲面就獲得了帕累托前沿三維曲面圖。觀察圖3可以發(fā)現(xiàn)，工期、成本較小時(shí)，魯棒值也較小，當(dāng)工期、成本都較大時(shí)，魯棒值也更大。相對(duì)于三維曲面與三個(gè)坐標(biāo)平面包裹范圍內(nèi)的可行解，帕累托曲面上的解工期更小、魯棒值更大、成本更低，是更優(yōu)的解。所以，工期、魯棒值和成本的權(quán)衡優(yōu)化在帕累托曲面上進(jìn)行。

4.4 敏感性分析

在求解得到非支配解集后，為了進(jìn)一步觀察模型和算法在項(xiàng)目參數(shù)發(fā)生變化時(shí)，求解結(jié)果的相應(yīng)波動(dòng)情況，接下來(lái)變化資源組合對(duì)結(jié)果進(jìn)行敏感性分析。

在LG住宅樓工程項(xiàng)目中，考慮了操作人員和管理人員兩類可更新資源。下面，在三種資源組合情況下求解得到相應(yīng)的非支配解集。如果同時(shí)觀察三個(gè)目標(biāo)的變化情況，難于分析目標(biāo)之間的關(guān)系，為此我們分別將工期、魯棒值和成本限定在一個(gè)較小范圍內(nèi)，逐對(duì)分析各目標(biāo)對(duì)資源變化的敏感程度及其相互影響，相關(guān)數(shù)據(jù)結(jié)果如表8所示，三種情況下的敏感性分析變化曲線如圖4～6所示。

圖6 工期、魯棒值資源敏感性分析變化曲線

圖4～6中資源組合1～3的資源可用量依次增大。在進(jìn)行成本、魯棒值敏感性分析時(shí)，不同資源組合下均選取了工期在440～460天之間的非支配解，形成圖4。觀察可以發(fā)現(xiàn)，成本較大的滿意解魯棒值也較大，與1.3.1中子模型分析的結(jié)果一致。而在三種資源條件下成本和魯棒值的變化并不大，也就是說(shuō)，將工期限定在一個(gè)較小范圍內(nèi)時(shí)，成本和魯棒值對(duì)資源變化較不敏感。

在進(jìn)行成本、工期敏感性分析時(shí)，不同資源組合下均選取了魯棒值在2000～2500之間的非支配解，形成圖5。觀察可以發(fā)現(xiàn)，大部分成本較大的滿意解工期相對(duì)也較大，與1.3.2中子模型分析的結(jié)果一致。而在三種資源條件下成本和工期的變化并不大，也就是說(shuō)，將魯棒值限定在一個(gè)較小范圍內(nèi)時(shí)，成本和工期對(duì)資源變化較不敏感。

表8 資源敏感性分析數(shù)據(jù)

在進(jìn)行工期、魯棒值敏感性分析時(shí)，不同資源組合下均選取了成本在1100～1150萬(wàn)元之間的非支配解，形成圖6。觀察可以發(fā)現(xiàn)，隨著工期的增加魯棒值呈明顯上升的態(tài)勢(shì)，與1.3.3中子模型分析的結(jié)果一致。工期相同時(shí)，資源充足的條件下滿意解的魯棒值更大，也就是說(shuō)，將成本限定在一個(gè)較小范圍內(nèi)時(shí)，工期和魯棒值對(duì)資源變化較為敏感。

綜上，我們應(yīng)用多目標(biāo)模型和非劣排序遺傳算法獲得了項(xiàng)目實(shí)例的非支配解集，各滿意解對(duì)應(yīng)于不同的進(jìn)度方案，它們?cè)诠て?、魯棒值和成本三個(gè)目標(biāo)值方面各有優(yōu)劣，決策者可根據(jù)自身對(duì)各指標(biāo)的傾向性不同進(jìn)行權(quán)衡取舍，選擇工期短、魯棒性大而且成本低的進(jìn)度方案。此外，敏感性分析結(jié)果表明，充足的資源有利于縮短項(xiàng)目工期、提高項(xiàng)目魯棒值。

5 結(jié)論

本文研究了不確定環(huán)境下基于時(shí)間、費(fèi)用及魯棒性權(quán)衡的多目標(biāo)項(xiàng)目調(diào)度優(yōu)化問(wèn)題。作者首先明確了研究問(wèn)題并對(duì)相關(guān)變量進(jìn)行了定義，隨后以工期最小化、魯棒值最大化和成本最小化為目標(biāo)構(gòu)建了多目標(biāo)項(xiàng)目調(diào)度優(yōu)化模型，通過(guò)安排各活動(dòng)的開(kāi)始時(shí)間使得工期最小化、魯棒值最大化且成本最小化。在此基礎(chǔ)上，為了分析三個(gè)目標(biāo)之間的權(quán)衡關(guān)系，將其分解為三個(gè)雙目標(biāo)子模型進(jìn)行深入討論，得到目標(biāo)間的權(quán)衡優(yōu)化關(guān)系?？紤]到研究問(wèn)題的NP-hard屬性和多目標(biāo)特點(diǎn)，設(shè)計(jì)非劣排序遺傳算法求解多目標(biāo)優(yōu)化模型，使用非劣排序的方法確定個(gè)體間的優(yōu)劣，并在算法中應(yīng)用精英保留策略、基于子模型權(quán)衡關(guān)系的優(yōu)化策略，設(shè)計(jì)不同版本算法在標(biāo)準(zhǔn)算例庫(kù)上對(duì)兩個(gè)策略進(jìn)行測(cè)試，結(jié)果表明兩個(gè)策略均可以提升算法的收斂度和近似Pareto前沿的分布效果。改變算例參數(shù)，發(fā)現(xiàn)增加資源投入能夠顯著縮短項(xiàng)目工期，但是隨著資源投入的增加，縮短工期的效果會(huì)變差。最后，給出一個(gè)項(xiàng)目實(shí)例，計(jì)算得到非劣解集，擬合出近似帕累托曲面。此外，項(xiàng)目實(shí)例的資源敏感性分析進(jìn)一步驗(yàn)證了子模型分析中目標(biāo)間的權(quán)衡優(yōu)化關(guān)系：成本和魯棒值同增同減，相互制約；工期和成本同增同減，可以共同優(yōu)化；工期和魯棒值同增同減，相互制約。在制定進(jìn)度計(jì)劃時(shí)，決策者可以增加資源投入有效縮短項(xiàng)目工期、提高項(xiàng)目魯棒值。本文的研究可以為多目標(biāo)項(xiàng)目調(diào)度制定進(jìn)度計(jì)劃提供定量化決策支持。需要指出的是，本文所進(jìn)行的研究未考慮活動(dòng)的多種執(zhí)行模式，仍有待進(jìn)一步深入研究，未來(lái)可以向著多模式項(xiàng)目調(diào)度方向拓展。