王偉鑫,葛顯龍,王 旭,倪 霖

(1.四川外國語大學(xué)國別經(jīng)濟(jì)與國際商務(wù)研究中心,重慶400031; 2.四川外國語大學(xué)國際商學(xué)院,重慶400031; 3.重慶交通大學(xué)管理學(xué)院,重慶400074; 4.重慶大學(xué)機(jī)械工程學(xué)院,重慶400040)

基于關(guān)鍵鏈的非搶占式多項(xiàng)目調(diào)度多屬性優(yōu)化

王偉鑫1,2,葛顯龍3,王 旭4,倪 霖4

(1.四川外國語大學(xué)國別經(jīng)濟(jì)與國際商務(wù)研究中心,重慶400031; 2.四川外國語大學(xué)國際商學(xué)院,重慶400031; 3.重慶交通大學(xué)管理學(xué)院,重慶400074; 4.重慶大學(xué)機(jī)械工程學(xué)院,重慶400040)

針對(duì)多項(xiàng)目調(diào)度中難以實(shí)現(xiàn)動(dòng)態(tài)調(diào)度和高效調(diào)度的問題,從多項(xiàng)目調(diào)度整體效用最大化角度,提出基于關(guān)鍵鏈的非搶占式多項(xiàng)目調(diào)度操作模式,構(gòu)建多項(xiàng)目調(diào)度模型.利用正態(tài)云模型中云滴的隨機(jī)性與穩(wěn)定性的特征改進(jìn)遺傳算法中交叉算子與變異算子的設(shè)置方式,并對(duì)模型進(jìn)行數(shù)據(jù)模擬和算例分析.結(jié)果表明,采用非搶占式操作模式,不僅可實(shí)現(xiàn)多項(xiàng)目調(diào)度的整體效用最大化,而且可實(shí)現(xiàn)多項(xiàng)目調(diào)度的帕累托改善并提高資源的利用率.

關(guān)鍵鏈;多項(xiàng)目調(diào)度;云遺傳算法;非搶占式

1　引　言

多項(xiàng)目調(diào)度具有動(dòng)態(tài)性和復(fù)雜性的特點(diǎn),因共享項(xiàng)目資源,故一個(gè)子項(xiàng)目調(diào)度計(jì)劃的變更會(huì)引起多項(xiàng)目間的級(jí)聯(lián)效用,使得項(xiàng)目執(zhí)行中存在延期完工的風(fēng)險(xiǎn)[1],且多項(xiàng)目調(diào)度存在閑置狀態(tài)的資源調(diào)配難度大等問題,降低了資源利用率[2].關(guān)鍵鏈方法從工期的不確定性和資源約束視角論述了該方法的優(yōu)越性[3],關(guān)鍵鏈的緩沖設(shè)置方式增強(qiáng)了其應(yīng)對(duì)不確定性的能力,但因不確定因素的誘因難以辨識(shí)制約了調(diào)度的效果.為了進(jìn)一步提高多項(xiàng)目調(diào)度的資源利用率并制定適合不確定環(huán)境下的調(diào)度策略,本文在采用關(guān)鍵鏈多項(xiàng)目調(diào)度方法的基礎(chǔ)上,分析非搶占式操作模式對(duì)調(diào)度計(jì)劃的影響,是關(guān)鍵鏈多項(xiàng)目調(diào)度研究的擴(kuò)展和延伸.

針對(duì)多項(xiàng)目調(diào)度應(yīng)對(duì)不確定性因素能力不足和資源利用率低等問題,目前的研究主要采用模糊調(diào)度、隨機(jī)調(diào)度和關(guān)鍵鏈方法(critical chain method,CCM)等[4-6],因關(guān)鍵鏈方法考慮了多項(xiàng)目調(diào)度工期的不確定性,更符合其實(shí)際需求而廣泛的應(yīng)用于多項(xiàng)目調(diào)度領(lǐng)域.Rabbania等[7]提出CCM的資源受限隨機(jī)網(wǎng)絡(luò)項(xiàng)目調(diào)度方法,但未能充分考慮關(guān)鍵鏈的特性,本質(zhì)上仍是一種隨機(jī)調(diào)度方法;Bevilacqua等[8]研究發(fā)現(xiàn)CCM能最大限度的縮短項(xiàng)目工期并降低運(yùn)行成本;彭武良等[9]分析了活動(dòng)多模式和工期的不確定的資源受限關(guān)鍵鏈項(xiàng)目調(diào)度問題,并建立了多模式關(guān)鍵鏈項(xiàng)目調(diào)度模型,其實(shí)質(zhì)是一種復(fù)雜的重調(diào)度過程;劉瓊等[10]提出以CCM多項(xiàng)目的魯棒性指標(biāo)最大化和工期最小化為目標(biāo),建立關(guān)鍵鏈多項(xiàng)目的調(diào)度優(yōu)化模型,提高了調(diào)度計(jì)劃應(yīng)對(duì)不確定性的能力.

隨著調(diào)度環(huán)境的變化和多項(xiàng)目調(diào)度的研究視角不斷延伸,國內(nèi)外學(xué)者根據(jù)多項(xiàng)目調(diào)度的動(dòng)態(tài)性和資源沖突等問題,探研調(diào)度模式在關(guān)鍵鏈多項(xiàng)目調(diào)度中的作用.Debels等[11]提出雙種群遺傳算法(BPGA)解決非搶占式執(zhí)行模式的資源受限項(xiàng)目調(diào)度問題;Buddhakulsomsiri等[12]證明在存在資源閑置和臨時(shí)資源不可用的情況下,非搶占式調(diào)度模式能有效的縮短項(xiàng)目工期.多項(xiàng)目調(diào)度傳統(tǒng)的調(diào)度操作模式(即搶占式操作模式)假設(shè)活動(dòng)一旦開始中途就不能停止直到活動(dòng)完成,傳統(tǒng)的調(diào)度操作模式在工期不確定及執(zhí)行動(dòng)態(tài)調(diào)度計(jì)劃情況下調(diào)度質(zhì)量還有待改進(jìn)[13].而多項(xiàng)目調(diào)度的非搶占式操作模式打破了傳統(tǒng)的活動(dòng)一旦開始中途就不能停止的操作模式,允許優(yōu)先級(jí)較高的任務(wù)搶占優(yōu)先級(jí)較低的任務(wù)資源,且重新開始沒有任何額外費(fèi)用[14].因此,非搶占式操作模式在提高資源利用率和縮短項(xiàng)目工期等方面的表現(xiàn)優(yōu)于傳統(tǒng)的搶占式操作模式.但基于關(guān)鍵鏈的多項(xiàng)目調(diào)度中常存在墨菲法則和帕金森定律的問題,且基于關(guān)鍵鏈的多項(xiàng)目調(diào)度的子項(xiàng)目之間存在級(jí)聯(lián)效應(yīng),單個(gè)項(xiàng)目延期會(huì)影響到其他的子項(xiàng)目.所以,基于關(guān)鍵鏈的多項(xiàng)目調(diào)度抵御不確定性的能力更弱,即魯棒性更低.

對(duì)現(xiàn)有的多項(xiàng)目調(diào)度問題進(jìn)行綜覽[15-20],以往研究多以工期最小化、成本最小化、資源平衡、時(shí)間–成本均衡以及現(xiàn)金流均衡等為優(yōu)化目標(biāo),多項(xiàng)目調(diào)度中存在資源利用率低和應(yīng)對(duì)不確定性因素能力不足等問題,以工期或成本等單一目標(biāo)為優(yōu)化目標(biāo),與多項(xiàng)目實(shí)際的需求不匹配.而項(xiàng)目的工期,成本及質(zhì)量等目標(biāo)間具有明顯的成本替代性,一個(gè)目標(biāo)的實(shí)現(xiàn)是以犧牲另一個(gè)目標(biāo)為代價(jià).因此,本文從多項(xiàng)目整體效用最大化角度出發(fā),對(duì)工期–成本–質(zhì)量–魯棒性目標(biāo)進(jìn)行多屬性均衡優(yōu)化,力求在多項(xiàng)目動(dòng)態(tài)調(diào)度的前提下,提高資源利用率.

綜上所述,分析非搶占式操作模式對(duì)基于關(guān)鍵鏈的多項(xiàng)目調(diào)度策略的影響,從多項(xiàng)目調(diào)度整體效用最大化角度,構(gòu)建并剖析以工期–成本–質(zhì)量–魯棒性為優(yōu)化目標(biāo)的多項(xiàng)目調(diào)度模型,利用正態(tài)云模型中云滴的隨機(jī)性與穩(wěn)定性的特征改進(jìn)遺傳算法中交叉算子與變異算子的設(shè)置方式.最后,通過算例驗(yàn)證模型和算法的有效性.

2　基于關(guān)鍵鏈的非搶占式多項(xiàng)目調(diào)度模型

針對(duì)多項(xiàng)目動(dòng)態(tài)調(diào)度過程中資源利用率低、調(diào)度的魯棒性較低以及工期與成本之間的背反關(guān)系問題展開研究,以工期、成本、質(zhì)量和魯棒性為優(yōu)化目標(biāo),但四個(gè)屬性不具備同類可比性.為此,采用多屬性效用函數(shù)法建立問題模型.本文所使用的符號(hào)定義如表1所示.

表1　符號(hào)定義Table 1 Notation definition

2.1效用函數(shù)及問題描述

多屬性效用函數(shù)利用試驗(yàn)心理學(xué)原理,把基于關(guān)鍵鏈的多項(xiàng)目調(diào)度策略映射為不同的效用值,從而找到使多項(xiàng)目調(diào)度效用最大化的資源分配和任務(wù)調(diào)度方案.為了更準(zhǔn)確的描述問題,需明確如下定義:

定義1屬性是影響調(diào)度決策的一個(gè)或一組變量.分為成本型屬性(即數(shù)值越低越好)和效益型屬性(即數(shù)值越高越好).成本型屬性可表示為rij=min(aij)/aij,i=1,2,...,I,j=1,2,...,J.效益型屬性可表示為rij=aij/max(aij),i=1,2,...,I,j=1,2,...,J.

在工期、成本、質(zhì)量和魯棒性四個(gè)屬性中,工期和成本屬性是成本型屬性;質(zhì)量和魯棒性是效益型屬性.對(duì)其進(jìn)行規(guī)范化處理可以得到矩陣R=(rij)I×J.

定義2在基于關(guān)鍵鏈的非搶占式多項(xiàng)目調(diào)度中,對(duì)整體服務(wù)質(zhì)量的滿意程度稱為效用.

定義3多項(xiàng)目調(diào)度過程中各優(yōu)化目標(biāo)之間建立的函數(shù)關(guān)系稱為效用函數(shù),記為U(rij).

基于關(guān)鍵鏈的非搶占式多項(xiàng)目調(diào)度問題包含有N個(gè)子項(xiàng)目,各個(gè)子項(xiàng)目之間并行執(zhí)行,不存在緊前緊后關(guān)系.根據(jù)多屬性效用函數(shù)的分解定理,可得

其中αT,αC,αQ,αL≥0,αT+αC+αQ+αL=1.

效用函數(shù)的優(yōu)化目標(biāo)是求解最大值,即效用值越大,生成的調(diào)度方案越優(yōu).因此,解空間是凸集且效用函數(shù)均為凹函數(shù),故采用效用函數(shù)的二次函數(shù)形式.項(xiàng)目總工期D的工期效用值為1,則

多項(xiàng)目調(diào)度的成本由可更新資源和不可更新資源的成本構(gòu)成.其效用函數(shù)值為1,則有

基于關(guān)鍵鏈的非搶占式多項(xiàng)目調(diào)度的質(zhì)量的效用值為1時(shí),則有

基于關(guān)鍵鏈的非搶占式多項(xiàng)目調(diào)度的魯棒性效用值為1時(shí),則有

2.2建立多屬性均衡優(yōu)化模型

本文所使用的符號(hào)定義見表1.為了使基于關(guān)鍵鏈的非搶占式多項(xiàng)目調(diào)度的效用最大化,提出以工期–成本–質(zhì)量–魯棒性為優(yōu)化目標(biāo)的決策變量,并利用多屬性效用函數(shù)構(gòu)建基于關(guān)鍵鏈的非搶占式多項(xiàng)目調(diào)度多屬性均衡優(yōu)化模型.其模型如式(6)～式(19)所示.

式(6)是目標(biāo)函數(shù),表示基于關(guān)鍵鏈的非搶占式多項(xiàng)目調(diào)度的多屬性均衡優(yōu)化問題的總效用最大;式(7)表示活動(dòng)j最早開始時(shí)間不能比它的緊前活動(dòng)i的持續(xù)時(shí)間小;式(8)表示采用自適應(yīng)緩沖方法設(shè)置項(xiàng)目的緩沖值,項(xiàng)目的緩沖由項(xiàng)目按時(shí)完工的期望概率決定;式(9)表示資源利用程度,決定了設(shè)置緩沖的數(shù)值.T在計(jì)算項(xiàng)目緩沖時(shí)表示關(guān)鍵鏈的長(zhǎng)度,在計(jì)算匯入緩沖時(shí)表示非關(guān)鍵鏈的長(zhǎng)度.在設(shè)置匯入緩沖時(shí),對(duì)比緩沖尺寸和非關(guān)鍵鏈上最后一個(gè)活動(dòng)的自由時(shí)差的大小,將較小者設(shè)置為緩沖大小,這種方法有效的避免因緩沖設(shè)置過大而產(chǎn)生的關(guān)鍵鏈發(fā)生變化的問題.式(10)和式(11)分別表示對(duì)項(xiàng)目中可更新資源和不可更新資源的約束;式(12)表示插入緩沖的位置,即當(dāng)關(guān)鍵鏈上的活動(dòng)出現(xiàn)一個(gè)不在關(guān)鍵鏈上的資源約束的活動(dòng)或者是緊前活動(dòng)時(shí),就在該活動(dòng)與關(guān)鍵鏈之間插入一個(gè)匯入緩沖PB.式(13)表示項(xiàng)目的總工期;式(14)表示項(xiàng)目的總成本;式(15)表示多項(xiàng)目的總質(zhì)量水平;式(16)和式(17)分別表示質(zhì)量?jī)r(jià)值和質(zhì)量指數(shù)的計(jì)算方法;式(18)表示多項(xiàng)目調(diào)度的魯棒性(采用活動(dòng)松弛時(shí)間和最小活動(dòng)松弛時(shí)間的均值之和量度其魯棒性);式(19)表示自由松弛時(shí)間的計(jì)算方式.當(dāng)關(guān)鍵鏈上活動(dòng)的自由松弛時(shí)間為零(關(guān)鍵鏈魯棒性最大)時(shí),非關(guān)鍵鏈上活動(dòng)的自由松弛時(shí)間也將最大化即非關(guān)鍵鏈上所有活動(dòng)的機(jī)動(dòng)時(shí)間將變得寬裕.因此,后續(xù)活動(dòng)的開始時(shí)間的穩(wěn)定性得到改善,使魯棒性得到提高.

3　求解算法設(shè)計(jì)研究

3.1優(yōu)先權(quán)調(diào)度規(guī)則

多項(xiàng)目調(diào)度方法產(chǎn)生的初始調(diào)度計(jì)劃是建立在各個(gè)活動(dòng)的優(yōu)先權(quán)確定的基礎(chǔ)上,確定各個(gè)活動(dòng)的優(yōu)先權(quán)將導(dǎo)致解的空間縮小,且不能確保生成的調(diào)度解使基于關(guān)鍵鏈的非搶占式多項(xiàng)目調(diào)度的多屬性均衡優(yōu)化目標(biāo)最優(yōu).優(yōu)先權(quán)規(guī)則下基于關(guān)鍵鏈的非搶占式多項(xiàng)目調(diào)度執(zhí)行步驟如下:

1)確定各個(gè)活動(dòng)的優(yōu)先權(quán);

2)生成多項(xiàng)目調(diào)度的積極計(jì)劃;

3)確定關(guān)鍵鏈與非關(guān)鍵鏈;

4)計(jì)算緩沖區(qū)并嵌入緩沖區(qū)并生成非搶占式關(guān)鍵鏈多項(xiàng)目調(diào)度計(jì)劃的方案.

將不在關(guān)鍵鏈上且有緊前關(guān)系的活動(dòng)串聯(lián)起來,所得到的就是多項(xiàng)目調(diào)度的非關(guān)鍵鏈.由于調(diào)度計(jì)劃的制定過程中會(huì)出現(xiàn)多條關(guān)鍵鏈的現(xiàn)象,對(duì)此問題,根據(jù)關(guān)鍵鏈上各個(gè)活動(dòng)的效用值選擇效用值最大的一條關(guān)鍵鏈作為最終關(guān)鍵鏈,其他的按非關(guān)鍵鏈處理.采用自適應(yīng)緩沖設(shè)置的方法設(shè)置關(guān)鍵鏈多項(xiàng)目調(diào)度的項(xiàng)目緩沖和匯入緩沖,根據(jù)項(xiàng)目緩沖和匯入緩沖的插入規(guī)則確定項(xiàng)目緩沖和匯入緩沖在各個(gè)活動(dòng)中間的插入位置,插入緩沖后所得到多項(xiàng)目調(diào)度計(jì)劃即為關(guān)鍵鏈多項(xiàng)目調(diào)度計(jì)劃的實(shí)施方案.

3.2云遺傳算法

標(biāo)準(zhǔn)遺傳算法(static genetic algorithm,SGA)存在收斂速度慢或陷入局部收斂等缺陷,需對(duì)交叉和變異概率進(jìn)行調(diào)試才能獲得較為理想的收斂效果.而本文中的算例對(duì)算法要求更高,為此,在傳統(tǒng)遺傳算法的基礎(chǔ)上引入云模型理論,利用云模型云滴的隨機(jī)性和穩(wěn)定傾向性的特征,改進(jìn)遺傳算法中的交叉和變異概率的設(shè)置方式,設(shè)計(jì)了云遺傳算法.在算法的初期設(shè)置較大的交叉和變異概率以求快速產(chǎn)生優(yōu)秀個(gè)體,在算法的后期設(shè)置較小的交叉和變異概率,適應(yīng)度高的優(yōu)秀個(gè)體以較小的概率參與交叉變異以保護(hù)優(yōu)秀個(gè)體不被破壞,從而加速了的算法的全局收斂.利用正態(tài)云模型的控制參數(shù)在種群適應(yīng)度發(fā)生變化時(shí)進(jìn)行自適應(yīng)調(diào)整,提高了搜索精度和搜索范圍的準(zhǔn)確程度,交叉概率Pc和變異概率Pm的生成算法如下:

Pc的生成算法.

其中k1,k2,k3,k4為[0,1]范圍內(nèi)的常數(shù),取k1=k3=1,k2=k4=0.5.由此可知,Pc和Pm的初始值較大,的初始值較大,但隨著種群的不斷進(jìn)化而逐漸減小.在標(biāo)準(zhǔn)遺傳算法的基礎(chǔ)上引入云模型理論,正態(tài)云模型穩(wěn)定傾向性保留了最大適應(yīng)度周圍的優(yōu)秀個(gè)體,并提高適應(yīng)度較低的個(gè)體,但隨著種群的不斷進(jìn)化而逐漸減小.在標(biāo)準(zhǔn)遺傳算法的基礎(chǔ)上引入云模型理論,正態(tài)云模型穩(wěn)定傾向性保留了最大適應(yīng)度周圍的優(yōu)秀個(gè)體,并提高適應(yīng)度較低的個(gè)體的搜索能力從而生成更大解空間內(nèi)的新的個(gè)體,有效改善了算法的隨機(jī)性.對(duì)于非搶占式多項(xiàng)目調(diào)度的多屬性均衡優(yōu)化問題,采用云遺傳算法進(jìn)行求解,能大幅度提高了算法的魯棒性.云遺傳算法的具體步驟如下:

1)編碼設(shè)計(jì):本文選用多組編碼的染色體結(jié)構(gòu),染色體的基因?qū)?yīng)活動(dòng)的編號(hào),基因的值對(duì)應(yīng)一個(gè)優(yōu)先權(quán)列表.自然編碼表示任務(wù)優(yōu)先權(quán),優(yōu)先權(quán)為1～m之間的自然數(shù),優(yōu)先權(quán)的數(shù)值越大表示優(yōu)先權(quán)越大.為保證染色體的有效性,活動(dòng)的優(yōu)先權(quán)必須與基因建立一一對(duì)應(yīng)的關(guān)系,以滿足解空間分布的均勻性和搜索的全局性的要求.染色體結(jié)構(gòu)如圖1所示.

圖1　染色體結(jié)構(gòu)Fig.1 Chromosome structure

2)初始種群:隨機(jī)產(chǎn)生優(yōu)先權(quán)的全排列Wu(t),染色體所確定的各個(gè)任務(wù)的優(yōu)先權(quán)是關(guān)鍵鏈生產(chǎn)的重要依據(jù),由上文中提出的關(guān)鍵鏈計(jì)劃生成的步驟確定最終關(guān)鍵鏈,并計(jì)算項(xiàng)目緩沖和嵌入緩沖,最后確定緩沖插入的位置.

3)適應(yīng)度函數(shù):適應(yīng)度函數(shù)是評(píng)價(jià)染色體優(yōu)劣的依據(jù),為此,設(shè)計(jì)是適應(yīng)度函數(shù)為fit(t)=1/u(t),其中u(t)表示個(gè)體的目標(biāo)值,所以適應(yīng)度函數(shù)值越小表示個(gè)體越優(yōu).

4)交叉算子:由云模型X發(fā)生器生成種群的交叉概率Pc,計(jì)算交叉算子的確定度u、Ex、En和He,由X條件云發(fā)生器生成一對(duì)個(gè)體,采用雙交叉點(diǎn)操作,選擇一個(gè)基因交叉點(diǎn)將選中的基因編碼置于子代染色體首位,在刪除父代染色體相同基因編碼的基礎(chǔ)上按原編碼順序復(fù)制到子代上,如果生成違反約束條件的子代染色體則對(duì)叉入點(diǎn)位置進(jìn)行調(diào)整.變異操作見圖2所示.

5)變異算子:由云模型X發(fā)生器生成種群的變異概率Pm,Ex取原個(gè)體,計(jì)算En和He,利用云發(fā)生器生成一個(gè)新個(gè)體,當(dāng)在(0,1)產(chǎn)生的隨機(jī)數(shù)temp＞u時(shí),則隨機(jī)選擇染色體中的兩個(gè)基因并對(duì)換兩者的基因碼,生成新的染色體,變異操作見圖3所示.

6)重復(fù)步驟2)到步驟5),當(dāng)Maxgen=50或滿足條件則停止操作,輸出結(jié)果.

4　試驗(yàn)仿真

4.1算例分析

以3個(gè)并行項(xiàng)目構(gòu)成的多項(xiàng)目調(diào)度問題為例,對(duì)基于關(guān)鍵鏈的非搶占式多項(xiàng)目調(diào)度的多屬性均衡優(yōu)化模型及云遺傳算法進(jìn)行試驗(yàn)仿真.多項(xiàng)目調(diào)度各個(gè)活動(dòng)的相關(guān)信息見圖4所示,共包含36個(gè)活動(dòng)及虛擬開始活動(dòng)和虛擬結(jié)束活動(dòng).基于關(guān)鍵鏈的非搶占式多項(xiàng)目調(diào)度問題中包含4種可更新資源和4種不可更新資源,資源種類、各活動(dòng)的資源消耗量和工期等資源使用信息詳見表2所示.單位工期的間接費(fèi)用率c=4,六種資源單價(jià)分別為

圖2　交叉操作Fig.2 Crossover operation

圖3　變異操作Fig.3 Mutation operation

由MATLAB實(shí)現(xiàn)云遺傳算法編程,對(duì)建立的模型進(jìn)行求解.設(shè)種群規(guī)模Popsize=50,為滿足種群多樣性的要求,進(jìn)化代數(shù)的取值為Maxgen=50,求得關(guān)鍵鏈在項(xiàng)目2上.因此,基于關(guān)鍵鏈的非搶占式多項(xiàng)目調(diào)度多屬性均衡優(yōu)化問題的最大效用值為u(T,C,Q,L)=0.863,T=32,C=1 568,Q=0.891,L= 0.732.

表2　資源使用信息Table 2 Using information of resources

圖4　多項(xiàng)目網(wǎng)絡(luò)結(jié)構(gòu)圖Fig.4 Network structure diagrams of multi-project

由圖4可知,基于關(guān)鍵鏈的非搶占式多項(xiàng)目調(diào)度問題利用多屬性效用函數(shù)建立數(shù)學(xué)模型,根據(jù)工期、費(fèi)用、質(zhì)量和魯棒性四個(gè)屬性均衡優(yōu)化項(xiàng)目目標(biāo),優(yōu)化的結(jié)果能幫助管理者和經(jīng)營者有效的控制和監(jiān)管多項(xiàng)目的進(jìn)度.根據(jù)算例的結(jié)果,管理者和經(jīng)營者根據(jù)項(xiàng)目關(guān)注點(diǎn)的不同做出多屬性的均衡優(yōu)化決策.

4.2非搶占式與搶占式操作模式對(duì)比分析

本文提出基于關(guān)鍵鏈的非搶占式多項(xiàng)目調(diào)度問題,從項(xiàng)目調(diào)度問題網(wǎng)站http://129.187.106.231/psplib/上下載標(biāo)準(zhǔn)算例,以PSPLIB‘?dāng)?shù)據(jù)J10,J20和J30為例,測(cè)試采用非搶占式和搶占式操作模式的結(jié)果,詳見表3所示.MRCPSP(%)(多模式資源受限項(xiàng)目調(diào)度問題,multi-mode resource-constrained project scheduling problems,MRCPSP)表示基于MRCPSP的關(guān)鍵路徑的平均偏差;NP-MRCPSP(%)(非搶占式多模式資源受限項(xiàng)目調(diào)度問題,non-preemptive multi-mode resource-constrained project scheduling problems,NP-MRCPSP)表示基于NP-MRCPSP的關(guān)鍵路徑的平均偏差;Impr.(%)表示NP-MRCPSP相對(duì)MRCPSP的平均完工時(shí)間的改善程度;BETTER表示非搶占式解決方案高于MRCPSP解決方案的的數(shù)量;EDUAL表示非搶占式解決方案等于MRCPSP解決方案的數(shù)量;WORSE表示非搶占式解決方案小于MRCPSP解決方案的的數(shù)量.

從表3可知,在資源約束條件下,項(xiàng)目工期與資源量密切相關(guān),影響不可執(zhí)行模式的分配,基于關(guān)鍵鏈的多項(xiàng)目調(diào)度問題采用非搶占式操作模式能明顯縮短項(xiàng)目工期.因此,非搶占式操作模式能得到更優(yōu)的多項(xiàng)目調(diào)度方案.

表3　非搶占式與搶占式操作模式對(duì)比統(tǒng)計(jì)結(jié)果Table 3 Comparative statistical results of operation mode of preemptive and non-preemptive

4.3算法對(duì)比分析

為了檢驗(yàn)云遺傳算法的性能,本文分別采用標(biāo)準(zhǔn)遺傳算法、禁忌搜索算法和云遺傳算法對(duì)上述算例進(jìn)行算例分析,采用各算法的計(jì)算結(jié)果收斂情況如圖5所示.

圖5　算法收斂對(duì)比圖Fig.5 The contrast diagram of algorithm converges

由圖5可見,雖然禁忌搜索算法的收斂速度最快,但是容易產(chǎn)生局部最優(yōu)解,而云遺傳算法收斂速度比禁忌搜索算法略慢,但其收斂下降速度最快,因此,其全局收斂能力在三者中最強(qiáng).并且,為了進(jìn)一步檢驗(yàn)算法的有效性,將上述算例計(jì)算20次對(duì)其最優(yōu)值、最劣值和平均值三個(gè)指標(biāo)進(jìn)行統(tǒng)計(jì),計(jì)算結(jié)果如表4所示:

分析表4所示的數(shù)據(jù),發(fā)現(xiàn)云遺傳算法的搜索成功率最大,禁忌搜索算法的搜索成功率最小.最劣值和平均值都是云遺傳算法的結(jié)果最小,從而反映出云遺傳算法的全局搜索能力最強(qiáng).

基于關(guān)鍵鏈的非搶占式多項(xiàng)目調(diào)度問題,三種算法均能計(jì)算出比較好的解,但是采用非搶占式操作模式會(huì)增加多項(xiàng)目調(diào)度活動(dòng)的數(shù)量.云遺傳算法動(dòng)態(tài)改變其交叉變異率,使得算法的初期能夠比較快的產(chǎn)生優(yōu)秀個(gè)體,算法的后期能保護(hù)最優(yōu)個(gè)體,且全局搜索能力強(qiáng).因此可以得出結(jié)論,云遺傳算法能在保證收斂的同時(shí)提高全局搜索能力.

試驗(yàn)表明,本文設(shè)計(jì)的云遺傳算法在全局搜索和快速收斂方面優(yōu)越其他智能算法,能夠保證基于關(guān)鍵鏈的非搶占式多項(xiàng)目調(diào)度問題對(duì)求解算法的要求.

表4　仿真結(jié)果對(duì)比分析Table 4 Comparative analysis of simulation results

分析表4所示的數(shù)據(jù),發(fā)現(xiàn)云遺傳算法的搜索成功率最大,禁忌搜索算法的搜索成功率最小.最劣值和平均值都是云遺傳算法的結(jié)果最小,從而反映出云遺傳算法的全局搜索能力最強(qiáng).

5　結(jié)束語

針對(duì)基于關(guān)鍵鏈的多項(xiàng)目調(diào)度資源利用率低、魯棒性較低及其成本與工期之間的背反關(guān)系問題展開研究,深入分析不確定因素對(duì)多項(xiàng)目調(diào)度內(nèi)部資源使用率的影響,按照活動(dòng)的可執(zhí)行性將其拆分為若干的子活動(dòng),并執(zhí)行非搶占式執(zhí)行模式,在提高多項(xiàng)目調(diào)度資源利用率的基礎(chǔ)上,降低不確定因素對(duì)多項(xiàng)目調(diào)度系統(tǒng)的影響,以工期–成本–質(zhì)量–魯棒性為優(yōu)化目標(biāo),利用效用函數(shù)建立多目標(biāo)均衡優(yōu)化模型,并設(shè)計(jì)云遺傳算法對(duì)問題進(jìn)行求解.

結(jié)果表明,基于關(guān)鍵鏈的多項(xiàng)目調(diào)度采用非搶占式操作模式,不僅可實(shí)現(xiàn)整體效用最大化,而且可實(shí)現(xiàn)多項(xiàng)目調(diào)度的帕累托改善并提高資源的利用率.對(duì)設(shè)計(jì)的算法進(jìn)行了實(shí)驗(yàn)計(jì)算,云遺傳算法在求解效率、收斂速度和穩(wěn)定性方面優(yōu)于其他智能算法.本文僅分析了基于關(guān)鍵鏈的非搶占式多項(xiàng)目調(diào)度問題,但沒有根據(jù)不確定性因素的特點(diǎn)及對(duì)多項(xiàng)目調(diào)度執(zhí)行過程的影響,采用不用的策略分別展開研究.基于多項(xiàng)目調(diào)度系統(tǒng)的復(fù)雜性,其執(zhí)行過程中的不確定因素和干擾的識(shí)別和描述還有待進(jìn)一步研究和細(xì)化.

[1]Sunil A,Mittal M L,Abhinav M.A multi-agent system for decentralized multi-project scheduling with resource transfers.International Journal of Production Economics,2013,146(2):646–661.

[2]Madjid T,Amir-Reza A,Kaveh K D.A new multi-objective multi-mode model for solving preemptive time cost quality trade-off project scheduling problems.Expert Systems with Applications,2014,41(4):1830–1846.

[3]田文迪,胡慕海,崔南方.不確定性環(huán)境下魯棒性項(xiàng)目調(diào)度研究綜述.系統(tǒng)工程學(xué)報(bào),2014,29(1):135–144. Tian W D,Hu M H,Cui N F.Review of studies on robust project scheduling under uncertainty.Journal of Systems Engineering, 2014,29(1):135–144.(in Chinese)

[4]Virginia Y,Analia A.Hybridizing a multi-objective simulated annealing algorithm with a multi-objective evolutionary algorithm to solve a multi-objective project scheduling problem.Expert System with Applications,2013,40(7):2421–2434.

[5]Voss S,Witt A.Hybrid flow shop scheduling as a multi-mode multi-project scheduling problem with batching requirements:A real-world application.International Journal of Production Economics,2007,105(2):445–458.

[6]Yang S L,Fu L.Critical chain and evidence reasoning applied to multi-project resource schedule in automobile R&D process. International Journal of Project Management,2014,32(1):166–177.

[7]Rabbania M,Fatemi G S M T,Jolaia F.A new heuristic for resource-constrained project scheduling in stochastic networks using critical chain concept.European Journal of Operational Research,2007,176(2):794–808.

[8]Bevilacqua M,Clarapica F E,Giacchetta G.Critical chain and risk analysis applied to high-risk industry maintenance:A case study. International Journal of Project Management,2009,27(4):419–432.

[9]彭武良,王成恩.關(guān)鍵鏈項(xiàng)目調(diào)度模型及遺傳算法求解.系統(tǒng)工程學(xué)報(bào),2010,25(1):123–131. Peng W L,Wang C E.Critical chain method project scheduling based model and its GA solution.Journal of Systems Engineering, 2010,25(1):123–131.(in Chinese)

[10]劉瓊,林魁,張超勇,等.基于關(guān)鍵鏈多項(xiàng)目魯棒性調(diào)度.計(jì)算機(jī)集成制造系統(tǒng),2012,18(4):813–820. Liu Q,Lin K,Zhang C Y,et al.Multi-project robust scheduling based on critical chain.Computer Integrated Manufacturing Systmems,2012,18(4):813–820.(in Chinese)

[11]Debels D,Vanhoucke M.A bi-population based genetic algorithm for the resource-constrained project scheduling problem.Lecture Notes on Computer Science,2005,3483,378–387.

[12]Buddhakulsomsiri J,Kim D.Properties of multi-mode resource-constrained project scheduling problems with resource vacations and activity splitting.European Journal of Operational Research,2006,175(1):279–295.

[13]Filip D,Erik D,Willy H.Proactive policies for the stochastic resource-constrained project scheduling problem.European Journal of Operational Research,2011,214(2):308–316

[14]Vincent V P,Mario V.A genetic algorithm for the preemptive and non-preemptive multi-mode resource-constrained project scheduling problem.European Journal of Operational Research,2010,201(2):409–418.

[15]Demeulemeester E,Herroelen W.A branch-and-bound procedure for the multiple resource-constrained project scheduling problem. Management Science,1992,38(12):1803–1818.

[16]何正文,賈濤,徐渝.截止日期越是下的融資費(fèi)用最小化項(xiàng)目調(diào)度.系統(tǒng)工程學(xué)報(bào),2009,24(4):494–498. He Z W,Jia T,Xu Y.Project scheduling for minimizing financing cost under deadline constraint.Journal of Systems Engineering, 2009,24(4):494–498.(in Chinese)

[17]Vanhoucke M,Debels D.The impact of various activity assumptions on the lead time and resource utilization of resource-constrained projects.Computers and Industrial Engineering,2008,54(1):140–154.

[18]張靜文,徐渝,何正文,等.項(xiàng)目調(diào)度中的時(shí)間–費(fèi)用權(quán)衡問題研究綜述.管理工程學(xué)報(bào),2007,21(1):92–97. Zhang J W,Xu Y,He Z W,et al.A review on the time/cost trade-offs problem in project scheduling.Journal of Industrial Engineering and Engineering Management,2007,21(1):92–97.(in Chinese)

[19]劉士新,宋健海.模糊多目標(biāo)資源受限項(xiàng)目調(diào)度問題的優(yōu)化方法.系統(tǒng)工程學(xué)報(bào),2008,23(6):744–750. Liu S X,Song J H.Approach for fuzzy multi-objective resource-constrained project scheduling problems.Journal of Systems Engineering,2008,23(6):744–750.(in Chinese)

[20]王宏,林丹,李敏強(qiáng).求解模糊資源受限項(xiàng)目調(diào)度問題的遺傳算法.系統(tǒng)工程學(xué)報(bào),2006,21(3):323–327. Wang H,Lin D,Li M Q.Application of genetic algorithm in solving fuzzy resource-constrained project scheduling problem.Journal of Systems Engineering,2006,21(3):323–327.(in Chinese)

Multi-attribute optimization for non-preemptive multi-project scheduling based on critical chain

Wang Weixin1,2,Ge Xianlong3,Wang Xu4,Ni Lin4
(1.Research Center for International Business and Economics,Sichuan International Studies University,Chongqing 400031,China; 2.School of International Business,Sichuan International Studies University,Chongqing 400031,China; 3.School of Management,Chongqing Jiaotong University,Chongqing 400074,China; 4.College of Mechanical Engineering,Chongqing University,Chongqing 400030,China)

For difficult to realize the dynamic dispatching and efficient project scheduling in multi-project scheduling,this paper proposes a non-preemptive operation mode for multi-project scheduling based on critical chain from the standpoint of maximizing the overall utility,constructs and analyzes the multi-project scheduling model.The randomness and stability of droplets in normal cloud model is adopted to improve the setting mode of crossover and mutation operator in the genetic algorithm,and a numerical simulation is carried out.The results show that the proposed non-preemptive operation mode can maximize the overall utility of multi-project scheduling and realize Pareto improvement to increase the resource utilization rate.

critical chain;multi-project scheduling;cloud genetic algorithms;non-preemptive

TP273

A

1000-5781(2016)05-0689-11

10.13383/j.cnki.jse.2016.05.013

2013-08-12;

2014-12-01.

國家自然科學(xué)基金資助項(xiàng)目(71502021);教育部人文社科基金資助項(xiàng)目(15XJC630007);教育部人文社科基金資助項(xiàng)目(14YJC630038);重慶市教委科學(xué)技術(shù)研究資助項(xiàng)目(KJ1500702).

王偉鑫(1986—),女,黑龍江齊齊哈爾人,博士,講師,研究方向:項(xiàng)目調(diào)度,工程項(xiàng)目管理,Email:xiaoxin301@126.com;

葛顯龍(1984—),男,河南信陽人,博士,副教授,碩士生導(dǎo)師,研究方向:網(wǎng)絡(luò)優(yōu)化,項(xiàng)目管理,Email:gexianlong@cqjtu.edu.cn;

王 旭(1963—),女,四川南充人,博士,教授,博士生導(dǎo)師,研究方向:物流工程,項(xiàng)目管理,Email:wx921@163.com;

倪 霖(1971—),男,重慶人,博士,副教授,碩士生導(dǎo)師,研究方向:供應(yīng)鏈管理與現(xiàn)代物流,項(xiàng)目管理,Email:nilin71@163.com.