基于云遺傳算法的關(guān)鍵鏈項(xiàng)目調(diào)度方法研究

周力，王杰

（東華大學(xué)　旭日工商管理學(xué)院，上?！?0051）

?

基于云遺傳算法的關(guān)鍵鏈項(xiàng)目調(diào)度方法研究

周力，王杰

（東華大學(xué)旭日工商管理學(xué)院，上海20051）

［摘要］針對資源約束下的項(xiàng)目調(diào)度問題，在前人研究的基礎(chǔ)上，設(shè)計(jì)基于云模型的遺傳算法用于求解關(guān)鍵鏈項(xiàng)目調(diào)度問題，利用調(diào)度問題庫PSPLIB中標(biāo)準(zhǔn)實(shí)例j301_1驗(yàn)證算法的可行性。

［關(guān)鍵詞］資源約束；關(guān)鍵鏈；項(xiàng)目調(diào)度；云遺傳算法；PSPLIB

1　引言

關(guān)鍵鏈項(xiàng)目調(diào)度問題以資源約束項(xiàng)目調(diào)度問題為基礎(chǔ)，是項(xiàng)目調(diào)度問題中的重要組成部分，該問題求解困難，多屬于NP-hard問題，是項(xiàng)目管理學(xué)者研究的重點(diǎn)。

近年來，學(xué)者們設(shè)計(jì)了各種智能算法求解關(guān)鍵鏈項(xiàng)目調(diào)度問題。2006年，劉士新等提出了一種基于啟發(fā)式規(guī)則的關(guān)鍵鏈調(diào)度方法；2013年，金敏力等在研究關(guān)鍵鏈項(xiàng)目調(diào)度的優(yōu)化問題模型基礎(chǔ)上，提出一種遺傳算法求解單模式關(guān)鍵鏈項(xiàng)目調(diào)度問題；2014年，張琦、廖良才等提出一種自適應(yīng)遺傳算法對關(guān)鍵鏈項(xiàng)目調(diào)度模型進(jìn)行求解。

本文在關(guān)鍵鏈項(xiàng)目管理思想的基礎(chǔ)上，設(shè)計(jì)基于云模型的遺傳算法求解單模式關(guān)鍵鏈項(xiàng)目調(diào)度問題，取調(diào)度問題庫PSPLIB標(biāo)準(zhǔn)算例j301_1進(jìn)行仿真試驗(yàn)，驗(yàn)證云遺傳算法在求解關(guān)鍵鏈項(xiàng)目調(diào)度問題上的性能。

2　問題描述

本文在建立關(guān)鍵鏈優(yōu)化調(diào)度問題模型時，采用以下問題簡化方式。將問題分為三個階段：①在以項(xiàng)目工期最短為調(diào)度目標(biāo)時，不考慮非關(guān)鍵鏈上的輸入緩沖區(qū)對工期的影響，考慮基于關(guān)鍵鏈上關(guān)鍵活動計(jì)算的項(xiàng)目緩沖區(qū)對項(xiàng)目工期的影響，尋找最優(yōu)關(guān)鍵鏈；②基于關(guān)鍵鏈計(jì)算項(xiàng)目緩沖區(qū)，插入到項(xiàng)目結(jié)束活動之后；③采用劉士新等提出的方法，查找非關(guān)鍵鏈，并計(jì)算和插入輸入緩沖區(qū)。

單執(zhí)行模式資源受限項(xiàng)目優(yōu)化調(diào)度問題的描述，如果同時考慮資源約束和活動工期的不確定性，那么該問題就轉(zhuǎn)變?yōu)閱文Ｊ疥P(guān)鍵鏈問題。

則可以建立基于關(guān)鍵鏈的單模式資源約束項(xiàng)目調(diào)度問題模型如下：

本文以標(biāo)準(zhǔn)問題庫PSPLIB中問題j301_1項(xiàng)目為例，如表1所示。

表1　項(xiàng)目實(shí)例表

續(xù)表

3　云遺傳算法設(shè)計(jì)

在云遺傳算法中，把問題的解表示成“染色體”，首先給出可行的解，即初始種群，然后按照適者生存的自然進(jìn)化法則，從中選擇出適應(yīng)值較高的個體，在新一代種群中再進(jìn)行復(fù)制、交叉和變異，在新一代種群中按照相同的原則進(jìn)行選擇，直到進(jìn)化到迭代代數(shù)為止。本文所采用的方式是利用最優(yōu)保留和輪盤賭相結(jié)合的方式，在每一代種群中選擇相對于種群規(guī)模的一定比例（10％）的最優(yōu)個體直接進(jìn)入到下一代中，這樣既有利于最優(yōu)個體的保留，也不破壞種群的多樣性，更有利于產(chǎn)生更優(yōu)秀的個體。同時采用父代和子代相互競爭的策略，在選擇的過程中，子代與父代有相同的權(quán)利在輪盤賭的過程中被復(fù)制到下一代中。算法以識別單模式關(guān)鍵鏈為目標(biāo)，隨機(jī)生成初始種群，以迭代次數(shù)為終止條件，以適應(yīng)度為評價準(zhǔn)則。

3.1云遺傳算法

對于一些改進(jìn)的自適應(yīng)遺傳算法，其交叉概率和變異概率自適應(yīng)于適應(yīng)度，原理可以描述為：高于種群平均適應(yīng)度的個體，隨著其適應(yīng)度的增加，為了對較優(yōu)個體進(jìn)行保護(hù)，交叉和變異概率逐漸減??；而低于種群平均適應(yīng)度的個體采用最大交叉變異概率，使其產(chǎn)生較優(yōu)個體。

云遺傳算法結(jié)合遺傳算法思想，沿用傳統(tǒng)遺傳算法的交叉、變異操作概念，由正態(tài)云模型的X條件云生成算法生成迭代過程中的交叉操作和變異概率。由于正態(tài)云模型具有隨機(jī)性和穩(wěn)定傾向性的特點(diǎn)，隨機(jī)性可以保持個體多樣性從而避免搜索陷入局部極值，而穩(wěn)定傾向性又可以很好地保護(hù)較優(yōu)個體從而對全局最值進(jìn)行自適應(yīng)定位。從而滿足快速尋優(yōu)的能力，并根據(jù)其隨機(jī)性能避免陷入局部最優(yōu)。其主要算法如下：

3.2適值函數(shù)與交叉變異操作

設(shè)i是當(dāng)前種群第i個個體，F(xiàn)（i）是適應(yīng)值函數(shù)，f（i）是第i個個體的目標(biāo)值（即項(xiàng)目持續(xù)時間），fmax和fmin分別是當(dāng)前種群的最大目標(biāo)值和最小目標(biāo)值。將目標(biāo)值轉(zhuǎn)化成適應(yīng)值的轉(zhuǎn)換公式如下：

式（7）中，C是屬于［0，1］的正實(shí)數(shù)，在這里取0.5。

本文選擇算子使用最優(yōu)保持策略和輪盤賭方式結(jié)合的方式來產(chǎn)生下一代群體。把上一代群體中適應(yīng)值最大的10％的個體不進(jìn)行交叉和變異操作，而直接進(jìn)入下一代群體中。另外的個體經(jīng)云遺傳算法的思想產(chǎn)生交叉和變異概率，通過pc和pm，選擇參與交叉和變異的個體，通過交叉和變異操作生成下一代種群。

交叉操作選擇隨機(jī)地從父代1中選擇若干個基因位置，將這些基因的值遺傳給子代中相應(yīng)的位置，子代中空缺的位置由父代2，由左到右，依次填補(bǔ)完整。通過變異算子使解空間向深度搜索。變異操作實(shí)質(zhì)上是基于局部搜索的變異，對于一個染色體，隨機(jī)產(chǎn)生一個基因，其鄰域是確定的。變異算子隨機(jī)產(chǎn)生在［1，n］內(nèi)兩個互異的整數(shù)i和j，交換這兩個位置的基因信息，生成一個新的染色體。在一個種群的進(jìn)化過程中由于變異產(chǎn)生部分個體。

4　算法比較與分析

由于初始種群是隨機(jī)產(chǎn)生的。為了盡可能的消除不確定性，選取不同的種群規(guī)模，迭代次數(shù)進(jìn)行仿真，對選用的j301_1的項(xiàng)目進(jìn)行多次測試，以項(xiàng)目調(diào)度時間最短作為選擇標(biāo)準(zhǔn)，選擇最優(yōu)個體作為比較對象。算法參數(shù)：種群規(guī)模取400和1 000，迭代次數(shù)為50。仿真結(jié)果如下：

當(dāng)種群規(guī)模P=400，迭代次數(shù)n=50時，仿真結(jié)果如表2所示。當(dāng)種群規(guī)模P=1 000，迭代次數(shù)n=50時，仿真結(jié)果如表3所示。

表2　種群規(guī)模4OO仿真結(jié)果表

表3　種群規(guī)模1 OOO仿真結(jié)果表

本文選取解的平均方差、最大方差、可行解比例三個指標(biāo)來統(tǒng)計(jì)算法的有效性，結(jié)果如表4所示。

表4　j3O1_1測試表

由仿真結(jié)果得知，當(dāng)?shù)螖?shù)確定的時候，種群規(guī)模越大，平均方差越小，求解效果越好。當(dāng)種群規(guī)模P=1 000時，求解效果最好。對應(yīng)工作安排產(chǎn)生的最短工程時間為46，仿真結(jié)果如圖1所示。

根據(jù)建立基于關(guān)鍵鏈的單模式資源約束項(xiàng)目調(diào)度問題模型Ftime=fn+PB即可求出項(xiàng)目調(diào)度時間Ftime。為了更好地理解云模型遺傳算法去求解單執(zhí)行模式關(guān)鍵鏈項(xiàng)目調(diào)度問題中的有效性和性能，本文選取調(diào)度問題庫PSPLIB算例，分別與本文的遺傳算法和其他智能算法（包括遺傳算法等）進(jìn)行比較。從仿真結(jié)果看，本文云遺傳算法更有效（如表5所示）。

5　結(jié)語

在關(guān)鍵鏈項(xiàng)目管理思想基礎(chǔ)上，設(shè)計(jì)云遺傳算法求解單模式關(guān)鍵鏈項(xiàng)目調(diào)度問題，用標(biāo)準(zhǔn)問題庫PSPLIB的問題進(jìn)行求解，通過求解結(jié)果進(jìn)行比較分析該算法的可行性、有效性和優(yōu)越性。但是，關(guān)鍵鏈項(xiàng)目管理實(shí)施是一個非常復(fù)雜的過程，還需要考慮緩存機(jī)制、調(diào)整關(guān)鍵鏈等等一系列問題。同時多模式關(guān)鍵鏈項(xiàng)目調(diào)度問題也是需要研究的項(xiàng)目管理NP問題。

圖1　云遺傳算法仿真圖

表5　仿真結(jié)果比較表

主要參考文獻(xiàn)

［1］GoIdratt F M.CriticaI Chain［M］.Great Barrington：The North River Press PubIishing Corporation，1997.

［2］田文迪，崔南方.關(guān)鍵鏈項(xiàng)目管理中關(guān)鍵鏈和非關(guān)鍵鏈的識別［J］.工業(yè)工程與管理，2009，14（2）：88-93.

［3］李俊亭，王潤孝，楊云濤.基于資源沖突調(diào)度的關(guān)鍵鏈項(xiàng)目進(jìn)度研究［J］.西北工業(yè)大學(xué)學(xué)報(bào).2010，28（4）：547-552.

［4］劉士新，宋健海，唐加福.資源受限項(xiàng)目調(diào)度中緩沖區(qū)的設(shè)定方法［J］.系統(tǒng)工程學(xué)報(bào)，2006，21（4）：381-386.

［5］劉娟.關(guān)鍵鏈單項(xiàng)目進(jìn)度管理方法研究［D］.武漢：華中科技大學(xué)，2008.

［6］金敏力，馮玉強(qiáng).遺傳算法的關(guān)鍵鏈項(xiàng)目調(diào)度基準(zhǔn)計(jì)劃問題研究［J］.沈陽理工大學(xué)學(xué)報(bào)，2013，32（2）：12-17.

［7］張琦，廖良才，王衛(wèi)威.基于改進(jìn)遺傳算法的關(guān)鍵鏈項(xiàng)目進(jìn)度計(jì)劃優(yōu)化［J］.2014，24（4）：24-28.

［8］彭武良，王成恩.關(guān)鍵鏈項(xiàng)目調(diào)度模型及遺傳算法求解［J］.系統(tǒng)工程學(xué)報(bào)，2010；25（1）：123-131.

［9］廖良才，張琦.基于混合遺傳算法和關(guān)鍵鏈的多資源多項(xiàng)目進(jìn)度計(jì)劃優(yōu)化［J］.科學(xué)技術(shù)與工程，2014，14（6）.

［10］李俊亭，王潤孝，楊云濤.關(guān)鍵鏈多項(xiàng)目整體進(jìn)度優(yōu)化［J］.計(jì)算機(jī)集成制造系統(tǒng)，2011，17（8）：1772-1779.

［11］彭武良，金敏力，紀(jì)國燾.多模式關(guān)鍵鏈項(xiàng)目調(diào)度問題及其啟發(fā)式求解［J］.計(jì)算機(jī)集成制造系統(tǒng)，2012，18（2）.

doi:10.3969/j.issn.1673 - 0194.2016.03.043

［中圖分類號］TP301.6

［文獻(xiàn)標(biāo)識碼］A

［文章編號］1673-0194（2016）03-0089-03

［收稿日期］2015-09-23