李 雪何正文王能民

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

1 引 言

項(xiàng)目調(diào)度中的大量研究問(wèn)題致力于獲得一定優(yōu)化指標(biāo)下的基準(zhǔn)進(jìn)度計(jì)劃,如工期、成本、凈現(xiàn)值等優(yōu)化目標(biāo).這些研究大多假定外部環(huán)境是確定的,制定的最優(yōu)進(jìn)度計(jì)劃可以按照預(yù)期逐步執(zhí)行.但在項(xiàng)目的實(shí)際執(zhí)行過(guò)程中存在各類不確定性,比如資源短缺、機(jī)器故障、氣候惡劣、工期滯后、供貨商延遲交付等情況[1].此時(shí),原本制定的最優(yōu)進(jìn)度計(jì)劃往往是不可行的,更無(wú)法保證項(xiàng)目執(zhí)行的穩(wěn)定性.所以,為了確保項(xiàng)目順利實(shí)施,管理者希望制定具有魯棒性[2]的進(jìn)度計(jì)劃.但是提升進(jìn)度計(jì)劃魯棒性需要投入額外的資源或時(shí)間,發(fā)生魯棒性成本.因此,在構(gòu)建進(jìn)度計(jì)劃時(shí)不但需要最大化項(xiàng)目實(shí)施的魯棒性,還需要最小化魯棒性成本.本文研究如何調(diào)度項(xiàng)目的活動(dòng)制定進(jìn)度計(jì)劃,實(shí)現(xiàn)魯棒性和成本的雙目標(biāo)權(quán)衡優(yōu)化.權(quán)衡兩個(gè)目標(biāo)一方面可以增強(qiáng)進(jìn)度計(jì)劃的抗干擾能力,另一方面可以有效避免在提升進(jìn)度計(jì)劃魯棒性的過(guò)程中投入過(guò)高的成本、降低項(xiàng)目收益,最終達(dá)到以低成本穩(wěn)定實(shí)施項(xiàng)目的目的.

項(xiàng)目成本與項(xiàng)目收益直接相關(guān),是項(xiàng)目調(diào)度中重點(diǎn)關(guān)注的優(yōu)化指標(biāo).其中,確定性環(huán)境下的時(shí)間/費(fèi)用權(quán)衡問(wèn)題是項(xiàng)目調(diào)度中廣泛研究的內(nèi)容[3?5],這類問(wèn)題都假定環(huán)境是已知確定的,在項(xiàng)目實(shí)施過(guò)程中不會(huì)發(fā)生變化.項(xiàng)目進(jìn)度計(jì)劃在實(shí)際執(zhí)行過(guò)程中常常受到各類不確定因素的干擾,影響項(xiàng)目進(jìn)度計(jì)劃的執(zhí)行,使項(xiàng)目難以按期完成,增加項(xiàng)目成本、降低項(xiàng)目收益[6].因此,進(jìn)度計(jì)劃要能夠抵抗、吸收不確定因素的干擾,即具有魯棒性[7],魯棒性越大,進(jìn)度計(jì)劃在執(zhí)行過(guò)程中越有能力抵抗不確定因素的干擾.壽涌毅等[8]研究活動(dòng)工期不確定情況下的魯棒優(yōu)化問(wèn)題,張立輝等[9]將魯棒調(diào)度中的時(shí)差概念與重復(fù)性調(diào)度方法結(jié)合,提出了適用于重復(fù)性項(xiàng)目的時(shí)差概念體系.王昱等[10]應(yīng)用魯棒優(yōu)化調(diào)度方法解決醫(yī)院手術(shù)時(shí)間不確定性的手術(shù)調(diào)度問(wèn)題,采用兩階段方法求解.黃敏等[11]研究隨機(jī)運(yùn)輸時(shí)間和成本下第四方物流的路徑魯棒優(yōu)化問(wèn)題,設(shè)計(jì)并改進(jìn)蟻群算法求解模型并驗(yàn)證算法的有效性.Lambrechts等[12]研究在隨機(jī)資源條件下獲得穩(wěn)定的基準(zhǔn)進(jìn)度方案,用基準(zhǔn)計(jì)劃與實(shí)際計(jì)劃活動(dòng)開(kāi)始的偏差加權(quán)和衡量進(jìn)度魯棒性.本文同樣是在不確定環(huán)境下進(jìn)行魯棒優(yōu)化調(diào)度,但同時(shí)優(yōu)化項(xiàng)目的魯棒性和成本是一個(gè)多目標(biāo)權(quán)衡問(wèn)題,已有不少學(xué)者針對(duì)項(xiàng)目調(diào)度領(lǐng)域內(nèi)的多目標(biāo)問(wèn)題展開(kāi)研究,主要是工期–魯棒性權(quán)衡問(wèn)題、時(shí)間/費(fèi)用權(quán)衡優(yōu)化等.Van de Vonder等[13]探討項(xiàng)目穩(wěn)定性與工期的權(quán)衡問(wèn)題,研究如何在活動(dòng)間分配緩沖時(shí)間、項(xiàng)目緩沖和接駁緩沖.李洪波等[14]設(shè)計(jì)仿真方法與非支配排序遺傳算法的混合優(yōu)化算法,求解復(fù)雜產(chǎn)品研發(fā)項(xiàng)目多目標(biāo)問(wèn)題的Pareto 最優(yōu)解,同時(shí)優(yōu)化項(xiàng)目工期和成本兩個(gè)指標(biāo).付亞平等[15]研究求解多目標(biāo)優(yōu)化問(wèn)題混合算法,分解模型為多個(gè)子問(wèn)題,獲得較好質(zhì)量和分布性的非支配解.Tabrizi等[16]提出一個(gè)魯棒混合整數(shù)規(guī)劃模型,最小化項(xiàng)目采購(gòu)成本、最大化進(jìn)度魯棒性,并采用非劣排序遺傳算法和改進(jìn)版本的多目標(biāo)差分進(jìn)化算法進(jìn)行求解.宋曉宇等[17]以最小化調(diào)度總費(fèi)用和最大化應(yīng)急點(diǎn)滿意度為目標(biāo)構(gòu)建應(yīng)急物資調(diào)度模型,然后應(yīng)用粒子群算法實(shí)現(xiàn)多目標(biāo)優(yōu)化問(wèn)題的求解.劉世新等[18]構(gòu)建模糊多目標(biāo)項(xiàng)目調(diào)度問(wèn)題,設(shè)計(jì)遺傳局域搜索算法求解生成近似有效解集,以便決策者進(jìn)行權(quán)衡選擇.在上述研究中,魯棒性和成本是項(xiàng)目調(diào)度優(yōu)化的重要指標(biāo),而且項(xiàng)目調(diào)度領(lǐng)域已有學(xué)者廣泛研究多目標(biāo)優(yōu)化問(wèn)題.在本文中,研究不確定環(huán)境下的魯棒性和成本雙目標(biāo)優(yōu)化問(wèn)題.

在上述現(xiàn)實(shí)和理論背景下,本文研究不確定環(huán)境下考慮魯棒性成本的多模式項(xiàng)目前攝性調(diào)度優(yōu)化問(wèn)題,以同時(shí)優(yōu)化項(xiàng)目魯棒性和考慮魯棒性的項(xiàng)目成本為目標(biāo)構(gòu)建優(yōu)化模型,在可更新資源和項(xiàng)目工期的約束下決策各活動(dòng)的執(zhí)行模式和開(kāi)始時(shí)間.將雙目標(biāo)模型解剖為單目標(biāo)子模型,設(shè)計(jì)迭代式遺傳算法求解,獲得魯棒性高且成本低的進(jìn)度方案Pareto解集供決策者權(quán)衡選擇.在標(biāo)準(zhǔn)算例集合上進(jìn)行算法對(duì)比測(cè)試,驗(yàn)證迭代式遺傳算法的求解效果,并進(jìn)行參數(shù)敏感性分析.論文首先界定研究問(wèn)題,構(gòu)建魯棒性和成本雙目標(biāo)優(yōu)化模型,借助算例說(shuō)明魯棒性和成本的權(quán)衡關(guān)系,通過(guò)子模型對(duì)模型深入分析,然后設(shè)計(jì)迭代式遺傳算法求解,并在隨機(jī)生成的標(biāo)準(zhǔn)算例集合上測(cè)試驗(yàn)證算法的有效性.

2 雙目標(biāo)優(yōu)化模型

2.1 問(wèn)題界定

本文研究的問(wèn)題是調(diào)度AoN(activity-on-node)網(wǎng)絡(luò)G=(N,A)中的活動(dòng)i=0,1,...,n+1,其中N和A分別代表活動(dòng)集合與活動(dòng)間優(yōu)先關(guān)系.項(xiàng)目網(wǎng)絡(luò)中的活動(dòng)從0～n+1依次排列,其中活動(dòng)0和活動(dòng)n+1均為虛擬活動(dòng),分別表示項(xiàng)目的開(kāi)始和結(jié)束,不占用時(shí)間和資源.活動(dòng)間的優(yōu)先關(guān)系保證活動(dòng)只能在其緊前活動(dòng)完成后開(kāi)始.活動(dòng)i以m= 1,2,...,Mi模式執(zhí)行時(shí)每天需要消耗rimk(k= 1,2,...,K)單位可更新資源,工期為dim.在項(xiàng)目執(zhí)行的每一階段,可更新資源k的最大可用量為Rk.活動(dòng)i發(fā)生延遲對(duì)于項(xiàng)目穩(wěn)定性影響的權(quán)重為wi,資源k的單位時(shí)間使用成本為ck,D表示項(xiàng)目的最大截止工期.ESi和LSi分別表示采用關(guān)鍵路徑法計(jì)算的活動(dòng)i最早、最晚開(kāi)始時(shí)間,St為t時(shí)刻正在執(zhí)行的活動(dòng)集合,Robu和TC 分別表示項(xiàng)目進(jìn)度的魯棒值和成本值.

用xim表示活動(dòng)i是否以模式m執(zhí)行,yit表示活動(dòng)i是否在時(shí)刻t開(kāi)始執(zhí)行,是雙目標(biāo)問(wèn)題的決策變量.確定活動(dòng)i在不同模式和不同時(shí)刻下的變量xim和yit的值,就為其安排了確定的模式和開(kāi)始時(shí)間,同時(shí),活動(dòng)的工期和結(jié)束時(shí)間也就確定了.項(xiàng)目中每個(gè)活動(dòng)都確定了執(zhí)行模式和開(kāi)始時(shí)間、結(jié)束時(shí)間,就形成了項(xiàng)目的進(jìn)度計(jì)劃方案.

在實(shí)際項(xiàng)目調(diào)度中,進(jìn)度計(jì)劃常常受到外來(lái)因素的干擾,為了增強(qiáng)項(xiàng)目魯棒性,在活動(dòng)之間應(yīng)當(dāng)留有一定的時(shí)間緩沖,增強(qiáng)進(jìn)度計(jì)劃的抗干擾能力.活動(dòng)i的緩沖時(shí)間表示在滿足資源約束的條件下,不推遲緊后活動(dòng)最早開(kāi)始時(shí)間前提下活動(dòng)i開(kāi)始時(shí)間最大變化量,表示方式如下

其中sei、sil為采用串行進(jìn)度生成方案(serial schedule generation scheme,SSGS)方法在給定各活動(dòng)的執(zhí)行模式和執(zhí)行順序時(shí)計(jì)算得到的活動(dòng)i的最早和最晚開(kāi)始時(shí)間,保證進(jìn)度方案滿足優(yōu)先關(guān)系約束、工期約束和資源約束,Lambrechts 等[12]提出該方法用于計(jì)算資源約束下的活動(dòng)緩沖時(shí)間.再者,應(yīng)用SSGS方法安排進(jìn)度計(jì)劃時(shí),會(huì)在滿足約束的條件下盡可能早地安排項(xiàng)目活動(dòng),所以有

按照進(jìn)度方案計(jì)劃,活動(dòng)i在時(shí)刻開(kāi)始執(zhí)行直到結(jié)束.活動(dòng)i實(shí)際執(zhí)行過(guò)程中,若受到不確定因素干擾,開(kāi)始時(shí)間發(fā)生延遲,在區(qū)間sei,sli內(nèi)任一時(shí)刻開(kāi)始執(zhí)行,都能夠有足量的資源保證活動(dòng)的正常執(zhí)行,而且不會(huì)推遲其緊后活動(dòng)的最早開(kāi)工時(shí)間.所以,該區(qū)間長(zhǎng)度為活動(dòng)i的緩沖時(shí)間.

由于不同活動(dòng)延遲對(duì)于進(jìn)度計(jì)劃的影響不同,為不同活動(dòng)添加緩沖時(shí)間對(duì)于進(jìn)度魯棒性提升的效果也不同.因此,需要對(duì)各活動(dòng)緩沖時(shí)間設(shè)置不同的權(quán)重.累積不穩(wěn)定性權(quán)重CIW(cumulative instability weight)計(jì)算方法如下

其中Succi?表示活動(dòng)i所有后續(xù)活動(dòng)的集合,wi為項(xiàng)目管理者依據(jù)以往經(jīng)驗(yàn)為項(xiàng)目各活動(dòng)設(shè)置的權(quán)重,權(quán)重越大,表示該活動(dòng)發(fā)生延遲時(shí)越難以調(diào)整糾正、對(duì)后續(xù)活動(dòng)的不利影響越大.CIW越大,活動(dòng)延遲對(duì)項(xiàng)目進(jìn)度的影響就越大,所以在為活動(dòng)添加相同緩沖時(shí),CIW 大的活動(dòng)可以更大幅度地提升項(xiàng)目魯棒性.

項(xiàng)目活動(dòng)緩沖時(shí)間越大,活動(dòng)執(zhí)行時(shí)越能夠抵抗不確定因素的干擾,穩(wěn)定性越強(qiáng).由此,采用項(xiàng)目活動(dòng)緩沖時(shí)間的加權(quán)和表示項(xiàng)目魯棒值

項(xiàng)目魯棒值越大,項(xiàng)目活動(dòng)總體抵抗不確定因素干擾的能力就越強(qiáng),項(xiàng)目執(zhí)行過(guò)程越穩(wěn)定,進(jìn)度計(jì)劃的魯棒性越強(qiáng).

項(xiàng)目成本包含兩部分,其一是緩沖時(shí)間內(nèi)項(xiàng)目活動(dòng)占用資源成本,其二是項(xiàng)目活動(dòng)實(shí)施時(shí)所消耗資源費(fèi)用.具體表示如下

本文的研究問(wèn)題可以界定為,在優(yōu)先關(guān)系約束、工期約束和資源約束條件下,以同時(shí)最大化項(xiàng)目魯棒值Robu、最小化項(xiàng)目成本TC 為目標(biāo)確定各變量xim、yit的值,制定魯棒性強(qiáng)且成本低的進(jìn)度計(jì)劃.

2.2 優(yōu)化模型構(gòu)建

依據(jù)問(wèn)題界定中定義的各類參數(shù)和變量,構(gòu)建魯棒性和成本多模式雙目標(biāo)權(quán)衡項(xiàng)目調(diào)度優(yōu)化模型如下,

上述各式構(gòu)建了在優(yōu)先關(guān)系約束、工期約束和資源約束的條件下,魯棒值最大化、成本最小化的多模式雙目標(biāo)項(xiàng)目調(diào)度優(yōu)化模型.式(1)為采用緩沖時(shí)間加權(quán)和表示的魯棒值,是最大化的目標(biāo).式(2)表示考慮魯棒性成本的項(xiàng)目進(jìn)度計(jì)劃各活動(dòng)占用資源的總成本最小化,是項(xiàng)目執(zhí)行過(guò)程各活動(dòng)工期和緩沖時(shí)間范圍內(nèi)所占用資源消耗成本的總和.式(3)表示項(xiàng)目中各活動(dòng)只能選取一種執(zhí)行模式,式(4)表示活動(dòng)在其時(shí)間窗內(nèi)選取一個(gè)時(shí)刻開(kāi)始執(zhí)行.式(5)為緊前緊后活動(dòng)間的優(yōu)先關(guān)系,緊后活動(dòng)的開(kāi)始時(shí)間不早于其緊前活動(dòng)的結(jié)束時(shí)間.式(6)表示項(xiàng)目的完成時(shí)間在最大截止工期之內(nèi),式(7)保證項(xiàng)目執(zhí)行過(guò)程中每一時(shí)刻各類資源使用量均不超過(guò)其可用量.式(8)為緩沖時(shí)間計(jì)算式,式(9)、式(10)為決策變量的定義及取值.

經(jīng)典的資源受限項(xiàng)目調(diào)度問(wèn)題是在確定性環(huán)境下展開(kāi)的強(qiáng)NP-hard問(wèn)題[19],在滿足優(yōu)先關(guān)系約束和資源約束的條件下,制定項(xiàng)目進(jìn)度計(jì)劃方案優(yōu)化一定的調(diào)度目標(biāo)(工期、成本、凈現(xiàn)值等).魯棒性和成本雙目標(biāo)優(yōu)化調(diào)度問(wèn)題可以看作經(jīng)典問(wèn)題的拓展,當(dāng)各活動(dòng)緩沖時(shí)間為零、且只在活動(dòng)執(zhí)行期間供給資源時(shí),雙目標(biāo)問(wèn)題即為傳統(tǒng)的成本最小化項(xiàng)目調(diào)度優(yōu)化問(wèn)題.因此,魯棒性和成本雙目標(biāo)權(quán)衡項(xiàng)目調(diào)度問(wèn)題也是強(qiáng)NP-hard問(wèn)題.

應(yīng)用上述模型,可以對(duì)魯棒性和成本進(jìn)行雙目標(biāo)權(quán)衡優(yōu)化,確定各活動(dòng)的模式和開(kāi)始時(shí)間,制定進(jìn)度計(jì)劃,優(yōu)選魯棒值大且成本低的進(jìn)度方案.

2.3 算例

下面用一個(gè)算例進(jìn)一步闡述模型中魯棒性和成本的權(quán)衡關(guān)系.算例活動(dòng)網(wǎng)絡(luò)圖如圖1所示.

圖1 算例網(wǎng)絡(luò)圖Fig.1 The network of a instance

圖1給出了活動(dòng)在不同執(zhí)行模式下所需的執(zhí)行時(shí)間、資源以及活動(dòng)權(quán)重,設(shè)單位時(shí)間資源最大可用量為8個(gè)單位,資源單位時(shí)間使用成本為1,項(xiàng)目工期為10.令虛擬開(kāi)始活動(dòng)1在零時(shí)刻開(kāi)始,虛擬結(jié)束活動(dòng)6在項(xiàng)目工期處結(jié)束.

依據(jù)網(wǎng)絡(luò)關(guān)系和活動(dòng)參數(shù),制定三個(gè)可行進(jìn)度計(jì)劃方案,圖2中各灰色矩形分別表示不同的活動(dòng),括號(hào)內(nèi)數(shù)字表示活動(dòng)所選取的執(zhí)行模式.

圖2 三個(gè)進(jìn)度計(jì)劃方案Fig.2 Three schedules

在方案1中,只有活動(dòng)3和活動(dòng)5有緩沖時(shí)間,分別為3、1,總時(shí)差為4.根據(jù)成本和魯棒值表示式計(jì)算可得,該進(jìn)度方案的成本為61、魯棒值為10.在方案2 中,各活動(dòng)的緩沖時(shí)間分別為1、3、2、2,總時(shí)差為8,進(jìn)度方案成本為80、魯棒值為24.在方案3中,活動(dòng)2、活動(dòng)3 和活動(dòng)5 的緩沖時(shí)間分別為3、2、3,總時(shí)差為8,該進(jìn)度方案成本值為80、魯棒值為28.

由算例的三個(gè)進(jìn)度方案可以看出,緩沖時(shí)間增加,需要更多的資源,會(huì)發(fā)生魯棒性成本,增加了項(xiàng)目總成本,但也會(huì)使得魯棒值得到提升.對(duì)比三個(gè)方案可知,方案2、方案3較方案1而言,魯棒值更大、消耗成本也更多.就方案2、方案3 而言,二者成本值相等,但方案3 魯棒值更大,是更優(yōu)的方案.在進(jìn)行魯棒性和成本雙目標(biāo)權(quán)衡時(shí),需要不斷剔除魯棒值小、成本大的方案(如方案2),優(yōu)選出魯棒值大、成本低的進(jìn)度方案(如方案1、方案3),供決策者根據(jù)自身偏好進(jìn)行權(quán)衡取舍.

2.4 單目標(biāo)子模型分析

為深入分析求解魯棒性和成本雙目標(biāo)優(yōu)化模型,將成本目標(biāo)轉(zhuǎn)化為約束條件,得到如下的魯棒值最大化單目標(biāo)模型

在存在預(yù)算約束的魯棒值最大化單目標(biāo)模型中,求得的最優(yōu)解Robumax(C?)必為雙目標(biāo)模型的可行解.另外,由于Robumax(C?)為在預(yù)算不超過(guò)C?時(shí)最大的魯棒值,所以在雙目標(biāo)模型的解空間中,不存在支配(Robumax(C?),C?)的解,故魯棒值最大化單目標(biāo)模型的最優(yōu)解必為雙目標(biāo)模型的Pareto解.

進(jìn)一步地,變化魯棒值最大化單目標(biāo)模型中的成本約束值C?求解多個(gè)單目標(biāo)問(wèn)題可以得到一系列雙目標(biāo)模型的Pareto解,示意圖見(jiàn)圖3.

由圖3可以看出,逐漸變換C?值,魯棒值最大化模型的解空間將會(huì)覆蓋整個(gè)雙目標(biāo)模型的解空間,相應(yīng)的最優(yōu)魯棒值與其對(duì)應(yīng)成本值形成雙目標(biāo)模型的帕累托前沿.由此,可以通過(guò)求解不同預(yù)算約束下的魯棒值最大化問(wèn)題來(lái)求解魯棒性和成本雙目標(biāo)模型的Pareto最優(yōu)前沿.

圖3 魯棒值最大化問(wèn)題解的分布示意圖Fig.3 Distribution diagram of solutions to the robustness maximization problem

變換預(yù)算值C?時(shí),首先應(yīng)當(dāng)確定其取值范圍,為此提出如下性質(zhì)并予以證明.

性質(zhì)在魯棒值最大化模型中,成本值上界為

成本值下界為

證明

首先變換成本值表示式,進(jìn)行放大,求其最大值.

成本值上界的計(jì)算式得證.

同樣變換成本值表示式,求其最小值.

由于?i0,則

成本值下界的計(jì)算式得證.上述性質(zhì)得證.

由上述性質(zhì)可知,在成本臨界值范圍內(nèi)變化C?求解魯棒值最大化子模型可獲得多個(gè)魯棒值最大化的解,同時(shí)也就得到雙目標(biāo)模型的一系列Pareto最優(yōu)解.

3 迭代式遺傳算法

由于魯棒性和成本雙目標(biāo)問(wèn)題的NP-hard屬性,本文采用啟發(fā)式算法求解.遺傳算法因其全局搜索能力強(qiáng),廣泛應(yīng)用于調(diào)度優(yōu)化相關(guān)研究中[20?25].在項(xiàng)目調(diào)度中,遺傳算法可以用于求解給定約束下的單一指標(biāo)優(yōu)化問(wèn)題.但在本文研究問(wèn)題中,由雙目標(biāo)模型轉(zhuǎn)換后得到的單目標(biāo)問(wèn)題需要不斷變換預(yù)算臨界值,在不同的約束下求解魯棒值最大化問(wèn)題,反復(fù)迭代計(jì)算得到多個(gè)魯棒值最大化的滿意解,然后剔除支配解、求解得到雙目標(biāo)問(wèn)題的Pareto 解集.基于上述模型求解需要,設(shè)計(jì)迭代式遺傳算法對(duì)預(yù)算約束下的魯棒值最大化模型進(jìn)行求解.

3.1 解的表示

采用有序活動(dòng)列表AL和模式列表ML表示進(jìn)度方案,圖4給出一個(gè)6個(gè)活動(dòng)的活動(dòng)列表和模式列表的示例圖.

圖4 解的表示示例Fig.4 An example of solution presentation

根據(jù)模式列表確定項(xiàng)目各活動(dòng)的執(zhí)行工期和所需資源量,然后應(yīng)用SSGS方法將上述活動(dòng)列表轉(zhuǎn)化為一個(gè)可行的進(jìn)度方案S={s1,s2,...,sn},以及相應(yīng)的各活動(dòng)最晚開(kāi)始時(shí)間列表

如前所述,運(yùn)用SSGS方法得到的進(jìn)度方案是在滿足各項(xiàng)約束下的各活動(dòng)的最早開(kāi)始時(shí)間.由以上兩個(gè)進(jìn)度方案開(kāi)始時(shí)間列表經(jīng)計(jì)算就可以得到各活動(dòng)的緩沖時(shí)間列表{?1,?2,...,?n},然后計(jì)算得到進(jìn)度計(jì)劃的魯棒值和成本值.

3.2 算法步驟

迭代式遺傳算法包含內(nèi)外兩層循環(huán),內(nèi)層采用遺傳算法基本操作步驟實(shí)現(xiàn)給定預(yù)算約束下魯棒值最大化單目標(biāo)子模型優(yōu)化,外層計(jì)算成本值上下界范圍,逐步變換成本臨界值并輸入到內(nèi)層,當(dāng)內(nèi)層算法計(jì)算完成后存儲(chǔ)子模型優(yōu)化最優(yōu)解,最終剔除支配解獲得最優(yōu)Pareto 解集.

迭代式遺傳算法的具體實(shí)施步驟如下.

步驟1讀入項(xiàng)目網(wǎng)絡(luò)數(shù)據(jù),包括項(xiàng)目活動(dòng)工期、優(yōu)先關(guān)系、執(zhí)行成本及資源量等.

步驟2應(yīng)用模型中的性質(zhì)計(jì)算得到成本值的上下界,將成本值下界作為初始成本臨界值應(yīng)用到內(nèi)層迭代算法中.

步驟3生成種群規(guī)模大小的初始種群,使得每個(gè)個(gè)體都滿足資源約束、優(yōu)先關(guān)系約束以及成本臨界值約束.

步驟4計(jì)算種群中個(gè)體的魯棒值目標(biāo)函數(shù),并按照魯棒值從大到小依次排序.

步驟5依據(jù)魯棒值大小復(fù)制精英個(gè)體到子代中,并進(jìn)行交叉操作和變異操作生成滿足各類約束的新個(gè)體進(jìn)入子代,形成子代種群.

步驟6判斷是否達(dá)到最大迭代次數(shù),若是,進(jìn)入下一步,否則返回步驟4.

步驟7記錄當(dāng)前最優(yōu)解的魯棒值和成本值,判斷成本臨界值是否超過(guò)成本值上界,若是,進(jìn)入下一步,否則增加成本臨界值返回步驟3.

步驟8整合所有記錄的最優(yōu)解,剔除非支配解形成Pareto解集并輸出,結(jié)束算法.

在預(yù)算值給定時(shí),魯棒值最大化單目標(biāo)問(wèn)題由內(nèi)層遺傳算法求解,它從外層獲取項(xiàng)目網(wǎng)絡(luò)數(shù)據(jù)和成本臨界值,求解預(yù)算約束下的魯棒值最優(yōu)進(jìn)度計(jì)劃,主要包含生成初始種群、個(gè)體排序、復(fù)制操作、交叉操作和變異操作五個(gè)步驟.逐個(gè)生成種群個(gè)體的活動(dòng)列表和模式列表,保留滿足工期約束和預(yù)算約束個(gè)體形成初始種群.計(jì)算魯棒值,按照魯棒值大小對(duì)種群個(gè)體排序.根據(jù)精英策略按比例復(fù)制種群中排序靠前的個(gè)體,直接進(jìn)入下一代種群.交叉操作在種群中隨機(jī)選擇父本和母本進(jìn)行活動(dòng)列表交叉(如圖5)和模式列表交叉(兩點(diǎn)交叉)操作,將新個(gè)體加入到下一代種群中.變異操作隨機(jī)選取種群中個(gè)體對(duì)活動(dòng)列表和模式列表進(jìn)行變異,變異后個(gè)體加入到下一代種群中.

圖5 交叉操作示例Fig.5 An example of the crossover operation

應(yīng)用上述五個(gè)步驟,執(zhí)行若干代,可以得到給定預(yù)算約束下的魯棒值優(yōu)化的最優(yōu)解.此外,為求解得到雙目標(biāo)模型的Pareto 最優(yōu)解集,迭代式遺傳算法還實(shí)現(xiàn)了如下功能:

1)根據(jù)2.4中的性質(zhì)方法計(jì)算成本值上界TCmax和成本值下界TCmin,確定成本臨界值變化的范圍;

2)按步長(zhǎng)變換成本臨界值,改變內(nèi)層魯棒值優(yōu)化的約束條件,得到預(yù)算約束臨界值變化的多個(gè)魯棒值優(yōu)化解;

3)執(zhí)行多個(gè)魯棒值優(yōu)化內(nèi)層算法,記錄相應(yīng)魯棒值優(yōu)化得到的滿意解,剔除支配解,得到雙目標(biāo)優(yōu)化的Pareto解集.

迭代式遺傳算法包含內(nèi)層和外層兩部分,內(nèi)層按照遺傳算法的步驟運(yùn)算獲得魯棒值最大化的最優(yōu)解,輸出給外層,外層計(jì)算出成本值的上下界,不斷變化,輸入到內(nèi)層進(jìn)行反復(fù)迭代,最終獲得魯棒性和成本雙目標(biāo)權(quán)衡的最優(yōu)Pareto解集.

4 計(jì)算實(shí)驗(yàn)

為了驗(yàn)證迭代式遺傳算法的有效性,應(yīng)用ProGen[26]在不同參數(shù)下生成的360個(gè)標(biāo)準(zhǔn)算例對(duì)算法進(jìn)行測(cè)試,對(duì)比迭代式遺傳算法與多重迭代改進(jìn)算法(Multi-Start Iteration Improvement,MSII),并將計(jì)算結(jié)果與不考慮預(yù)算約束的魯棒性最大化單目標(biāo)算法進(jìn)行比較.變化工期比例和資源比例參數(shù),進(jìn)行敏感性分析.

4.1 實(shí)驗(yàn)設(shè)計(jì)

計(jì)算實(shí)驗(yàn)將迭代式遺傳算法與多重迭代改進(jìn)算法進(jìn)行對(duì)比.多重迭代改進(jìn)算法從一個(gè)可行解出發(fā),變化活動(dòng)列表和模式列表獲得鄰點(diǎn),取當(dāng)前最優(yōu)解繼續(xù)迭代,直到達(dá)到最大迭代次數(shù)輸出最優(yōu)解.然后變換初始可行解繼續(xù)重復(fù)上述迭代步驟,得到多個(gè)最優(yōu)解形成集合,剔除支配解即得到最優(yōu)Pareto解集.

在對(duì)比兩個(gè)版本算法的求解效果時(shí),需對(duì)比算法求解得到的Pareto解集的優(yōu)劣.由于最優(yōu)Pareto 解集是未知的,這里用近優(yōu)的Pareto參考集代替.將迭代式遺傳算法運(yùn)行若干代并將代際種群結(jié)合起來(lái)形成一個(gè)群體,計(jì)算得到群體中的所有非支配解即構(gòu)成參考非支配解集.

定義如下三個(gè)參數(shù)描述算法計(jì)算得到的Pareto解集.

1)平均計(jì)算時(shí)間ACT

算法計(jì)算相同參數(shù)下10個(gè)算例的平均計(jì)算時(shí)間,表征算法在計(jì)算Pareto前沿時(shí)運(yùn)算的速度,平均計(jì)算時(shí)間越短說(shuō)明算法運(yùn)算速度越快.

2)非支配解集相對(duì)于參考非支配解集的收斂度cp

確定第g代種群P(g)中的非支配解集F(g),收斂度指標(biāo)計(jì)算方法如下(進(jìn)行歸一化處理)

其中、分別為參考解集P?中第k個(gè)目標(biāo)的最大值和最小值.

收斂度值cp越小,說(shuō)明算法計(jì)算得到的Pareto 前沿越接近參考集形成的近優(yōu)Pareto前沿,計(jì)算效果越好,反之則計(jì)算效果越差.

3)非支配解集相對(duì)于參考非支配解集的分布性dp

首先確定種群P(g)中的非支配解集F(g),將各進(jìn)度方案成本值區(qū)間范圍等分成若干個(gè)小區(qū)間,按照下式計(jì)算分布性指標(biāo),即

分布性值dp越大,說(shuō)明算法計(jì)算得到的Pareto 前沿上的點(diǎn)分布越均勻,計(jì)算效果越好,反之則計(jì)算效果越差.

應(yīng)用ProGen生成標(biāo)準(zhǔn)算例時(shí)的參數(shù)設(shè)置見(jiàn)表1,活動(dòng)網(wǎng)絡(luò)規(guī)模設(shè)置四個(gè)水平,項(xiàng)目最大截止日期和資源比例分別設(shè)置三個(gè)水平,各參數(shù)組合下分別生成10 個(gè)算例,共得到360個(gè)標(biāo)準(zhǔn)算例進(jìn)行算法測(cè)試.

表1 算例參數(shù)表Table 1 Parameters of the instances

算法采用Visual Studio 2010中的C++語(yǔ)言編程,在CPU 主頻為2.5GHz,內(nèi)存8GB的個(gè)人計(jì)算機(jī)上運(yùn)行.將種群規(guī)模設(shè)置為100,最大迭代次數(shù)為100,復(fù)制、交叉、變異比例分別為0.2、0.74 和0.06,在給定參數(shù)下運(yùn)算進(jìn)行求解.

4.2 測(cè)試結(jié)果

為驗(yàn)證迭代式遺傳算法的求解效果,設(shè)計(jì)多重迭代改進(jìn)算法進(jìn)行對(duì)比,兩個(gè)版本算法的測(cè)試結(jié)果見(jiàn)表2.

表2 算法測(cè)試結(jié)果Table 2 Test results of algorithms

從計(jì)算時(shí)間上看,多重迭代改進(jìn)算法在不同活動(dòng)數(shù)下差距較小,迭代式遺傳算法計(jì)算時(shí)間隨著活動(dòng)數(shù)增加逐漸增大.這是由于迭代式遺傳算法需要變換成本值反復(fù)執(zhí)行內(nèi)外層算法.當(dāng)活動(dòng)數(shù)逐漸增加時(shí),項(xiàng)目網(wǎng)絡(luò)變得復(fù)雜,成本上下界范圍顯著增加,內(nèi)外層算法迭代執(zhí)行的次數(shù)也驟然增加,運(yùn)算時(shí)間變長(zhǎng).

多重迭代改進(jìn)算法的收斂度在各活動(dòng)數(shù)下均較高,而迭代式遺傳算法的收斂度始終較低,算法計(jì)算得到的Pareto解集距離最優(yōu)解集更近.這是由于將雙目標(biāo)模型轉(zhuǎn)化為子模型后,相比于直接在整個(gè)解空間中搜索更為有序,效率更高,計(jì)算得到的最優(yōu)解形成的Pareto前沿距離最優(yōu)前沿更近.

就分布性而言,多重迭代改進(jìn)算法在各活動(dòng)下表現(xiàn)都較差.而迭代式遺傳算法計(jì)算效果明顯更好.這是由于魯棒值最大化子模型中的預(yù)算值在上下界范圍內(nèi)逐漸變化、反復(fù)求解,相比于雙目標(biāo)的大范圍隨機(jī)搜索更為分散且有方向性,能夠有效獲得不同預(yù)算值下的解,Pareto前沿上的點(diǎn)分布也就更為均勻.

綜上,在各活動(dòng)數(shù)下,迭代式遺傳算法相比于多重迭代改進(jìn)算法的收斂度更低、分布性更高,即計(jì)算得到的Pareto前沿更接近參考集形成的Pareto 前沿,且Pareto 前沿上的點(diǎn)分布更為均勻.所以,迭代式遺傳算法計(jì)算效果更好,將雙目標(biāo)模型轉(zhuǎn)化為魯棒值最大化子模型能夠有效求解本文的魯棒性和成本雙目標(biāo)權(quán)衡問(wèn)題的Pareto 前沿,供決策者在其上進(jìn)行魯棒值和成本的權(quán)衡,選擇魯棒性大、成本低的進(jìn)度方案.

4.3 進(jìn)度方案結(jié)果對(duì)比

為了更直觀地驗(yàn)證迭代式遺傳算法的計(jì)算效果,對(duì)比進(jìn)度方案優(yōu)劣,在不考慮成本的條件下實(shí)現(xiàn)魯棒值最大化單目標(biāo)算法,并計(jì)算得到相應(yīng)進(jìn)度計(jì)劃的成本值,將其與Pareto前沿上魯棒值最大的進(jìn)度計(jì)劃進(jìn)行對(duì)比,結(jié)果如表3.表中分別給出了兩種算法計(jì)算得到的魯棒值最大化進(jìn)度計(jì)劃的魯棒值和成本值,以及魯棒值最大化算法計(jì)算得到的魯棒值、成本相對(duì)于迭代式遺傳算法的增量.

表3中,在各活動(dòng)數(shù)下,應(yīng)用迭代式遺傳算法得到最大魯棒值與魯棒值最大化算法計(jì)算得到的最優(yōu)解十分接近.在魯棒值總體差別不大的情況下,各活動(dòng)數(shù)下迭代式遺傳算法計(jì)算得到的進(jìn)度方案成本值更小.這是因?yàn)槲覀冊(cè)谀Ｐ椭锌紤]了魯棒性成本,進(jìn)行魯棒值和成本的雙目標(biāo)權(quán)衡,有效選擇出魯棒值大、成本小的進(jìn)度方案.也就是說(shuō),迭代式遺傳算法可以計(jì)算得到更低成本的進(jìn)度計(jì)劃,在保證項(xiàng)目進(jìn)度計(jì)劃魯棒性的同時(shí)降低了項(xiàng)目成本,得到了更優(yōu)的進(jìn)度方案.

表3 魯棒值最大化對(duì)比結(jié)果Table 3 Comparable results of robustness maximization

4.4 敏感性分析

為分析項(xiàng)目最大截止日期和資源可用量對(duì)項(xiàng)目魯棒值和成本的影響,保持其他參數(shù)不變,分別變化工期比例ρD和資源比例pk,運(yùn)行迭代式遺傳算法求解相應(yīng)魯棒值和成本值,計(jì)算結(jié)果如表4.

表4 敏感性分析結(jié)果Table 4 Results of sensitivity analysis

根據(jù)表4分別繪制魯棒值、成本隨工期比例和資源比例變化趨勢(shì)圖,如圖6～圖9所示.觀察圖6,在不同活動(dòng)數(shù)下,平均成本都隨著工期比例的增大而增大,工期延長(zhǎng)使得項(xiàng)目占用資源的總時(shí)間變長(zhǎng)從而造成成本增加.圖7顯示工期延長(zhǎng)后,平均魯棒值幾乎不發(fā)生變化,說(shuō)明當(dāng)前資源已被充分利用,即使增加項(xiàng)目工期也沒(méi)有多余資源可以為活動(dòng)添加有效的緩沖時(shí)間,無(wú)法提升項(xiàng)目魯棒值.由此說(shuō)明,在資源已經(jīng)得到充分利用時(shí),增大項(xiàng)目最大截止工期非但不能有效提升項(xiàng)目魯棒值,反而會(huì)顯著增加項(xiàng)目成本,這對(duì)管理者而言是一種得不償失的舉措,特別是活動(dòng)繁多的復(fù)雜項(xiàng)目,為防止成本過(guò)度消耗要注意避免增加工期比例參數(shù).

圖6 工期比例對(duì)成本的影響Fig.6 The impact of the duration ratio on the cost

圖7 工期比例對(duì)魯棒值的影響Fig.7 The impact of the duration ratio on the robustness

觀察圖8、圖9,當(dāng)資源比例逐漸增大時(shí),在各活動(dòng)數(shù)下平均成本均明顯增大,但是平均魯棒值卻無(wú)明顯變化,即在當(dāng)前參數(shù)條件下,增加資源投入會(huì)使得項(xiàng)目成本增加,對(duì)魯棒值無(wú)明顯影響.資源已經(jīng)十分充足,再增加額外的資源只會(huì)增加成本,對(duì)魯棒性提升也毫無(wú)用處,這也是管理者應(yīng)當(dāng)避免的舉措.

圖8 資源比例對(duì)成本的影響Fig.8 The impact of the resource ratio on the cost

圖9 資源比例對(duì)魯棒值的影響Fig.9 The impact of the resource ratio on the robustness

5 結(jié)束語(yǔ)

本文從項(xiàng)目調(diào)度現(xiàn)實(shí)情況出發(fā),在不確定環(huán)境下進(jìn)行魯棒性和成本的雙目標(biāo)權(quán)衡.構(gòu)建魯棒性和成本雙目標(biāo)優(yōu)化模型,最大化項(xiàng)目魯棒值的同時(shí)最小化項(xiàng)目成本,將雙目標(biāo)模型轉(zhuǎn)換為預(yù)算約束下的魯棒值最大化子模型,并提出性質(zhì)求解成本值上界和下界.考慮到問(wèn)題的NP-hard屬性,設(shè)計(jì)了迭代式遺傳算法,并將計(jì)算成本值上下界的性質(zhì)應(yīng)用到算法迭代進(jìn)程中.為驗(yàn)證算法的有效性展開(kāi)大規(guī)模算法測(cè)試,進(jìn)行算法對(duì)比.最后,通過(guò)敏感性分析得到相應(yīng)的管理啟示.本文的研究可為管理者制定具有穩(wěn)定性的進(jìn)度計(jì)劃提供決策支持,便于對(duì)進(jìn)度方案的魯棒性和成本進(jìn)行權(quán)衡.需要指出的是,魯棒性的表示方法并不唯一,在后續(xù)研究中可以應(yīng)用其他指標(biāo)表示項(xiàng)目魯棒性,使魯棒值更能代表進(jìn)度計(jì)劃執(zhí)行時(shí)的魯棒性.