基于關鍵鏈的非搶占式多項目調度多屬性優(yōu)化

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

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

基于關鍵鏈的非搶占式多項目調度多屬性優(yōu)化

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

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

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

關鍵鏈;多項目調度;云遺傳算法;非搶占式

1　引　言

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

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

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

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

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

2　基于關鍵鏈的非搶占式多項目調度模型

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

表1　符號定義Table 1 Notation definition

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

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

定義1屬性是影響調度決策的一個或一組變量.分為成本型屬性(即數(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.

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

定義2在基于關鍵鏈的非搶占式多項目調度中,對整體服務質量的滿意程度稱為效用.

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

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

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

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

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

基于關鍵鏈的非搶占式多項目調度的質量的效用值為1時,則有

基于關鍵鏈的非搶占式多項目調度的魯棒性效用值為1時,則有

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

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

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

3　求解算法設計研究

3.1優(yōu)先權調度規(guī)則

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

1)確定各個活動的優(yōu)先權;

2)生成多項目調度的積極計劃;

3)確定關鍵鏈與非關鍵鏈;

4)計算緩沖區(qū)并嵌入緩沖區(qū)并生成非搶占式關鍵鏈多項目調度計劃的方案.

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

3.2云遺傳算法

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

Pc的生成算法.

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

1)編碼設計:本文選用多組編碼的染色體結構,染色體的基因對應活動的編號,基因的值對應一個優(yōu)先權列表.自然編碼表示任務優(yōu)先權,優(yōu)先權為1～m之間的自然數(shù),優(yōu)先權的數(shù)值越大表示優(yōu)先權越大.為保證染色體的有效性,活動的優(yōu)先權必須與基因建立一一對應的關系,以滿足解空間分布的均勻性和搜索的全局性的要求.染色體結構如圖1所示.

圖1　染色體結構Fig.1 Chromosome structure

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

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

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

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

6)重復步驟2)到步驟5),當Maxgen=50或滿足條件則停止操作,輸出結果.

4　試驗仿真

4.1算例分析

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

圖2　交叉操作Fig.2 Crossover operation

圖3　變異操作Fig.3 Mutation operation

由MATLAB實現(xiàn)云遺傳算法編程,對建立的模型進行求解.設種群規(guī)模Popsize=50,為滿足種群多樣性的要求,進化代數(shù)的取值為Maxgen=50,求得關鍵鏈在項目2上.因此,基于關鍵鏈的非搶占式多項目調度多屬性均衡優(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　多項目網(wǎng)絡結構圖Fig.4 Network structure diagrams of multi-project

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

4.2非搶占式與搶占式操作模式對比分析

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

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

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

4.3算法對比分析

為了檢驗云遺傳算法的性能,本文分別采用標準遺傳算法、禁忌搜索算法和云遺傳算法對上述算例進行算例分析,采用各算法的計算結果收斂情況如圖5所示.

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

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

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

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

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

表4　仿真結果對比分析Table 4 Comparative analysis of simulation results

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

5　結束語

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

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

[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)境下魯棒性項目調度研究綜述.系統(tǒng)工程學報,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]彭武良,王成恩.關鍵鏈項目調度模型及遺傳算法求解.系統(tǒng)工程學報,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]劉瓊,林魁,張超勇,等.基于關鍵鏈多項目魯棒性調度.計算機集成制造系統(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]何正文,賈濤,徐渝.截止日期越是下的融資費用最小化項目調度.系統(tǒng)工程學報,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]張靜文,徐渝,何正文,等.項目調度中的時間–費用權衡問題研究綜述.管理工程學報,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]劉士新,宋健海.模糊多目標資源受限項目調度問題的優(yōu)化方法.系統(tǒng)工程學報,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]王宏,林丹,李敏強.求解模糊資源受限項目調度問題的遺傳算法.系統(tǒng)工程學報,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.

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

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

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

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

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