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

2、urcc-constrainedproject-schedulingproblem)是一個重要的優化問題，它是最多見的生產調度問題，是項目管理中最為經典和核心的問題之一1項目調度進展進程項目調度問題自20世紀中期被提出來，傳統的計劃技術有甘特圖(又稱橫道圖，GantCharl,Ge)、關鍵活動圖、網絡計劃技術。幾種典型的網絡計劃技術有：關鍵路徑發(CriticalPathMethod,CPM)項目計劃評審技術(ProgramEvaluationandReviewTechnique,PERT)優先圖方式(PDM)、圖解評審技術(GraphicalEvaluationandReviepGERT)、

3、風險評審技術(VentureEvaluationandReviewTechnique,VERT).最初被普遍應用于項目進度計劃的工具是甘特圖技術，它用二維坐標的形式，用線條在二維空間中表似乎出整個項目期間計劃和實際的活動完成情形，直觀表明項目中所含各項活動的執行順序，和每項活動的開始/結束時刻和持續時刻。該方式形象直觀，易于掌握，可是不能表現工作間的彼此依賴關系，不能表現工作過早開始或過完開始所造成的后杲。20世紀50年代中期進展起來的網絡計劃技術迅速滲透到項目調度領域,以網絡圖的形式來表示項目進度計劃。它能明確反映各活動時刻的前后順序和彼此制約的邏輯關系，通過計算時刻參數，可找出計劃中的關鍵

4、活動及關鍵線路,反映出各活動的時差。其思想是通過緊縮關鍵工作線路的持續時刻，從而使工程的工期、費用實現優化。具有代表性的是關鍵路徑法與計劃評審技術。兩種方式都是采用平面網絡結構表示項目的工作細分結構，專門好的反映了項目組成各工作之間的時序依賴關系。二者的卻別在于對項目各工作的執行時刻的估量方式。關鍵路徑發采用一點估量法，直接按照歷史數據和以往經驗給出唯一的估量值，不考慮不肯定性因素。這種方式可能會造成與項目實際情形的較大誤差。評審技術進行了必然的改良，采用三點估量法，即以經驗豐碩的項目管理者所掌握的完成一項工作所需要的可能最少時刻、可能最多時刻及最大可能時刻為基礎，來取得估量執行時刻。通過數理

5、統計的大體理論，對項目進度進行了定量分析，能夠取得較高的計劃。可是這兩種方式有一個一路的缺點，就是沒有考慮資源約束，這與實際情形不符合，由此便產生了資源受限項目調度問題。2資源受限項目調度問題研究現狀資源受限項目調度問題描述任何項目的策劃和執行都包括大量不同的活動及各類人力、物力資源。在項目活動的組織安排總，有些活動是能夠同時進行的，有些活動則是必需在其他若干活動完成以后才能進行的。同時，每項活動本身還需要必然的持續時刻，且利用不同類、不同數量的資源如機械設備、物資材料、勞動力等。資源是項目執行進程中不可缺少的重要組成部份，而這些資源的有效可用量往往具有局限。如何以最佳方式安排執行項目中的各個

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

7、一種有限的資源，問題是如何分派這些資源才能實現最優的管理目標?這些目標可能是:工程的工期最短，工程拖期最少，工程拖期懲罰最小，工程的凈收益最大等。總而言之，RCPSP問題是研究具有優先關系約束活動的項目在資源受限的條件下使某些管理目標最優的調度問題資源受限項目調度問題研究內容的類型自從資源第一項目調度問題提出以來，已經出現了種類繁多的RCPSP問題。辛潤勤依照以下幾個方面對資源受限項目調度問題進行分類按照項目調度目標分類（1）最小化項目工期：（3）最大化項目凈現值（4）資源均衡問題按照資源類型分類（1）非可再生資源：資源的可利用量在整個項目工期內具有約束，一旦消耗完就不能再生。（2）可再生資源

8、：資源的可利用量在項目中每一階段內受到約束，某階段的數量有限，但利用以后被釋放能夠再生。（3）雙重資源約束：資源的可利用量既在整個項目工期內具有約束，而且在項目工期中的每一個時刻段內受到約束。依照模型的不同分類（1）單執行模式資源約束項目調度問題：每項活動只有一種執行模式，消耗必然的資源在一個給定的加工時刻內完成。（2）多執行模式資源約束項目調度問題：運行活動能夠以多種執行模式之一進行操作，每種執行模式對應一種資源組合和相應的活動執行時刻。資源受限項目調度問題求解方式研究資源受限的工程調度問題在現代企業中顯示出愈來愈重要的研究價值。隨著最優化技術的不斷進展，國內外學者陸續提出了一系列性能優良的

9、優化算法，并將這些算法應用于解決項目調度問題。劉士新等按照搜集到的資料，對這些算法進行歸納并概述。算法概述解決資源受限項目調度這種問題的方式能夠分為兩類，一是致力于取得最優解的精準算法，另一類就是啟發式算法。常常利用于求解RCPSP的主要精準算法有線性計劃（linearprogramming）和分枝限界法（branchandbound）,精準算法的研究主如果集中在利用數學計劃問題來對項目調度進行公式化的求解，這種算法雖然在某些程度上能夠取得精準解乃至是最優解.，但它只能解決中小項目的調度。隨著問題規模的擴大，肯定性算法的求解時刻將以指數級的速度增加。因此啟發式算法求解RCPSPo何正文等在“求

10、解資源約束項目調度問題的啟發式算法綜述”一文中，論述了求解RCPSP的啟發式算法。第一在對各類優先權規則進行歸納的基礎上，概述基于優先權規則的RCPSP啟發式算法研究現狀;第二,綜述項目進度的表述方式及常常利用超啟發式策略，匯總求解RCPSP的超啟發式的研究功效。基于優先權規則的啟發式算法基于不同的優先權規則從可安排活動集合當選擇活動，從而將部份進度擴展為滿意的完全進度。常常利用的優先權規則主要有以下幾種：最大分級位置權重規則、最遲完成時刻規則、最多緊后活動規則、最遲開始時刻規則、最小松弛規則。同時還擴展出多通道算法，如：多重優先權規則啟發式算法、前向-后向進度安排啟發式算法、抽樣性啟發式算法

11、、適應性啟發式算法等等。超啟發式算法該類算法將項目進度表述為一組編碼，利用超啟發式策略對編碼進行搜索優選后，再轉化為進度安排。進度安排常常利用的表述方式有活動列表、隨機鍵、轉移向量、進度設計、直接表述。文中總結出求解RCPSP常常利用的啟發式策略有模擬退火、禁忌搜索、遺傳算法和等等。模擬退火：從某個初始解開始，一個鄰點通過對當前解的擴展來生成。若是鄰點好于當前解則被同意;不然，它以必然的概率被同意，同意概率依賴于該解變壞的程度和當前的溫度參數。隨著算法的進行，溫度被慢慢降低以減小同意壞的鄰點的概率。達到規定的溫度后算法終止，最后固定下來的解即為滿意解.。禁忌搜索：對于所有鄰點解進行評價并選擇其

12、中最好的一個進行進一步的搜索。為了避免搜索返回方才離開的局部最長處而形成循環，通過成立一個禁忌列表來限制向某些鄰點的移動。這種禁忌狀態在某種特定的條件下也能夠被從頭激活。遺傳算法：并行地考慮解的一個集合或群體，在已生成的初始群體的基礎上,新的解通過交叉和/或變異操作來取得。在新解生成后，適應度通常常利用所求解問題的目標函數來表示最高的解“生存”下來組成下一代，而其余的解通過所謂的選擇機制被淘汰，從而使解的質量不斷得到改善。同時還提出了其他類型的啟發式算法如蟻群算法、可變鄰點搜索技術等等。結合其他學者的觀點，超啟發式算法被普遍以為是在性能、可擴展性和易于實現性等方面衡量后的最佳方式。是目前學者們

13、研究資源受限項目調度問題最常常利用的方式另外，以色列學者高德拉特將約束理論(TheoiyofConstraint.TOC)應用于項目管理領域，提出了基于關鍵鏈的項目管理理論，從中進展出一種新的項目調度理論：基于關鍵鏈的項目調度理論啟發式算法在RCPSP問題中的應用下面第一基于一些比較典型的超啟發式算法(遺傳算法、蟻群算法、模擬退火)模型和關鍵鏈法結合一些文獻進行整理和綜述，并提出自己的觀點。遺傳算法遺傳算法(GeneticAlgorithm)是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化進程的計算模型，是一種通過模擬自然進化進程搜索最優解的方式。資源受限項目調度求解的是工期最小、凈現值

14、最大等一些最優解.，所以能夠運用遺傳算法來求解。/基于遺傳算法的資源約束型項目調度優化楊利宏等網基于遺傳算法，著重討論優化資源有限一工期最短問題。該優化進程是在多資源約束下，通過檢索隨機生成的活動調度挑選出資源約束下最小工期的調度方式。最后通過某公司的電腦橫機研發項目為研究對象，針對多資源約束的項目計劃和調度問題，采用遺傳算法優化項目的調度方式。整個遺傳算法的流程如下圖所示。在進行優化計算前，第一完成從搜索空間到遺傳空間的轉換，進行兩方面的工作：（1）將目標函數轉換成適度函數，即將最小值問題通過比例運算轉化成最大值問題。（2）染色體編碼，通過基于隨機優先權把實際的AON網絡轉換成項目活動的調度

15、。按照適應度函數，計算適度值。接下去是在遺傳空間上進行選擇、交叉、變異，明白找到最優解。選擇：在這基礎上，按照計算出來的適度值，采用輪盤賭操作進行選擇，選擇出需要繁衍的父代群體。那個進程就是“選擇操作”交叉：本文采用兩點交叉的運算模式，為了不產生重碼，文中提出了基于位置映射關系的兩點交叉。既能夠保證不重復，也能夠專門好地保證個體的繼承性。變異：采用基于中心位置的變異。分為四步：計算變異基因的個數U、生成U個隨機數作為基因的變異、定位到相關的染色體、采用中心位置變異的方式，隨機與本染色體內的其他等位基因調換數值，從而生成新的染色體。作者將該方式實際應用到企業生產中，并取得了必然的功效，從而證明了

16、運用遺傳算法進行項目調度優化的可行性。他的長處在于采用啟發式群體隨機搜索的方式，在搜索的進程中不易陷入局部最優。可是其缺點是局部搜索能力較差并容易早熟收斂。一種求解資源受限項目調度的遺傳算法杜,淡、彭武良在文中求解利用可更新資源的單模式資源受限項目調度問題的遺傳算法。一樣是求解最小化的項目工期。在繼承了基于排列和基于優先級的編碼方案的長處，提出了一種新的基于優先權排列的編碼方案。采用了串行調度方式生成項目計戈h文中解釋了遺傳算法的思想。把問題的解表示成“染色體”在執行進化之前,給出一群“染色體”，即種群。然后，依照適者生存的原則，從當選擇出較適應環境的“染色體”進行復制，再通過交叉，變異進程產

17、生更適應環境的新一代。如此一代一代進化，就會收斂到最適應環境的一個染色體。就是問題的最優解。較之于楊利宏等10在對于遺傳算法在項目調度中的應用，本文的完點在于提出了一種新的基于優先權的編碼方案。染色體中包括兩種信息：位置和值。這種方式保留了基于優先權編碼的長處，同時這種方式能夠達到搜索空間更小的目的。在解碼方案中，采用了基于串行調度算法進行對染色體的解碼并生產項目計劃。調度進程被分為n個階段，每一個階段只調度一個活動，并包括了已調度集和決策集。在解碼進程中，需要從決策集當選擇活動，優先權值較高的活動將優先被選擇，并取得更早的調度。/運用遺傳算法優化項目中現金流問題的研究前面提到的算法的應用都是

18、為了解決工期最小化問題。可是在實際生產進程，往往會伴隨著現今的流入和流出，現金流的凈現值很多時候都更能夠真實地反映企業的盈利狀況。徐柏群等網將遺傳算法運用到現金流的優化問題上。考慮到項目的間接費用與獎懲機制，給出了模型的形式化描述，還討論了里程碑事件支付和相等事件距離支付兩種常見的支付模式。并通過數值進行不同支付模式的調度結果的比較。本文采用的遺傳算法的流程大體如下圖所示：那個流程與楊利宏，楊東10利用遺傳算法解決工期最小化問題的最主要區別在于不用進行從搜索空間到遺傳空間的轉換。這是由于現金流中解決的是最大值問題，而在遺傳算法中能維持良好生存能力的個體是適應度大的個體，本身就是一個最大值問題文

19、中交叉算子采用的是MCUOX,長處是染色體通過交叉后仍能維持優先關系的約束。變異操作包括了針對活動的變異和針對模式的變異。在調度方面，文中給出對于一個給定的可調度的基因序列，在計算該染色體的適應值之前，應該先對染色體上的活動進行調度，計算各活動的開始執行時刻、結束時刻和AOA活動圖中各事件的發生時刻。從而由目標函數肯定適度值函數：fiinesSt=叩以一碑TV"式中：儆當前種群中笫i個染色體的適應值；即韓-該染色體的目標函數值；礙"皿一一當前種群最小的目標函數值。文中還通過實驗算例得出了一些結論：（DPEO和ETI兩種支付模型的比較。二者的不同主要在于PEO模式下的支付在給

20、定的一組里程碑事件上,而在ETI模式下則每相等時刻距離發生一次支付。由于現金具有時刻價值，PEO模式下的調度方案往往會使支付時刻提前。兩種模式生成的最優調度一般都具有初期支付行為涉及的支付量較大，后期支付行為的支付量相對較小的特點。（2）獎懲機制的作用分析：算例中得出，由于獎懲機制的左右，項目的平均工期都比沒有獎懲機制下的要短，很多還能提前完工取得獎勵。（3）遺傳算法的有效性分析：在對各個算例別離進行的50次實驗中，遺傳算法所取得的NPV最優值的平均值遠大于隨機搜索算法在所有測試中所能取得的最大NPV,而且性能差距隨實在例規模的擴大而進一步增大。/遺傳、模擬退火算法結合喻小光等提出：遺傳算法是

21、一種較易避免陷入局部最小的并行搜索，可是局部搜索能力較差并容易早熟收斂是其致命的弱點。相反的，模擬退火是一種具有很強的搜索能力并以穩固的速度收斂的局部搜索技術。基于此，在“應用遺傳模擬退火算法實現資源受限項目調度”一文中，他們將模擬退火嵌入遺傳算法中,提出了“遺傳模擬退火算法（GeneticSimulatedAnnealingAlgorithm,GSA）.GSA繼承了二者的長處，因此在文中提出了一種基于GSA的混合元啟發式方式RCPSPGSA用于解決以最小化項目工期為目標的RCPSP.該算法的大體框架如下：初始化算法參數產生初始種群評估初始種群，令Best二當前最優解，K=0若是終止條件知足，

22、調入11（終止條件為：進化迭代次數達到預設值或最優解持續N次迭代沒有發生改變）選擇、交又、變異操作產生具有種群個體數量個個體的臨時下代種群，該種群中個體將作為SA的初始解。計算、更新Best.利用固定步長SA改良臨時下代種群中的每一個個體。更新Best令K=K+l,t尸；Itj,轉入4（4是退溫速度）本文通過數值實驗分析，引入正交實驗分析法解決參數組合選擇問題。實驗的結果證明該方式選擇的參數組合具有突出的性能。可是該方式的一個缺點是比較耗時，所以未來主要著眼于提高RCPSPGSA的時刻性能。蟻群算法（ACO）蟻群算法是超啟發式算法中常常利用來解決RCPSP的一類算法。基于蟻群優化算法的資源受限

23、項目調度的問題研究”焦超的在文中對幾種重要的求解RCPSP的方式進行了比較，總結歸納蟻群算法的演技現狀及應用領域，討論了該算法用于資源受限項目調度問題的大體思路。在此基礎上設計了一種基于蟻群優化算法的單執行模式資源受限項目調度問題優化算法。作者在論述蟻群優化算法的大體思想之前，總結昆蟲學家的一個發覺：自然界的螞蟻能在沒有任何可見提示下找出從蟻穴動身到食物源的最短路徑。在此進程中，螞蟻會分泌一種化學物質一一信息素。這種信息素遺留在螞蟻走過的路徑上，為其他螞蟻指引移動方向。螞蟻老是趨向于向信息素強度高的方向移動。從而通過螞蟻多的路徑對后來的螞蟻越有吸引力。這一路徑的進程被成為螞蟻的自催化行為。AC

24、O的大體思想就是通過構造具有類似真是蟻群尋徑特點的人工蟻群來實現對解空間的搜索，最終在正反饋的作用下集中到最優解上。文中就ACO指出其缺點在于信息素缺乏，進化速度慢，在解決較大規模時候很難在可同意的計算本錢和時刻內找到最優解。因此作者乂介紹了兒種改良算法如：a）帶精英策略的螞蟻系統一一使螞蟻系統在較短時刻內找出優化解b）蟻群系統一一采用了能反映問題特點的狀態轉移規則采川了效率更高的全局更新規則引入新的信息素更新方式C)最大一最小螞蟻系統d)蟻群算法與其他優化算法的融合。比較有代表性的有ACO與GA的結合、ACO與免疫算法的結合等等。在前面有提到遺傳算法與模擬退火結合來解決資源受限項目調度問題，

25、算法的結合利用也是未來RCPSP研究的一個方面，能夠結合多方面的長處提出更優的解法。在將蟻群算法應用到RCPSP問題中時，作者以為需要解決兩個關鍵問題，一是構建既適合算法需要、乂能反映問題特征的螞蟻巡游路徑；二是選擇適當的信息選策略。蟻群算法的流程如下：所有人工螞蟻從工作1動身開始搜索進程。通過反復應用狀態轉移規則并在知足資源約束的最先時刻調度下一工作構建項目調度計劃，明白項目掃尾工作。在搜索進程有兩次信息更新，局部更新和全局更新。局部更新使路徑上的信息素不斷揮發，有利用探索新解，擴大對解空間的搜索。全局更新表現了最優路徑維持策略。進一步的，文中按照正交法設計實驗，并采用項目調度標準問題庫中的

26、基準問題進行實驗，證明了算法的有效性，并通過對計算結果的分析取得了算法的優化解參數設置。綜觀全文，運用蟻群算法的優越性在于其不對問題的數學特性作具體的要求。求解的速度較快。可是文中并無就信息素和啟發式信息策略較好的聯系起來。接下來的探索應該放提高在更能反映RCPSP特征的信息素和啟發式信息策略的算法性能。蟻群算法應用到以現金流最大化為目標的項目調度問題，劉秋蓮M在文中以優化現金流為目標，對多模式資源約束型折現流時一刻-費用衡量項目問題進行調度(MRCTCTPDF),第一次將蟻群算法成功用于工程項目的現金流優化。在設計了新的蟻群算法構建方式和基于現金流凈現值的啟發式，同時充分考慮了活動的優先關系

27、、資源約束、項目執行進程中的各項資金流和資金的時刻價值因素，使項目的凈現值最大化比較真是全面反映了工程項目進行進程中的現金流狀況。基于MRCTCTPDF的特點，成立出非線性整數計劃模型，要求收益最大，從而肯定目標函數。在此基礎上，肯定算法。算法主要由兩個嵌套循環組成，內循環是讓每只螞蟻從一個活動移動到另外一個活動，外循環是讓每只螞蟻完成一趟遍歷以后從頭開始新的遍歷。框架如下：InitializeptkcromoncsLoopZtatthisleveleachloopiscalledaniteration*/InitializeantsLoop7eatthis1-cvcleachloopisca

28、lledstep*/solution-stepandlocallyupdatesthepheromoneUntilallantshavebuiltacompletesolutionGloballyupdatesthepberomonesUntilEek!condition當螞蟻遍歷完所有的活動后，按照目標函數，對這次遍歷計算凈現值，每次新的遍歷取得新的NPV后都要與之前取得的最優解比較，保留大者。本文將蟻群算法應用到項目調度現金流最大化的問題中，是對蟻群算法應用領域的一個拓展。蟻群算法在工程項目現金流優化方面具有很強的優勢。體此刻:其全局收斂、并行性、不對問題的數學特性作具體要求、求解速度快，

29、已經在以最短工期為目標的RCPSP中取得成功。同時蟻群算法屬于構建性算法，算法的解是通過啟發式慢慢生成的，這與現金流貫穿整個項目進程的特性相同。本文的不足的地方在于蟻群算法的表現對于參數設置十分敏感，可是文中并無找到有效的方式來解決參數設置的問題。只是按照經驗和反復實驗來取得參數。這方面也是未來研究中重點考慮的問題。關鍵鏈法關鍵鏈方式是在約束理論基礎上進展起來的一種項目進度計劃技術，作為一種全新的項目管理哲學，已經引發眾多學者的關注和探索。以下集中介紹各文獻中從不同角度對關鍵鏈在項目計劃調度方面的研究。關鍵鏈項目計劃調度方式研究張靜文等網第一介紹關鍵鏈近五年的研究概況，第二從多個角度論述關鍵鏈

30、對傳統項目計劃調度方式CPM/PERT的改良的地方，最后提出肯定輸入緩沖量最小值的方式。文中總結關鍵鏈對CPM/PERT的改良的地方在于以下幾點：（1）對資源的觀點不同。CPM/PERT假定資源供給無窮，因此安排項目僅考慮活動時刻的優先關系約束。現實中資源老是稀缺的，關鍵鏈技術最大改良的地方就是考慮到資源的有限性，活動的安排受到優先關系和資源約束的雙重限制。（2）對人行為特征的熟悉不同。CPM/PERT從純技術性角度追求計劃的科學性及完美性，輕忽人心理因素對項目進度所產生的影響，表現為CPM估量的活動工期中包括大量安排豐裕時刻，在“學生綜合癥”的影響下，乂浪費了本來的豐裕時刻。關鍵鏈方式考慮到

31、上述人的行為特征，以活動50%的CPM時刻作為其估量的執行時刻來安排項目進度計劃，有效避免“學生綜合癥、（3）對風險的態度不同。CPM/PERT以90%乃至更大的概率估量活動工期，包含的風險極小，致使了收益小。關鍵鏈方式以50%的可能完成時刻作為估量的活動執行時刻，同時通過設置項目緩沖、匯入緩沖和資源緩沖將項目不肯定因素在項目系統內部“消化”。所以關鍵鏈是站在全局角度考慮項目執行的風險，而非僅僅考慮單個活動的風險。（4）在網絡圖中的表現形式不同。關鍵路徑是一條從起始節點到終止節點的通路，路徑不止一條。而關鍵鏈是考慮活動邏輯關系和資源沖突后制約整個項目周期的一個工作序列，往往不是一條通路。（5）

32、肯定進程不同。CP一次即可肯定，而肯定關鍵鏈是一個周而復始，不斷優化的進程。當資源限量轉變時，關鍵鏈需要從頭肯定。在關鍵鏈中緩沖區的肯定，作者的觀點獨到。目前緩沖區尺寸的肯定都能夠以為是最大值，本文提出了存在緩沖區尺寸最小值的說法。歸結起來，即項目緩沖最小值能夠是0,可是對于輸入緩沖來講，即便所有非關鍵工序均無拖延，山于工序間邏輯關系及資源沖突，輸入緩沖的最小值也不能為0.文中舉例說明了這一點。得出的結論是最小輸入緩沖由PB=0時項目的最優調度計劃肯定，各條非關鍵鏈的最小緩沖值在最優調度計劃時整條非關鍵鏈的浮動時差。實際中，項目進度通常居于最大值和最小值之間。由此編制的項目進度計劃不是一個肯定

33、的時刻點計劃，而是一個進度區間計戈IJ,保證了編制的進度計劃具有應付不肯定環境關鍵鏈技術在RCPSP問題中的應用研究韓文民，龔悄巧網采用遺傳算法，提出一種關鍵鏈的識別方式，取得一條近優的關鍵鏈。在項目緩沖的設置方面，既考慮了關鍵鏈自身的因素，乂考慮非關鍵鏈對其影響。通過對資源受限項目調度問題的典型案例求解，較為詳盡地描述了方式的具體應用進程。文中指出現有的識別關鍵鏈算法常為啟發式算法，其缺點在于難以處置大規模問題而且效率低。所以本文采用了遺傳算法進行關鍵鏈的識別。具體步驟能夠用以下的流程圖來表示。利用遺傳算法來肯定關鍵鏈，文中對比研究發覺該方式能更好的降低項目周期，具有更好的實用性。在對于緩沖

34、的數量肯定，提到目前的緩沖量的設置方式都將匯入緩沖和、項目緩沖別離對待，可是作者以為二者是有緊密的聯系的。一旦某匯入緩沖不足以抵消該非關鍵鏈帶來的延誤影響，則現在這種影響最終仍是由項目緩沖來消解。所以按照中心極限定律，每條鏈路的實際執行時刻能夠視為服從正態散布：pf W%) = FIT"e dzcr而緩沖量的大小設置于完工期望有關PB =& f fL 'J J入.口 .=基于關鍵鏈的柔性資源受限項目調度問題研究羅榮桂等岡介紹了關鍵鏈法的大體思想。別離提到了約束理論、項目工期估量、緩沖區機制。接著在傳統關鍵路徑方式的基礎上肯定關鍵鏈。最后將關鍵鏈運用到柔性資源約束的項目

35、調度中并通過實例求解。關于項目工期的估量，文中考慮到許多不肯定性因素的存在，加入了大量的安全時刻，采用低風險（90%概率完工）的估量時刻。前面的論述中，有提到采用90%完工率的估量時刻其實會因為“學生綜合征”的現象存在而浪費很多沒必要要的時刻，這也是本文的一個缺點。對于緩沖區機制，依照風險聚合原理引入的項目緩沖(PB)、匯入緩沖(FB)及資源緩沖(RB)。CCM將關鍵鏈活動的安全儲蓄以PB的形式轉移到關鍵鏈以后，在任何非關鍵鏈與關鍵鏈處加入匯入緩沖FB。RB是一種虛活動，插入在需要關鍵資源的關鍵鏈任務之前。作者以關鍵路徑的時刻長度為目標，提出了一種肯定關鍵鏈的改良方式。a)肯定項目網絡圖的關鍵

36、路徑b)肯定初始可行集c)從可行集中安排關鍵路徑上的活動d)調動初始可行集的其他活動(考慮資源的供給和需求)e)以最先完成的活動時刻為下一個決策點，肯定新的可行集合，按照最先開始和最晚結束時刻肯定關鍵鏈本文中將這一方式運用到柔性資源約束的項目調度，主要考慮人力資源的柔性。提出在必然的資源柔性度下，如何合理分派柔性資源使項目既知足工序前后約束乂知足項目活動對不同資源技術的需求，并通過優化方式使項目的總工期文頂用此方式來解決具有柔性資源受限的項目調度問題，確實達到了優化項目工期的目的。可是，項目管理的實施是一個超級復雜的進程，需要考慮到不同的環境，和項目運行的本錢，風險問題，如何平衡這些不肯定因素

37、進行資源配置來優化系統的績效將是研究的重點。項目調度問題的拓展研究前面提到對于RCPSP的分類中，按目標能夠分為項目工期最小化、現金流最大化和資源均衡的項目調度。按模式能夠分為單模式和雙模式。在前面的論述中，只涉及到在單執行模式下，以項目工期最小化、現金流最大為目標的項目調度問題。實際上，很多學者在資源受限項目調度的更多方面都有很多的研究。下面就這些研究來對RCPSP問題進一步的論述。RCPSP目標的研究單淚源等17在針對資源受限下的項目資源均衡問題的自身特點及其與傳統資源受限項目調度問題的相似的地方，設計了一種以優先值法作為粒子表達資源均衡問題的粒子群優化算法。在對資源受限的項目調度中資源均

38、衡問題進行描述后，作者采用了資源需求量方差為指標，這一目標值越小，即均衡效果越好。基于此成立RLP的數學模型。在將粒子群算法用來解決RLP問題時,，文中指出取優先值法來表達粒子的內容。粒子的每一個維度代表一個活動的優先級大小。同時采用并行進度的生成機制。將RLP轉換成RCPSP的方式。算法能夠在較少次數的迭代后找出最優解。在一般的情形下，咱們研究的都是實現單一目標的資源受限項目調度問題。那么，有可能對多目標資源受限項目進行調度嗎？劉士新、宋健海19就設計了一種求解模糊多目標資源受限項目調度問題的遺傳局域搜索(GLS)算法，目標就是生成近似有效解集，以便決策者在決策進程中有更多的選擇。算法利用線

39、性加權效川函數將多目標組合優化問題轉換為單目標組合優化問題。通過系統的方式生成目標權系數向量，對于每次生成的權系數向量，挪用GLS算法求解以極小化效用函數為單一目標的子問題，由此生成的近似有效解集更具有多樣性。這是在考慮實際項目中，需要考慮的通常不單單是單一的目標，應該要在工期、現金流、資源和其他更多方面進行衡量，選擇最佳的組合來完成項目。多目標的項目調度問題應該成為研究的重點。多項目的RCPSP問題研究資源受限項目調度問題依照所研究的項目數量能夠分為資源受限的單項目調度問題(rc-sPSP)和資源受限的多項目調度問題(rc-mPSP).對于單項目的研究,國內外學者已經取得很多的功效，相較之下

40、，多項目的研究就較少。羅榮桂等19就國內外關于多項目調度問題的現狀進行研究。這方面的研究中，有些學者試圖用解決單項目的方式來求解多項目問題。成為“單項目”方式。通過增加虛擬的源節點和尾節點來將多個單項目人工連接成一個大項目。求解多項目調度問題的啟發式算法大部份能夠歸結為基于優先規則的方式。而這些規則的效果則有專門大的不同。文中舉例說明了這點。在對于啟發式進行改良后，提出了往復式的前向-后向調度算法，用于改良可行解。遺傳算法、模擬退火等元啟發式算法在多項目調度中應用極少，有關學者提出帕累托模擬退火和日光束搜索方式來描述和量化資源受限的多個項目活動的交叉影響,并取得了較好效果。對于多項目的調度問題

41、，作者以為有待深切研究的在于：單項目調度問題有一個公認的標準問題庫PSPLIB(KolischandSprecher,1996)和PSPLIB/max(ChristophSchwindt,1998),因此各類算法能夠方便地進行彼此比較，也能夠與問題的最優解或已知最好解來進行比較，從而判斷算法的好壞18191o對于rcmPSP,則缺乏如此公認的問題庫，難以判斷算法的好壞。rcmPSP的問題庫，將是此后的一個重要研究課。RCPSP其他方面的研究另外，在單執行模式資源受限的工程調度問題的擴展下，劉士新等呷研究了多執行模式工程調度的優化算法。雒興剛，汪定偉，唐加福網結合企業實際的項目調度，在任務不可拆分的經典資源受限項目調度問題的基礎上針對任務可拆分的項目調度問題提出了總項目工期最短的數學模型。梁燕、金煒如針對緊急事件調度的緊迫性特點，成立了一種基于資源約束的啟發式項目調度方式