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

摘 要：

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

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

中圖分類號：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

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

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

1 問題陳述

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

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

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

2 前攝策略

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

2.1 優(yōu)化方法

本文采用的優(yōu)化方法是前攝策略基于最晚開始時間優(yōu)先規(guī)則的啟發(fā)式方法[1]得到近優(yōu)調(diào)度，根據(jù)本文緩沖區(qū)設置方法從后向前重新調(diào)整各活動，直至得到最終近優(yōu)調(diào)度。

2.2 關鍵鏈技術(shù)

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

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

2.3 時間緩沖策略

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

2.3.1 確定緩沖位置

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

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

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

2.3.2 估計緩沖區(qū)大小

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

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

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

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

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

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

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

βi=NP/NT(7)

δi=NS/NT(8)

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

Δ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 是采用傳統(tǒng)方法估計活動i的執(zhí)行時間；ai是采用關鍵鏈方法估計活動i的執(zhí)行時間。根據(jù)文獻[2]的方法得到活動i的自由時間rtfi。這樣各非關鍵鏈的緩沖大小為

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

PB=ΔB(12)

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

算法1 時間緩沖區(qū)啟發(fā)式算法步驟如下：

a)采用基于最晚開始時間優(yōu)先規(guī)則的啟發(fā)式算法來求得近優(yōu)調(diào)度。

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

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

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

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

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

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

3 仿真實驗及分析

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



3.1 仿真驗證

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

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

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

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



3.2 仿真結(jié)果分析

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

4 結(jié)束語

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

參考文獻：

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

[2]丁然.不確定條件下魯棒性生產(chǎn)調(diào)度的研究[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]莫巨華.基于關鍵鏈的項目調(diào)度模型與算法[D].沈陽：東北大學，2005：15-23.

[8]劉士新，王夢光，唐加福.資源受限工程調(diào)度問題的優(yōu)化方法綜述[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]張靜文，胡信布，王茉琴.關鍵鏈項目計劃調(diào)度方法研究[J].科技管理研究，2008，28(3)：280-283.

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

[13]單汨源，龍穎.一種關鍵鏈緩沖機制改進方法及其應用研究[J].項目管理技術(shù)，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].計算機集成制造系統(tǒng)，2008，14(5)：1029-1035.