折現(xiàn)流多模式資源約束項目調(diào)度問題研究

黃少榮

（廣東司法警官職業(yè)學(xué)院，廣東廣州510520）

折現(xiàn)流多模式資源約束項目調(diào)度問題研究

黃少榮

（廣東司法警官職業(yè)學(xué)院，廣東廣州510520）

針對帶折現(xiàn)現(xiàn)金流的多模式資源約束項目調(diào)度問題研究，在考慮實際工程中對最終凈現(xiàn)值產(chǎn)生影響的多種因素的基礎(chǔ)上，建立以最大化現(xiàn)金流凈現(xiàn)值為優(yōu)化目標(biāo)的非線性數(shù)學(xué)模型，提出一種改進的遺傳模擬退火算法對模型進行求解.該算法利用遺傳算法進行全局并行搜索，種群每個新產(chǎn)生的個體在交叉和變異后采用模擬退火技術(shù)進行局部串行優(yōu)化，使之移動到最近的局部最優(yōu)點再進入下一代迭代.采用針對活動的整數(shù)編碼方式，基因的值表示活動的優(yōu)先權(quán)和執(zhí)行模式，每個個體對應(yīng)一個滿足時序約束和資源約束的項目調(diào)度方案.仿真結(jié)果表明，新算法能有效地對多模式資源約束項目調(diào)度問題做出合理調(diào)度，使項目收益最大化，并且比傳統(tǒng)的遺傳算法具有更高的求解質(zhì)量和求解效率，為承包商在項目投資和進度管理上提供了定量化決策支持.

多模式資源約束項目調(diào)度；現(xiàn)金流；凈現(xiàn)值；遺傳算法；模擬退火

1 引言

多模式資源約束項目調(diào)度問題（multi-mode resource-constrained project scheduling problem，MRCPSP）是典型資源約束項目調(diào)度問題（resource-constrained project scheduling problem，RCPSP）的擴展，是近年來項目管理領(lǐng)域的研究熱點，已被證明是強NP-難問題［1］.MCPSP一般以工期最短、成本最低或資源均衡為優(yōu)化目標(biāo)，但這些目標(biāo)沒有結(jié)合企業(yè)財務(wù)狀況，不能有效地反映項目的整體收益.隨著較高的利率和昂貴的融資費用，尤其對于資金密集型的項目，項目凈現(xiàn)值（net present value，NPV）最大化已成為一個更加貼近現(xiàn)實的項目調(diào)度優(yōu)化目標(biāo)［2］.以凈現(xiàn)值作為優(yōu)化目標(biāo)的MRCPSP稱為折現(xiàn)流MRCPSP（MRCPSP with discounted cash flow，MCPSPDCF），MRCPSPDCF能夠有效管理項目執(zhí)行過程中的現(xiàn)金流入和現(xiàn)金流出，規(guī)避項目風(fēng)險，并使企業(yè)收益最大化，不僅是項目投資決策的重要評價指標(biāo)，而且對提高整個項目管理的質(zhì)量具有重要的指導(dǎo)意義和實用價值［3］.

MRCPSPDCF的研究目標(biāo)就是在滿足項目資源約束和優(yōu)先關(guān)系約束的條件下，合理選擇所有活動的執(zhí)行模式，安排活動的開工時間，以達(dá)到項目現(xiàn)金流凈現(xiàn)值最大化的優(yōu)化目標(biāo).MRCPSPDCF不僅要選擇項目中各活動的執(zhí)行模式，還要確定活動的開工期，而且復(fù)雜的非線性現(xiàn)金流分析方法進一步提高了問題求解的難度，對求解算法提出了更高的要求，精確算法和啟發(fā)式算法只能求解中小規(guī)模的MRCPSPDCF問題［4］.隨著問題規(guī)模的不斷擴大，混合優(yōu)化算法被提出來用于求解該類問題［5］.

遺傳算法與模擬退火算法都是啟發(fā)式隨機搜索算法，遺傳算法的局部搜索能力較差，但把握搜索過程總體的能力較強；模擬退火算法具有較強的局部搜索能力，并能使搜索過程避免陷入局部最優(yōu).本文充分利用遺傳算法全局搜索能力強和模擬退火局部搜索能力強的特點，提出一種引入模擬退火的遺傳算法智能調(diào)度策略，對MRCPSPDCF模型進行優(yōu)化求解，并用實例驗證新算法的有效性和高效性.

2 MRCPSPDCF優(yōu)化模型

2.1 問題描述

本文對MRCPSPDCF問題采用基于事件（eventbased）的研究方法，即項目網(wǎng)絡(luò)用AoA（Activity-on-Arc）方式表述，現(xiàn)金流和事件相聯(lián)系.如圖1所示，E是項目G＝（E，A）的事件集，連接事件i到j(luò)的有向邊（i，j）對應(yīng)于活動集A中的一項活動，每一個活動具有Kij種不同的執(zhí)行模式（Kij≥1），不同執(zhí)行模式對應(yīng)不同的資源需求、工期和現(xiàn)金流，模式一經(jīng)選定并不能更改直至完成，活動不具有搶先權(quán).

圖1 網(wǎng)絡(luò)圖示例Fig.1 A network diagram of the example

本文在文獻(xiàn)［6－7］研究成果的基礎(chǔ)上，綜合考慮了凈現(xiàn)值最大化問題中的諸多因素，如活動時序約束、執(zhí)行模式、資源約束、業(yè)主支付和獎懲機制等，構(gòu)造出一種多模式、基于完成進度的事件支付、帶獎懲制度和間接費用分析的非線性整數(shù)規(guī)劃MRCPSPDCF模型，模型的優(yōu)化目標(biāo)是在滿足時序約束和資源約束前提下，找出該項目的最優(yōu)活動調(diào)度方案，使得項目結(jié)束時現(xiàn)金流折現(xiàn)值最大化，即：

式（1）表示優(yōu)化目標(biāo)是最大化項目凈現(xiàn)值.NPV（S）是最終調(diào)度S下的凈現(xiàn)值，由相應(yīng)的現(xiàn)金流入折現(xiàn)值CFin（S）與現(xiàn)金流出折現(xiàn)值CFout（S）決定.

式（2）表示時序約束：事件j的任意直接后繼活動都必須在其所有直接前趨活動執(zhí)行完畢之后才能開始發(fā)生.其中，P（j）為事件j的緊前事件集合，S（j）為事件j的后繼事件集合，為活動（i，j）采用模式k的執(zhí)行工期；［ETij，LTij］為活動（i，j）的時間窗；為表示活動（i，j）是否在時間t結(jié)束的0－1變量，如果活動（i，j）在時間t結(jié)束，則，否則為表示活動（i，j）是否采用第k種模式，如果是，則，否則

式（3）表示資源約束：在單位工期內(nèi)，正在執(zhí)行的活動的各種資源使用量不超過其最大使用限額.其中，At為時期t時正在進行的活動集合，V代表資源種數(shù)，Rv為第v種資源單位工期的供應(yīng)量，rkijv代表活動（i，j）采用模式k執(zhí)行時單位工期對資源v的使用量.

2.2 現(xiàn)金流計算

對承包商而言，現(xiàn)金流入代表業(yè)主的支付，現(xiàn)金流出代表人力、設(shè)備、原材料和管理等造成的費用.項目執(zhí)行過程中，產(chǎn)生的現(xiàn)金流包括：

（1）項目開始時的預(yù)付款：合同簽訂后項目開工，業(yè)主按合同總價U的一定比例λ向承包商預(yù)付定金：λU.

（2）項目執(zhí)行過程的支付款：項目執(zhí)行過程中，業(yè)主和承包商雙方約定在支付事件完成時按一定比率進行支付.若n是支付事件，則其支付量為Pn＝其中θ為支付比率；lastn（S）為調(diào)度S中事件n之前發(fā)生的最近一次支付事件的發(fā)生時間（如果n為第一個支付事件，則lastn（S）＝0）；Ti（S）為項目在調(diào)度S下第i項事件的發(fā)生時間，TN（S）對應(yīng)于最后一項事件N的發(fā)生時間，表示整個項目工期；Wij為活動（i，j）的掙值；所有支付事件的支付量之和為按一定折現(xiàn)率α折現(xiàn)到?項目開始時為：

（4）直接費用：包括固定費用和資源費用.活動（i，j）在調(diào)度S中選擇模式k執(zhí)行，發(fā)生固定費用為每單位時間資源成本為為第i種資源的單價.折現(xiàn)到活動開始時為：.活動（i，j）的直接費用為固定費用與資源費用的折現(xiàn)之和：.所有活動的費用折現(xiàn)值之和為：

（5）間接費用：即財務(wù)費、管理費等雜項費用.It表示發(fā)生在時間t的間接費用，整個工期全部間接費用折現(xiàn)到項目開始時為：.當(dāng)It＝ I為常數(shù)時，用等比數(shù)列求和可表示成：

（6）獎懲額：合同規(guī)定完工期限［DE－ΔT，DE＋ΔT］，項目若在規(guī)定期限內(nèi)完成，則獎金（罰金）為0；項目若提前完成，獎金為γ（TN（S））·U；推遲完成，罰金為δ（TN（S））·U.γ和δ為獎勵比率和懲罰比率.獎金（罰金）BP的折現(xiàn)值如下：

上述現(xiàn)金流中（1）－（3）為CFin（S），（4）－（5）為CFout（S），（6）根據(jù)完工情況可以為CFin（S）或CFout（S），則式（1）的目標(biāo)函數(shù)的計算詳細(xì)如下：

3 基于模擬退火的混合遺傳算法

3.1 遺傳算法

遺傳算法（Genetic Algorithm，GA）是Holland通過人工模擬自然進化的自適應(yīng)系統(tǒng)而得到的一種高度并行的自適應(yīng)隨機搜索算法，具有全局優(yōu)化、隱含并行、自組織、自適應(yīng)和自學(xué)習(xí)性等優(yōu)點，已經(jīng)被廣泛應(yīng)用于解決實際工程問題［8］.由于允許使用非常復(fù)雜的目標(biāo)函數(shù)，能夠限制變量的變化范圍，GA在MRCPSP問題上已經(jīng)表現(xiàn)出優(yōu)異的性能，但存在著容易產(chǎn)生早熟收斂，局部尋優(yōu)能力較差的缺點［9］.

GA是一種迭代算法，首先隨機生成一個由經(jīng)過基因編碼的一定數(shù)目的個體組成的初始種群，按照選擇、復(fù)制、交叉和變異等遺傳操作演化出新的一代，并根據(jù)個體的適應(yīng)度，按優(yōu)勝劣汰原則，引導(dǎo)搜索過程向最優(yōu)解逼近，末代種群的最優(yōu)個體經(jīng)過解碼，作為問題近似最優(yōu)解.

3.2 模擬退火

模擬退火（Simulated Annealing，SA）是Metropolis提出的一種源于固體退火原理的局部搜索方法，后由Kirkpatrick等將退火思想引入組合優(yōu)化領(lǐng)域［10］.SA具有較強的局部尋優(yōu)能力，允許在尋優(yōu)過程中以一定概率接受變壞的解使得算法能夠跳出局部最優(yōu)解，已經(jīng)在資源約束調(diào)度問題中取得成功應(yīng)用，但存在著由于對整個搜索空間的情況了解不多而導(dǎo)致搜索效率不高的不足.

SA在項目調(diào)度問題上進行搜索時，目標(biāo)函數(shù)作為內(nèi)能，溫度為控制參數(shù).由初始解開始，對當(dāng)前解重復(fù)“在鄰域內(nèi)產(chǎn)生新解→計算目標(biāo)函數(shù)差→接受或拒絕”迭代，逐步降溫，算法終止時的解為所得的近似最優(yōu)解.

3.3 模擬退火遺傳算法混合優(yōu)化策略

為了克服GA早熟收斂的缺陷，提高GA的局部搜索能力，必須加強種群多樣性，在更優(yōu)解鄰域中尋找更優(yōu)解，在劣質(zhì)解鄰域中也要尋找更優(yōu)解，這樣才能保證產(chǎn)生更好的調(diào)度方案.為此，在GA的全局搜索過程中結(jié)合SA的局部搜索，構(gòu)成一種混合搜索算法（GASA），其基本思想是：對于每個新產(chǎn)生的個體在進入下一代種群前應(yīng)用SA技術(shù)，使之移動到最近的局部最優(yōu)點.

算法流程如下：

Step1設(shè)置進化代數(shù)g＝1，最大進化代數(shù)為G，設(shè)置種群規(guī)模M、交叉率Pc和變異率Pm；

Step2隨機生成M個個體組成初始種群P（t）；

Step3計算種群P（t）中各個個體的適應(yīng)度，保存最優(yōu)個體；

Step4選擇N個適應(yīng)值最好的個體直接復(fù)制到下一代種群；

Step5設(shè)置初始溫度t0、終止溫度tf，降溫速率Δt；

Step6對剩下的（M－N）個個體分別進行交叉、變異操作，比較個體適應(yīng)度Δ＝f（Xi＋1）－f（Xi），若Δ＞0或［Δ≤0且exp（－Δt／ti）＞random（0，1）］，接受此次交叉或變異，轉(zhuǎn)Step8；否則拒絕；

Step7降溫，使ti＝ti－Δt，若ti＞tf，轉(zhuǎn)Step6；

Step8將交叉、變異后得到的（M－N）個個體復(fù)制到新種群，與Step4復(fù)制下來的N個個體組成新一代種群P（t＋1）；

Step9評價P（t＋1）中各個個體的適應(yīng)度，保存最優(yōu)個體；

Step10終止條件判斷：若g≤G，則g＝g＋1，轉(zhuǎn)Step4，繼續(xù)進化過程；否則，輸出當(dāng)前最優(yōu)個體，算法結(jié)束.

GASA算法結(jié)合GA的全局并行搜索能力強和SA的局部串行搜索能力強的特點，將SA引入到GA中，用于MRCPSPDCF的求解，既能夠避免遺傳算法存在的“早熟”問題，大大減小遺傳算法陷入局部最優(yōu)解的可能性，又能增強算法的全局收斂性，提高算法的收斂速度.GASA比兩者分開時的單一算法，其魯棒性和優(yōu)化性能均得到很大提高，對于優(yōu)化MRCPSPDCF等NP－h(huán)ard問題非常有效，可以在很短的時間內(nèi)求出比較好的解.

4 算法設(shè)計

4.1 編碼及初始種群生成

由于MRCPSPDCF問題需要對項目中的所有活動排序，同時還要對各個活動做出模式選擇，所以采用整數(shù)編碼方式，個體上的基因?qū)?yīng)活動的次序和它選擇的執(zhí)行模式，每個基因的編碼都是由一對數(shù)字構(gòu)成，第一個是活動編號，第二個是模式編號.圖2表示的是一個有6個基因的個體，該個體表示活動的執(zhí)行順序為：2、1、3、5、4、6，活動2、5、4選擇模式1執(zhí)行，活動1、3、6選擇模式2執(zhí)行.

圖2 基因中的活動和模式Fig.2 Activity and modes in the gene

采用基于時序序列的方式對個體上的活動進行調(diào)度，每個個體從第一個基因位開始規(guī)劃，只要一項活動滿足以下條件即可立刻獲得調(diào)度，依次填充進基因序列：①沒有被調(diào)度；②滿足時序約束：所有前驅(qū)活動已經(jīng)執(zhí)行完畢；③滿足資源約束：當(dāng)前的資源滿足活動在該模式下的需求.④非嚴(yán)格遞增：在基因序列上的前一個活動已經(jīng)開始執(zhí)行或已執(zhí)行完畢.在滿足資源約束的前提下活動隨機選取某一模式執(zhí)行，其開工時間為為該活動所有前趨活動中最遲完工的時間.直到把所有活動都放進相應(yīng)基因位，即形成一個個體，該個體為一個滿足時序約束與資源約束的調(diào)度方案.

4.2 個體適應(yīng)度評價

一旦所有活動被規(guī)劃，則這個項目的凈現(xiàn)值可以在它的現(xiàn)金流量圖中找到，直接以待求解的目標(biāo)函數(shù)max NPV（S）作為個體適應(yīng)度函數(shù).

4.3 復(fù)制、交叉與變異

（1）選擇N個適應(yīng)度最好的個體直接復(fù)制到下一代種群；

（2）采用輪盤賭的方式從當(dāng)前種群中選擇一個個體以交叉率Pc進行交叉.如果不需要交叉，直接將該個體放入緩沖池；如果需要交叉，再用輪盤賭的方式從當(dāng)前種群中選擇另一個個體，對這兩個個體采用MCUOX（多分量均勻有序交叉）方法進行交叉：

從父代和子代的第一個活動開始迭代，隨機從父母中選擇一個個體，找到它第一個沒有分配給子體的活動，分配給子體當(dāng)前正等待分配的基因位，如果活動的父母雙方具有相同的模式，則子代同樣選取這種模式；如果父母代的模式是不同的，則隨機選擇其中之一代為子代的模式.交叉后得到一個子體，將子體保存到緩沖池.重復(fù)本步驟，直到緩沖池中的個體數(shù)目為（M－N）.

（3）對交叉得到的緩沖池中的（M－N）個個體以隨機指定一個位置根據(jù)變異率Pm進行變異，將變異點（某個活動的執(zhí)行模式）隨機地替換為另一種可執(zhí)行模式；將變異后的個體復(fù)制到新種群中.

至此，得到一個含有M個個體的新一代種群P（t＋1）.

5 實例及分析

5.1 實例

某工程項目的活動網(wǎng)絡(luò)圖如圖3所示，共有9個事件14個活動，活動之間有時序約束，活動可采用常用規(guī)模式N或通過增加資源投入來縮短工期的壓縮模式C進行.項目合同總價U為35 000元，預(yù)付款比例γ為20%，在支付事件（3，5，7）完成后按一定比例支付該事件的累計掙值，支付比例θ為80%，余款在項目結(jié)束時結(jié)清.折現(xiàn)率α為0.005，項目截止日期為（50±2）d，超出期限每提前（拖延）單位工期按合同總價的1.5%（1%）進行獎勵（懲罰），項目執(zhí)行過程中需要用到兩種可更新資源，單位資源成本分別為30元和20元，單位工期的資源限量分別為12和8，每單位工期發(fā)生的間接費用為200元.每項活動的詳細(xì)信息如表1所示.

圖3 項目活動網(wǎng)絡(luò)圖Fig.3 Project network diagram

5.2 結(jié)果與分析

種群規(guī)模M＝30，最大進化代數(shù)T＝500，交叉率Pc＝0.9，變異率Pm＝0.2，初始溫度t0＝100、終止溫度tf＝0，降溫速率Δt＝10，選擇個數(shù)N＝15；算法運行結(jié)果為：項目最大凈現(xiàn)值為：6 384.98元，工期52 d，最佳調(diào)度方案如表2所示.

表1 活動信息Table 1 Activity information

表2 最佳調(diào)度方案活動執(zhí)行信息表Table 2 Details of the best project scheduling scheme

表2可以看出，本文提出算法能有效優(yōu)化MCPSPDCF問題，對多模式資源約束項目做出合理調(diào)度，使整個項目的現(xiàn)金流折現(xiàn)值最大，達(dá)到凈收益最大化目標(biāo).

為了比較算法的性能，將本文提出算法與傳統(tǒng)遺傳算法（參數(shù)設(shè)置、遺傳操作與GASA一致）在優(yōu)化MCPSPDCF問題上做比較，兩種算法各運行100次，結(jié)果如表3所示.

表3 兩種算法比較結(jié)果Table 3 Com parison between GASA＆GA running results

表3可以看出，本文提出的算法取得的最大NPV和平均NPV均優(yōu)于傳統(tǒng)遺傳算法，并且在100次的運行中其找到最優(yōu)解的次數(shù)明顯多于傳統(tǒng)遺傳算法.證明該算法在解決這類問題上具有較高的優(yōu)化性能，避免了遺傳算法容易早熟的缺點，并且能夠更好地綜合考慮影響現(xiàn)金流的多種因素和資金的時間價值，實現(xiàn)現(xiàn)金流凈現(xiàn)值的最大化.

6 結(jié)語

本文針對具有多個不同執(zhí)行模式的資源約束項目調(diào)度問題，綜合考慮不同模式帶來不同的現(xiàn)金流以及資金的時間價值，以凈現(xiàn)值為優(yōu)化目標(biāo)建立數(shù)學(xué)模型，利用改進模擬退火遺傳算法對項目執(zhí)行過程進行管理、控制與優(yōu)化，得到理想的項目調(diào)度方案，使項目的現(xiàn)金流入與現(xiàn)金流出保持最佳結(jié)構(gòu)，實現(xiàn)項目現(xiàn)金流凈現(xiàn)值的最大化，從而取得較好的經(jīng)濟效益和社會效益.

現(xiàn)金流貫穿項目管理的始終，是項目管理的核心.以凈現(xiàn)值作為目標(biāo)進行項目活動進度規(guī)劃是目前的一大研究熱點，但基于凈現(xiàn)值的多模式資源受限項目調(diào)度問題的研究還不成熟，許多新的模型、算法、理論和應(yīng)用有待深入研究和發(fā)展［7］，結(jié)合多種優(yōu)化技術(shù)的混合算法將是解決這類問題的有效途徑.

［1］方 晨，王 凌.資源約束項目調(diào)度研究綜述［J］.控制與決策，2010，25（5）：641－650.

［2］RUSSELLR A.A comparison of heuristics for scheduling project with cash flows and resource restrictions［J］. Management Science，1986，32（10）：1291－1300.

［3］何正文，任世科，徐 渝.基于資金約束的項目支付進度問題研究［J］.系統(tǒng)工程學(xué)報，2012，6（3）：399.

［4］ICMELIO，ERENGUC SS.A branch and bound procedure for the resource constrained project scheduling problem with discounted cash flows［J］.Management Science，1996，42（10）：1395－1408.

［5］SAID E.Optimum cash flow scheduling of construction projects［J］.Civil Engineering and Environmental Systems，2009，9（9）：69－85.

［6］張靜文，徐 渝，何正文.多模式資源約束型折現(xiàn)流時間－費用權(quán)衡權(quán)衡進度［J］.系統(tǒng)工程，2005，23（5）：17－21.

［7］李詩嫻.基于凈現(xiàn)值的資源受限型項目調(diào)度問題研究［D］.天津：天津大學(xué)，2012.

［8］HOLLAND JH.Adaptation in Nature and Artificial Systems［M］.Cambridge：MIT Press，1992.

［9］VANPETERHEM V，VANHOUCHK M.A genetic algorithm for the preemptive and non-preemptive multi-mode resource-constrained project scheduling problem［J］.European Journal of Operation Research，2010，201（20）：409－418.

［10］KIPKPARTRICK S，GELATT C D，VECCHI M P.Optimization by simulated annealing［J］.Science，1983，220（4598）：671－680.

［責(zé)任編輯：王景周］

Research on multi-mode resource constrained project scheduling problem with discounted cash flows

HUANG Shaorong
（Guangdong Justice Police Vocational College，Guangzhou 510520，China）

To solve the multi-mode resource constrained project scheduling problem with discounted cash flows（MRCPSPDCF），the model of MRCPSPDCF with the objective function of maximizing the net present value（NPV）was formulated，and the important factors are considered in this model.A modified genetic algorithm combining the idea of the simulated annealing（GASA）for solving this model is proposed.This algorithm combines the crossover and mutation operation of genetic algorithm，and after each crossover and mutation operation，a simulated annealing algorithm was utilized for local search.The gene coding and the GASA operating methods which could satisfy both the precedence relations and resource constrains are introduced.The experimental results demonstrate that the proposed algorithm not only can elegantly solve the MRCPSPDCF，but also has better performance than genetic algorithm，it provides a new method for MRCPSPDCF and offer quantization decision-making information for the project contractor.

multi-mode resource-constrained project scheduling problem； cash flow； net present value； genetic algorithm； simulated annealing

TP306.1

A

1000－9965（2015）04－0357－06

10.11778／j.jdxb.2015.04.015

2015－05－07

廣東省自然科學(xué)基金項目（101754539192000000）

黃少榮（1976－），女，副教授，CCF高級會員，研究方向：計算機應(yīng)用、計算智能；Mobile：15914450007；E-mail：huangshaorong＠163.com