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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

37、。實際上，很多學者在資源受限項目調度的更多方面都有不少的研究。下面就這些研究來對RCPSP問題進一步的闡述。RCPSP目標的研究單淚源等17在針對資源受限下的項目資源均衡問題的自身特點及其與傳統資源受限項目調度問題的相似之處，設計了一種以優先值法作為粒子表達資源均衡問題的粒子群優化算法。在對資源受限的項目調度中資源均衡問題進行描述后，作者采用了資源需求量方差為指標，這一目標值越小，即均衡效果越好。基于此建立RLP的數學模型。 在將粒子群算法用來解決RLP 問題時，文中指出取優先值法來表達粒子的內容。粒子的每個維度代表一個活動的優先級大小。同時采用并行進度的生成機制。將RLP轉換成RCPSP的方

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

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

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

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