王櫟綺,何立華(中國石油大學(華東)經(jīng)濟管理學院,山東青島　266580)

基于向量投影TOPSIS法的資源均衡優(yōu)化

王櫟綺,何立華
(中國石油大學(華東)經(jīng)濟管理學院,山東青島266580)

針對資源均衡優(yōu)化問題,定義了一種基于向量投影的TOPSIS指標為資源均衡性度量的新指標.對于多個資源均衡優(yōu)化方案,首先確定正、負理想優(yōu)化方案,計算各方案在正、負理想方案上的向量投影,然后計算各個方案的相對貼近度,再根據(jù)相對貼近度的大小衡量各個優(yōu)化方案的優(yōu)劣.該指標可以有效避免當采用傳統(tǒng)的均值、方差或熵等度量指標評價某幾個優(yōu)化方案時,同一度量指標下這幾個優(yōu)化方案的目標函數(shù)值都相等而無法對這幾個優(yōu)化方案進行區(qū)別的不足.其次,構(gòu)建了基于向量投影的TOPSIS為度量指標的資源均衡優(yōu)化模型,并針對該模型設(shè)計了相應(yīng)的粒子群算法.最后,運用一個算例驗證分析了所提指標和算法的可行性和有效性.

資源均衡;TOPSIS;向量投影;粒子群算法

引用格式:Wang Liqi,He Lihua．Resources Equilibrium Optimization Based on by TOPSIS of Vector Projection [J]．Journal of Gansu Sciences,2016,28(2):113G118．[王櫟綺,何立華．基于向量投影TOPSIS法的資源均衡優(yōu)化[J]．甘肅科學學報,2016,28(2):113G118．]

資源均衡問題是指在項目工期保持不變的情況下,通過合理調(diào)整網(wǎng)絡(luò)計劃中非關(guān)鍵路徑上的工序,盡量避免出現(xiàn)資源的高峰和低谷現(xiàn)象,使每天資源需求量趨于均衡的過程[1].資源均衡問題在理論上已被證明是NPGhard組合優(yōu)化問題[2],在實踐中有著廣泛的應(yīng)用價值.關(guān)于資源均衡問題的研究,一直吸引著國內(nèi)外眾多學者和實際工作者的關(guān)注,并從不同角度提出了各種資源均衡優(yōu)化的模型和算法[3G5].在資源均衡優(yōu)化模型中,學者們提出了多種衡量資源均衡性的度量指標,以絕對偏差最小作為度量資源均衡性的指標[6,7],以每天資源需求量的平方和作為目標函數(shù)[8,9],以矩最小來評價項目的資源均衡性[10G12],這些指標雖易操作、簡單明了,但其誤差較大.為了更好地反映優(yōu)化方案的資源均衡性,有學者提出了以方差作為資源均衡性的度量指標[13,14].此外,何大義等[15]提出的極大熵準則可知,熵本身是一個連續(xù)的函數(shù),熵越大該分布就越接近于均勻分布.對此,文獻[16G18]中提出以資源熵作為目標函數(shù),來度量各個優(yōu)化方案的資源均衡性.研究基于逼近理想解排序法(TOPSIS,technique for order perference by similarity to ideal solution)指標為資源均衡性度量標準的新指標,來評價多個資源均衡優(yōu)化方案的優(yōu)劣.

1　基于向量投影TOPSIS法的指標

1．1相關(guān)概念

首先,給出向量投影和相對貼近度等概念.

由于不同的評價屬性具有不同的量綱,因此在決策之前需要對屬性進行無量綱和同趨化處理.對于具有多個屬性的方案X＝(xij)m×n,可以進行規(guī)范化處理: j＝1

對于資源均衡優(yōu)化方案來說,要求每天資源需求量越趨于均衡越好.對此,可以將每個均衡優(yōu)化方案Xi中的資源需求量看作一個向量,先將向量的每一維作簡化處理,該指標越小越好.如果有多種資源,在簡化處理后,再對每一種資源作規(guī)范化處理.方案Xi同趨化處理后記作Pi＝

定義2稱為決策方案的正理想方案,其中:

定義3稱為決策方案的負理想方案,其中:

定義4TOPSIS是一種逼近于理想解的排序法,可以采用相對貼近度的大小表示方案Xi與其他方案的接近程度[20],記作其中:PrXi＋表示方案Xi在正理想方案上的向量投影;PrXi－表示方案Xi在負理想方案上的向量投影. Ci(Ci∈0,1[])越大,表示該方案越接近正理想方案,說明方案Xi越優(yōu)[21].

1．2傳統(tǒng)度量指標計算現(xiàn)假設(shè)有A、B、C三個方案,分別以均值、方差、熵值及基于向量投影的TOPSIS作為度量指標對這三個方案進行評價.A、B、C三個方案數(shù)據(jù)值如表1所列.表1中數(shù)字代表每天該方案的波動性,方案要求越趨于均衡越好.

(1)以均值為度量指標,有

(2)以方差為度量指標,有

表1　A、B、C三個方案數(shù)據(jù)值Table 1　Data value of A,B and C scheme

(3)以熵值為度量指標[16],有

根據(jù)式(4)~式(6),分別以均值、方差、熵值衡量三個方案的均衡性,計算結(jié)果如表2所列.

表2　計算結(jié)果Table 2　Calculation results table

1．3基于向量投影TOPSIS的新指標

表3　處理后的A、B、C三個方案Table 3　A,B and C scheme after treating

(2)確定正、負理想方案根據(jù)定義2和定義3,分別確定正理想方案和負理想方案,如表4所列.

表4　正、負理想方案Table 4　Positive and negative ideal optimization schemes

(3)計算三個方案在正、負理想方案上的向量投影根據(jù)式(1),A、B、C三個方案在正、負理想方案上的向量投影分別為

(4)計算各個方案的相對貼近度根據(jù)公式(3),A、B、C三個方案的相對貼近度分別為

由于CA＜CB＜Cc,因此C方案優(yōu)于B方案優(yōu)于A方案.從上述計算分析可以看出,以基于向量投影的TOPSIS作為均衡性度量指標,可以對采用傳統(tǒng)度量指標不能區(qū)分的方案進行區(qū)別.

2　問題描述與模型構(gòu)建

資源均衡優(yōu)化是指在項目工期固定的情況下,通過合理調(diào)整網(wǎng)絡(luò)計劃中非關(guān)鍵路徑上的工序,使資源需求量趨于均衡的過程.在均衡優(yōu)化中,假設(shè)滿足以下條件[12,22]:項目總工期一定;各個活動的持續(xù)時間不變,且在活動的持續(xù)時間內(nèi)所需要的資源量不變,對項目的重要程度都一樣;活動間的邏輯關(guān)系不變;活動是連續(xù)的;資源供應(yīng)在各個時期是充足的,即不考慮資源供給的限制;活動為單模式.在此,以基于向量投影的TOPSIS為指標構(gòu)建資源均衡優(yōu)化模型,有

式(7)表示各優(yōu)化方案的相對貼近度,要求越大越好; PrXj＋表示優(yōu)化方案Xj在正理想優(yōu)化方案Pr＋上的投影,PrXj－表示優(yōu)化方案Xj在負理想優(yōu)化方案Pr－上的投影.式(8)表示優(yōu)化方案Xj在正、負理想方案上的投影.為了書寫方便,用b表示正負理想方案,j表示優(yōu)化方案個數(shù),bn表示正、負理想優(yōu)化方案中第n天的資源消耗量.式(9)表示活動i的實際開始時間與其最早開始時間之差不超過其總時差,ti表示活動i的實際開始時間,ESi表示活動i的最早開始時間, TFi表示活動i的總時差.式(10)表示各個活動的持續(xù)時間非負,I表示活動數(shù).

3　算法

粒子群算法(PSO,particle swarm optimizaG tion)是模擬生物群體行為而構(gòu)造的一種隨機搜索算法[23].粒子在飛行的過程中,用一個速度決定它們飛行的方向和距離,所有粒子通過追隨當前最優(yōu)粒子在解的空間中進行搜索[24].粒子群中粒子在尋優(yōu)的過程中,根據(jù)式(11)~式(12)來更新自己的速度和位置[25]:

式(11)表示粒子速度的更新,其中:非負常數(shù)w為慣性因子,通常情況下w在[0．4,0．9]范圍內(nèi)取值;非負常數(shù)c1和c2為學習因子,一般取c1＝c2＝2; r1、r2為[0,1]范圍內(nèi)的隨機數(shù)[16].式(12)表示粒子位置的更新.

用粒子群算法求解資源均衡優(yōu)化問題,以活動數(shù)N表示粒子空間探索維數(shù)[16],在此,粒子規(guī)模取30個.滿足約束條件式(9)和式(10)的一組活動的開始時間為Sj＝(sj1,sj2,?,sjn)(j＝1,2,?,M).為了保證生成的優(yōu)化方案可行,粒子飛行的位置需要限制在一定范圍內(nèi).由于每個活動的實際開始時間在其最早開始時間ESj和最晚開始時間LSj內(nèi)變化,因此設(shè)定粒子位置xj的變化范圍為xj∈[ESj,LEj].粒子通過不斷地迭代更新,達到最佳適應(yīng)度值,即此時所對應(yīng)的粒子的位置即為問題的一個可行解.

4　算例分析

采用文獻[17]中的算例,該項目中每個活動對項目的重要程度相同且均需要消耗一種資源.為了更加符合實際,將活動H的資源需求量由原文中的0改為3,各個活動的持續(xù)時間和資源需求量如圖1所示.

4．1不同優(yōu)化方案比較

根據(jù)單代號網(wǎng)絡(luò)圖,用粒子群算法通過MATG LAB編程計算,項目工期T＝16天.選擇不同相對貼近度下的8種資源均衡優(yōu)化方案,這8種方案每天的資源需求量如表5所列.

(1)計算每天資源需求量平均值.通過計算,8個方案中每天資源需求量平均值相等,即＝7.

圖1　項目單代號網(wǎng)路Fig．1　Program list code network

表5　每天資源需求量Table 5　Daily resources demand table

表6　每天資源需求量偏差Table 6　Deviation of daily resource requirements

(3)確定正、負理想優(yōu)化方案.按照定義2和定義3確定正、負理想優(yōu)化方案,每天資源需求量如表7所列.

(4)計算各方案在正負理想方案上的向量投影.根據(jù)向量投影概念及式(1)計算,得

表7　正、負理想方案每天資源需求量Table 7　Daily resource requirements of positive and negative ideal scheme

(5)計算各優(yōu)化方案的相對貼近度.根據(jù)相對貼近度的概念和公式(3)計算,得

同理有

4．2三種指標計算結(jié)果對比

通過以上計算可以看出,方案8優(yōu)于其余各個方案.現(xiàn)分別以方差、資源熵、相對貼近度三個指標作為資源均衡優(yōu)化度量指標,對各個方案的優(yōu)化結(jié)果進行對比分析,三種均衡性度量指標計算結(jié)果如表8所列.

表8　三種指標計算結(jié)果Table 8　Calculation results of three indexes

將8種優(yōu)化方案的計算結(jié)果按照相對貼近度的大小從小到大排序,見表8.從表8可以看出,以方差或熵作為資源均衡性度量指標,方案5、方案6和方案7的目標函數(shù)值都相等,即難以對這三個方案進行區(qū)別.而當以基于向量投影的TOPSIS作為資源均衡性度量指標,可以看出方案7優(yōu)于方案5和方案6.對于方案5和方案6,方案5在第一天和第二天所需資源量分別是7和3,方案6在第一天和第二天所需資源量分別是3和7.相應(yīng)的,正理想優(yōu)化方案中第一天和第二天所需資源量分別是7和7,負理想優(yōu)化方案中第一天和第二天的資源量分別是3和3,因此方案5和方案6的相對貼近度相等.

此外,比較表8中三種度量指標下各個方案均衡性計算結(jié)果,不僅可以看出,以基于向量投影的TOPSIS作為資源均衡性度量指標,各個優(yōu)化方案的優(yōu)劣排序與以方差或熵為度量指標的排序一致,而且對采用傳統(tǒng)度量指標如方差、熵等難以區(qū)別的方案5、方案6及方案7可以進行甄別,并能找到最優(yōu)方案(方案8最優(yōu)).因此,以研究所提的基于向量投影的TOPSIS作為資源均衡性度量指標,具有可行性和有效性.

5　結(jié)語

定義了一種基于向量投影的TOPSIS指標作為資源均衡性度量新指標.對于工程項目的某幾種資源均衡優(yōu)化方案,這一指標不僅避免了當采用傳統(tǒng)的均值、方差或熵等指標來衡量其均衡性時,同一度量指標下這幾個優(yōu)化方案的目標函數(shù)值都相等而無法對這幾個方案進行甄別的不足,還可以在多個優(yōu)化方案中找到最優(yōu)方案.以基于向量投影的TOPSIS作為均衡性度量指標,不僅能夠解決各種拓展的資源均衡優(yōu)化問題,而且可以用于各種項目調(diào)度問題、方案評選以及群決策等問題中.

[1]Koulinas G K,Anagnostopoulos K P．A New Tabu SearchG based HyperGheuristic Algorithm for Solving Construction Leveling Problems with Limited Resource Availabilities[J]．Automation in Construction,2013,31:169G175．

[2]Blazewicz J,Lenstra J K．Scheduling Subject to Resource ConG straints Classification and Complexity[J]．Discrete Applied Mathematics,1983,5(1):11G24．

[3]Drótos M,Kis T．Resource Leveling in a Machine Environment [J]．European Journal of Operational Research,2011,212(1): 12G21．

[4]龐南生,紀昌明．廣義時序下活動多模式與離散型資源均衡優(yōu)化[J]．系統(tǒng)工程學報,2011,26(4):538G545．

[5]Hariga M A,EIGSayegh S M．Cost Optimization Model for the MultiGresource Leveling Problem with Allowed Activity SplitG ting[J]．Journal of Construction Engineering and ManageG ment,2011,137(1):56G64．

[6]Said M E．Resource Leveling in Construction by Optimization [J]．Journal of Construction Engineering and Management, 1989,115(2):302G316．

[7]Senouci A B,Eklin N N．Use of Genetic Algorithms in ReG source Scheduling of Construction Projects[J]．Journal of Construction Engineering and Management,2004,130(6):869G877．

[8]Tarek H．Optimization of Resource Allocation and Leveling UG sing Genetic Algorithms[J]．Journal of Construction EngiG neering and Management,1999,125(3):167G175．

[9]Son J,Skibniewski M J．MultiGheuristic Approach for Resource Leveling Problem in Construction Engineering:Hybrid ApG proach[J]．Journal of Construction Engineering and ManageG ment,1999,125(1):23G31．

[10]徐哲,賈子君,李科．工程項目資源均衡優(yōu)化的混合遺傳算法研究[J]．數(shù)學的實踐與認識,2011,41(6):24G29．

[11]Hiyassat M．Applying Modified Minimum Moment Method to Multiple Resource Leveling[J]．Journal of Construction EngiG neering and Management,2001,127(3):192G198．

[12]Christodoulou SE,Ellinas G,Michaelidou K A．Minimum MoG ment Method for Resource Leveling Using Entropy MaximiG zation[J]．Journal of Construction Engineering and ManageG ment,2010,136(5):518G527．

[13]王祖和,亓霞．多資源均衡的權(quán)重優(yōu)選法[J]．管理工程學報, 2002,16(3):91G93．

[14]田豐春,楊種學,楊寧．虛擬樣機工程中的項目資源均衡優(yōu)化研究[J]．計算機工程與科學,2011,33(12):184G188．

[15]何大義,邱菀華．運用熵極大化準則求解連續(xù)型不確定性決策問題[J]．系統(tǒng)工程理論與實踐,2002,22(9):97G100．

[16]乞建勛,王強,賈海紅．基于熵權(quán)和粒子群的資源均衡新方法研究[J]．中國管理科學,2008,16(1):90G95．

[17]Symeon Christodoulou,Georgios Ellinas,Pooyan Aslani．EntropyG based Scheduling of ResourceGconstrained Construction Projects [J]．Automation in Construction,2009,18(7):918G928．

[18]丁繼勇,王卓甫,李慧敏．配套施工條件下水電工程多資源均衡優(yōu)化[J]．水力發(fā)電學報,2013,32(5):299G305．

[19]楊靜,邱菀華．基于離差的模糊多屬性決策法及其應(yīng)用[J]．系統(tǒng)工程,2008,26(6):107G110．

[20]屈文閣．一種區(qū)間數(shù)多屬性決策方法在經(jīng)濟評價中的應(yīng)用[J]．甘肅科學學報,2013,25(4):152G155．

[21]周宏安,劉三陽．基于離差最大化模型的模糊多屬性決策投影法[J]．系統(tǒng)工程與電子技術(shù),2007,29(5):741G744．

[22]陸惠民,杜訓．工程項目資源優(yōu)化的混合整數(shù)規(guī)劃算法[J]．東南大學學報:自然科學版,1991,21(4):123G129．

[23]劉琦鈾,施燦濤,李鐵克．基于混合粒子群算法的工藝規(guī)劃與調(diào)度集成問題研究[J]．工業(yè)工程與管理,2013,18(6):20G26．

[24]陳志勇,杜志達,周華．基于微粒群算法的工程項目資源均衡優(yōu)化[J]．土木工程學報,2007,40(2):93G96．

[25]彭武良,郝永平．求解資源受限項目調(diào)度問題的改進粒子群算法[J]．系統(tǒng)工程,2010,28(4):84G88．

Resources Equilibrium Optimization Based on by TOPSIS of Vector Projection

Wang Liqi,He Lihua
(School of Economics and Management,China University of Petroleum,Qingdao 266580,China)

A new index for measuring resource equilibrium is defined on the basis of TOPSISindex of vecG tor projection for the problems of resources equilibrium optimization．For multiGresources equilibrium optiG mization schemes,first,positive and negative ideal optimization schemes shall be determined to calculate its vector projection and then its relative closeness which is used to measure its advantages and disadvantages in reverse．This index can effectively avoid the disadvantages of being unable to distinguish several optimiG zation schemes when they are evaluated by traditional measurement indexes like mean,variance,entropy and so on,which has same objective function valve under the same measurement index．Second,the relevant particle swarm optimization is designed based on resources equilibrium optimization model which is build on the basis of the measurement index TOPSIS of vector projection．Third,the feasibility and effectiveness of the indexes and algorithms mentioned are analyzed through applying example verification．

Resource equilibrium;TOPSIS;Vector projection;Particle swarm optimization

F062．1

A

1004G0366(2016)02G0113G06

10．16468/j．cnkii．ssn1004G0366．2016．02．024．

2015G06G13;

2015G09G14．

山東省自然科學基金項目(ZR2015GM009);中央高?；究蒲袠I(yè)務(wù)費專項基金(15CX05007B)．

王櫟綺(1989G),女,碩士研究生,研究方向為工程項目管理．EGmail:wangliqi369369＠163．com．