如何制定進度計劃一直是各種行業(yè)中非常重要的問題。制定進度計劃的主要目的是在一定的資源約束下使工期最短，或者是在工期一定的約束條件下使資源（費用）消耗最小。由此自20世紀60年代以來隨著運籌學的發(fā)展產生了很多相關的研究成果，近期的研究主要圍繞固定資源約束下的進度計劃制定而展開。Bouleiman和Lecocq提出了一類模擬退火算法以有效得對工作節(jié)點進行排序[1], Rolf等學者運用拉格朗日松弛提出了一種基于最早開始時間的整數規(guī)劃方法對進度計劃進行優(yōu)化[2].然而相關的大多數研究是從傳統(tǒng)的“機器排序”問題演變而來，并不很適用于解決工程項目中的進度問題。

　　工程項目的進度計劃與傳統(tǒng)的“機器排序”問題有著較大差異：一是工作節(jié)點有著明確的先后作業(yè)順序并且一般不能改變，例如房屋的修建必須是從基礎開始。二是工作節(jié)點的作業(yè)時間有著較大的不確定性，由于氣候、設計等因素造成的工期變化極為常見。三是由于工程項目進度計劃的時間窗單位比較大，所以最初的進度計劃制定沒有像一般的制造加工業(yè)那樣要求精確。因此工程項目中的進度優(yōu)化集中于研究對資源如何進行分配，而不是各工序之間的作業(yè)次序調整。

　　1、網絡計劃優(yōu)化

　　現(xiàn)代的工程項目都是應用基于CPM和PERT的網絡計劃技術作為計劃、分配、控制的重要手段和工具。最常見的網絡計劃進度優(yōu)化方法是強制縮短法，即采取措施使網絡計劃中的某些關鍵工作的持續(xù)時間盡可能縮短[3].目前關于工期進度優(yōu)化方法的研究思路也集中于不斷改進強制縮短法，力求在優(yōu)化項目工期的同時，使所增加的額外成本最小。吳育華等學者提出了割集平行路線差額法解決工期優(yōu)化的算法[4]，劉津明運用“最大流最小截”理論研究了工期一成本非線性變化時工期優(yōu)化的算法思路[5].隨著現(xiàn)代信息技術的日益成熟，使用Management scientist等軟件可以非常迅捷的求出基于上述強制壓縮法進行進度優(yōu)化的最優(yōu)結果[6].

　　強制壓縮法要求必須從外界投入新的資源到關鍵線路的工作節(jié)點中，然而在現(xiàn)實工程項目建設中經常缺乏多余資源，這就要求利用網絡計劃中非關鍵工作的既有資源進行工期優(yōu)化，解決所謂的趕工問題�；�于上述思想，本文對單代號網絡計劃中固定資源約束下的工期優(yōu)化算法進行探討。

　　2 、算法思想

　　利用非關鍵工作的既有資源進行工期優(yōu)化，就是利用非關鍵工作的時差，抽調其中的部分資源用于加強關鍵工作，以縮短關鍵工作的持續(xù)時間，使工期縮短〔3].利用關鍵線路的轉移進行工期優(yōu)化的最終結果，是使網絡計劃中出現(xiàn)盡可能多的關鍵線路，或者是關鍵線路的工期與次關鍵線路的工期差值最小。即當原關鍵線路的工期經過優(yōu)化達到設定縮短的工期目標時，就認為工期優(yōu)化已達到期望。

　　利用關鍵線路的轉移優(yōu)化工期，必須先明確關鍵線路上有可以壓縮的關鍵工作，非關鍵工作節(jié)點有關鍵線路上可壓縮工作節(jié)點壓縮所需的資源，并且這種資源可以分割轉移。非關鍵工作節(jié)點上的資源轉移會延長其自身的工期，而關鍵線路上的工作節(jié)點接受了轉移的所需資源后會縮短計劃工期，從而縮短項目的整體工期。根據資源輸出和輸入節(jié)點的位置，原網絡計劃中的所有線路工期有可能出現(xiàn)不同程度的延長或縮短，但壓縮后的原關鍵線路工期不能小于次關鍵線路工期。同時，工作節(jié)點上資源的輸出或輸入量也受到最小資源需求用量和最大壓縮時間的約束。因此，將非關鍵工作中的資源轉移到關鍵線路上的工作中進行工期優(yōu)化，要解決如下問題：如何選擇進行資源輸出的非關鍵工作節(jié)點，各非關鍵工作節(jié)點輸出多少資源，以及如何選擇關鍵線路中的資源輸入節(jié)點，各壓縮節(jié)點輸入多少資源。

　　3 、算法模型

　　3.1 前提假設

　　為簡化研究，進一步假設網絡計劃的所有節(jié)點中只有一種可以分割轉移并且影響工期的資源。以往的大部分工期優(yōu)化研究都是基于成本費用和工期之間的關系，通常項目所需的各種資源也能轉化為費用進行衡量，因此我們的假設不失一般性。調整非關鍵工作節(jié)點的總時差會影響其后工作節(jié)點的最早開始時間，加大項目的不確定性，因此這里僅選擇具有自由時差的非關鍵工作節(jié)點作為資源輸出對象。同時，假設工期優(yōu)化前的網絡計劃中只有一條關鍵線路，在滿足約束前提下，各工作節(jié)點的資源變化量與工期變化量成線性關系。

　　3. 2 變量假設

　　設網絡計劃由m個工作節(jié)點和二條線路組成分別記為J＝{1,2, ……,m}和I={1,2…二}.特別地，將關鍵線路表示為cp , cp∈ I ，關鍵線路上的p個工作節(jié)點表示為cpk, cpk ∈ J, k∈P, P ={1 , 2, ……, p} .以xj表示工作節(jié)點 j 資源的輸入或輸出量，qj為工作節(jié)點j的計劃資源用量。qj‘表示工作節(jié)點j資源需求量的極值，對于關鍵線路上的節(jié)點，qj’表示工期經過最大壓縮后，完成工作所需的資源量，對于非關鍵線路上的節(jié)點，qj‘表示充分利用自由時差后完成工作需要的資源量，因此有xj ≤ |qj – qj’|.由前所述，在網絡計劃只做一次性工期優(yōu)化的前提下，同一工作節(jié)點的資源只能單方向轉移（輸入輸出）或者不發(fā)生變化。設tj為工作節(jié)點j的計劃工期，以△tj表示工作節(jié)點j工期變動的最大范圍。對于非關鍵工作節(jié)點，△tj表示可以利用的自由時差，對于關鍵線路上的工作節(jié)點，△tj表示極限壓縮時間。設aj為工作節(jié)點j上資源與工期時間的相關系數，aj表示約束條件下單位資源量對工期的影響程度，由資源變化量與工期變化量成線性關系的假設，有

　　進而工作節(jié)點j因為資源量變化而引起的工期時間變化量為ajxj.設Tcp, Ti （i≠cp）分別表示關鍵線路和非關鍵線路的計劃工期，aij表示工作節(jié)點j的資源變化對線路i工期的影響系數。

　　3.3算法分析

　　令Aj＝qj×tj, Bj＝{Aj}.Aj表示節(jié)點j上包含有工期和資源用量的計劃安排，Bj表示關于節(jié)點j所有可行計劃安排的集合。根據是否是關鍵節(jié)點，有：

　　基于關鍵線路的轉移而提出的工期優(yōu)化算法，是尋找能最大壓縮工期的集合B,B={Bj}, j ∈ J .

　　以Fmax表示關鍵線路節(jié)點輸入資源后所能壓縮的最大工期，固定資源約束下的工期優(yōu)化問題可以轉化為解決如下嵌套模型：

　　式（2）表示對于非關鍵工作節(jié)點在工作量恒定的前提下輸出資源會導致其工期延長但工期延長量不能超過可利用的自由時差。同理式（3）表示對于關鍵線路上的工作節(jié)點輸入資源會使工期縮短工期的縮短量不能超過極限壓縮時間。（4）式表示工期優(yōu)化后的關鍵線路工期不小于網絡計劃中的其它線路的工期。（5）式表示節(jié)點資源改變對工作線路工期的影響。式（6）和式（7）分別表示非關鍵工作節(jié)點中輸出的資源全部輸入到關鍵線路的工作節(jié)點中，各節(jié)點資源量改變的絕對值非負。

　　在實際工期優(yōu)化時，非關鍵工作節(jié)點的自由時差和充分利用時差后完成工作所需的最小資源量，關鍵線路上工作節(jié)點的極限壓縮時間和對應的需求資源量是已知的，由

　　可以求出各節(jié)點的資源時間相關系數從而把上述模型轉化為線性規(guī)劃問題求解。下面以一個算例說明固定資源約束下運用轉移關鍵線路法進行工期優(yōu)化的解決過程。

　　4 、算例說明

　　我們引用文獻[7l的算例作為工期優(yōu)化對象隨機給出了關鍵線路上工作節(jié)點的最大壓縮工期并以（tj+△tj） （qj-qj‘）=qj×tj 給出各節(jié)點工期極值下的資源需求量。圖1顯示了單代號網絡圖中各工作節(jié)點的計劃工期和資源消耗量。

　　各工作節(jié)點上的資源一時間參數如表1所示。

　　網絡計劃各工作線路的計劃工期以及其上可進行資源轉移的節(jié)點如表2所示。

　　對此算例進行工期優(yōu)化，實質上就是從H, J, E,L,M節(jié)點向C, F, 1, K節(jié)點輸入資源，這里用lindo程序運算求解，主要結果如圖2所示。

　　圖2中的結果表明在不從外界投入資源的情況下，可以利用網絡計劃中的既有資源，使工期最大縮短4個時間單位。在實際的工程建設中，很多都是以季度作為制訂網絡計劃的時間單位，因此上述算法對于工程實踐中的工期優(yōu)化有著明顯的意義。圖3為算例經過工期優(yōu)化后的網絡計劃圖（數據取整），優(yōu)化后的網絡計劃中出現(xiàn)了3條關鍵線路：A一B一H一O,A一C一F一I一K一O, A一M一O.

　　5 、小結

　　本文提出了運用關鍵線路的轉移進行工期優(yōu)化的一類算法。在網絡計劃的既定資源約束下，利用非關鍵工作的自由時差將其上的資源轉移到關鍵線路的可壓縮工作上，從而縮短了整個網絡計劃的工期。為簡化模型，本文只利用有自由時差的非關鍵工作作為資源輸出對象，但也可以將具有時差的工作節(jié)點一并考慮，從而可能獲得更大的優(yōu)化效果。此外，節(jié)點的工期一資源并非一定成線性關系，已有學者利用灰色預測方法對這一問題進行了深入研究[8].在實際的工程項目中，工期優(yōu)化還必須考慮資源均衡等諸多現(xiàn)實問題。因此一般情況下僅需將原關鍵線路的工期進行一次性優(yōu)化到達工期優(yōu)化的期望值即可，實際上如果在優(yōu)化后新的關鍵線路上仍然有可以繼續(xù)壓縮的工作節(jié)點，并且非關鍵節(jié)點上也有相應的時差資源，就可以再次利用上述算法進一步進行優(yōu)化。但如果完全利用非關鍵節(jié)點的時差資源后仍不能滿足工期優(yōu)化期望，則必須重新利用強制壓縮法從外部投入新的資源。在明確資源和工期的相關系數后，本文提出的算法轉化為了很多商業(yè)軟件都能求解的規(guī)劃問題，對算法在實際工程行業(yè)中的推廣有著積極作用。

　　參考文獻：

　　[1]K. Houleiman. H.Lecocq. A new efficient simulated annealing algorithm for the resource一constrained project scheduling problem and its multiple mode version [J]. European Journal of0perational Research. 2003（149）：268一281.

　　[2]Rolf H.Solving project scheduling problem、by minimum cut computations [J]. Management Science, 2003, 49（3）：330-350.

　　[3]白思俊�，F(xiàn)代項目管理（中）[M].北京：機械工業(yè)出版社，2003.

　　[4]吳育華，李崇斌，吳靈慧。割集平行路線差額法—一種確定網絡計劃最佳工期的有效算法[J].管理工程學報，1996,10（2）：67一71.

　　[5]劉津明。工程項目進度計劃優(yōu)化方法的研究[J].天津大學學報，2003,36（5）：610一613.

　　[6]David R. Anderson, Dennisn J. Sweeney, Thomas A. Williams. An Introduction to Management Science Quantitative Approaches to Decision Making [M].Thom son Learning, 2003： 340.

　　[7]Son一Sen Len, Chung一 Hue i Yang, Jiun一Ching Huang. Resource leveling in construction by genetic algorithm一based optimization and in decision support system application[J]. Automation in Cnostiuction,2000（10）：27一41.

　　碧森尤信　作者：陸紹凱，武振業(yè)