基于前攝策略的項目調度優化方法研究

(哈爾濱理工大學 a.軟件學院; b.計算機科學與技術學院， 哈爾濱 150080)

摘 要：

為了解決不確定性因素對項目調度造成的擾動，在綜合考慮項目資源緊張度、網絡圖結構復雜度等因素影響的前提下，對關鍵鏈和非關鍵鏈分別添加適當時間緩沖，減小了不確定性因素帶來的擾動，提高了項目調度的健壯性。在此基礎上提出以在制品水平和凈成本最低為目標的項目調度優化方法；最后通過大量仿真驗證，結果表明該方法優于文獻中的項目調度方法。

關鍵詞：前攝策略； 不確定性； 健壯性； 關鍵鏈； 時間緩沖

中圖分類號：TP301文獻標志碼：A

文章編號：1001-3695(2009)04-1294-03

Optimization algorithm for project scheduling with proactive strategy

ZHANG Hong-guoa， YANG Qiu-geb

(a.College of Software， b.College of Computer Science Technology， Harbin University of Science Technology， Harbin 150080， China)

Abstract:

For solving the disturbances caused by uncertain factors of the project scheduling， respectively added appropriate time buffers to critical chain and non-critical chain under considering the effects of project resource intensity and network structure complexity which lowered the disturbances caused by uncertain factors and enhanced the project scheduling robustness. Based on this， proposed the project scheduling optimization method to minimize the level of the products and the net cost. Finally by a large number of simulations verifying， the results show that this method works successfully and is superior to other project scheduling methods.

Key words：proactive strategy; uncertainty; robustness; critical chain; time buffering

隨著全球化經濟的到來，市場競爭日趨激烈，現代項目面臨的環境日趨復雜，對項目管理的要求也更高，如準時完工率更高、成本更低等[1]。然而由于不確定因素的存在給項目調度帶來的不利影響，計劃階段確定的項目調度優化模型在實施時難以順利執行或性能指標發生變化甚至不再可行[2]，要求項目計劃與調度具有更高的健壯性和可行性。對于決策者來說，如何處理項目調度執行過程中的不確定因素成為必須考慮的問題[3]。不確定條件下的項目調度問題實際上是一個調度策略選擇問題，所以，為了提高調度健壯性而致力于研發前攝調度策略，抵御可能出現的聯機擾動、保持足夠的靈活性或最小化這些擾動對調度中活動的影響[4]。

針對上述問題，關鍵鏈[5]作為一種全新的項目管理方法，已經在多個企業獲得了成功的應用，并引起了學術界相當的重視和研究[6~15]。但仍有很多關鍵問題需要解決，如在多資源強耦合約束情況下關鍵鏈的識別與選擇、緩沖區尺寸的確定、項目綜合指標的優化等[1，6]。文獻[15]考慮了資源緊張度和項目網絡復雜度，并從某一角度分析了估計緩沖的方法。文獻[1，7，11~13]均沒有考慮這兩個因素，本文方法正是基于這個缺陷提出新的調度方法。基于RCPSP的調度理論，本文采用前攝策略基于優先規則的啟發式優化方法得到近優調度，通過對調度中的活動添加時間緩沖實現目標函數，最后通過仿真實驗驗證了該方法的優越性。

1 問題陳述

典型的資源受限項目調度問題可描述如下：在一個項目中，整個項目結構由一張有向網絡圖表示，共有I項活動。由于技術上的要求，某些活動之間存在著緊前關系，如活動j在它任一緊前活動i，i∈PRED（j）(PRED（j）為活動j的緊前活動集)完成之前不能開始。用P(i)表示活動i的緊前活動集，S(i)表示活動i的緊后活動集。圖中各活動順序編號應保證P(i)中的活動編號小于i。活動1是惟一最早開始的活動，活動I是惟一最晚完成的活動，均為不消耗資源且執行時間為0的虛活動，且分別代表整個項目的開始和結束。整個項目的合同工期是D，設項目完工期的上界是D。

一個可行調度方案是指各項活動的開始時間都已確定，且滿足工藝緊前關系及資源約束。活動i (i=1，2，…，I) 的計劃開始時間為SSTi，執行時間為di，執行期間需要第k 種資源量為rik ，資源k 的單位成本為ck ，完成活動i的成本為Ci=∑Kk=1ckdirik。第k種資源總量為常量Rk (k=1，2，…，K)，在項目完成前的任一時刻， 正在執行的所有活動所利用的資源總數不能超過資源總量Rk。St為在(t-1，t)時間段內正在進行的活動集合，最小化凈成本和在制品水平采用文獻[6]和[9]中的目標函數。典型的資源受限項目調度問題可建立如下數學模型：

min PC(S)=∑Ii=1Cif SSTi(1)

minWIP(S)=∑Ii=1(1/|S(i)|×∑j∈S(i)(SSTj-SFTi))(2)

SSTi+di≤SSTj，j∈S(i)(3)

∑i:i∈Strik≤Rk， t=1，2，…，γ;k=1，2，…，K(4)

P(D≤D)≥P0(5)

其中：式(1)為目標函數，代表項目凈成本最小，f 為成本折扣因子，取f=0. 99。從目標函數可以看到，活動開始得越晚，項目凈成本越小。式(2)代表在制品水平最小；式(3)代表緊前關系約束；式(4)保證在每一階段使用的資源量不能大于其可用量；式(5)是一個完工概率滿足條件，其中P0是完工率。

2 前攝策略

Aytug 等人[4]為了預先處理不確定性提出前攝調度策略。前攝調度是基于計劃調度結構，通過給每一個活動提供計劃執行時間，并且在資源被占用情況下，這種計劃調度將引導調度的執行。前攝調度的目的是建立一個健壯性計劃調度，在調度執行期間盡可能地保護其不受干擾。

2.1 優化方法

本文采用的優化方法是前攝策略基于最晚開始時間優先規則的啟發式方法[1]得到近優調度，根據本文緩沖區設置方法從后向前重新調整各活動，直至得到最終近優調度。

2.2 關鍵鏈技術

從相關文獻的研究得出，采用關鍵鏈技術能有效地降低項目受不確定性因素影響的程度和提高項目調度的健壯性，并在成本等方面獲得了成功應用。緩沖區的設置為保證項目按時完成提供了有效的途徑。

決定關鍵鏈的約束條件有兩個方面，即緊前關系約束和資源約束。前者是指后項活動的開始依賴于前項活動的完成；后者是指需要相同資源的活動之間的依賴性，一項活動的開展需占用同一資源的其他活動的完成。

2.3 時間緩沖策略

在本文中采用加入時間緩沖區的方法來及時吸收項目執行過程中的不確定因素對項目初始調度的擾動，這給項目進度控制帶來了極大的可操作性，保證在確定環境下的項目計劃在動態環境下能夠順利執行。設置時間緩沖區后，保護關鍵鏈工作順利執行——實現了調度的健壯性，保證項目調度滿足項目完工率，并且實現了項目的最終目標。

2.3.1 確定緩沖位置

關鍵鏈和非關鍵鏈的確定參考文獻[7]。對關鍵鏈(CC)設置項目緩沖(PB)，在其末端嵌入項目緩沖，用于保護項目總工期和吸收整個系統的不確定性。對非關鍵鏈(NCC)，設置輸入緩沖為FB，使各個作業以最晚時間開始，若非關鍵性活動i的結束時間等于某一關鍵性活動的開始時間，且該關鍵性活動是活動i的時間緊后或資源緊后活動，則活動i之后為匯入位置，即在非關鍵鏈到關鍵鏈的入口處設置輸入緩沖。

在非關鍵鏈匯入關鍵鏈的入口處，設置輸入緩沖來保護關鍵鏈免受非關鍵鏈的不確定性影響，這對非關鍵鏈而言，起到了項目緩沖作用。PB和FB只能置于鏈路尾端來吸收整個項目的不確定因素，其大小反映線路上活動的不確定性，屬鏈路上活動共有[15]。

此外，當需要投入某種資源來啟動關鍵鏈活動，而其前續關鍵活動又使用其他資源時，需要在該活動之前設置資源緩沖(resource buffer， RB)。RB是針對關鍵鏈上所有活動所需的各種資源，設置在關鍵鏈上第一個使用這些資源活動的開始時間前不占用時間，其作用在于確保資源供應。這樣就解決了關鍵鏈間的資源沖突。非關鍵鏈與非關鍵鏈的資源沖突可以充分利用時差給項目調度帶來的“柔性”功能來解決。每設置一個輸入緩沖區，都要考慮資源沖突的消除。

2.3.2 估計緩沖區大小

根據關鍵鏈中緩沖機制的原理和約束理論[5]，在確定緩沖大小時應該考慮到項目網絡圖的復雜度和資源供應的緊張程度[14]。

如果活動所用資源在執行中接近其資源總量，則活動所在鏈路更容易出現延期，緩沖應設置大些；如果活動的緊前活動比較多，則其更容易受前面活動的影響而延期，緩沖應設置大些；如果活動的后續活動比較多，則其延期對后續活動的影響更大，帶來的擾動更大，緩沖應設置大些。這樣充分考慮到實際項目中各活動的活動復雜度，緩沖大小依據活動復雜度的大小設置更加接近實際情況，這樣也就提高了優化精度。

鑒于此，在綜合考慮項目資源緊張度、項目復雜度等不確定因素情況下，提出一種新方法來估計緩沖大小。將資源緊張度α、活動復雜度β和δ吸收到緩沖時間的估算中。

1)資源緊張度 用αi表示活動i的資源緊張程度。

αi=max{∑nj=1rjt/Rt}，t∈[STi，STi+Di](6)

其中：Rt為項目在t時段的資源供應限量；rjt為在t時段執行的活動j所需的資源量；n為在t時段執行活動的總數；STi和Di分別為活動i的開始時間和工期。

2)活動復雜度 文獻[14]提出的關于鏈路復雜度的概念，用活動所在鏈路的復雜度來反映活動的復雜度，但僅提到活動i的緊前活動，本文又考慮到活動i的緊后活動。用NP 、NS和NT分別表示活動所在鏈路上活動的緊前活動數目、緊后活動數目和鏈路上的活動總數，則活動的復雜度可用下式表示:

βi=NP/NT(7)

δi=NS/NT(8)

綜合考慮這些因素的情況下，根據根方差法[10]的啟發，緩沖估計為

ΔB={∑i∈CC[(si-ai)2×αi×βi×δi]}1/2(9)

ΔB*={∑i∈NCC[(si-ai)2×αi×βi×δi]}1/2(10)

其中：si 是采用傳統方法估計活動i的執行時間；ai是采用關鍵鏈方法估計活動i的執行時間。根據文獻[2]的方法得到活動i的自由時間rtfi。這樣各非關鍵鏈的緩沖大小為

FB=min{ΔB*， rtfi}(11)

PB=ΔB(12)

活動i為鏈路的最后一個活動。根據關鍵鏈和式(9)計算項目緩沖PB，把PB插入關鍵鏈末尾即項目末尾。自后向前檢查與關鍵鏈有接口的各非關鍵鏈，將FB插入到該非關鍵鏈與關鍵鏈的入口之處。最后檢視插入緩沖后的網絡，包含各活動的估計時間及其所用的資源，重新平衡資源沖突后對非關鍵鏈進行調整得到近優項目調度。算法1給出了時間緩沖區啟發式算法，步驟f)保證了在整個算法執行過程中，各工作的計劃開始時間滿足緊前關系和資源約束。在調整中，各活動從最晚開始時間向左調整，調整的最大距離為插入的緩沖值，同一鏈路的緊前活動不一定要調整。盡可能地保證各活動的開始時間是最晚的，進而保證在制品水平是最低的。

算法1 時間緩沖區啟發式算法步驟如下：

a)采用基于最晚開始時間優先規則的啟發式算法來求得近優調度。

b)確定關鍵鏈和非關鍵鏈NCC(l) (l=1，2，…，L)。

c)確定資源緊張度αi和項目復雜度βi和δi。對于非關鍵鏈NCCl，采用式(7)~(9)分別得到αi、βi和δi。

d）如果l小于L則返回到步驟c）。

e）確定時間緩沖位置和大小。關鍵鏈緩沖大小根據式(12)得到；非關鍵鏈緩沖大小根據式(11)得到。

f）從后向前檢測是否存在緊后關系和資源沖突，調整各活動的開始時間向左移動，得到最終項目調度圖。

實際上，本文方法是根據各工作在指定資源分配方式下，綜合考慮資源緊張度和項目復雜度而分別設置緩沖區的，而不是對非關鍵鏈的每一活動均添加緩沖，造成緩沖浪費，得不到盡可能的最晚開始時間， 在制品水平也不是最低的。

3 仿真實驗及分析

為了測試本文方法的正確性和有效性，算法用VC++6.0編碼驗證，算法運行在Pentium 4 2.40 GHz/512 MB PC上。測試問題選自文獻[2]所采用的標準問題庫PSPLIB中的問題J301-1.SM為例來驗證本文算法的性能。例題的項目網絡圖如圖1所示。



3.1 仿真驗證

實驗中假設測試問題中各工作的執行時間不包含安全時間，項目執行過程的仿真方法如下：關鍵鏈管理方法以50% 可能完成的執行時間作為工作的估計執行時間。從各活動的完工分布來看，以各工作50%可能完成時間為均值，以服從均勻分布U～[0.75，1.5}的隨機數為方差，為各工作生成符合對數正態分布的隨機整數(小數采用四舍五入方式)作為實際執行時間，更符合項目實際執行情況。項目起始活動1的直接后序活動按計劃開始時間開始，其他活動在項目執行過程中按計劃開始時間從小到大的順序依次執行。

通過式(7)~(9)分別得到αi、βi和δi的值如表1所示。

通過文獻[7]中關鍵鏈和非關鍵鏈的判定方法和本文緩沖估計方法，識別出各鏈路并計算出緩沖區大小，如表2中的信息所示。括號中的數據是根據式(9)和(10)得到的。由于非關鍵鏈{2}只有一個活動，并且緊前活動為虛活動，其緩沖設為0。

通過以上計算和算法1得到J301-1.SM問題的最終項目調度圖如圖2所示，灰色表示關鍵鏈活動，黑色表示添加的緩沖。根據式(6)~(10)模擬運行100次得到表3中的完工率。



3.2 仿真結果分析

從表3的性能對比中可以看到，采用本文方法得到的在制品水平和凈成本均得到降低，項目完工率雖然有下降的趨勢，但保證在99%以上，這證明本文方法達到了預期目標。對算法分析得到時間復雜度很低，根據算法1中各步驟的實際執行時間T(n)=n log n+7n+C，計算出時間復雜度為O(n log n)。這就證明了本文提出的項目調度優化方法的優越性。

4 結束語

本文指出了不確定性問題必須要考慮的重要性， 并且重點強調了為實現項目調度目標建立一個前攝調度的必要性。首先，建立一個開始調度如最晚開始時間優先的調度；其次通過添加時間緩沖來保護調度避免受到的擾動影響最小。本文基于RCPSP的調度理論和方法，設計了一種緩沖區的設定方法。該方法采用關鍵鏈技術，同時考慮了資源約束及資源約束下的自由松弛、資源緊張度、項目復雜度等影響因素，通過計算得到關鍵鏈和非關鍵鏈適當的緩沖大小。最后通過驗證，證明該方法既避免了因緩沖區設置而產生的活動間資源沖突、保護關鍵鏈工作順利執行——實現了調度的健壯性，又降低了項目在制品水平和凈成本。

參考文獻：

[1]劉士新，宋健海，唐加福.資源受限項目調度中緩沖區的設定方法[J].系統工程學報，2006，21(4): 381-386.

[2]丁然.不確定條件下魯棒性生產調度的研究[D].濟南：山東大學，2007：1-3.

[3]LAMBRECHTS O， DEMEULEMEESTER E， HERROELEN W. Pro-active and reactive strategies for resource-constrained project scheduling with uncertain resource availabilities [J]. Journal of Scheduling， 2007， 11(2):121-136.

[4]AYTUG H， LAWLEY M， McKAY K， et al. Executing production schedules in the face of uncertainties: a review and some future directions [J]. European Journal of Operational Research， 2005， 161(1): 86-110.

[5]GOLDRATT E M. Critical chain [M]. Great Barrington: North River Press， 1997:16-20.

[6]HERROELEN W， LEUS R. On the merits and pitfalls of critical chain scheduling[J].Journal of Operations Management，2001，19(5):559-577.

[7]莫巨華.基于關鍵鏈的項目調度模型與算法[D].沈陽：東北大學，2005：15-23.

[8]劉士新，王夢光，唐加福.資源受限工程調度問題的優化方法綜述[J].控制與決策，2001，16(增刊)：647-651.

[9]TABARES L V， FERRERIA J A， COELHO J S. On the optimal management of project risk [J]. European Journal of Operational Research， 1998， 107(2):451-469.

[10]NEWBOLD R C. Project management in the fast lane-applying the theory of constraints [M]. Cambridge: St Lucie Press， 1998:1-5.

[11]張靜文，胡信布，王茉琴.關鍵鏈項目計劃調度方法研究[J].科技管理研究，2008，28(3)：280-283.

[12]徐小琴，韓文民.關鍵鏈匯入緩沖區的設置方法[J].工業工程與管理，2007(5)：51-55.

[13]單汨源，龍穎.一種關鍵鏈緩沖機制改進方法及其應用研究[J].項目管理技術，2006(9)：32-35.

[14]OYA I T， WALTER O R， SANADRA D E. An investigation of buffer sizing techniques in critical chain scheduling [J].European Journal of Operational Research， 2006， 172(2):401-416.

[15]褚春超.緩沖估計與關鍵鏈項目管理[J].計算機集成制造系統，2008，14(5)：1029-1035.