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

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

　　1、網(wǎng)絡(luò)計劃優(yōu)化

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

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

　　2 、算法思想

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

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

　　3 、算法模型

　　3.1 前提假設(shè)

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

　　3. 2 變量假設(shè)

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

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

　　3.3算法分析

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

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

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

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

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

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

　　4 、算例說明

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

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

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

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

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

　　5 、小結(jié)

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

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

　　[5]劉津明。工程項目進度計劃優(yōu)化方法的研究[J].天津大學(xué)學(xué)報，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è)