資源受限項目調(diào)度問題文獻綜述

1、資源受限項目調(diào)度問題綜述摘要針對資源受限項目調(diào)度問題，總結國內(nèi)外項目調(diào)度的發(fā)展過程及研究成果。在對問題的類型進行分類的基礎上，結合大量文獻對常見的算法進行描述并重點介紹了關鍵技術的研究狀況。進一步地，將資源受限項目調(diào)度問題做進一步的拓展，簡略介紹多目標、多項目、任務可拆分的項目調(diào)度問題。最后對問題進行總結，并提出自己的看法。0 引言現(xiàn)代項目越來越趨于大型化、復雜化，要求工期更短、成本更低。再加上行業(yè)細分越來越發(fā)達這種新情況給項目管理帶來了更高的要求。如何在更短時間內(nèi)、在保證質(zhì)量的前提下，以更低的成本完成項目，成為項目管理人員關心的問題。在項目運作過程中，資源受限項目調(diào)度問題RCPSP(reso

2、urce-constrained project scheduling problem)是一個重要的優(yōu)化問題，它是最常見的生產(chǎn)調(diào)度問題，是項目管理中最為經(jīng)典和核心的問題之一1 項目調(diào)度發(fā)展過程項目調(diào)度問題自20世紀中期被提出來，傳統(tǒng)的計劃技術有甘特圖（又稱橫道圖，Gant Chart,Gc）、關鍵活動圖、網(wǎng)絡計劃技術。幾種典型的網(wǎng)絡計劃技術有：關鍵路徑發(fā)（Critical Path Method,CPM）、項目計劃評審技術（Program Evaluation and Review Technique,PERT）、優(yōu)先圖方法（PDM）、圖解評審技術（Graphical Evaluation a

3、nd Review,GERT）、風險評審技術（Venture Evaluation and Review Technique,VERT）.最初被廣泛應用于項目進度計劃的工具是甘特圖技術，它用二維坐標的形式，用線條在二維空間中表似乎出整個項目期間計劃和實際的活動完成情況，直觀表明項目中所含各項活動的執(zhí)行順序，以及每項活動的開始/結束時間和持續(xù)時間。該方法形象直觀，易于掌握，但是不能體現(xiàn)工作間的相互依賴關系，不能體現(xiàn)工作過早開始或者過完開始所造成的后果。 20世紀50年代中期發(fā)展起來的網(wǎng)絡計劃技術迅速滲透到項目調(diào)度領域，以網(wǎng)絡圖的形式來表示項目進度計劃。它能明確反映各活動時間的先后順序和相互制約的

4、邏輯關系，通過計算時間參數(shù)，可找出計劃中的關鍵活動及關鍵路線，反映出各活動的時差。其思想是通過壓縮關鍵工作路線的持續(xù)時間，從而使工程的工期、費用實現(xiàn)優(yōu)化。具有代表性的是關鍵路徑法與計劃評審技術。兩種方法都是采用平面網(wǎng)絡結構表示項目的工作細分結構，很好的反映了項目組成各工作之間的時序依賴關系。二者的卻別在于對項目各工作的執(zhí)行時間的估計方法。關鍵路徑發(fā)采用一點估計法，直接根據(jù)歷史數(shù)據(jù)和以往經(jīng)驗給出唯一的估計值，不考慮不確定性因素。這種方法可能會造成與項目實際情況的較大偏差。評審技術進行了一定的改進，采用三點估計法，即以經(jīng)驗豐富的項目管理者所掌握的完成一項工作所需要的可能最少時間、可能最多時間及最大

5、可能時間為基礎，來得到估計執(zhí)行時間。通過數(shù)理統(tǒng)計的基本理論，對項目進度進行了定量分析，能夠得到較高的計劃。但是這兩種方法有一個共同的缺點，就是沒有考慮資源約束，這與實際情況不符合，由此便產(chǎn)生了資源受限項目調(diào)度問題。2 資源受限項目調(diào)度問題研究現(xiàn)狀2.1資源受限項目調(diào)度問題描述 任何項目的策劃和執(zhí)行都包含大量不同的活動及各種人力、物力資源。在項目活動的組織安排總，有些活動是可以同時進行的，有些活動則是必須在其他若干活動完成之后才能進行的。同時，每項活動本身還需要一定的持續(xù)時間，且使用不同類、不同數(shù)量的資源如機器設備、物資材料、勞動力等。資源是項目執(zhí)行過程中不可缺少的重要組成部分，而這些資源的有效

6、可用量往往具有局限。如何以最佳方式安排執(zhí)行項目中的各個活動，以使其順利完成，就構成了資源受限項目調(diào)度問題的基本概念。黃敏鎂、江濤將這一概念描述為：“項目由一系列相互關聯(lián)的活動構成，整個項目的結構由一張AON（activity-on-node）有向網(wǎng)絡圖表述。RCPSP的調(diào)度決策需要同時滿足項目活動之間的時序約束和資源約束。RCPSP的解是在滿足時序約束和資源約束條件下產(chǎn)生的一種使某些管理目標最優(yōu)化的調(diào)度，即每個活動何時開始及采用何資源或執(zhí)行模式。劉秋蓮將一般的資源受限的工程調(diào)度問題描述如下:在一個(或多個)工程中，包含 著很多相互關聯(lián)(滿足緊前關系)的工作，每項工作的完成需要一定數(shù)量的資源并

7、有一定的工期，在工程的每一個階段都可能有多個工作競爭同一種有限的資源， 問題是如何分配這些資源才能實現(xiàn)最優(yōu)的管理目標?這些目標可能是:工程的工 期最短，工程拖期最少，工程拖期懲罰最小，工程的凈收益最大等?？偠灾?， RCPSP問題是研究具有優(yōu)先關系約束活動的項目在資源受限的條件下使某些管理目標最優(yōu)的調(diào)度問題2.2資源受限項目調(diào)度問題研究內(nèi)容2.2.1RCPSP 的類型自從資源首先項目調(diào)度問題提出以來，已經(jīng)出現(xiàn)了種類繁多的RCPSP問題。辛潤勤按照以下幾個方面對資源受限項目調(diào)度問題進行分類2.2.1.1根據(jù)項目調(diào)度目標分類（1）最小化項目工期：（3）最大化項目凈現(xiàn)值（4）資源均衡問題2.2.1.

8、2根據(jù)資源類型分類3 非可再生資源：資源的可使用量在整個項目工期內(nèi)具有約束，一旦消耗完就不能再生。（2）可再生資源：資源的可使用量在項目中每一階段內(nèi)受到約束，某階段的數(shù)量有限，但使用之后被釋放可以再生。（3）雙重資源約束：資源的可使用量既在整個項目工期內(nèi)具有約束，而且在項目工期中的每個時間段內(nèi)受到約束。2.2.1.3按照模型的不同分類（1）單執(zhí)行模式資源約束項目調(diào)度問題：每項活動只有一種執(zhí)行模式，消耗一定的資源在一個給定的加工時間內(nèi)完成。（2）多執(zhí)行模式資源約束項目調(diào)度問題： 運行活動可以以多種執(zhí)行模式之一進行操作，每種執(zhí)行模式對應一種資源組合和相應的活動執(zhí)行時間。2.2.2資源受限項目調(diào)度問

9、題求解方法研究資源受限的工程調(diào)度問題在現(xiàn)代企業(yè)中顯示出越來越重要的研究價值。隨著最優(yōu)化技術的不斷發(fā)展，國內(nèi)外學者陸續(xù)提出了一系列性能優(yōu)良的優(yōu)化算法，并將這些算法應用于解決項目調(diào)度問題。劉士新等根據(jù)收集到的資料，對這些算法進行歸納并概述。2.2.2.1算法概述解決資源受限項目調(diào)度這類問題的方法可以分為兩類，一是致力于取得最優(yōu)解的精確算法，另一類就是啟發(fā)式算法。常用于求解RCPSP 的主要精確算法有線性規(guī)劃（linear programming）和分枝限界法(branch and bound).精確算法的研究主要是集中在利用數(shù)學規(guī)劃問題來對項目調(diào)度進行公式化的求解，這類算法雖然在某些程度上能夠得到

10、精確解甚至是最優(yōu)解，但它只能解決中小項目的調(diào)度。隨著問題規(guī)模的擴大，確定性算法的求解時間將以指數(shù)級的速度增加。因此啟發(fā)式算法求解RCPSP。何正文等在“求解資源約束項目調(diào)度問題的啟發(fā)式算法綜述”一文中，闡述了求解RCPSP的啟發(fā)式算法。首先在對各種優(yōu)先權規(guī)則進行歸納的基礎上 ,概述基于優(yōu)先權規(guī)則的RCPSP 啟發(fā)式算法研究現(xiàn)狀;其次,綜述項目進度的表述方式及常用超啟發(fā)式策略,匯總求解 RCPSP 的 超啟發(fā)式的研究成果。l 基于優(yōu)先權規(guī)則的啟發(fā)式算法基于不同的優(yōu)先權規(guī)則從可安排活動集合中選擇活動 ,從而將部分進度擴展為滿意的完全進度。常用的優(yōu)先權規(guī)則主要有以下幾種：最大分級位置權重規(guī)則、最遲完

11、成時間規(guī)則、最多緊后活動規(guī)則、最遲開始時間規(guī)則、最小松弛規(guī)則。同時還擴展出多通道算法，如：多重優(yōu)先權規(guī)則啟發(fā)式算法、前向-后向進度安排啟發(fā)式算法、抽樣性啟發(fā)式算法、適應性啟發(fā)式算法等等。l 超啟發(fā)式算法該類算法將項目進度表述為一組編碼，利用超啟發(fā)式策略對編碼進行搜索優(yōu)選后，再轉化為進度安排。進度安排常用的表述方式有活動列表、隨機鍵、轉移向量、進度設計、直接表述。文中總結出求解RCPSP常用的啟發(fā)式策略有模擬退火、禁忌搜索、遺傳算法和等等。模擬退火：從某個初始解開始 ,一個鄰點通過對當前解的擴展來生成。如果鄰 點好于當前解則被接受;否則,它以一定的概率被接受 ,接受概率依賴于該解變壞的程度以及當

12、前的溫度參數(shù)。隨著算法的進行 ,溫度被逐步降低以減小接受壞的鄰點的概率。達到規(guī)定的溫度后算法終止 ,最后 固定下來的解即為滿意解。 禁忌搜索：對于所有鄰點解進行評價并選擇其中最好的一個進行進一步的搜索。為了避免搜索返回剛剛離開的局部最優(yōu)點而形成循環(huán), 通過建立一個禁忌列表來限制向某些鄰點的移動。這種禁忌狀態(tài)在某種特定的條件下也可以被重新激活。 遺傳算法：并行地考慮解的一個集合或群體, 在已生成的初始群體的基礎上, 新的解通過交叉和/ 或變異操作來獲得。在新解生成后, 適應度 通常用所求解問題的目標函數(shù)來表示最高的解“生存”下來構成下一代, 而其余的解通過所謂的選擇機制被淘汰, 從而使解的質(zhì)量不

13、斷得 到改善。 同時還提出了其他類型的啟發(fā)式算法如蟻群算法、可變鄰點搜索技術等等。結合其他學者的觀點，超啟發(fā)式算法被普遍認為是在性能、可擴展性和易于實現(xiàn)性等方面權衡后的最佳方法。是目前學者們研究資源受限項目調(diào)度問題最常用的方法另外，以色列學者高德拉特將約束理論（Theory of Constraint,TOC）應用于項目管理領域，提出了基于關鍵鏈的項目管理理論，從中發(fā)展出一種新的項目調(diào)度理論：基于關鍵鏈的項目調(diào)度理論2.2.2.2啟發(fā)式算法在RCPSP問題中的應用下面首先基于一些比較典型的超啟發(fā)式算法（遺傳算法、蟻群算法、模擬退火）模型以及關鍵鏈法結合一些文獻進行整理和綜述，并提出自己的看法。

14、2.2.2.2.1遺傳算法遺傳算法（Genetic Algorithm）是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優(yōu)解的方法。資源受限項目調(diào)度求解的是工期最小、凈現(xiàn)值最大等一些最優(yōu)解，所以可以運用遺傳算法來求解。ü 基于遺傳算法的資源約束型項目調(diào)度優(yōu)化 楊利宏等基于遺傳算法，著重討論優(yōu)化資源有限工期最短問題。該優(yōu)化過程是在多資源約束下，通過檢索隨機生成的活動調(diào)度篩選出資源約束下最小工期的調(diào)度方式。最后通過某公司的電腦橫機研發(fā)項目為研究對象，針對多資源約束的項目計劃和調(diào)度問題，采用遺傳算法優(yōu)化項目的調(diào)度方法。整個遺傳算法的流程

15、如下圖所示。在進行優(yōu)化計算前，首先完成從搜索空間到遺傳空間的轉換，進行兩方面的工作：（1）將目標函數(shù)轉換成適度函數(shù)，即將最小值問題通過比例運算轉化成最大值問題。（2）染色體編碼，通過基于隨機優(yōu)先權把實際的AON網(wǎng)絡轉換成項目活動的調(diào)度。根據(jù)適應度函數(shù)，計算適度值。接下去是在遺傳空間上進行選擇、交叉、變異，知道找到最優(yōu)解。選擇：在這基礎上，根據(jù)計算出來的適度值，采用輪盤賭操作進行選擇，選擇出需要繁殖的父代群體。這個過程就是“選擇操作”交叉：本文采用兩點交叉的運算模式，為了不產(chǎn)生重碼，文中提出了基于位置映射關系的兩點交叉。既可以保證不重復，也可以很好地保證個體的繼承性。變異：采用基于中心位置的變異

16、。分為四步：計算變異基因的個數(shù)U、生成U個隨機數(shù)作為基因的變異、定位到相關的染色體、采用中心位置變異的方法，隨機與本染色體內(nèi)的其他等位基因調(diào)換數(shù)值，從而生成新的染色體。 作者將該方法實際應用到企業(yè)生產(chǎn)中，并取得了一定的成果，從而證明了運用遺傳算法進行項目調(diào)度優(yōu)化的可行性。他的優(yōu)點在于采用啟發(fā)式群體隨機搜索的方法，在搜索的過程中不易陷入局部最優(yōu)。但是其缺陷是局部搜索能力較差并容易早熟收斂。一種求解資源受限項目調(diào)度的遺傳算法杜焱、彭武良在文中求解使用可更新資源的單模式資源受限項目調(diào)度問題的遺傳算法。同樣是求解最小化的項目工期。在繼承了基于排列和基于優(yōu)先級的編碼方案的優(yōu)點，提出了一種新的基于優(yōu)先權排

17、列的編碼方案。采用了串行調(diào)度方法生成項目計劃。文中解釋了遺傳算法的思想。把問題的解表示成“染色體”在執(zhí)行進化之前，給出一群“染色體”，即種群。然后，按照適者生存的原則，從中選擇出較適應環(huán)境的“染色體”進行復制，再通過交叉，變異過程產(chǎn)生更適應環(huán)境的新一代。這樣一代一代進化，就會收斂到最適應環(huán)境的一個染色體。就是問題的最優(yōu)解。較之于楊利宏等10在對于遺傳算法在項目調(diào)度中的應用，本文的亮點在于提出了一種新的基于優(yōu)先權的編碼方案。染色體中包含兩種信息：位置和值。這種方法保留了基于優(yōu)先權編碼的優(yōu)點，同時這種方法可以達到搜索空間更小的目的。在解碼方案中，采用了基于串行調(diào)度算法進行對染色體的解碼并生產(chǎn)項目計

18、劃。調(diào)度過程被分為n 個階段，每個階段只調(diào)度一個活動，并包含了已調(diào)度集和決策集。在解碼過程中，需要從決策集中選擇活動，優(yōu)先權值較高的活動將優(yōu)先被選擇，并得到更早的調(diào)度。ü 運用遺傳算法優(yōu)化項目中現(xiàn)金流問題的研究 前面提到的算法的應用都是為了解決工期最小化問題。但是在實際生產(chǎn)過程，往往會伴隨著現(xiàn)今的流入和流出，現(xiàn)金流的凈現(xiàn)值很多時候都更能夠真實地反映企業(yè)的盈利狀況。徐柏群等將遺傳算法運用到現(xiàn)金流的優(yōu)化問題上?？紤]到項目的間接費用與獎懲機制，給出了模型的形式化描述，還討論了里程碑事件支付和相等事件間隔支付兩種常見的支付模式。并通過數(shù)值進行不同支付模式的調(diào)度結果的比較。本文采用的遺傳算法的

19、流程大體如下圖所示：這個流程與楊利宏，楊東10利用遺傳算法解決工期最小化問題的最主要區(qū)別在于不用進行從搜索空間到遺傳空間的轉換。這是由于現(xiàn)金流中解決的是最大值問題，而在遺傳算法中能保持良好生存能力的個體是適應度大的個體，本身就是一個最大值問題文中交叉算子采用的是MCUOX,優(yōu)點是染色體經(jīng)過交叉后仍能保持優(yōu)先關系的約束。變異操作包含了針對活動的變異和針對模式的變異。在調(diào)度方面，文中給出對于一個給定的可調(diào)度的基因序列，在計算該染色體的適應值之前，應該先對染色體上的活動進行調(diào)度，計算各活動的開始執(zhí)行時間、結束時間以及AOA活動圖中各事件的發(fā)生時間。從而由目標函數(shù)確定適度值函數(shù)：式中：當前種群中第i個

20、染色體的適應值；該染色體的目標函數(shù)值；當前種群最小的目標函數(shù)值。文中還通過實驗算例得出了一些結論：（1）PEO和ETI兩種支付模型的比較。二者的差別主要在于PEO模式下的支付在給定的一組里程碑事件上，而在ETI模式下則每相等時間間隔發(fā)生一次支付。由于現(xiàn)金具有時間價值，PEO模式下的調(diào)度方案往往會使支付時間提前。兩種模式生成的最優(yōu)調(diào)度一般都具有早期支付行為涉及的支付量較大，后期支付行為的支付量相對較小的特點。（2）獎懲機制的作用分析：算例中得出，由于獎懲機制的左右，項目的平均工期都比沒有獎懲機制下的要短，很多還能提前完工獲得獎勵。（3）遺傳算法的有效性分析：在對各個算例分別進行的50 次實驗中，

21、遺傳算法所得到的NPV最優(yōu)值的平均值遠大于隨機搜索算法在所有測試中所能得到的最大NPV，并且性能差距隨著實例規(guī)模的擴大而進一步增大。ü 遺傳、模擬退火算法結合喻小光等提出：遺傳算法是一種較易避免陷入局部最小的并行搜索，但是局部搜索能力較差并容易早熟收斂是其致命的弱點。相反的，模擬退火是一種具有很強的搜索能力并以穩(wěn)定的速度收斂的局部搜索技術?；诖?，在“應用遺傳模擬退火算法實現(xiàn)資源受限項目調(diào)度”一文中，他們將模擬退火嵌入遺傳算法中，提出了“遺傳模擬退火算法（Genetic Simulated Annealing Algorithm,GSA ）.GSA繼承了二者的優(yōu)點，因此在文中提出了一

22、種基于GSA的混合元啟發(fā)式方法RCPSPGSA用于解決以最小化項目工期為目標的RCPSP.該算法的大體框架如下：初始化算法參數(shù)產(chǎn)生初始種群評估初始種群，令Best=當前最優(yōu)解，K=0如果終止條件滿足，調(diào)入11（終止條件為：進化迭代次數(shù)達到預設值或最優(yōu)解持續(xù)N次迭代沒有發(fā)生改變）選擇、交叉、變異操作產(chǎn)生具有種群個體數(shù)量個個體的臨時下代種群，該種群中個體將作為SA的初始解。計算、更新Best.使用固定步長SA改進臨時下代種群中的每個個體。更新Best令K=K+1,t=t,轉入4（是退溫速率） 本文通過數(shù)值實驗分析，引入正交實驗分析法解決參數(shù)組合選擇問題。實驗的結果證明該方法選擇的參數(shù)組合具有突出的

23、性能。但是該方法的一個缺點是比較耗時，所以將來主要著眼于提高RCPSPGSA的時間性能。2.2.2.2.2蟻群算法(ACO)蟻群算法是超啟發(fā)式算法中常用來解決RCPSP的一類算法。Ø 基于蟻群優(yōu)化算法的資源受限項目調(diào)度的問題研究”焦超在文中對幾種重要的求解RCPSP的方法進行了比較，總結概括蟻群算法的演技現(xiàn)狀及應用領域，討論了該算法用于資源受限項目調(diào)度問題的基本思路。在此基礎上設計了一種基于蟻群優(yōu)化算法的單執(zhí)行模式資源受限項目調(diào)度問題優(yōu)化算法。作者在闡述蟻群優(yōu)化算法的基本思想之前，總結昆蟲學家的一個發(fā)現(xiàn)：自然界的螞蟻能在沒有任何可見提示下找出從蟻穴出發(fā)到食物源的最短路徑。在此過程中，

24、螞蟻會分泌一種化學物質(zhì)信息素。這種信息素遺留在螞蟻走過的路徑上，為其他螞蟻指引移動方向。螞蟻總是趨向于向信息素強度高的方向移動。從而經(jīng)過螞蟻多的路徑對后來的螞蟻越有吸引力。這一路徑的過程被成為螞蟻的自催化行為。 ACO的基本思想就是通過構造具有類似真是蟻群尋徑特點的人工蟻群來實現(xiàn)對解空間的搜索，最終在正反饋的作用下集中到最優(yōu)解上。文中就ACO指出其缺點在于信息素缺乏，進化速度慢，在解決較大規(guī)模時候很難在可接受的計算成本和時間內(nèi)找到最優(yōu)解。因此作者又介紹了幾種改進算法如：a) 帶精英策略的螞蟻系統(tǒng)使螞蟻系統(tǒng)在較短時間內(nèi)找出優(yōu)化解b) 蟻群系統(tǒng)采用了能反映問題特點的狀態(tài)轉移規(guī)則 采用了效率更高的全

25、局更新規(guī)則 引入新的信息素更新方式c) 最大最小螞蟻系統(tǒng)d) 蟻群算法與其他優(yōu)化算法的融合。比較有代表性的有ACO與GA的結合、ACO與免疫算法的結合等等。在前面有提到遺傳算法與模擬退火結合來解決資源受限項目調(diào)度問題，算法的結合使用也是將來RCPSP研究的一個方面，可以結合多方面的優(yōu)點提出更優(yōu)的解法。在將蟻群算法應用到RCPSP問題中時，作者認為需要解決兩個關鍵問題，一是構建既適合算法需要、又能反映問題特征的螞蟻巡游路徑；二是選擇恰當?shù)男畔⑦x策略。蟻群算法的流程如下：所有人工螞蟻從工作1出發(fā)開始搜索過程。通過反復應用狀態(tài)轉移規(guī)則并在滿足資源約束的最早時刻調(diào)度下一工作構建項目調(diào)度計劃，知道項目收

26、尾工作。在搜索過程有兩次信息更新，局部更新和全局更新。局部更新使路徑上的信息素不斷揮發(fā)，有利用探索新解，擴大對解空間的搜索。全局更新體現(xiàn)了最優(yōu)路徑保持策略。進一步的，文中根據(jù)正交法設計實驗，并采用項目調(diào)度標準問題庫中的基準問題進行試驗，證明了算法的有效性，并通過對計算結果的分析得到了算法的優(yōu)化解參數(shù)設置。綜觀全文，運用蟻群算法的優(yōu)越性在于其不對問題的數(shù)學特性作具體的要求。求解的速度較快。但是文中并沒有就信息素和啟發(fā)式信息策略較好的聯(lián)系起來。接下來的探索應該放提高在更能反映RCPSP特征的信息素和啟發(fā)式信息策略的算法性能。Ø 蟻群算法應用到以現(xiàn)金流最大化為目標的項目調(diào)度問題，劉秋蓮在文

27、中以優(yōu)化現(xiàn)金流為目標，對多模式資源約束型折現(xiàn)流時間-費用權衡項目問題進行調(diào)度（MRCTCTPDF），首次將蟻群算法成功用于工程項目的現(xiàn)金流優(yōu)化。在設計了新的蟻群算法構建方法和基于現(xiàn)金流凈現(xiàn)值的啟發(fā)式，同時充分考慮了活動的優(yōu)先關系、資源約束、項目執(zhí)行過程中的各項資金流以及資金的時間價值因素，使項目的凈現(xiàn)值最大化比較真是全面反映了工程項目進行過程中的現(xiàn)金流狀況。 基于MRCTCTPDF的特點，建立出非線性整數(shù)規(guī)劃模型，要求收益最大，從而確定目標函數(shù)。在此基礎上，確定算法。算法主要由兩個嵌套循環(huán)組成，內(nèi)循環(huán)是讓每只螞蟻從一個活動移動到另外一個活動，外循環(huán)是讓每只螞蟻完成一趟遍歷之后重新開始新的遍歷。

28、框架如下： 當螞蟻遍歷完所有的活動后，根據(jù)目標函數(shù)，對這次遍歷計算凈現(xiàn)值，每次新的遍歷得到新的NPV后都要與之前得到的最優(yōu)解比較，保留大者。本文將蟻群算法應用到項目調(diào)度現(xiàn)金流最大化的問題中，是對蟻群算法應用領域的一個拓展。蟻群算法在工程項目現(xiàn)金流優(yōu)化方面具有很強的優(yōu)勢。體現(xiàn)在：其全局收斂、并行性、不對問題的數(shù)學特性作具體要求、求解速度快，已經(jīng)在以最短工期為目標的RCPSP中取得成功。同時蟻群算法屬于構建性算法，算法的解是通過啟發(fā)式逐步生成的，這與現(xiàn)金流貫穿整個項目過程的特性相同。本文的不足之處在于蟻群算法的表現(xiàn)對于參數(shù)設置十分敏感，但是文中并沒有找到有效的方法來解決參數(shù)設置的問題。只是根據(jù)經(jīng)驗

29、和反復實驗來獲得參數(shù)。這方面也是將來研究中重點考慮的問題。2.2.2.2.3關鍵鏈法關鍵鏈方法是在約束理論基礎上發(fā)展起來的一種項目進度計劃技術，作為一種全新的項目管理哲學，已經(jīng)引起眾多學者的關注和探索。以下集中介紹各文獻中從不同角度對關鍵鏈在項目計劃調(diào)度方面的研究。ü 關鍵鏈項目計劃調(diào)度方法研究張靜文等首先介紹關鍵鏈近五年的研究概況，其次從多個角度闡述關鍵鏈對傳統(tǒng)項目計劃調(diào)度方法CPM/PERT的改進之處，最后提出確定輸入緩沖量最小值的方法。文中總結關鍵鏈對CPM/PERT的改進之處在于以下幾點：（1）對資源的看法不同。CPM/PERT假定資源供給無限，因而安排項目僅考慮活動時間的優(yōu)

30、先關系約束?，F(xiàn)實中資源總是稀缺的，關鍵鏈技術最大改進之處就是考慮到資源的有限性，活動的安排受到優(yōu)先關系和資源約束的雙重限制。（2） 對人行為特征的認識不同。CPM/PERT從純技術性角度追求計劃的科學性及完美性，忽視人心理因素對項目進度所產(chǎn)生的影響，體現(xiàn)為CPM估計的活動工期中包含大量安排富余時間，在“學生綜合癥”的影響下，又浪費了原本的富余時間。關鍵鏈方法考慮到上述人的行為特征，以活動50%的CPM時間作為其估計的執(zhí)行時間來安排項目進度計劃，有效避免“學生綜合癥”。（3）對風險的態(tài)度不同。CPM/PERT以90%甚至更大的概率估計活動工期，蘊含的風險極小，導致了收益小。關鍵鏈方法以50%的可

31、能完成時間作為估計的活動執(zhí)行時間，同時通過設置項目緩沖、匯入緩沖以及資源緩沖將項目不確定因素在項目系統(tǒng)內(nèi)部“消化”。所以關鍵鏈是站在全局角度考慮項目執(zhí)行的風險，而非僅僅考慮單個活動的風險。（4）在網(wǎng)絡圖中的表現(xiàn)形式不同。關鍵路徑是一條從起始節(jié)點到終止節(jié)點的通路，路徑不止一條。而關鍵鏈是考慮活動邏輯關系和資源沖突后制約整個項目周期的一個工作序列，往往不是一條通路。（5）確定過程不同。CP一次即可確定，而確定關鍵鏈是一個循環(huán)往復，不斷優(yōu)化的過程。當資源限量變化時，關鍵鏈需要重新確定。 在關鍵鏈中緩沖區(qū)的確定，作者的見解獨到。目前緩沖區(qū)尺寸的確定都可以認為是最大值，本文提出了存在緩沖區(qū)尺寸最小值的說

32、法。歸結起來，即項目緩沖最小值可以是0，但是對于輸入緩沖來說，即使所有非關鍵工序均無拖延，由于工序間邏輯關系及資源沖突，輸入緩沖的最小值也不能為0.文中舉例說明了這一點。得出的結論是最小輸入緩沖由PB=0時項目的最優(yōu)調(diào)度計劃確定，各條非關鍵鏈的最小緩沖值在最優(yōu)調(diào)度計劃時整條非關鍵鏈的浮動時差。實際中，項目進度通常居于最大值和最小值之間。由此編制的項目進度計劃不是一個確定的時間點計劃，而是一個進度區(qū)間計劃，保證了編制的進度計劃具有應付不確定環(huán)境的柔性。如下圖所示：ü 關鍵鏈技術在RCPSP問題中的應用研究韓文民，龔悄巧采用遺傳算法，提出一種關鍵鏈的識別方法，得到一條近優(yōu)的關鍵鏈。在項目

33、緩沖的設置方面，既考慮了關鍵鏈自身的因素，又考慮非關鍵鏈對其影響。通過對資源受限項目調(diào)度問題的典型案例求解，較為詳盡地描述了方法的具體應用過程。 文中指出現(xiàn)有的識別關鍵鏈算法常為啟發(fā)式算法，其缺點在于難以處理大規(guī)模問題而且效率低。所以本文采用了遺傳算法進行關鍵鏈的識別。具體步驟可以用以下的流程圖來表示。使用遺傳算法來確定關鍵鏈，文中對比研究發(fā)現(xiàn)該方法能更好的降低項目周期，具有更好的實用性。在對于緩沖的數(shù)量確定，提到目前的緩沖量的設置方法都將匯入緩沖和、項目緩沖分別對待，但是作者認為二者是有密切的聯(lián)系的。一旦某匯入緩沖不足以抵消該非關鍵鏈帶來的延誤影響，則此時這種影響最終還是由項目緩沖來消解。所

34、以根據(jù)中心極限定律，每條鏈路的實際執(zhí)行時間可以視為服從正態(tài)分布：而緩沖量的大小設置于完工期望有關 ü 基于關鍵鏈的柔性資源受限項目調(diào)度問題研究羅榮桂等介紹了關鍵鏈法的基本思想。分別提到了約束理論、項目工期估計、緩沖區(qū)機制。接著在傳統(tǒng)關鍵路徑方法的基礎上確定關鍵鏈。最后將關鍵鏈運用到柔性資源約束的項目調(diào)度中并通過實例求解。關于項目工期的估計，文中考慮到許多不確定性因素的存在，加入了大量的安全時間，采用低風險（90%概率完工）的估計時間。前面的闡述中，有提到采用90%完工率的估計時間其實會因為“學生綜合征”的現(xiàn)象存在而浪費很多不必要的時間，這也是本文的一個缺點。對于緩沖區(qū)機制，按照風險聚

35、合原理引入的項目緩沖(PB)、匯入緩沖(FB)及資源緩沖(RB)。CCM將關鍵鏈活動的安全儲備以PB的形式轉移到關鍵鏈之后，在任何非關鍵鏈與關鍵鏈處加入?yún)R入緩沖FB。RB是一種虛活動，插入在需要關鍵資源的關鍵鏈任務之前。作者以關鍵路徑的時間長度為目標，提出了一種確定關鍵鏈的改進方法。a) 確定項目網(wǎng)絡圖的關鍵路徑b) 確定初始可行集c) 從可行集中安排關鍵路徑上的活動d) 調(diào)動初始可行集的其他活動（考慮資源的供應和需求）e) 以最早完成的活動時刻為下一個決策點，確定新的可行集合，根據(jù)最早開始和最晚結束時間確定關鍵鏈本文中將這一方法運用到柔性資源約束的項目調(diào)度，主要考慮人力資源的柔性。提出在一定

36、的資源柔性度下，如何合理分配柔性資源使項目既滿足工序先后約束又滿足項目活動對不同資源技能的需求，并通過優(yōu)化方法使項目的總工期 文中用此方法來解決具有柔性資源受限的項目調(diào)度問題，確實達到了優(yōu)化項目工期的目的。但是，項目管理的實施是一個非常復雜的過程，需要考慮到不同的環(huán)境，以及項目運行的成本，風險問題，如何平衡這些不確定因素進行資源配置來優(yōu)化系統(tǒng)的績效將是研究的重點。2.2.2.2.4項目調(diào)度問題的拓展研究前面提到對于RCPSP的分類中，按目標可以分為項目工期最小化、現(xiàn)金流最大化以及資源均衡的項目調(diào)度。按模式可以分為單模式和雙模式。在前面的闡述中，只涉及到在單執(zhí)行模式下，以項目工期最小化、現(xiàn)金流最

37、大為目標的項目調(diào)度問題。實際上，很多學者在資源受限項目調(diào)度的更多方面都有不少的研究。下面就這些研究來對RCPSP問題進一步的闡述。RCPSP目標的研究單淚源等17在針對資源受限下的項目資源均衡問題的自身特點及其與傳統(tǒng)資源受限項目調(diào)度問題的相似之處，設計了一種以優(yōu)先值法作為粒子表達資源均衡問題的粒子群優(yōu)化算法。在對資源受限的項目調(diào)度中資源均衡問題進行描述后，作者采用了資源需求量方差為指標，這一目標值越小，即均衡效果越好?；诖私LP的數(shù)學模型。 在將粒子群算法用來解決RLP 問題時，文中指出取優(yōu)先值法來表達粒子的內(nèi)容。粒子的每個維度代表一個活動的優(yōu)先級大小。同時采用并行進度的生成機制。將RL

38、P轉換成RCPSP的方式。算法可以在較少次數(shù)的迭代后找出最優(yōu)解。 在一般的情況下，我們研究的都是實現(xiàn)單一目標的資源受限項目調(diào)度問題。那么，有可能對多目標資源受限項目進行調(diào)度嗎？劉士新、宋健海19就設計了一種求解模糊多目標資源受限項目調(diào)度問題的遺傳局域搜索(GLS)算法，目標就是生成近似有效解集，以便決策者在決策過程中有更多的選擇。算法利用線性加權效用函數(shù)將多目標組合優(yōu)化問題轉換為單目標組合優(yōu)化問題。通過系統(tǒng)的方法生成目標權系數(shù)向量，對于每次生成的權系數(shù)向量，調(diào)用GLS算法求解以極小化效用函數(shù)為單一目標的子問題，由此生成的近似有效解集更具有多樣性。這是在考慮實際項目中，需要考慮的通常不僅僅是單一

39、的目標，應該要在工期、現(xiàn)金流、資源以及其他更多方面進行權衡，選擇最佳的組合來完成項目。多目標的項目調(diào)度問題應該成為研究的重點。多項目的RCPSP問題研究 資源受限項目調(diào)度問題按照所研究的項目數(shù)目可以分為資源受限的單項目調(diào)度問題（rc-sPSP）和資源受限的多項目調(diào)度問題(rc-mPSP).對于單項目的研究，國內(nèi)外學者已經(jīng)取得很多的成果，相比之下，多項目的研究就較少。羅榮桂等19就國內(nèi)外關于多項目調(diào)度問題的現(xiàn)狀進行研究。這方面的研究中，有些學者試圖用解決單項目的方法來求解多項目問題。成為“單項目” 方法。通過增加虛擬的源節(jié)點和尾節(jié)點來將多個單項目人工連接成一個大項目。求解多項目調(diào)度問題的啟發(fā)式算

40、法大部分可以歸結為基于優(yōu)先規(guī)則的方法。而這些規(guī)則的效果則有很大的不同。文中舉例說明了這點。在對于啟發(fā)式進行改進后，提出了往復式的前向-后向調(diào)度算法，用于改進可行解。 遺傳算法、模擬退火等元啟發(fā)式算法在多項目調(diào)度中應用極少，有關學者提出帕累托模擬退火和日光束搜索方法來描述和量化資源受限的多個項目活動的交叉影 響,并取得了較好效果。 對于多項目的調(diào)度問題，作者認為有待深入研究的在于：單項目調(diào)度問題有一個公認的標準問題庫 PSPL IB ( Kolisch and Sp recher , 1996 ) 和PSPL IB/ max ( Christop h Schwindt , 1998) , 因此各

41、類算法可以方便地進行相互比較 ,也可以與問題的最優(yōu)解或已知最好解來進行比較 ,從而判斷算法的優(yōu)劣 1819 。對于 rcmPSP ,則缺乏這樣公認的問題庫 ,難以判斷算法的優(yōu)劣。rcmPSP 的問題庫 ,將是今后的一個重要研究課。 RCPSP其他方面的研究此外，在單執(zhí)行模式資源受限的工程調(diào)度問題的擴展下，劉士新等研究了多執(zhí)行模式工程調(diào)度的優(yōu)化算法。雒興剛, 汪定偉 ,唐加福結合企業(yè)實際的項目調(diào)度，在任務不可拆分的經(jīng)典資源受限項目調(diào)度問題的基礎上針對任務可拆分的項目調(diào)度問題提出了總項目工期最短的數(shù)學模型。梁燕、金燁針對緊急事件調(diào)度的緊迫性特點，建立了一種基于資源約束的啟發(fā)式項目調(diào)度方法，并將該方法與關鍵鏈法結合確定最終的調(diào)度方案。3、總結及展望3.1本文總結 作為項目管