資源約束下項目調(diào)度魯棒優(yōu)化模型研究

陳偉偉，張云寧，歐陽紅祥

(河海大學(xué) 商學(xué)院，江蘇 南京211100)

資源受限的項目調(diào)度問題(resource - constrained project scheduling problem，RCPSP)是研究如何在同時滿足項目任務(wù)之間的資源約束和時間約束的情況下，將有限的資源合理地分配給各個任務(wù)并確定任務(wù)的開始時間，使項目工期最短。該類問題雖然理論模型十分豐富，但求解相當(dāng)困難，屬于強NP -hard 問題，受到國內(nèi)外眾多學(xué)者的關(guān)注［1-3］。在考慮相互獨立的多個項目與項目之間對共享資源競爭的情況下，進一步研究RCPSP，資源約束下的多項目調(diào)度問題(resource constrained multi-project scheduling problem，RCMPSP)就應(yīng)運而生。

在建設(shè)工程多項目管理中，資源包括資金、勞動力、技術(shù)及管理人員、原材料、設(shè)備、外部協(xié)作單位等，難免會遇到資源沖突的問題。然而，多項目調(diào)度相比單個項目調(diào)度資源種類繁多，關(guān)系復(fù)雜。多項目調(diào)度問題無法像單個項目調(diào)度那樣耗費全部資源去保證一個項目的順利實施，而是必須先分析項目之間錯綜復(fù)雜的關(guān)系及資源的特點，權(quán)衡之后再將資源進行分配。鑒于此，將基于均值-魯棒性模型、調(diào)度魯棒優(yōu)化問題，結(jié)合遺傳算法對資源受限多項目進度計劃進行研究。

1 多項目調(diào)度魯棒優(yōu)化模型

在實際執(zhí)行過程中，調(diào)度的目標(biāo)是提高調(diào)度方案的穩(wěn)定性，通常吸收一部分可以預(yù)期的不確定事件的干擾來增強方案的魯棒性。對任務(wù)工期不確定的資源約束下多項目調(diào)度問題建立魯棒模型。項目管理人員可通過調(diào)整模型中參數(shù)的權(quán)重系數(shù)，得出若干個可行解和最優(yōu)解，從而做出決策。

1.1 均值-魯棒模型

在研究RCMPSP 時，每種模型都有優(yōu)點和缺點，通常只關(guān)注于決策者的一方面，而忽略了其他方面。為了達到更多方面的折中，羊曉飛［4］提出了一種新的魯棒優(yōu)化模型，即均值-魯棒優(yōu)化模型。該優(yōu)化模型中包含兩層優(yōu)化：

(l)第一層優(yōu)化。不考慮魯棒性的期望性能，以期望性能作為優(yōu)化指標(biāo)，其目標(biāo)函數(shù)如下：

定義：壞場景φ∈Ωβ和壞場景集合Ωβ，令T=β×E*，β≥1，則可定義Ωβ?Ω 是一個場景的子集，表示給定的調(diào)度方案π 在實現(xiàn)時的性能大于給定值T的所有場景的集合，即：

(2)第二層優(yōu)化。根據(jù)壞場景集定義魯棒性度量RM(π)：

運用上述均值-魯棒優(yōu)化模型，考慮從單個最壞場景推廣到多個壞場景組成的集合，提出了針對所定義的壞場景集的魯棒優(yōu)化準(zhǔn)則。在該準(zhǔn)則下，可在群體上抑制壞場景性能的惡化，達到項目管理人員在建設(shè)項目過程中抗風(fēng)險的目的。

1.2 調(diào)度模型的假設(shè)

(1)RCMPSP 關(guān)系到一個共享資源庫和若干個并行項目，且所有資源的供給量是有限的。

(2)對共享的有限資源競爭是若干個并行項目之間的唯一聯(lián)系。

(3)并行項目之間互相獨立，且項目之間不存在緊前關(guān)系。

(4)任務(wù)之間存在緊前關(guān)系，但不存在循環(huán)與反饋，且所有任務(wù)均需可更新的資源。

1.3 目標(biāo)函數(shù)構(gòu)建

在采用魯棒優(yōu)化模型研究RCMPSP 問題的過程中，國內(nèi)外學(xué)者提出了不同的算法和規(guī)則。例如，在求解隨機資源受限項目調(diào)度問題中，BALLESTIN 等［5］將情景集的概念應(yīng)用于最優(yōu)調(diào)度規(guī)則中;在離散情景的應(yīng)用中，PADMAN 等［6］用其表示既定目標(biāo)任務(wù)結(jié)束時間的不確定性，HERROELEN 等［7］用其表示任務(wù)工期的波動性。

然而，在大多數(shù)的研究中，多項目調(diào)度以所有項目延期加權(quán)最小為目標(biāo)函數(shù)的模型中，并未考慮到項目延期與項目工期的關(guān)系，即項目工期越長，其延期時間越長的可能性越大。因此，基于單項目魯棒調(diào)度原理，從所有項目延期加權(quán)與項目工期之比的角度出發(fā)，建立魯棒的目標(biāo)函數(shù)進行多項目調(diào)度問題研究。

由于各個項目任務(wù)工期具有不確定性，因此情景集Ω={1，2，…，Φ}為任務(wù)工期的隨機性，情景φ∈Ω。在情景φ 下，第i個項目中第j個任務(wù)Aij的工期向量為在調(diào)度方案π 中，任務(wù)Aij的結(jié)束時間為則第i個項目的工期為所有任務(wù)的最晚完成時間取決于項目的調(diào)度方案π 和工期向量，即項目延期的情況取決于調(diào)度方案。據(jù)此所設(shè)計的魯棒優(yōu)化目標(biāo)函數(shù)如下：

該目標(biāo)是要找到滿足資源及活動邏輯關(guān)系的情景φ，使得各項目延期與項目工期之比的加權(quán)與魯棒性度量加權(quán)最小。其中，風(fēng)險系數(shù)α∈［0，1］表示項目管理者抗風(fēng)險偏向的程度。

1.4 調(diào)度模型的構(gòu)建

其中，It為第t階段內(nèi)正在進行的活動集合。

與傳統(tǒng)的模型相比，該模型是一個覆蓋面更廣的魯棒優(yōu)化模型，通過兩次求解資源受限項目調(diào)度問題，不僅大大降低了計算復(fù)雜性，而且具有理論和實際意義。另外，該模型應(yīng)用于實際問題時，T=β·E*，β≥1 具有實際意義。如果把T看作項目管理者期望的項目工期延期與項目計劃工期的加權(quán)，則式(2)表示所有超過項目管理者預(yù)期的壞場景集合，而式(3)則表示對所有超出項目管理者預(yù)期的壞場景的懲罰。在分析確定的任務(wù)時，在全部Φ 個情景中，可以近似擬合任務(wù)j的工期為任意概率分布。實際運用時，情景集由歷史數(shù)據(jù)得到，任務(wù)的概率分布不需要了解，這使得的魯棒優(yōu)化模型更具有普適性和優(yōu)越性。

2 魯棒調(diào)度數(shù)學(xué)模型遺傳算法求解

遺傳算法(genetic algorithm，GA)是一種有效解決最優(yōu)化問題的方法，可以較快地搜索到全局最優(yōu)解，特別適用于多極點的優(yōu)化問題。遺傳算法對需要求解的目標(biāo)函數(shù)形態(tài)沒有明確要求，比傳統(tǒng)的優(yōu)化方法更加優(yōu)越。在任務(wù)工期不確定的情況下求解魯棒優(yōu)化模型，一般先從全部情景中獲得一個小樣本，即Φ 個情景，用來對全部情景進行樣本估計。因此采用小樣本估計方法通過遺傳算法來求解RCMPSP 魯棒優(yōu)化模型。

2.1 模型求解GA 算法參數(shù)和操作設(shè)計

根據(jù)GA 算法優(yōu)化流程，對建立的魯棒優(yōu)化模型求解流程設(shè)計如下：

(1)編碼方案。大多數(shù)學(xué)者運用遺傳算法求解確定型RCPSP，采用任務(wù)列表法對染色體進行編碼。為了能夠給項目管理者提供良好的決策依據(jù)，求解的基準(zhǔn)調(diào)度需要良好的穩(wěn)定性和魯棒性，通常采用直接表達方式。在用遺傳算法求解魯棒優(yōu)化模型時，選取項目中每個任務(wù)的開始時間作為染色體π =(π1，π2，…，πj)，也就是把調(diào)度方案假定為遺傳算法中的染色體［8］。

(2)初始種群。采用隨機方法產(chǎn)生初始種群，使得各項目中的每個任務(wù)可以獲得一個最早開始時間到最遲開始時間之間的隨機值。

(3)適應(yīng)值函數(shù)。針對魯棒優(yōu)化模型，設(shè)計適應(yīng)值函數(shù)如下：

其中，f(i)為當(dāng)前代中染色體i的適配值，在Φ種情景下如果目標(biāo)函數(shù)值越小，則算法中個體的適應(yīng)值越大。πi為第i個染色體代表的調(diào)度方案。

(4)選擇算子。采用賭輪盤選擇法，將上一代的優(yōu)先個體傳遞到下一代。每個染色體被選擇的概率按照式(7)計算：

(5)交叉算子。采用單點交叉算子，選取一個隨機交叉點，通過在交叉點上交換親代的基因得到若干個子代染色體。其中交叉概率為pc。

(6)變異算子。通過交叉算子獲得子代染色體后，再進一步使用變異算子優(yōu)化調(diào)度方案。變異算子通過改變一個或若干個基因的值從而增加種群的多樣性，設(shè)變異概率為pm。變異通常有3種方式：均勻變異、增量變異和非均勻變異。這里采用均勻變異算子。

2.2 模型求解GA 算法步驟

資源約束下的多項目調(diào)度問題的魯棒模型具體求解步驟如下［9］：

(1)初始設(shè)定遺傳算法中的每個參數(shù)，并讀取全部的情景樣本值;

(2)根據(jù)給定各項目中的每個任務(wù)分配一個最早開始時間和最遲開始時間之間的隨機值生成初始種群，根據(jù)式(6)計算每個個體的適應(yīng)值;

(3)根據(jù)式(7)選擇個體，采用概率pc、pm分別進行交叉運算、變異運算;

(4)重復(fù)步驟(3)直到新一代種群產(chǎn)生;

(5)按照式(6)計算當(dāng)前種群中每一個個體的適應(yīng)值，并保留和記錄最佳個體;

(6)當(dāng)?shù)螖?shù)達到規(guī)定的代數(shù)，轉(zhuǎn)步驟(7);否則，迭代次數(shù)加1，返到步驟(3);

(7)輸出最佳個體，終止程序。其中最佳個體為項目調(diào)度問題的最優(yōu)魯棒解。

3 仿真算例

采用Matlab 軟件對給出的一個算例進行仿真調(diào)度，選取文獻［10］中的算例進行求解分析。該算例含有3 個不同網(wǎng)絡(luò)結(jié)構(gòu)的項目，其網(wǎng)絡(luò)活動如圖1 所示。這3 個項目分別由6、8、7 個活動組成，所有活動共享4 種資源(r1，r2，r3，r4)，每個資源的約束總量為4。每個項目的計劃工期和需求的資源量如表1 和表2 所示。3 個項目的重要性權(quán)重分別為w1=0.5、w2=0.3、w3=0.2。3 個項目具有相同的任務(wù)開工時間，在資源無約束的情況下項目的完工工期分別為13 d、13 d 和10 d，計劃完工工期是23 d、23 d 和20 d。

圖1 各項目的網(wǎng)絡(luò)活動圖

表1 各項目活動的持續(xù)時間

3.1 模型求解

假設(shè)項目中任務(wù)j的隨機工期+3］中的一個正整數(shù)，從所有情景集中隨機選取500 個情景作為項目實際的情景集合，再從實際的情景集合中隨機選取50 個情景作為小樣本進行求解，即Φ =50。假定總代數(shù)GEN=200，種群大小POP=20，交叉概率pc=0.6，變異概率pm=0.1，魯棒優(yōu)化模型中α=0.5，使用均勻變異算子求解。

通過逐步迭代進化搜索所有情景下的魯棒調(diào)度方案，如圖2 所示，遺傳算法求解效果顯著。隨著代數(shù)的增加，目標(biāo)函數(shù)值逐漸減小，在GEN=30 左右開始趨于穩(wěn)定，第60 代種群的目標(biāo)函數(shù)值與最初種群的目標(biāo)函數(shù)值相比明顯變小。

表2 各項目活動的資源需求

圖2 遺傳算法求解的進化過程

3.2 結(jié)果分析

為了表明上述的調(diào)度魯棒優(yōu)化準(zhǔn)則的適用性，逐步調(diào)整風(fēng)險系數(shù)α，每一個風(fēng)險系數(shù)α 可以對應(yīng)一個不同的調(diào)度方案。全部情景下調(diào)度方案的E(π)與RM(π)的變化如表3 所示。

表3 風(fēng)險系數(shù)α 對解的影響

由表3 可知，隨著α 的增加，E(π)不斷增大，RM(π)則逐漸減小。當(dāng)抗風(fēng)險系數(shù)α 選擇較大時，項目工期的延期期望值會有所增大，但魯棒性度量減小，即風(fēng)險較大;當(dāng)抗風(fēng)險系數(shù)α 較小時，多項目調(diào)度方案有較小的進度延期期望值，但此時的魯棒性度量較大，即風(fēng)險較小;α=0 時，此時的魯棒性度量最大，表明模型對項目風(fēng)險控制具有一定的有效性。因此，項目管理者根據(jù)自身的風(fēng)險偏好，選擇符合項目實際情況的風(fēng)險系數(shù)α，從而得到可以選擇的多項目調(diào)度方案以供決策。

4 結(jié)論

建立了資源約束環(huán)境下的多項目魯棒性調(diào)度模型，提出了多項目調(diào)度問題實現(xiàn)最大化的魯棒性研究的一種算法。考慮到項目工期越長，其延期時間越長的可能性越大，采用了各項目工期延遲與活動計劃工期之比作為指標(biāo)，改進并建立了多項目調(diào)度模型。同時，在魯棒模型的建立中，改進了傳統(tǒng)魯棒模型的不足，采用均值-魯棒模型進行研究，能夠更全面地提高魯棒調(diào)度的抗風(fēng)險能力，為項目管理者提供了新的決策方法。

［1］KOLISCH R，PADMAN R. An integrated survey of deterministic project scheduling［J］. Omega，2001，29(3)：249 -272.

［2］KOLISCH R，HARTMANN S. Experimental investigation of heuristics for resource - constrained project scheduling：an update［J］. European Journal of Operational Research，2006，174(1)：23 -37.

［3］壽涌毅.資源約束下多項目調(diào)度的迭代算法［J］.浙江大學(xué)學(xué)報：工學(xué)版，2004，38(8)：1095 -1099.

［4］羊曉飛.基于場景和模糊描述的不確定Job Shop 魯棒調(diào)度［D］.濟南：山東大學(xué)圖書館，2009.

［5］BALLESTIN F，TRAUTMANN N. An iterated -local- search heuristic for the resource - constrained weighted earliness-tardiness project scheduling problem［J］. International Journal of Production Research，2008，46(22)：6231 -6249.

［6］PADMAN R，ZHU D. Knowledge integration using problem spaces：a study in resource - constrained project scheduling［J］. Journal of Scheduling，2006，9(2)：133 -152.

［7］HERROELEN W，LEUS R. Project scheduling under uncertainty：survey and research potentials［J］. European Journal of Operational Research，2005，165(2)：289 -306.

［8］王偉.任務(wù)工期不確定的資源受限項目調(diào)度優(yōu)化［D］.杭州：浙江大學(xué)圖書館，2010.

［9］壽涌毅，王偉. 基于魯棒優(yōu)化模型的項目調(diào)度策略遺傳算法［J］.管理工程學(xué)報，2009(4)：148 -152.

［10］鄭彥琦.基于活動成本目標(biāo)的資源受限多項目進度計劃［D］.武漢：華中科技大學(xué)圖書館，2007.