基于隨機(jī)活動工期的多模式現(xiàn)金流均衡項(xiàng)目調(diào)度優(yōu)化

寧敏靜， 何正文， 劉人境

(1.西安交通大學(xué) 管理學(xué)院，陜西 西安 710049; 2.過程控制與效率工程教育部重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710049; 3.西南石油大學(xué) 經(jīng)濟(jì)管理學(xué)院，四川 成都 610500)

0 引言

在現(xiàn)實(shí)的項(xiàng)目管理領(lǐng)域，越來越多的項(xiàng)目呈現(xiàn)出投資規(guī)模大、實(shí)施周期長的特征。自身融資能力有限的承包商不能滿足巨額投資資金需求?，F(xiàn)金流均衡項(xiàng)目調(diào)度問題(CFBPSP，cash flow balance project scheduling problems)研究可以在一定程度上解決這一問題，通過合理地安排活動的開始時(shí)間，來實(shí)現(xiàn)項(xiàng)目現(xiàn)金流入與流出的動態(tài)均衡[1,2]。過長的周期導(dǎo)致項(xiàng)目在執(zhí)行過程中有可能出現(xiàn)較多的不確定擾動，使之處于不確定環(huán)境中，通常表現(xiàn)為活動工期的變化性?；陔S機(jī)活動工期的現(xiàn)金流均衡項(xiàng)目調(diào)度問題的研究，能夠?yàn)椴淮_定環(huán)境中的項(xiàng)目提供現(xiàn)金流盡可能保持均衡的進(jìn)度計(jì)劃，使承包商在項(xiàng)目執(zhí)行過程中避免產(chǎn)生自身難以承受的資金缺口，從而保證項(xiàng)目的順利實(shí)施[3,4]。

值得注意的是，在實(shí)際的項(xiàng)目執(zhí)行過程中，在遇到不確定擾動時(shí)，承包商為了實(shí)現(xiàn)既定的計(jì)劃安排，經(jīng)常通過調(diào)整資源或資金投入量的方法來改變項(xiàng)目進(jìn)度[5,6]。因此，本文研究基于隨機(jī)活動工期的多模式現(xiàn)金流均衡項(xiàng)目調(diào)度問題，具有更為明確的現(xiàn)實(shí)背景，其研究成果能夠?yàn)閷?shí)際中的項(xiàng)目進(jìn)度管理和現(xiàn)金流控制提供直接的理論支持。

縱觀項(xiàng)目調(diào)度問題的研究[7～10]，不確定環(huán)境下項(xiàng)目調(diào)度問題的研究主要集中在時(shí)間維度，目標(biāo)函數(shù)多是進(jìn)度安排的魯棒性，而關(guān)于資金維度的研究則不多，只有少數(shù)關(guān)于不確定條件下折現(xiàn)流項(xiàng)目調(diào)度問題(PSPDCF, project scheduling problems with discounted cash flows)的研究[11～13]。本文研究隨機(jī)活動工期下的現(xiàn)金流均衡問題，充實(shí)了不確定環(huán)境中項(xiàng)目調(diào)度問題關(guān)于資金維度的研究。

1 問題界定及符號定義

本文采用AoN網(wǎng)絡(luò)[14]表示項(xiàng)目。活動之間滿足網(wǎng)絡(luò)優(yōu)先關(guān)系約束，活動開始時(shí)間不得早于其緊前活動的最晚結(jié)束時(shí)間?；顒泳哂卸喾N執(zhí)行模式，不同模式對應(yīng)不同的工期、費(fèi)用。需要說明的是，受不確定因素的影響，活動在各模式下的工期為服從一定均值分布的隨機(jī)變量，當(dāng)活動完成后獲得相應(yīng)的掙值。合同總價(jià)款為所有活動的掙值之和。要求項(xiàng)目必須在計(jì)劃截止時(shí)間之前完成。此外，對于在不確定環(huán)境下實(shí)施的項(xiàng)目來說，進(jìn)度計(jì)劃必須具有一定的穩(wěn)定性。為了確保進(jìn)度計(jì)劃在執(zhí)行過程中的穩(wěn)定性，要求計(jì)劃的魯棒性不得低于一個(gè)設(shè)定的閾值，這可以通過對活動工期隨機(jī)分布的估計(jì)，結(jié)合由計(jì)劃截止時(shí)間和AoN網(wǎng)絡(luò)所決定的總時(shí)間裕量，由項(xiàng)目管理者權(quán)衡決定。在項(xiàng)目開始時(shí)，業(yè)主首先付給承包商部分預(yù)付款，之后進(jìn)行里程碑支付，規(guī)定最后一次支付安排在項(xiàng)目結(jié)束時(shí)刻。項(xiàng)目完工時(shí)，業(yè)主必須向承包商支付除質(zhì)量保證金外的剩余合同價(jià)款，質(zhì)量保證金在質(zhì)保期滿后再行支付。表1給出了文中用到的所有符號的定義。

表1 符號定義表

2 構(gòu)建模型

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

基于隨機(jī)活動工期多模式現(xiàn)金流均衡項(xiàng)目調(diào)度問題的優(yōu)化模型可構(gòu)建如下：

(1)

(7)

通過上述優(yōu)化模型，便可在給定的多個(gè)約束條件下，借助對活動模式q及計(jì)劃開始時(shí)間的安排，合理地調(diào)整項(xiàng)目的現(xiàn)金流入與流出以最小化現(xiàn)金流缺口，從而最大可能地保證項(xiàng)目現(xiàn)金流的動態(tài)均衡。在此需要特別說明的是，在上述優(yōu)化模型中，約束條件式(5)和(6)之間實(shí)際上存在著如下內(nèi)在聯(lián)系：如果項(xiàng)目的計(jì)劃截止時(shí)間D提前，則每個(gè)活動可調(diào)整的時(shí)間窗就會變小，所以，進(jìn)度計(jì)劃的魯棒性也會隨之下降。此時(shí)，若魯棒性閾值設(shè)置得過高，則會造成問題模型無解。因此，項(xiàng)目管理者必須根據(jù)實(shí)際情況審慎地權(quán)衡兩者之間的關(guān)系，以取得一個(gè)最佳的進(jìn)度計(jì)劃安排；否則，如果僅按照主觀經(jīng)驗(yàn)去決策，其甚至無法得到一個(gè)可行的進(jìn)度計(jì)劃安排。而本文所構(gòu)建的調(diào)度優(yōu)化模型，則為項(xiàng)目管理者的上述決策提供了一個(gè)直接的定量化分析工具。

2.2 問題的求解難度分析

在該模型中，通過令活動工期等于隨機(jī)活動工期的均值，從而將不確定性項(xiàng)目調(diào)度問題轉(zhuǎn)化為確定性項(xiàng)目調(diào)度問題。假定Robu*=0，η=1，即在給定的確定性項(xiàng)目調(diào)度條件下，項(xiàng)目執(zhí)行過程中業(yè)主不對承包商進(jìn)行任何支付，而在質(zhì)量保證期滿后進(jìn)行一次性支付。這種情況下，Gmax必然發(fā)生在項(xiàng)目完工時(shí)刻，由此可將上述模型的目標(biāo)簡化為：

基于隨機(jī)活動工期的多模式現(xiàn)金流均衡項(xiàng)目調(diào)度問題即可轉(zhuǎn)化為時(shí)間/費(fèi)用權(quán)衡問題的工期子問題[15]。該問題已被證明為強(qiáng)NP-hard[16]，因此，本文的研究問題也必然是強(qiáng)NP-hard問題。

3 算法

鑒于問題的NP-hard屬性，本文采用模擬退火算法進(jìn)行求解，該算法被證明是求解項(xiàng)目調(diào)度問題的高效算法[17～21]。分析可知模型中存在兩個(gè)決策變量，分別為活動執(zhí)行模式及活動開始時(shí)間，相應(yīng)地，在鄰點(diǎn)生成時(shí)有兩個(gè)算子，兩者之間存在如下關(guān)系：活動執(zhí)行模式的確定不依賴活動開始時(shí)間安排；確定活動開始時(shí)間安排在活動執(zhí)行模式選定之后，可以省略生成鄰點(diǎn)時(shí)活動執(zhí)行模式的可行性判斷，提高算法搜索效率。根據(jù)此內(nèi)在邏輯，采用嵌套的方式尋找滿意解。

3.1 解的表示及初始可行解的生成

鑒于所研究問題中活動具有多種執(zhí)行模式的特征，采用如下兩個(gè)列表表示問題的解：

·執(zhí)行模式列表ML：該列表由N+1個(gè)元素，第n個(gè)元素代表活動n選擇的執(zhí)行模式q。

·時(shí)間裕量列表SL：該列表由N+1個(gè)元素，第n個(gè)元素代表活動n的時(shí)間裕量εn(εn∈[0,Ln-En])，其中，En和Ln分別是活動n的最早和最晚開始時(shí)間，由CPM法計(jì)算得到。

依據(jù)上述解的表示方式，可按照下述迭代程序求得活動的開始時(shí)間：

步驟2依據(jù)時(shí)間裕量列表SL，為各活動選擇一個(gè)時(shí)間裕量εn，n=1,2,…,N；

步驟4應(yīng)用CPM法計(jì)算得到活動的開始時(shí)間sn，n=0,1,2,…,N+1；

步驟5如果項(xiàng)目的結(jié)束時(shí)間超過截止時(shí)間sN+1>D，則對其目標(biāo)函數(shù)進(jìn)行懲罰，令Gmax=U；否則，生成一個(gè)可行的調(diào)度。

問題的初始可行解(MLini,SLini)按如下方式得到：首先，為每個(gè)活動隨機(jī)分配執(zhí)行模式，得到MLini，計(jì)算sN+1，若不大于D，則接受MLini。否則，重復(fù)該操作，直至得到可行的MLini。在時(shí)間裕量列表SLini上，將所有的εn都定義為0。

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

當(dāng)前解(MLcur,SLcur)的鄰點(diǎn)通過如下兩個(gè)算子得到：

·模式變換(MC)算子：在MLcur上隨機(jī)地選擇一個(gè)活動(始末兩個(gè)虛活動除外)，將其由當(dāng)前執(zhí)行模式列表MLcur中的執(zhí)行模式變換為另外一種，在新模式安排下計(jì)算項(xiàng)目結(jié)束時(shí)間，如果不晚于項(xiàng)目截止日期D，則得到MLneig；否則，重復(fù)該操作直至獲得MLneir。

·裕量改變(SC)算子：選擇一個(gè)活動，將εn改變?yōu)閇0,Ln-En]中的另一值，計(jì)算得到各活動的開始時(shí)間，若項(xiàng)目結(jié)束時(shí)間不晚于截止日期D，并且滿足魯棒性閾值約束Robu*，則得到SLneir；否則，重復(fù)該操作直至獲得SLneir。

3.3 模擬退火參數(shù)設(shè)置

模擬退火算法中所涉及的一些參數(shù)設(shè)置如下，需要說明的是，在本文中內(nèi)外兩層嵌套中的參數(shù)設(shè)置相同。

·初始溫度：初始溫度Stempout、Stempin通過式子VGmax/lnPr：得到，其中VGmax是初始解的100個(gè)鄰點(diǎn)中目標(biāo)函數(shù)值的最大絕對差值，Pr是初始接受概率，設(shè)為0.97。

·退火速率：從初始溫度開始，溫度按照一定的比率μout(0<μout<1)、μin(0<μin<1)持續(xù)下降，均設(shè)為0.95。

·固定溫度下的迭代次數(shù)：在某一固定溫度下的迭代次數(shù)Num1、Num2均達(dá)到10×n時(shí)，進(jìn)行降溫處理。

·終止溫度：溫度降至終止溫度Etempout、Etempin(等于0.1)時(shí)，算法終止。

3.4 算法搜索流程

模擬退火嵌套算法的搜索流程如下：

上述算法采用C++語言編程，計(jì)算實(shí)驗(yàn)在基于主頻為2.1GHz英特爾處理器且內(nèi)存為2048MB的個(gè)人計(jì)算機(jī)上運(yùn)行。

4 實(shí)例

4.1 案例背景

本文所選實(shí)例是2008年中天集團(tuán)有限公司總承包施工的一個(gè)CB大廈項(xiàng)目，位于西安市浐灞半島，屬于浐灞半島開發(fā)的二期工程之一。CB大廈建筑面積66303平方米。項(xiàng)目總工期830天，合同總價(jià)款11451.7萬元。項(xiàng)目采用AoN方式表示，見圖1。項(xiàng)目包含39個(gè)活動(活動0和38分別為虛擬開始活動和結(jié)束活動)?；顒泳哂屑蛹焙统Ｒ?guī)兩種執(zhí)行模式，由于施工過程中不確定因素的影響，兩種執(zhí)行模式下的活動工期均是服從一定均值分布的隨機(jī)變量?；顒釉诿糠N執(zhí)行模式下的平均工期、工期標(biāo)準(zhǔn)差、費(fèi)用及活動完成后得到的掙值見表2。預(yù)付款比例γ為7.5%，質(zhì)量保證金比例η為7.5%，業(yè)主在12個(gè)里程碑活動3、5、7、9、11、13、18、25、31、33、36、38上對承包商進(jìn)行支付，支付比例θ為85%。

為了保證隨機(jī)活動工期下進(jìn)度計(jì)劃的穩(wěn)定性，降低項(xiàng)目執(zhí)行過程中因?yàn)橛?jì)劃改變所造成的調(diào)整成本，項(xiàng)目要滿足一定的魯棒性閾值約束。本案例中，項(xiàng)目的魯棒性閾值Robu*由如下方法得到：首先，由計(jì)劃截止日期D和AoN網(wǎng)絡(luò)，應(yīng)用關(guān)鍵路徑法得到項(xiàng)目的總時(shí)差；其次，找到網(wǎng)絡(luò)圖中的所有路徑，將總時(shí)差分配分別給各條路徑上權(quán)重系數(shù)最大的活動，將總時(shí)差分配給這些具有最大權(quán)重系數(shù)的活動上，繼而得到項(xiàng)目魯棒性閾值Robu*的上界；同樣地，將總時(shí)差分別分配給各條路徑上權(quán)重系數(shù)最小的活動，繼而得到項(xiàng)目魯棒性閾值Robu*的下界；最后，在這個(gè)區(qū)間內(nèi)取一個(gè)值Robu*=70作為項(xiàng)目魯棒性閾值約束。

圖1 CB大廈項(xiàng)目AoN網(wǎng)絡(luò)圖

表2 項(xiàng)目參數(shù)表

4.2 理論結(jié)果與現(xiàn)實(shí)情況的比較

本文求解得到的項(xiàng)目滿意進(jìn)度安排如下:ML*=(1,2,2,2,2,2,2,2,2,1,1,2,2,2,2,2,2,2,2,1,2,2,2,1,1,1,1,2,1,2,2,2,2,1,1,1,2,1,1)，其中，1和2分別表示活動的常規(guī)和加急執(zhí)行模式。

SL*=(0,0,363,60,131,192,159,286,187,344,399,215,226,386,260,257,449,350,322,342,544,378,385,397,625,387,406,436,651,395,434,423,469,469,451,494,494,679)

而在實(shí)際中，項(xiàng)目的進(jìn)度安排如下：

ML0=(1,2,1,1,2,2,2,1,1,1,2,2,1,1,1,2,2,2,1,1,1,1,2,2,2,2,1,1,2,2,1,1,1,2,1,2,1,1,1)

SL0=(0,0,197,60,124,135,152,251,180,338,279,205,206,438,250,238,519,333,355,319,647,364,361,392,375,691,378,389,444,769,387,414,418,446,446,444,474,472,797)

G0max=3498.33(萬元)

圖2 承包商累計(jì)資金缺口GT隨時(shí)間變化曲線

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

圖3 承包商最大累計(jì)資金缺口隨不同參數(shù)變化曲線

表3 承包商最大累計(jì)資金缺口隨參數(shù)的變化情況

5 結(jié)論

本文采用基于活動的研究方法，研究了多模式下具有隨機(jī)活動工期的現(xiàn)金流均衡項(xiàng)目調(diào)度問題。首先，界定研究問題，在截止日期約束下，安排活動執(zhí)行模式與開始時(shí)間，給相關(guān)活動留有適當(dāng)時(shí)間緩沖，使之滿足魯棒性閾值約束，保證基準(zhǔn)進(jìn)度的穩(wěn)定性，并使得承包商在項(xiàng)目執(zhí)行過程中的最大累計(jì)資金缺口最小；隨后，在此基礎(chǔ)上構(gòu)建0-1整數(shù)規(guī)劃模型，并設(shè)計(jì)模擬退火算法進(jìn)行求解；最后，通過一個(gè)實(shí)例對研究問題進(jìn)行說明，得到承包商現(xiàn)金流均衡的滿意進(jìn)度安排，將其與凈現(xiàn)值最大化進(jìn)度安排進(jìn)行對比分析，說明本文問題模型的有效性，并討論關(guān)鍵參數(shù)對現(xiàn)金流均衡的影響。得到結(jié)論：承包商現(xiàn)金流均衡情況隨著魯棒性閾值的減小而好轉(zhuǎn)，且當(dāng)魯棒性閾值水平設(shè)置得過高時(shí)，問題無解。需要指出的是，在現(xiàn)實(shí)中，項(xiàng)目具有多種支付方式，將本文研究問題與支付進(jìn)度問題相結(jié)合，是有待于進(jìn)一步研究的問題。