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

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

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

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

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

　　2 、算法思想

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

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

　　3 、算法模型

　　3.1 前提假設(shè)

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

　　3. 2 變量假設(shè)

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

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

　　3.3算法分析

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

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

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

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

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

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

　　4 、算例說(shuō)明

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

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

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

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

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

　　5 、小結(jié)

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

　　參考文獻(xiàn)：

　　[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)代項(xiàng)目管理（中）[M].北京：機(jī)械工業(yè)出版社，2003.

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

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