資源約束項目計劃外在穩(wěn)健性研究*

崔萬安

(1.廣西民族大學(xué) 管理學(xué)院，廣西 南寧 530006；2.武漢大學(xué) 博士后流動站，湖北 武漢 430072)

一、引言

資源約束項目計劃考慮了稀缺資源的合理分配問題，更接近項目管理的實際情況，在實踐中得到比較廣泛的應(yīng)用。它通常以工期(或費(fèi)用、凈現(xiàn)值)為優(yōu)化的目標(biāo)函數(shù)來尋找最優(yōu)的項目計劃，然而，活動工期的分布函數(shù)難以準(zhǔn)確地估計，資源的最大可獲得量通常也會發(fā)生變動，項目執(zhí)行過程中的不確定因素也不能窮盡。因此，資源約束項目計劃在執(zhí)行中不可避免地發(fā)生偏離甚至被破壞。對此，許多學(xué)者提出制定穩(wěn)健性的項目計劃[1-3]，項目計劃穩(wěn)健性的直觀含義是：一個計劃能夠承受由于不可控因素導(dǎo)致活動工期的“較小”的增加(即對項目工期產(chǎn)生有限的影響)，則稱該計劃具有穩(wěn)健性[1-2]。

Goldratt[4]提出在活動之后插入緩沖區(qū)，以增加項目計劃的穩(wěn)健性。在插入緩沖區(qū)之前，必須確定活動之間的資源依賴關(guān)系，識別出關(guān)鍵鏈(Wiest[5]稱之為關(guān)鍵序列)，否則無法確定緩沖區(qū)的插入將對其他活動產(chǎn)生哪些影響，而Goldratt[4]并未說明識別關(guān)鍵鏈的優(yōu)化方法。在此，關(guān)鍵鏈?zhǔn)侵赣苫顒又g的技術(shù)優(yōu)先關(guān)系和資源依賴關(guān)系以及總時差為零的活動組成的路徑。劉士新等[6]、趙道致等[7]、王淑云等[8]、王仁超等[9]提出各活動之后緩沖區(qū)的設(shè)定方法。

Van De Vonder等[2]研究了項目工期與穩(wěn)定性之間均衡問題，但沒有說明如何建立資源鏈接，如何確定最晚項目計劃(right-justified schedule)，不能保證活動時差的正確性。

AI-Fawzan 與Haouari[3]以項目中所有活動的自由時差之和作為穩(wěn)健性的度量指標(biāo)，建立了以項目工期和穩(wěn)健性為優(yōu)化目標(biāo)函數(shù)的雙目標(biāo)優(yōu)化模型，Abbasi 等人[10]研究了它的有效求解算法。

Kobylański與 Kuchta[11]研究表明，AI-Fawzan 與Haouari[3]方法未必能達(dá)到制定穩(wěn)健性項目計劃的目的。因此，Kobylański與 Kuchta[11]提出用項目中活動自由時差與工期比例的最小值(或活動自由時差的最小值)作為度量穩(wěn)健性的指標(biāo)。在一個既定工期T的約束下，求解穩(wěn)健性最大的項目計劃。該度量方法在一定程度上達(dá)到了制定穩(wěn)健性項目計劃的目的，缺陷在于：Kobylański與Kuchta[11]未說明如何確定活動之間的資源依賴關(guān)系，無法確定自由時差的正確性；T值如何確定尚無有效方法；該優(yōu)化模型為二次優(yōu)化的NP難問題，需要有效的求解算法；若T值等于資源約束項目計劃最短工期時，那么，制定的穩(wěn)健性項目計劃的穩(wěn)健性指標(biāo)值都為零，等價于資源約束項目計劃。

盡管前人提出制定穩(wěn)健的項目計劃[1-3]，但根據(jù)前人[1-3，10-12]對項目計劃穩(wěn)健性的研究來看，尚未發(fā)現(xiàn)對項目計劃的穩(wěn)健性進(jìn)行系統(tǒng)的分類和研究，難以把握項目計劃穩(wěn)健性的關(guān)鍵問題，因此出現(xiàn)了上述問題。

崔萬安和王先甲[13]把項目計劃的穩(wěn)健性劃分為內(nèi)在穩(wěn)健性(Intrinsic robustness)和外在穩(wěn)健性(Extrinsic robustness)，并對內(nèi)在穩(wěn)健性的影響因素進(jìn)行了分析。其中，外在穩(wěn)健性是指在內(nèi)在穩(wěn)健性確定的情況下，在最早項目計劃中的部分或全部活動之后增加緩沖區(qū)，因此使新的項目計劃工期對活動工期變化的不敏感性的增加稱為外在穩(wěn)健性。在此，緩沖區(qū)(buffer time)是指在活動i的自由時差之上增加的一段時間Δbi，活動推遲至此區(qū)間完成，不影響其后開始的活動，因此將這段時間稱為緩沖區(qū)。

本文對外在穩(wěn)健性的影響因素、度量方法進(jìn)行分析。

二、外在穩(wěn)健性的影響因素

緩沖區(qū)的大小、緩沖區(qū)的插入位置、活動之間的資源依賴關(guān)系這三個因素直接影響外在穩(wěn)健性的大小。

(一)緩沖區(qū)的大小

如果確定在哪個(或哪些)活動之后插入緩沖區(qū)，則緩沖區(qū)越大，活動工期的變化對項目工期的影響就越不敏感。如圖1，最大資源可獲得量R=5個單位，矩形及其內(nèi)的字母表示活動及其編號，其水平方向長度表示活動工期，垂直方向長度則表示所需資源量；若確定在最早項目計劃中的活動G之后插入緩沖區(qū)3個單位，也就是項目的計劃完成工期為14個單位，很顯然，由此增強(qiáng)的項目計劃穩(wěn)健性是以延長項目工期為代價的。

圖1 資源約束項目計劃

(二)緩沖區(qū)的插入位置

如上所述，若確定圖1的項目計劃完成工期為14個單位(即比最早項目計劃的項目工期延長3個單位)，那么，有多種插入緩沖區(qū)的方案，不同方案得到的項目計劃對活動工期變化的敏感性不同。如方案1：在A、C、G后各插入1個單位的緩沖區(qū)，B之后插入3個單位緩沖區(qū)，A、B、C、D、G的最早開始時間分別變?yōu)?、0、5、7、10；如方案2：將3個單位的緩沖區(qū)都插入到A之后，其他活動之后不插入緩沖區(qū)，A、B、C、D、G的最早開始時間分別變?yōu)?、0、7、4、11；等等。顯然，方案1得到的項目計劃比方案2要好，對于方案2，若C或G的工期只要稍微延長，項目工期就會超過14個單位，但對于方案1，即便A、C、G的工期都延長一個單位，項目工期仍可保持在14個單位，剛好按計劃完成。

(三)活動之間的資源依賴關(guān)系

一個活動完成之后其釋放的資源究竟分配給哪個(或哪些)活動，一個活動究竟從哪個(或哪些)活動獲取所需資源。如圖1所示，在時刻t=4時，當(dāng)A、B完成后，其釋放的資源可以分配給C、D，在時刻t=8時，C、D釋放的資源可以分配給G，分配方法有多種。如方法1：A釋放的資源全部分配給C，C恰好獲得所需資源，B釋放的資源分配給D一個單位(剩余資源不分配)，D獲得所需資源，C釋放的資源分配給G，G恰好獲得所需資源；方法2：B釋放的資源全部分配給C，A釋放的資源分配給C、D各一個單位，這時C、D得到所需資源，D釋放的資源分配給G一個單位，C釋放的資源分配給G兩個單位，G得到所需資源。這樣由方法1可以確定兩條路徑，即A→C→G，B→D，前一條路徑比后一條路徑長3個單位；而由方法2可以確定3條等長的路徑，即A→C→G，B→C→G，A→D→G；方法1只需要對路徑A→C→G重點控制，而方法2則需要對3條路徑進(jìn)行重點控制，顯然后者的控制難度就更大一些。對于這兩種方法，即便在同一位置插入相同大小的緩沖區(qū)，項目計劃的穩(wěn)健性也不一定相等。

上述三個外在穩(wěn)健性的影響因素具有密切的聯(lián)系，如果單獨考慮一個影響因素而忽視其他因素，則難以把握項目計劃穩(wěn)健性對該因素的敏感程度。活動之間的資源依賴關(guān)系是研究外在穩(wěn)健性的先決條件，如果該因素沒有確定，另外兩個因素就無法討論，在圖1中，如果在B之后插入1個單位的緩沖區(qū)時，究竟哪些活動的開始時間需要向后推遲，無法確定。而一旦活動之間的資源依賴關(guān)系確定，則任意一個位置插入緩沖區(qū)對活動開始時間乃至項目工期的影響即可確定。因此，下面假定活動之間的資源依賴關(guān)系已確定的前提下，研究外在穩(wěn)健性的度量問題。

三、外在穩(wěn)健性的度量方法

從緩沖區(qū)插入的位置看，可以分為關(guān)鍵活動之后、非關(guān)鍵活動之后，前者還包括一類特殊的情形，即關(guān)鍵序列上的最后一個關(guān)鍵活動之后。在此，關(guān)鍵序列是指考慮活動之間的技術(shù)優(yōu)先關(guān)系和資源依賴關(guān)系下總時差為零的活動組成的路徑。如圖1，若建立資源依賴關(guān)系后，可以找到A→C→G，B→D兩條路徑，則A→C→G就是關(guān)鍵序列。

可以在關(guān)鍵序列(或非關(guān)鍵序列)上的每一個活動之后都插入緩沖區(qū)，也可以僅在其中部分活動之后插入緩沖區(qū)，也可以只在關(guān)鍵序列(或非關(guān)鍵序列)上的最后一個活動之后插入緩沖區(qū)，不同的方法，最后帶來的項目計劃穩(wěn)健性的增加可能不同。

如圖1，假定有A→C→G，B→D兩條序列，若在A、C、G之后分別插入一個單位的緩沖區(qū)，項目計劃工期仍為14個單位，各活動的工期延長只要不超過插入的緩沖區(qū)，就不會對緊后活動的開始時間產(chǎn)生影響，若僅限一個活動工期延長，活動A、C、G的工期最大延長量可以分別達(dá)到3、2、1個單位而不影響項目計劃工期，若3個單位緩沖區(qū)全部插入到G之后，則A、C、G的工期最大延長量都可達(dá)到3個單位而不影響項目計劃工期。對于后一種插入方式，一旦緊前活動不能按計劃時間完成，緊后活動就不能按計劃時間開始，可能導(dǎo)致資源調(diào)度費(fèi)用、協(xié)調(diào)費(fèi)用的增加；對于前一種插入方式，C、G的最大可延長量都小于后一種插入方式，一旦超過其最大可延長量，項目計劃工期就會延長，因此將會消耗更多的資源，以及項目竣工投產(chǎn)收入的延遲實現(xiàn)等帶來的直接和間接損失。

在此，根據(jù)外在穩(wěn)健性的定義僅考慮緩沖區(qū)的插入與項目計劃穩(wěn)健性的增加之間的關(guān)系，把外在穩(wěn)健性的度量指標(biāo)(E)定義為：不影響項目計劃工期的條件下，所有活動工期的最大可延長量中的最小值。即：

E=minj∈Abi.

其中，A為活動的集合；bi為活動i的工期最大可延長量。

四、外在穩(wěn)健性度量指標(biāo)E的討論

E關(guān)注的是活動工期延長或完成時間推遲與項目工期的關(guān)系。如圖1，若有A→C→G，B→D兩條序列，存在方案一：在A、C、G之后分別插入一個單位緩沖區(qū)后，E值為1；方案二：僅在C之后插入3個單位緩沖區(qū)則E值為0；方案三：僅在G后插入3個單位緩沖區(qū)則E值為3。顯然，對方案二來說，插入緩沖區(qū)后并未改善E值，因為G的完成時間不可以推遲，而G則決定了項目計劃能否按期完成；但A、C的完成時間均可推遲，從這個意義上講，E是一種保守的度量方法。

E可等價為求所有關(guān)鍵序列上最后一個活動之后緩沖區(qū)的最小值。

在插入緩沖區(qū)的值b一定的條件下，求E的最大化問題，實質(zhì)就是在關(guān)鍵序列之后插入緩沖區(qū)b。

E與項目成本雙目標(biāo)優(yōu)化實質(zhì)上就是確定外在穩(wěn)健性增加帶來收益的增加與項目工期延長帶來成本增加之間的關(guān)系。研究外在穩(wěn)健性必須考慮成本的優(yōu)化，否則沒有意義。

五、結(jié)束語

本文對外在穩(wěn)健性的影響因素進(jìn)行了定性分析，提出了外在穩(wěn)健性的度量指標(biāo)并對之進(jìn)行了討論。下一步，我們將通過數(shù)學(xué)模型，研究外在穩(wěn)健性增加與項目成本增加之間的數(shù)量關(guān)系，確定最優(yōu)的外在穩(wěn)健性的值。

參考文獻(xiàn)：

[1] Willy Herroelen and Roel Leus.Robust and reactive project scheduling：a review and classification of procedures[J].International Journal of Production Research，2004，42(8)：1599-1620.

[2] Stijn Van de Vonder，Erik Demeulemeester，Willy Herroelen and Roel Leus.The trade-off between stability and makespan in resource-constrained project scheduling[J].International Journal of Production Research，2006，44(2)：215-236.

[3] M.A.Al-Fawzan and Mohamed Haouari.A bi-objective model for robust resource-constrained project scheduling[J].International Journal of Production Economics，2005，96(2)：175-187.

[4] Goldratt E M.Critical Chain[M].Great Barrington：North River Press，1997.

[5] Wiest J.D.Some properties of schedules for large projects with limited resources[J].Operations Research，1964，12(3)：395-418.

[6] 劉士新，宋健海，唐加福.基于關(guān)鍵鏈的資源受限項目調(diào)度新方法[J].自動化學(xué)報，2006，32(1)：60-66.

[7] 趙道致，廖 華，劉一騮.關(guān)鍵鏈法：一種新型的項目進(jìn)度計劃方法[J].天津理工學(xué)院學(xué)報，2005，21(2)：8-12.

[8] 王淑云，朱祥松，李 潔.基于資源約束的擴(kuò)張關(guān)鍵路徑法研究[J].管理工程學(xué)報，2006，20(6)：109-111.

[9] 王仁超，歐陽斌，王 琳，等.工程項目計劃“關(guān)鍵性”問題拓展研究[J].系統(tǒng)工程與電子技術(shù)，2004，26(7)：914-917，923.

[10] Babak Abbasi，Shahram Shadrokh and Jamal Arkat.Bi-objective resource-constrained project scheduling with robustness and makespan criteria[J].Applied Mathematics and Computation，2006，180(1)：146-152.

[11] Przemyslaw Kobylański，Dorota Kuchta，A note on the paper by M.A.Al-Fawzan and M.Haouari about a bi-objective problem for robust resource-constrained project scheduling[J].International Journal of Production Economics，2007，107(2)：496-501.

[12] Hédi Chtourou.Mohamed Haouari A two-stage-priority-rule-based algorithm for robust resource-constrained project scheduling[J].Computers & Industrial Engineering，2008，55(1)：183-194.

[13] 崔萬安，王先甲.資源約束項目計劃內(nèi)在穩(wěn)健性影響因素分析[J].太原理工大學(xué)學(xué)報(社會科學(xué)版)，2010，28(1)：20-23.