歐陽紅祥，陳偉偉，李 欣

(1.河海大學(xué) 商學(xué)院，江蘇 南京210098;2.中石化集團管道儲運分公司 南京輸油處，江蘇 南京210046)

資源優(yōu)化有兩類問題，一類是資源有限工期最短問題，另一類是工期固定資源均衡問題。工期固定資源均衡問題按涉及的資源種類數(shù)，可分為單資源和多資源均衡問題。工期固定資源均衡問題理論上屬于組合優(yōu)化問題，目前解決這類問題常用的方法有解析式法、啟發(fā)式算法及智能優(yōu)化算法［1］。解析式算法只適用于較小規(guī)模、較少資源的優(yōu)化。啟發(fā)式算法可以求解大規(guī)模資源均衡問題，但由于其優(yōu)化準(zhǔn)則、算法都與特定的問題有關(guān)，因此算法的可移植性和通用性較差［2］。智能優(yōu)化算法主要包括遺傳算法、模擬退火算法、螞蟻算法，以及神經(jīng)網(wǎng)絡(luò)等。遺傳算法是一類可用于復(fù)雜系統(tǒng)優(yōu)化計算的魯棒搜索算法，與其他方法相比，其具有自行概率搜索、運算并行性，以及搜索效率高等優(yōu)點［3］，因此許多學(xué)者借助遺傳算法來求解資源均衡問題，并取得了豐富的成果。在以往的許多研究中，學(xué)者們往往基于項目各作業(yè)的開工時間進行編碼，這種編碼方式容易導(dǎo)致在求解過程中產(chǎn)生不滿足作業(yè)間邏輯關(guān)系約束的非可行解。目前解決的辦法有兩種：一是通過修復(fù)算子對不滿足作業(yè)間邏輯約束的非可行解進行修復(fù);二是通過特定的編碼方式來避免求解過程中產(chǎn)生違反作業(yè)間邏輯關(guān)系約束的非可行解［4］。相比較而言，后一種辦法效率更高?；诖?，筆者提出了一種基于間隔率的編碼與解碼方法，可以避免在交叉、變異等遺傳操作中出現(xiàn)違反作業(yè)間邏輯關(guān)系的情況，從而大大提高遺傳算法解決該類問題的尋優(yōu)速度。

1 多資源均衡優(yōu)化模型

1.1 假設(shè)和定義

假設(shè)1 各項活動在優(yōu)化過程中是不可拆分的，其持續(xù)時間是固定的;各項活動所需資源種類數(shù)和數(shù)量在優(yōu)化過程中保持不變。

假設(shè)2 在優(yōu)化過程中，項目的總工期不變，并且在任一時間段內(nèi)，各種資源的供應(yīng)量足夠多，可滿足需求。

定義1V={1，2，…，N}為網(wǎng)絡(luò)計劃中所有活動的集合，Di和LSi為活動i的持續(xù)時間和最遲開始時間，Pred(i)為由活動i的緊前活動組成的集合，Si和Fi分別為活動i的計劃開始時間和計劃完成時間。為滿足既定的邏輯關(guān)系和總工期不變的要求，Si∈［max(Fh)，LSi］，其中，h∈Pred(i)，i∈V?；顒觟的計劃開始時間的取值范圍如圖1 所示。

定義2 稱PFi為間隔率，PFi= (Si-max(Fh))/(LSi-max(Fh))。從圖1 可以看出，0≤PFi≤1。若PFi=0，則表示活動i的計劃開始時間與緊前活動h的計劃完成時間相等，也即活動h按計劃完成后，活動i立即開始。若PFi=1，則意味著活動i的計劃開始時間與其最遲開始時間相等。

定義3 假如某一項目需要K種資源(如材料、設(shè)備等)，第i項活動單位時間內(nèi)所需第k種資源數(shù)量記為項目總工期記為T，第t時刻項目所需第k種資源數(shù)量記為

圖1 活動i 的計劃開始時間的取值范圍

1.2 優(yōu)化模型描述

多資源均衡優(yōu)化的目標(biāo)是尋找各項活動的計劃開始時間，使得在項目總工期內(nèi)各種資源需要量盡可能均衡。用于評價資源均衡效果的指標(biāo)主要有不均衡系數(shù)、方差、最大絕對離差和極差值這4 種［5-6］。由于方差更能體現(xiàn)項目在各時刻資源需求的不均衡程度，因此，筆者選擇該指標(biāo)用于評價資源需求均衡程度。

假如第k種資源需求的方差用δ(k)表示，則：

對于多資源均衡問題，由于資源的重要性有所差別，因此可采用不同的權(quán)重系數(shù)來反映其對目標(biāo)函數(shù)的影響程度。為消除不同資源在數(shù)量等級、單位等方面的差異，需要對資源量進行標(biāo)準(zhǔn)化處理［7-8］。對數(shù)據(jù)進行標(biāo)準(zhǔn)化處理的方法有很多，筆者采用極小-極大化方法。設(shè)為第k種資源需要量的最大值，則若用表示第k種資源需要量的最小值，則第t時刻項目所需第k種資源數(shù)量經(jīng)過極小-極大化變化后變成為可按式(3)進行計算。

第k種資源需要量的平均值ˉR(k)經(jīng)過極小-極大化變化后變成ˉR(k)'，則：

通過上述變換后，各種資源需要量的取值都在區(qū)間［0，1］內(nèi)，并且變成了一個無量綱的數(shù)，從而消除了資源在數(shù)量級、單位等方面對目標(biāo)函數(shù)取值的影響。

綜上所述，多資源均衡的目標(biāo)函數(shù)可定義為：

約束條件為：

式(5)中，ω(k)為選定的一組權(quán)系數(shù)，滿足，其他符號同前。

2 遺傳算法

遺傳算法是模擬生物在自然環(huán)境中的遺傳和進化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法，它最早由美國密執(zhí)安大學(xué)的HOLLAND 教授提出。20 世紀(jì)70 年代JONG 基于遺傳算法的思想，在計算機上進行了大量的純數(shù)值函數(shù)優(yōu)化計算實驗，在一系列研究工作的基礎(chǔ)上，20 世紀(jì)80 年代由GOLDBERG 進行歸納總結(jié)，形成了遺傳算法的基本框架。遺傳算法的基本運算過程如下［9-10］：

(1)初始化。令進化代數(shù)計數(shù)器t=0，最大進化代數(shù)為T，隨機生成M個個體作為初始群體P(t);

(2)個體評價。計算群體P(t)中各個個體的適應(yīng)度;

(3)選擇運算。通過選擇運算選出最優(yōu)的個體直接遺傳到下一代;

(4)交叉運算。通過配對交叉產(chǎn)生新的個體;

(5)變異運算。將個體串中某些基因座上的基因值作出變動;群體P(t)經(jīng)過選擇、交叉和變異運算之后得到下一代群體P(t+1)。

(6)終止條件判斷。若t=T，則以進化過程中所得到的具有最大適應(yīng)度個體作為最優(yōu)解輸出，終止計算。

3 算例

某網(wǎng)絡(luò)計劃如圖2 所示，箭頭線上方的數(shù)字表示活動所需資源數(shù)量(假設(shè)項目中所有活動使用兩種資源)，箭頭線下方的數(shù)字表示活動的持續(xù)時間(時間單位為天)，假定兩種資源的權(quán)重分別為0.7和0.3。

圖2 活動所需資源數(shù)量

3.1 計算活動的時間參數(shù)

根據(jù)給定的網(wǎng)絡(luò)計劃，采用關(guān)鍵線路法(critical path method，CPM)計算各項活動的最早開始時間(ES)和最遲開始時間(LS)。

3.2 浮點數(shù)編碼

考慮到資源均衡優(yōu)化目標(biāo)函數(shù)和約束條件的復(fù)雜性，筆者采用浮點數(shù)編碼方法。以各項活動的間隔率(PF)作為決策變量，個體的每個基因值用區(qū)間［0，1］內(nèi)的一個浮點數(shù)來表示。各項活動的浮點數(shù)編碼如表1 所示。由間隔率的定義可知，可行解集合{PFi}對應(yīng)唯一的計劃開始時間序列S。

表1 浮點數(shù)編碼

3.3 染色體解碼

染色體解碼的實質(zhì)是將各活動的間隔率轉(zhuǎn)換成對應(yīng)的計劃開始時間。解碼的規(guī)則如下：

3.4 選擇運算

筆者采用輪盤賭選擇法來選擇遺傳個體。其基本思想是：各個個體被選中的概率與其適應(yīng)度大小成正比。具體過程為：①先計算出群體中所有個體的適應(yīng)度總和;②計算每個個體的相對適應(yīng)度大小，即為該個體被遺傳到下一代的概率;③使用模擬賭盤操作(即0 到1 的隨機數(shù))來確定各個個體被選中的次數(shù)。

3.5 交叉運算

筆者采用單點交叉算子，具體執(zhí)行過程如下：①對群體中的個體進行兩兩隨機配對;②隨機設(shè)置交叉點位置;③依預(yù)先設(shè)定的概率(p=0.8)，互換交叉點后的基因值，形成兩個新的個體。

3.6 變異運算

采用均勻變異算子，具體操作過程如下：①指定個體編碼串中的某個基因座為變異點;②依預(yù)先設(shè)定的概率(p=0.05)從對應(yīng)基因的取值范圍［0，1］中隨機取一數(shù)值代替原數(shù)值。

3.7 運算結(jié)果

利用Matlab 7.0 提供的遺傳算法工具箱，結(jié)合具體問題編制相應(yīng)的適應(yīng)度函數(shù)、選擇函數(shù)、交叉函數(shù)和變異函數(shù)，優(yōu)化運行過程經(jīng)過51 代，其適應(yīng)度函數(shù)值下降到3.201。優(yōu)化后各項活動的計劃開工時間如表2 所示。各資源需求量優(yōu)化前后的對比如圖3 和圖4 所示。資源1 的方差由37.7 下降到2.8，資源2 的方差由7.71 下降到4.14。

表2 各項活動計劃開工和完工時間 天

圖3 第1 種資源優(yōu)化前/后需求量對比

圖4 第2 種資源優(yōu)化前/后需求量對比

4 結(jié)論

遺傳算法是一類具有較好魯棒性的搜索算法，由于其模型簡單、易于實現(xiàn)、無需梯度信息和參數(shù)少等特點使其在組合優(yōu)化問題中顯示出良好的求解效果。筆者將遺傳算法引入到資源均衡優(yōu)化問題中，建立了基于間隔率的資源均衡優(yōu)化模型，從而避免了在優(yōu)化過程中容易產(chǎn)生無效解的情況，大大提高了優(yōu)化效率。在此基礎(chǔ)上，敘述了算法流程，并通過算例證明所引入的算法具有一定的可行性和有效性，為工程項目實施中的資源安排提供了一種新的思路和方法。同時，研究過程也表明，優(yōu)化結(jié)果與參數(shù)的選擇有很大關(guān)系，因此，如何融合其他算法對現(xiàn)有模型進行改進，使其具有更好的全局收斂性，還有待進一步研究。

［1］HARRIS R B. Packing method for resource leveling［J］. Journal Construction Engineering and Management，1990，116(2)：331 -350.

［2］謝潔銳，黃忠民，俞守華，等. 一種“工期固定，資源均衡”的神經(jīng)網(wǎng)絡(luò)模型設(shè)計［J］. 計算機應(yīng)用與軟件，2005，22(1)：66 -68.

［3］駱剛，劉爾烈，王健.遺傳算法在網(wǎng)絡(luò)計劃資源優(yōu)化中的應(yīng)用［J］.天津大學(xué)學(xué)報，2004(2)：179 -183.

［4］LEU S S，YANG C H，HUANG J C. Resource leveling in construction by genetic algorithm- based optimization and its decision support system application［J］.Automation in Construction，2000(10)：27 -41.

［5］TAREK H. Optimization of resource allocation and leveling using genetic algorithms［J］.Journal of Construction Engineering and Management，1999(3)：167-175.

［6］張淑山，張連營. 建設(shè)項目多資源優(yōu)化的進化算法實現(xiàn)［J］.科技進步與對策，2009(11)：88 -90.

［7］張連營，張金平，王亮.工程項目資源均衡的遺傳算法及其Matlab 實現(xiàn)［J］.管理工程學(xué)報，2004(1)：52-55.

［8］王首緒，周學(xué)林.遺傳算法優(yōu)化施工網(wǎng)絡(luò)計劃的多種資源均衡［J］.重慶交通學(xué)院學(xué)報，2001(6)：39-45.

［9］玄光男，程潤偉.遺傳算法與工程設(shè)計［M］. 北京：科學(xué)出版社，2000：43 -98.

［10］雷英杰. Matlab 遺傳算法工具箱及應(yīng)用［M］. 西安：西安電子科技大學(xué)出版社，2005：65 -98.