基于關鍵鏈的型號軟件項目進度管理技術研究

摘要：關鍵鏈是項目進度管理的一種新方法。針對關鍵鏈技術的兩個難點問題：如何識別關鍵鏈和如何設置緩沖區，結合型號軟件項目開發的特點，分別給出了識別關鍵鏈的數學模型的求解算法和一種改進型的緩沖區的設置方法。

關鍵詞：型號軟件項目；關鍵鏈技術；關鍵鏈識別；緩沖區設置

中圖分類號：G40-034 文獻標志碼：Ａ文章編號：１６７３－２９１Ｘ（２０10）32－０175－04

引言

型號軟件作項目是以軍事需要為需求背景的具有高科技特征的特殊商品。它具有研制周期長、投資數額大、技術風險高、參研單位廣、環境不確定及影響因素多等特點。這些特點決定了對其進行管理與控制的復雜性，只要一個環節出現問題，就可能會出現研制周期延長、費用開支增加，從而造成巨大的經濟損失和影響。

目前，型號軟件的承制單位大多為非軟件企業，即其主導產品并非軟件，缺乏完整有效的軟件項目進度管理體系。而且開發單位長期以來受計劃模式的影響，項目進度計劃往往以政治任務作為制定的依據，同時，沒有借助于先進的進度管理理論和方法，沒能將型號軟件項目看成一個完整的系統，進度計劃制訂過粗。其次，型號軟件項目缺乏動態的進度控制，使得型號軟件項目的進度經常是前松后緊，最終很可能造成進度延期。因此，在型號軟件作項目進度周期中，我們可以采用關鍵鏈技術對型號軟件項目進行進度管理與控制。

一、基于關鍵鏈的項目進度管理框架

（一）傳統的項目進度管理問題分析

1.工期估計時，在任務中加入安全時間，導致工期估計過長

由于型號軟件的開發技術難度大，而且軟件是一種邏輯產品，其中很多方面無法借用現有的經驗，并且型號軟件項目的開發進度往往是一項政治任務，這就導致在估計工期時，往往會選擇低風險的即高完成概率的工期估計，在工期中加入盡可能長的安全時間。然而，低風險（90%概率完工）的工期估計可能會是50%概率完工工期的2倍或者更多（如圖1），這樣就將不確定性因素包括在每個任務工期的估計上，從而大大延長了整個項目工期。

2.主張盡早開始盡早結束，過長工期估計很少被提前完成

傳統的 PERT/CPM方法大多主張早開始早結束的管理理念，會把工序盡早地安排。但是，任務提前完成只會使資源早用，而且有極大可能是提前被浪費。另外，雖然在單個任務工期的估計中都考慮了不確定因素，但由于學生惰性和帕金森癥的影響，實際工作中卻很少提前完成，并仍然有大量延誤現象。這反而使得他們誤認為工期時間估計過短[1]。

3.合并事項或合并路線的影響，使任務提前完成很難被有效利用，且增加項目延誤的可能性

在網絡計劃中通常存在著眾多路線，而這些路線最終都將匯入關鍵路線中。而后續任務的開工必須以其所有緊前任務的完工為前提，這就淹沒了部分任務提前完工的效益，而大大增加了項目延遲風險，且并行程度越高，延遲可能性越大。通常，合并任務延遲概率為： Pdelay＝1-pi。其中：pi為該合并任務的各緊前任務的完工概率。如圖2所示，關鍵線路上有一合并任務需要前面3條線路完工才能開始。即便是3條線路的完工概率為50%，則至少有1條線路延誤的概率將高達87.5%。即使3條線路的完工概率都提高到90%，那么，至少有1條線路延誤的概率仍達27.1%。倘若緊前任務更多的話，情況將更加嚴重，延誤的概率將更大。

4.無視資源競爭

傳統的關鍵路徑，沒有考慮資源的競爭問題，即使計劃再縝密，一個任務的延期也會打亂整個項目的進度。不能找出真正完成任務的瓶頸。同時非關鍵路徑上的工序使用資源也會影響到關鍵路徑上的工序對同種資源的需求。

（二）基于關鍵鏈的項目進度管理概念模型

考慮到傳統的項目進度管理手段在型號軟件項目的開發中的存在諸多不足，本文借鑒Goldratt約束理論（TOC）的五大步驟[1]，提出基于關鍵鏈的型號軟件項目進度管理概念模型，以此來突破型號軟件項目的各種制約因素。模型的具體演算步驟如下：

步驟一，確定關鍵鏈，在充分借鑒網絡計劃技術的基礎上，將關鍵鏈與經典網絡計劃技術兼容、統一。使用將項目進度編制與資源分配相結合的網絡圖來制定進度計劃，并以此確定醒目進度中的關鍵鏈。

步驟二，充分使用關鍵鏈，根據關鍵鏈中所有任務的作業時間進行計算，往后集中成為項目緩沖以吸收不確定性對關鍵鏈所產生的影響；除了關鍵鏈以外，項目中其他所有的任務、路徑及資源盡全平配合關鍵鏈，增加資源緩沖RB，計算非關鍵鏈上的輸入緩沖FB和項目緩沖PB以保護關鍵鏈。

步驟三，生成項目的進度計劃。

步驟四，確定項目的進度控制方案，監控緩沖區的消蝕情況來控制項目的進度，當緩沖區消蝕超過設置的范圍，進行進度計劃的糾偏，如果采取糾偏措施后，進度仍不能滿足基線計劃，則需要啟動計劃調整程序，轉到步驟一，重新制定進度計劃。

步驟五，結束。

使用關鍵鏈進行型號軟件進度管理的主要難點在于關鍵鏈的確定和各種緩沖區的確定方法，本文將在后兩章重點介紹如何確定關鍵鏈及如何計算緩沖區的大小。

二、識別關鍵鏈

（一）關鍵鏈數學模型描述

實施關鍵鏈型號軟件項目進度管理的第一步就是生成基于關鍵鏈的項目進度計劃。相對于傳統的PERT/CPM技術，關鍵鏈在制定進度計劃時就考慮資源的約束。由于型號軟件開發的特殊性，往往需要處理多資源約束的問題。關鍵鏈的項目進度計劃轉化成一個多資源約束的進度編排問題（MRCPSP，Multiple Resources Project Scheduling Problem）。在MRCPSP中通常包含多種資源，每個任務也可能分配多種資源，所以在編排進度的時候就需要同時考慮任務的邏輯制約和多資源的約束關系。MRCPSP的數學模型可以如下描述[2]。

假設：集合Ta|i＝1，……，n，代表N個待排進度的任務集合；集合RR|k＝1，……，K，代表資源集合，Rk代表第k類資源的可用總數；Rik代表任務ai需要占用的、類資源的數量；集合SS|i＝1，……，N代表N個任務的開始時間集合；A（t）＝a|t＜Si＜t+Di代表t時刻正在進行的任務集合；rk（t）表示t時刻正在進行的任務集合所消耗的k類資源的總數量；S（ai）代表待排任務ai的開始時間；D（ai）代表任務ai的工期；S（ai）表示后置任務的開始時間；任務之間的邏輯關系用有向圖D＝＜V，E＞表示；其中，V為頂點集，代表任務集，E＝＜v，v＞|v，v∈V代表任務v是v的前置任務，任務v必須在前置任務vi完成之后才能開始。

問題：求得滿足下列條件的各個任務的開始時間SS|i∈V，使得編排得到的目工期最短。

S（a）+Di（a）≤S（aj），（＜ai，ai＞∈E）（1）

rk（t）≤Rk（t），（＜ii，j＞∈E）（2）

其中：式（1）式表示待排任務的開始日期加上該待排任務的持續時間不能超過后置任務的開始日期，這表示關鍵鏈技術滿足傳統的PERT/CPM技術中關鍵路徑的相關要求，是對建立在約束理論和關鍵路徑上的新的項目進度管理技術。

式（2）表明t時刻正在進行的任務集合所消耗的k的總數量不能超過k資源的可用總數，表示關鍵鏈基數考慮了資源的約束問題，是對對傳統的PERT/CPM技術升級改進。

（二）關鍵鏈數學模型求解

1.從理論上說，資源約束條件下的優化問題是一種組合優化問題，這類問題受到活動的先后次序和資源限制的雙重約束，使問題本身具有內在的復雜性，難以得到數學上的最優解。本文為采用基于優先規則的啟發式方法，來得到一個一定名義上的滿意解。

2.基于PERT/CPM的平行調度法

基于優先規則的啟發式方法包括兩大類：順序調度法和平行調度法[3]。Kolisch在文獻[4]中證明了在所有生成單一可行計劃的基于優先規則的啟發式方法中，平行調度生成方案的計算效率要比順序調度生成方案的計算效率高。

因此，本文選用平行調度法，并在使用PERT/CPM編制的進度計劃的基礎上，采用基于優先規則ACTIM的啟發式方法，建立了一種基于PERT/CPM的平行調度法來對上述問題進行求解，通過改進后的算法在沒有資源約束時識別出的關鍵鏈與關鍵路徑一樣，這樣既吸收了傳統網絡計劃技術的優點，同時克服了當有資源約束時傳統網絡計劃技術的不足，具體步驟如下：

第一步，在工作結構分解（WBS）的基礎上，根據PERT/CPM方法，繪制出型號軟件項目開發的網絡圖，并確定其關鍵路徑，采用ACTIM啟發式方法中的優先規則，為關鍵路徑上的任務賦予屬性A＝1，而對于非關鍵路徑上的任務，為其賦予屬性A＝0。令集合S為該型號軟件項目中的所有項目任務。

第二步，令 等于項目開始時間。

第三步，判斷任務開始時間在[t，t＝1]時段內的所有任務，采用啟發式規則（這里采用ACTIM準則）先安排A＝1的任務，然后調度A＝0的任務。每調度一個任務i，要判斷其對第k種資源的需求量rik是否超過第k種資源的供給量Rik。若rik＞Rk，則將任務i推遲至t+1時刻開始；若rik≤Rik則對任務i進行調度，并且從S中去掉任務i。

第四步，令t＝t+1。若S不為空，則轉到第三步；若S為空，則轉下一步。

第六步，設置項目緩沖、輸入緩沖。

第七步，輸出項目進度計劃。

三、緩沖區的設置方法

（一）現有計算方法比較分析

緩沖量的大小對整個型號軟件項目進度計劃的工期估計以及項目的可行性有著十分重要的影響。本文將首先對幾種已有的緩沖量計算方法進行簡單的介紹和分析，然后在此基礎上提出一種新的緩沖量計算方法。目前緩沖量的計算通常有以下4種方法[5]：

（1）Goldratt法：項目緩沖和輸入緩沖的大小等于前鏈路上各任務50%完成概率下的工期估計之和的一半，即：

buffer＝ti50%（3）

（2）剪貼法：各任務90%完成概率和50%完成概率下的工期估計的差值之和的一半，即

buffer＝Δti（4）

（3）均方差法：該方法基于項目中各任務相互獨立的假定，由Lencent科技公司最早提出，即

buffer＝[（Δti）2]（5）

在方法（2）和（3）中，Δti為各任務90%完成概率和50%完成概率下的工期估計的差，任務i為位于緩沖區前鏈路上的任務，令Si和Ai為別為完成概率為90%和50%的工期估計，即

Δti＝Si-Ai＝ti90%+ti50%，i∈（1，……，n）（6）

（4）彈性系數法

彈性系數法以PERT的三點估計（a，m，b）為基礎，以兩點時間估計（a，b ）代替三點估計，將時間估計m吸收到任務彈性系數K，然后以最樂觀時間進行項目計劃，通過K計算出緩沖區來吸收不確定因素。利用彈性系數K來衡量緩沖區的大小，其計算公式為：

PB＝（b-a）×K（7）

FB＝（b-a）×K（8）

其中，CC表示關鍵鏈上的任務，NCC表示非關鍵鏈上的任務，K表示關鍵鏈上任務的彈性系數，K表示非關鍵鏈上任務的彈性系數。彈性系數K＝，假如PERT的三點估計（a，m，b）中的最可能時間m越接近樂觀時間a，則表明任務延期的可能性越小，K值就越小；對應的m越接近悲觀時間b，則表明任務延期的可能性越大，K值就越大。

前三種緩沖量確定方法雖然簡潔明了，但是都沒有考慮任務持續時間分布的差異以及任務的不確定性會受任務在項目進度計劃中所處的位置的影響的問題，即：距離現在越遙遠的事務越難預測。因此，距離項目開始時間越遠的任務不確定性越大；況且也有考慮到不同的利益相關者所具有的風險偏好也不相同。例如，Goldratt法作為一種線性方法，緩沖區大小隨著相關鏈路持續時間的增長而線性增長，而事實上，這種線性增長的緩沖區在很多情況中都顯得過不合時宜。

而彈性系數法中，用K值體現了各任務持續時間分布的差異，不同的任務由于其持續時間分布的不同對輸入緩沖和項目緩沖的貢獻值不相同，因此K也不盡相同。這雖然解決了任務持續時間分布的差異的問題，但仍難以解決任務的不確定性會受任務在項目進度計劃中所處的位置的影響這個問題。

（二）改進的緩沖區設置算法

緩沖區是為了聚合因為消減單個任務安全時間后產生的風險提出的。事實上，一方面，型號軟件項目的研制的進度管理方面借鑒了一般武器裝備的研制方法，每個任務的計劃工期都是經過專家的評審估計出來的；另一方面，型號軟件項目的研制過程中涉及諸多技術難題，其進度計劃的制定一般考慮了政治和其他方面的因素，和一般社會上的軟件項目的進度設置有很大的區別。

綜上所述，為了避免傳統的緩沖區的設置方法的缺陷，并考慮到型號軟件項目自身的特點，本文在型號軟件項目的進度管理中，在彈性系數法的基礎上，結合型號軟件的特殊型，提出在彈性系數算法模型中加入位置權數α和進度浮動因子Δ的算法。通過α值來反映任務由于在項目進度計劃中所處的位置差異而表現出來的不同的不確定性，通過浮動因子Δ來反映型號軟件的特殊性。

該算法的具體步驟如下：

第一步，本文采用傳統PERT/CPM技術，以PERT的三點估計中的最可能時間m來確定關鍵鏈CC，并且明確關鍵鏈上的任務項和非關鍵鏈上的任務項。

第二步，分別明確關鍵鏈上浮動因子Δi和非關鍵鏈上浮動因子Δj。 是一個介于0和1之間的值。普通的方法直接使用的m只是粗暴的代表著50％的完成概率的估計工期，這往往和實際情況不符，也和型號軟件開發自身的特點大向徑庭。這樣可以采用模糊綜合評判或專家打分的方法等專家的經驗為關鍵鏈和非關鍵鏈上每個任務項賦予一個浮動因子Δ。

第三步，在浮動因子Δ的基礎上，以PERT的三點時間估計確定K。計算公式如下：

Kip＝Δi×K，i∈Scc（9）

Kjf＝Δi×K，j∈（Sncc）（10）

其中，K＝代表普通的彈性系數，Scc代表關鍵鏈中任務的集合，Sncc代表非關鍵鏈中任務的集合。由于分別關鍵鏈上浮動因子Δi和非關鍵鏈上浮動因子Δj各不相同，這樣就解決了由于其持續時間分布的不同對輸入緩沖和項目緩沖的貢獻值不相同造成的問題，同時考慮了型號軟件項目的特殊性。

第四步，根據任務在關鍵鏈中所處的位置，計算位置權數。通過位置權數α進一步評估項目任務的不確定性，以各任務的時間中點為基準，測量其與項目開始時間的距離，再除以項目的時間長度，稱為位置權數α，所以

αip＝，i∈Scc（11）

αjf＝，j∈Sncc（12）

其中，l表示各任務的時間中點與項目開始時間的距離；L表示項目的時間長度，即關鍵鏈開始的時間到關鍵鏈結束的時間之間的距離。這就解決任務的不確定性會受任務在項目進度計劃中所處的位置的影響這個問題。

第五步，利用加入了浮動因子Δi的關鍵鏈上每個任務的彈性系數Kip和位置權數αip計算項目緩沖PB，以及加入了浮動因子Δj的非關鍵鏈上每個任務的彈性系數Kjf和位置權數αip計算輸入緩沖FB。計算公式如下：

PB＝（bi-ai）×K×αip，i∈Scc（13）

FB＝（b-a）×K×αjf，j∈Sncc（14）

結語

使用關鍵鏈技術對型號軟件項目進行進度管理，可以消除或減少不確定性和資源的約束對型號軟件項目造成的影響。本文針對關鍵鏈技術中的兩個難點問題：如何識別關鍵鏈和如何設置緩沖區，進行了重點研究。在分析現有的方法基礎上， 結合型號軟件項目開發的特點，作了一定的改善，分別給出了識別關鍵鏈的數學模型的求解算法和一種改進型的緩沖區的設置算法，從理論上論證了其可行性，但是還有待進一步的實踐檢驗。

參考文獻：

[1] 哈羅德·科茲納.項目管理：計劃、進度和控制的系統方法[M].北京：電子工業出版社，2002：692-707.

[2] 唐力波，馬力.關鍵鏈研究與基于關鍵鏈的項目管理系統[J].計算機工程與實踐，2004，25（11）：2077-2078.

[3] 徐南榮，仲偉俊.科學決策理論與方法[M].南京：東南大學出版社，1996：576-598.

[4] Kolisch，R.．Serial and parallel resource-constrained project scheduling methods revisited：Theory and computation[J]．European Journal of Operational Research．1996，（90）：320-333.

[5] 王俊.航天型號項目進度管理技術研究和系統實現[D].北京：北京信息控制研究所，2008.