工程項目的進度計劃與傳統(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ù)時間盡可能縮短.目前關(guān)于工期進度優(yōu)化方法的研究思路也集中于不斷改進強制縮短法，力求在優(yōu)化項目工期的同時，使所增加的額外成本最小。吳育華等學(xué)者提出了割集平行路線差額法解決工期優(yōu)化的算法，劉津明運用“最大流最小截”理論研究了工期一成本非線性變化時工期優(yōu)化的算法思路.隨著現(xiàn)代信息技術(shù)的日益成熟，使用Managementscientist等軟件可以非常迅捷的求出基于上述強制壓縮法進行進度優(yōu)化的最優(yōu)結(jié)果.
強制壓縮法要求必須從外界投入新的資源到關(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)化達(dá)到設(shè)定縮短的工期目標(biāo)時，就認(rèn)為工期優(yōu)化已達(dá)到期望。
利用關(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＝和I=.非凡地，將關(guān)鍵線路表示為cp，cp∈I，關(guān)鍵線路上的p個工作節(jié)點表示為cpk，cpk∈J，k∈P，P=.以xj表示工作節(jié)點j資源的輸入或輸出量，qj為工作節(jié)點j的計劃資源用量。qj‘表示工作節(jié)點j資源需求量的極值，對于關(guān)鍵線路上的節(jié)點，qj’表示工期經(jīng)過最大壓縮后，完成工作所需的資源量，對于非關(guān)鍵線路上的節(jié)點，qj‘表示充分利用自由時差后完成工作需要的資源量，因此有xj≤
進而工作節(jié)點j因為資源量變化而引起的工期時間變化量為ajxj.設(shè)Tcp，Ti分別表示關(guān)鍵線路和非關(guān)鍵線路的計劃工期，aij表示工作節(jié)點j的資源變化對線路i工期的影響系數(shù)。
3.3算法分析
令A(yù)j＝qj×tj，Bj＝.Aj表示節(jié)點j上包含有工期和資源用量的計劃安排，Bj表示關(guān)于節(jié)點j所有可行計劃安排的集合。根據(jù)是否是關(guān)鍵節(jié)點，有：
基于關(guān)鍵線路的轉(zhuǎn)移而提出的工期優(yōu)化算法，是尋找能最大壓縮工期的集合B，B=，j∈J.
以Fmax表示關(guān)鍵線路節(jié)點輸入資源后所能壓縮的最大工期，固定資源約束下的工期優(yōu)化問題可以轉(zhuǎn)化為解決如下嵌套模型：
式表示對于非關(guān)鍵工作節(jié)點在工作量恒定的前提下輸出資源會導(dǎo)致其工期延長但工期延長量不能超過可利用的自由時差。同理式表示對于關(guān)鍵線路上的工作節(jié)點輸入資源會使工期縮短工期的縮短量不能超過極限壓縮時間。式表示工期優(yōu)化后的關(guān)鍵線路工期不小于網(wǎng)絡(luò)計劃中的其它線路的工期。式表示節(jié)點資源改變對工作線路工期的影響。式和式分別表示非關(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、算例說明
我們引用文獻(xiàn)RolfH.Solvingprojectschedulingproblem、byminimumcutcomputations.ManagementScience，2003，49330-350.
白思俊。現(xiàn)代項目治理67一71.
劉津明。工程項目進度計劃優(yōu)化方法的研究.天津大學(xué)學(xué)，2003，36610一613.
DavidR.Anderson，DennisnJ.Sweeney，ThomasA.Williams.AnIntroductiontoManagementScienceQuantitativeApproachestoDecisionMaking.ThomsonLearning，2003：340.
Son一SenLen，Chung一HueiYang，Jiun一ChingHuang.Resourcelevelinginconstructionbygeneticalgorithm一basedoptimizationandindecisionsupportsystemapplication.AutomationinCnostiuction，200027一41.
