求解資源受限多項(xiàng)目調(diào)度的改進(jìn)遺傳規(guī)劃算法

陳浩杰 丁國(guó)富 張 劍 閻開(kāi)印

西南交通大學(xué)機(jī)械工程學(xué)院先進(jìn)設(shè)計(jì)與制造技術(shù)研究所，成都，610031

0 引言

資源受限項(xiàng)目調(diào)度問(wèn)題(resource constrained project scheduling problem , RCPSP)[1-2]是項(xiàng)目管理中最為經(jīng)典和核心的NP難問(wèn)題[3]，但RCPSP并不完全適用于眾多復(fù)雜實(shí)際場(chǎng)景，故需要進(jìn)行不同方面的擴(kuò)展，如多技能RCPSP優(yōu)化[4]、多模式RCPSP優(yōu)化[5]等，其中資源受限多項(xiàng)目調(diào)度問(wèn)題(resource constrained multi-project scheduling problem, RCMPSP)是應(yīng)用最廣泛的擴(kuò)展模式[6-8]，項(xiàng)目管理中約90%是在多項(xiàng)目下進(jìn)行的[9]。

近年來(lái)，RCMPSP的求解方式主要以元啟發(fā)式(如進(jìn)化智能算法)和啟發(fā)式(如優(yōu)先級(jí)規(guī)則)為主。在元啟發(fā)式的研究中，XIN等[10]提出了一種遺傳算法，其編碼方式基于活動(dòng)優(yōu)先級(jí)且在搜索過(guò)程中結(jié)合存儲(chǔ)鄰接矩陣，從而提高了搜索能力且避免產(chǎn)生非法解修復(fù)過(guò)程。ZHENG等[11]設(shè)計(jì)了一種多智能體架構(gòu)，并結(jié)合關(guān)鍵鏈技術(shù)以求解分布式RCMPSP。TIAN等[12]通過(guò)研究單項(xiàng)目、多項(xiàng)目和活動(dòng)等三個(gè)層次的資源流特性，提出了一種適用于求解RCMPSP的改進(jìn)關(guān)鍵鏈技術(shù)。PREZ等[13]提出了一種求解RCMPSP的多模態(tài)遺傳算法，通過(guò)擴(kuò)展搜索過(guò)程中的種群多樣性來(lái)避免算法陷入局部最優(yōu)。

大量研究表明，PR調(diào)度具備快速響應(yīng)能力和良好的求解能力，但不同的PR具備不同的特性導(dǎo)致其適用的目標(biāo)函數(shù)和場(chǎng)景不同，且PR本身不具備優(yōu)化能力，因此考慮根據(jù)不同PR的優(yōu)勢(shì)去構(gòu)造適用更廣、求解能力更強(qiáng)的PR。于是超啟發(fā)式的理念被提出和逐步應(yīng)用[19]。

遺傳算法是具備很強(qiáng)通用性和優(yōu)化能力的元啟發(fā)式算法，其優(yōu)化過(guò)程被模擬到超啟發(fā)式算法上形成遺傳規(guī)劃算法(genetic programing，GP)和基因表達(dá)式編程(gene expression programming，GEP)。GP和GEP的進(jìn)化過(guò)程相似，主要區(qū)別在于個(gè)體的編碼方法和結(jié)果的表達(dá)[20]。在調(diào)度領(lǐng)域，GEP的應(yīng)用主要集中在作業(yè)車(chē)間調(diào)度(job shop scheduling，JSP)[21-22]。針對(duì)項(xiàng)目調(diào)度，JIA等[23]提出了一種求解RCPSP的GEP框架。相比而言，GP在項(xiàng)目調(diào)度中的應(yīng)用更廣泛。CHAND等[24]將GP運(yùn)用到RCPSP求解并成功進(jìn)化出了調(diào)度求解能力更強(qiáng)的PR。在此基礎(chǔ)上，CHAND等[25]考慮了資源擾動(dòng)下的RCPSP，再次驗(yàn)證了遺傳規(guī)劃的有效性和適應(yīng)能力。LIN等[26]設(shè)計(jì)了一種雙層超啟發(fā)式遺傳規(guī)劃算法求解多技能RCPSP，通過(guò)高層的超啟發(fā)式算法搜索更好的低層啟發(fā)式算法。

綜上所述，現(xiàn)有研究已經(jīng)成功將GP運(yùn)用于RCPSP，但據(jù)文獻(xiàn)調(diào)研并未發(fā)現(xiàn)GP在RCMPSP問(wèn)題上的應(yīng)用。相較于RCPSP，RCMPSP具備項(xiàng)目層的優(yōu)先級(jí)屬性，且由于不同項(xiàng)目之間的資源搶占和沖突會(huì)導(dǎo)致資源需求方面的屬性選取受到影響，GP的有效性需要進(jìn)一步驗(yàn)證；同時(shí)，現(xiàn)有RCPSP超啟發(fā)式調(diào)度的研究均是優(yōu)化單目標(biāo)，而實(shí)際場(chǎng)景中多目標(biāo)優(yōu)化的目標(biāo)間競(jìng)爭(zhēng)關(guān)系會(huì)為優(yōu)化帶來(lái)額外困難[27]，并且超啟發(fā)式編碼的特性使傳統(tǒng)GP在搜索過(guò)程中容易陷入局部最優(yōu)?；诖?，本文提出一種應(yīng)用于多目標(biāo)RCMPSP問(wèn)題的改進(jìn)遺傳規(guī)劃(improved genetic programing，IGP)算法。

1 問(wèn)題描述

RCMPSP是調(diào)度由n個(gè)項(xiàng)目組成的項(xiàng)目集P={1,2,…,n}來(lái)滿(mǎn)足某個(gè)/些目標(biāo)最優(yōu)，其中每個(gè)項(xiàng)目i∈P都由z+2個(gè)具備有向無(wú)循環(huán)邏輯關(guān)系的活動(dòng)Ai={ai0,ai1,…,ai(z+1)}構(gòu)成，其中活動(dòng)ai0和ai(z+1)為虛擬活動(dòng)，表示項(xiàng)目i的開(kāi)始和結(jié)束。在n個(gè)項(xiàng)目的執(zhí)行過(guò)程中，共需要K種共用可更新資源，每種資源k(k∈K)的最大單位供應(yīng)量為Rk，且設(shè)定在執(zhí)行中的任意時(shí)刻t處于執(zhí)行的活動(dòng)集合為Et。對(duì)于任意活動(dòng)aij∈Ai,j={0,1,…,z+1}，sij為開(kāi)始時(shí)間，dij為持續(xù)時(shí)間，Sij為緊后活動(dòng)集合，rijk為活動(dòng)aij對(duì)資源k的需求量。衡量RCMPSP的調(diào)度優(yōu)劣通常是依據(jù)完工時(shí)間[14-16]，根據(jù)文獻(xiàn)[15]采用兩個(gè)目標(biāo)函數(shù)值分別從項(xiàng)目和項(xiàng)目集兩個(gè)角度進(jìn)行PR的性能評(píng)估——平均項(xiàng)目完工時(shí)間偏差Q1和項(xiàng)目集完工時(shí)間偏差Q2。設(shè)項(xiàng)目i的關(guān)鍵路徑長(zhǎng)度為L(zhǎng)i，實(shí)際調(diào)度后所得到的完工時(shí)間為Ci，RCMPSP的數(shù)學(xué)模型如下：

min(Q1,Q2)

(1)

(2)

(3)

s.t.

sib-sij≥dij

(4)

di0,di(z+1)=0ri0k,ri(z+1)k=0

(5)

(6)

i∈Pb∈Sijj∈Aik∈Kt∈{0,1,…}

其中，式(4)表明項(xiàng)目?jī)?nèi)部各活動(dòng)的緊前緊后關(guān)系，即活動(dòng)必須在其所有緊前活動(dòng)完成后才能開(kāi)始；式(5)為虛擬活動(dòng)約束，即所有虛擬活動(dòng)都不需要任何資源且持續(xù)時(shí)間為0；式(6)為資源約束，即在任意時(shí)刻，處于執(zhí)行狀態(tài)的活動(dòng)所需資源之和不得超過(guò)該類(lèi)資源的最大供應(yīng)量。目標(biāo)函數(shù)式(1)表示采用非支配解的方式優(yōu)化評(píng)估，如下所示：

(7)

式中，z1、z2表示兩個(gè)不同的求解策略。

當(dāng)式(7)中的不等式至少有一個(gè)嚴(yán)格小于時(shí)，稱(chēng)z1支配z2，記z1?z2。若策略z不受到其他任何策略的支配，則z是非支配解。本文的優(yōu)化目標(biāo)是優(yōu)化生成一組應(yīng)用于RCMPSP的非支配混合優(yōu)先級(jí)規(guī)則(hybrid priority rule, HPR)，HPR構(gòu)成的集合稱(chēng)為Pareto解集(非支配解集)。

2 求解RCMPSP的IGP

WANG等[15]認(rèn)為，不同PR求解多目標(biāo)下的RCMPSP，Q1目標(biāo)最優(yōu)的PR是最小項(xiàng)目及活動(dòng)持續(xù)時(shí)間之和規(guī)則，Q2目標(biāo)最優(yōu)的PR是最大緊后總數(shù)規(guī)則，而B(niǎo)ROWNING等[14]認(rèn)為，在不同的問(wèn)題約束或驗(yàn)證算例下，調(diào)度RCMPSP最好的PR往往不同?？梢钥闯觯瑔我坏腜R調(diào)度時(shí)存在一定的局限性，因此需要通過(guò)訓(xùn)練生成適合求解RCMPSP的調(diào)度性能優(yōu)、通用性強(qiáng)的PR。為進(jìn)化出求解RCMPSP的更優(yōu)PR，本文提出了一種IGP算法，其流程如圖1所示，收集多種不同工況數(shù)據(jù)并將其分為訓(xùn)練集和測(cè)試集，通過(guò)IGP訓(xùn)練后得到Pareto解集，再將Pareto解集的各PR在訓(xùn)練集和測(cè)試集上驗(yàn)證。

圖1 IGP流程圖Fig.1 Flow chart of IGP

2.1 編碼設(shè)計(jì)及初始化種群

不同于啟發(fā)式或元啟發(fā)式算法直接得到問(wèn)題的解，基于超啟發(fā)式算法的IGP是為了得到求解問(wèn)題的進(jìn)化/混合PR。IGP基因是通過(guò)各種優(yōu)先級(jí)屬性經(jīng)過(guò)一定的功能運(yùn)算符組合后得到的，為了應(yīng)用于RCMPSP求解，首先需要建立優(yōu)先級(jí)屬性集。在項(xiàng)目調(diào)度中優(yōu)先選擇哪個(gè)活動(dòng)主要是根據(jù)活動(dòng)本身的時(shí)間、活動(dòng)的資源需求和活動(dòng)在項(xiàng)目中的邏輯關(guān)系。在RCPSP中只需要考慮活動(dòng)層面和資源層面的屬性計(jì)算即可，而RCMPSP則需要在多個(gè)項(xiàng)目的不同活動(dòng)之間做出決策，因此需要考慮項(xiàng)目層的屬性。通過(guò)分析現(xiàn)有的20種PR[14-16]可知，項(xiàng)目關(guān)鍵路徑長(zhǎng)度在多項(xiàng)目調(diào)度中是主要決策依據(jù)，因此本文在RCPSP超啟發(fā)式屬性集[24]上增加了項(xiàng)目關(guān)鍵路徑長(zhǎng)度，從資源、活動(dòng)和項(xiàng)目的角度提取了10個(gè)優(yōu)先級(jí)屬性，并對(duì)屬性進(jìn)行歸一化處理，如表1所示。在RCMPSP中需要在同一時(shí)刻決策來(lái)自多個(gè)項(xiàng)目的活動(dòng)，因此活動(dòng)時(shí)間相關(guān)屬性及關(guān)鍵路徑長(zhǎng)度采用最大最小歸一化方式；各個(gè)活動(dòng)的邏輯關(guān)系只與本項(xiàng)目有關(guān)，在衡量活動(dòng)重要程度歸一化(如Nts和Ntcs)時(shí)只考慮與本項(xiàng)目活動(dòng)總數(shù)的比值；不同項(xiàng)目之間存在資源搶占，在衡量資源的歸一化(如Rmax和Ravg)時(shí)采用公共資源的最大供應(yīng)量比。功能集選擇的超啟發(fā)式最常用的六種功能運(yùn)算符為“+”、“-”、“×”、“/”、“max”和“min”。

表1 優(yōu)先級(jí)屬性

根據(jù)IGP流程，在第一個(gè)項(xiàng)目集下訓(xùn)練時(shí)需要隨機(jī)初始化種群，隨機(jī)初始化種群中每個(gè)個(gè)體的頂層編碼以0.5的概率控制為Fall或Rise，下層結(jié)構(gòu)樹(shù)則采用ramped half-and-half方法隨機(jī)生成，除頂層外，樹(shù)深度控制在2～6之間[29]，圖2所示的樹(shù)的深度為3。

(a)降序編碼結(jié)構(gòu)

2.2 NSGA-Ⅱ評(píng)估和遺傳算子

IGP是應(yīng)用于多目標(biāo)RCMPSP下的求解PR訓(xùn)練，因此需要建立相應(yīng)PR的評(píng)估方式來(lái)實(shí)現(xiàn)進(jìn)化過(guò)程中的基因取舍。多目標(biāo)優(yōu)化問(wèn)題可以對(duì)每個(gè)目標(biāo)賦予相應(yīng)的權(quán)重轉(zhuǎn)化為單目標(biāo)問(wèn)題，但在大多數(shù)實(shí)際場(chǎng)景中，權(quán)重很難確定且可能變化，因此本文采用NSGA-Ⅱ[30]來(lái)分配虛擬適應(yīng)度以實(shí)現(xiàn)PR個(gè)體評(píng)估，主要步驟如下。

(1)根據(jù)種群中個(gè)體計(jì)算的目標(biāo)函數(shù)值，將整個(gè)種群進(jìn)行分支配解分層，同層的解為非支配關(guān)系，上層個(gè)體支配下層個(gè)體，不同層級(jí)解的關(guān)系如下所示：

G1?G2?…?Gg?…?Gm

(8)

式中，m為當(dāng)前種群分層后的最大層數(shù)；Gg為第g層個(gè)體。

(2)計(jì)算相同等級(jí)各個(gè)個(gè)體間的擁擠距離，由于不同目標(biāo)同樣數(shù)量級(jí)不同，所以仍然需要?dú)w一化，其計(jì)算公式如下：

(9)

式中，V為目標(biāo)函數(shù)集合；ov,a為個(gè)體a在目標(biāo)函數(shù)v下的值，下標(biāo)a+1和a-1代表在目標(biāo)函數(shù)值v下該非支配層中經(jīng)排序后個(gè)體a的相鄰個(gè)體。

(3)根據(jù)支配等級(jí)和空間距離分配其虛擬適應(yīng)度，即首先判斷個(gè)體所屬非支配層，層級(jí)越低越優(yōu)，處于相同層級(jí)的個(gè)體擁擠距離越大越優(yōu)。

除了PR個(gè)體的評(píng)估，在IGP的進(jìn)化過(guò)程中需要用到傳統(tǒng)遺傳算子選擇、交叉和變異。其中選擇算子采用錦標(biāo)賽選擇[31]；根據(jù)文獻(xiàn)[24]，交叉算子采用子樹(shù)交叉模式，即隨機(jī)數(shù)小于交叉率Pc時(shí)，兩父代個(gè)體交換部分子樹(shù)，而變異算子則是當(dāng)隨機(jī)數(shù)小于變異率Pm時(shí)，用一個(gè)隨機(jī)生成的子樹(shù)替換父代個(gè)體某一節(jié)點(diǎn)下的子樹(shù)。此外，配合頂層判別編碼方式，在變異算子中增加判別變異方式，即當(dāng)隨機(jī)數(shù)小于Pm時(shí)，父代個(gè)體的頂層編碼方式發(fā)生變化，如Fall編碼變化為Rise編碼，遺傳算子的執(zhí)行順序如圖1所示。

2.3 多樣性種群更新

GP樹(shù)狀的編碼方式會(huì)使整個(gè)種群出現(xiàn)許多功能相似或相同但結(jié)構(gòu)不同的編碼，如圖3所示。其中圖3a和圖3b雖然是兩種結(jié)構(gòu)不同的編碼，但最終產(chǎn)生的優(yōu)先級(jí)表達(dá)式是一致的；而圖3c和圖3d則是對(duì)同一個(gè)優(yōu)先級(jí)表達(dá)值Tef進(jìn)行平方和加倍處理，在調(diào)度過(guò)程中各個(gè)活動(dòng)的Tef值相對(duì)大小是固定的，因此2Tef和(Tef)2的調(diào)度排序效果也是一致的。也正是因?yàn)樯鲜鰞煞N情況，傳統(tǒng)GP在進(jìn)化搜索過(guò)程中因種群的多樣性降低而易陷入局部最優(yōu)，導(dǎo)致訓(xùn)練效果不佳。為此本文設(shè)計(jì)了一種種群更新方式，在更新過(guò)程中建立虛擬適應(yīng)度FK存儲(chǔ)上一個(gè)工況的信息,作為更新是否舍棄當(dāng)前個(gè)體的依據(jù)，以提升泛化性能。假設(shè)種群規(guī)模為Size,主要步驟如下：

(a)相同功能結(jié)構(gòu)PR1 (b)相同功能結(jié)構(gòu)PR2

(1)建立相同個(gè)體臨時(shí)儲(chǔ)存集合Snew、Sold和不同個(gè)體臨時(shí)存儲(chǔ)集合D，計(jì)算遺傳算子更新后的新種群中每個(gè)子代個(gè)體的各個(gè)目標(biāo)函數(shù)值，如果原種群中沒(méi)有目標(biāo)函數(shù)值完全相同的父代個(gè)體，則該個(gè)體放入D，否則該子代個(gè)體的FK置為空(非支配層為0，擁擠距離為0)并放入Snew，對(duì)應(yīng)的相同父代個(gè)體放入Sold。

(2)對(duì)于屬于Snew中的每個(gè)子代個(gè)體，解析其優(yōu)先級(jí)表達(dá)式是否與對(duì)應(yīng)的相同父代個(gè)體一致或相似，如果否那么將該子代個(gè)體移入集合D中。

(3)對(duì)于Snew中余下各個(gè)子代個(gè)體，判斷其對(duì)應(yīng)父代個(gè)體FK是否為空，如果為空且隨機(jī)產(chǎn)生的判斷數(shù)小于0.5.則將該子代移入集合D中。

(4) 將D中的個(gè)體與原種群合并，選擇前Size個(gè)虛擬適應(yīng)度最好的個(gè)體生成下一代種群并判斷是否為當(dāng)前工況下的最大迭代次數(shù)，如果是，則將最終種群各個(gè)個(gè)體的虛擬適應(yīng)度設(shè)置為該個(gè)體的FK值。

3 IGP性能驗(yàn)證及比較

3.1 實(shí)驗(yàn)環(huán)境和參數(shù)設(shè)置

IGP基于MyEclipse 2017開(kāi)發(fā)，計(jì)算機(jī)配置為2.80 GHz雙核處理器，8 GB內(nèi)存。根據(jù)文獻(xiàn)[16]，一個(gè)工況的項(xiàng)目集由4個(gè)活動(dòng)數(shù)量不同的項(xiàng)目構(gòu)成，分別來(lái)源于PSPLIB數(shù)據(jù)庫(kù)[32]中的J30、J60、J90和J120庫(kù)(每個(gè)項(xiàng)目包含30、60、90、120個(gè)非虛活動(dòng))，且項(xiàng)目集每種資源的最大單位供應(yīng)Rk為20。選擇PSPLIB數(shù)據(jù)庫(kù)4個(gè)活動(dòng)庫(kù)的前50組數(shù)據(jù)構(gòu)成驗(yàn)證數(shù)據(jù)集，其中前30組為訓(xùn)練項(xiàng)目集，其余為測(cè)試集。IGP中所需參數(shù)根據(jù)經(jīng)驗(yàn)設(shè)定為：最大迭代次數(shù)Mgen=20，種群規(guī)模Size=200，交叉率Pc=0.9，變異率Pm=0.2。

3.2 評(píng)價(jià)方式

參考文獻(xiàn)[15]，采用性能排名對(duì)PR進(jìn)行評(píng)價(jià)，即不同的PR調(diào)度同一個(gè)工況項(xiàng)目集時(shí)，根據(jù)目標(biāo)函數(shù)的大小產(chǎn)生兩組排名(Q1和Q2)，用50組項(xiàng)目集下的平均排名W衡量PR調(diào)度性能的相對(duì)優(yōu)劣，計(jì)算方式如下：

(10)

式中，M為項(xiàng)目集的總數(shù)量；wm,v,l為規(guī)則l在項(xiàng)目集m下調(diào)度目標(biāo)v對(duì)應(yīng)的排名值，其值為小于|Nrule|的正整數(shù)；Urule為參與排名的規(guī)則集合。

3.3 算例下IGP性能分析

IGP的訓(xùn)練結(jié)果為一組HPR(Pareto解集)，采用IGP訓(xùn)練10次，將第一次訓(xùn)練產(chǎn)生的HPR與20種經(jīng)典PR[15]的性能進(jìn)行對(duì)比，如表2所示。表2中HPR1至HPR10為本次訓(xùn)練得到的10種不同結(jié)構(gòu)的HPR。10次訓(xùn)練結(jié)果的統(tǒng)計(jì)表見(jiàn)表3。表3中，Npar為該次實(shí)驗(yàn)得到的非支配HPR的數(shù)量，pdo為該次實(shí)驗(yàn)訓(xùn)練出的HPR的W值高于20種傳統(tǒng)PR的W值占所有非支配HPR的比例。

表2 傳統(tǒng)PR和HPR的W值

表3 HPR性能排名結(jié)果統(tǒng)計(jì)表

從表2中可以看出，IGP本次訓(xùn)練得到的80% HPR(除HPR8和HPR10外)性能排名均高于20種傳統(tǒng)PR，而HPR8和HPR10性能排名僅次于EDDF和MINSLK兩種規(guī)則。從表3中可以看出，10次訓(xùn)練產(chǎn)生的HPR優(yōu)于20種傳統(tǒng)PR的占比平均值大于80%，而剩余20%規(guī)則也優(yōu)于大部分傳統(tǒng)PR(表2)，由此可以得到IGP訓(xùn)練的HPR調(diào)度能力比單一傳統(tǒng)PR更優(yōu)秀，證明本文提出的IGP既保留了基于啟發(fā)式的PR的快速響應(yīng)能力又解決了PR不具備優(yōu)化能力的問(wèn)題。

表4 HPR的Pareto前沿次數(shù)統(tǒng)計(jì)結(jié)果

從圖4中可以看出，相較于傳統(tǒng)PR，本文提出的IGP生成的HPR普遍目標(biāo)函數(shù)值較小，處于支配地位。同時(shí)圖4中的Pareto前沿(Pareto前沿為HPR2、HPR5、HPR9、HPR4、WACRU和MS)大部分是IGP生成的HPR。從表4中可以看出，大多數(shù)訓(xùn)練情況下，HPR的Pareto前沿次數(shù)最大值要遠(yuǎn)高于傳統(tǒng)PR，同時(shí)平均有70%的HPR出現(xiàn)Pareto前沿的次數(shù)高于20種傳統(tǒng)PR，證明了IGP的有效性。

圖4 工況1下不同PR和HPR目標(biāo)函數(shù)支配關(guān)系Fig.4 Objective function domination relationship of different PR and HPR under condition 1

現(xiàn)有GP超啟發(fā)式求解調(diào)度文獻(xiàn)較少，文獻(xiàn)[24-26]的重點(diǎn)在于GP在不同RCPSP問(wèn)題上的實(shí)現(xiàn)，并非對(duì)GP的進(jìn)化過(guò)程做出改進(jìn)。為此，對(duì)比表3和表4可進(jìn)一步證明本文提出的IGP訓(xùn)練的有效性。從表3中可以看出，IGP訓(xùn)練得到的Pareto解集中HPR的平均數(shù)量是8.5而GP為3.8，可以得出IGP能夠訓(xùn)練出非支配解的范圍更廣，而GP由于相同/相似功能編碼的存在，非支配解的范圍大大降低。GP訓(xùn)練的HPR支配20種傳統(tǒng)PR的占比平均值為9%，遠(yuǎn)低于IGP，可以看出本文提出的IGP的訓(xùn)練能力更強(qiáng)，更容易避免局部最優(yōu)。從表4中可以看出，對(duì)于相同的傳統(tǒng)PR，GP生成的HPR的支配能力低于IGP，其Pareto前沿出現(xiàn)的次數(shù)較低甚至在某些訓(xùn)練下要弱于傳統(tǒng)的PR。由此可以看出IGP訓(xùn)練的HPR具備更強(qiáng)的通用性。

為進(jìn)一步驗(yàn)證IGP訓(xùn)練出的HPR比現(xiàn)有啟發(fā)式算法具備更強(qiáng)的調(diào)度能力，選擇文獻(xiàn)[18]中的啟發(fā)式PSGS-SLK進(jìn)行對(duì)比。第一次IGP訓(xùn)練的HPR與PSGS-SLK調(diào)度50組算例的支配關(guān)系如表5所示，其中Nd為HPR支配PSGS-SLK的算例個(gè)數(shù)，Nnd為二者互為非支配關(guān)系的算例個(gè)數(shù)，Npd為PSGS-SLK支配HPR的算例個(gè)數(shù)。10次訓(xùn)練后的結(jié)果統(tǒng)計(jì)表如表6所示，pd代表支配算例個(gè)體大于被支配算例個(gè)數(shù)的HPR(即Nd大于Npd)占該次訓(xùn)練的所有HPR的比例。

通過(guò)表5和表6可以看出，大多數(shù)的HPR能夠?qū)崿F(xiàn)大部分工況支配PSGS-SLK或與其成非支配關(guān)系，表明相較于現(xiàn)有的啟發(fā)式算法，IGP所訓(xùn)練的HPR具備更好的調(diào)度能力。

表5 HPR與PSGS-SLK支配關(guān)系表

表6 HPR與PSGS-SLK支配關(guān)系統(tǒng)計(jì)表

3.4 實(shí)例下IGP性能驗(yàn)證

本文以某飛機(jī)總裝廠(chǎng)機(jī)電調(diào)試部分裝配作業(yè)為例對(duì)算法進(jìn)行驗(yàn)證。該廠(chǎng)采用兩條并行裝配線(xiàn)裝配兩種不同機(jī)型的飛機(jī)且均包括機(jī)電調(diào)試作業(yè)，對(duì)于同一架次飛機(jī)而言，該部分的調(diào)試工作會(huì)影響后續(xù)的裝配工作，因此既要考慮本架次飛機(jī)該工位的裝配時(shí)間最短又要考慮兩架飛機(jī)的總裝配時(shí)間最短。該部分裝配工作需要共用同一班組人員(總?cè)藬?shù)為18)和3種公用工裝(總數(shù)均為10)。兩種機(jī)型機(jī)電調(diào)試裝配作業(yè)的緊前緊后關(guān)系及所需資源通過(guò)掃描本文首頁(yè)OSID二維碼可見(jiàn)，該廠(chǎng)目前以最晚開(kāi)工時(shí)間為優(yōu)先級(jí)進(jìn)行生成調(diào)度，即EDDF。通過(guò)關(guān)鍵路徑法可得項(xiàng)目1和項(xiàng)目2的關(guān)鍵路徑分別為50和55，而IGP第一次訓(xùn)練后的HPR和EDDF的調(diào)度結(jié)果見(jiàn)表7，10次訓(xùn)練結(jié)果見(jiàn)表8。表7中，C1和C2分別為項(xiàng)目1和項(xiàng)目2的完成時(shí)間，表8中Pd為支配EDDF的HPR占總的HPR的比例，Pnd為與EDDF互為非支配關(guān)系的HPR的比例。

從表7中可以看出，IGP生成的大多數(shù)HPR的調(diào)度性能要優(yōu)于EDDF，且剩余HPR和EDDF相比各有優(yōu)勢(shì)，在未分配權(quán)重時(shí)互為非支配關(guān)系，由此可以證明IGP能夠?yàn)镽CMPSP調(diào)度帶來(lái)更多有效的HPR。在表8的統(tǒng)計(jì)結(jié)果中，除第7次訓(xùn)練和第10次訓(xùn)練IGP產(chǎn)生了EDDF支配的HPR(分別占比12.5%和28.6%)外，其余HPR均為支配EDDF或與EDDF互為非支配關(guān)系，且在大多數(shù)訓(xùn)練情況下IGP生成的HPR支配EDDF的概率較大，驗(yàn)證了本文提出的IGP在實(shí)例調(diào)度中的有效性。

表7 HPRs和EDDF的調(diào)度結(jié)果

表8 HPR與EDDF的訓(xùn)練結(jié)果

4 結(jié)論

為了實(shí)現(xiàn)多目標(biāo)RCMPSP下的PR最優(yōu)進(jìn)化，本文對(duì)GP進(jìn)行改進(jìn)，提出一種IGP算法：

(1)通過(guò)現(xiàn)有的20種求解RCMPSP問(wèn)題的PR，從資源、活動(dòng)和項(xiàng)目的角度提取屬性，并根據(jù)屬性的類(lèi)型設(shè)計(jì)了不同的歸一化方式，同時(shí)設(shè)計(jì)了判別編碼，確保最小化/最大化同一種優(yōu)先級(jí)表達(dá)式均能迭代搜索，從而保證解空間的完整性。

(2)結(jié)合NSGA-Ⅱ的虛擬適應(yīng)度分配的評(píng)估方法，不設(shè)置權(quán)重而是對(duì)種群中個(gè)體進(jìn)行非支配分層并計(jì)算不同層個(gè)體的擁擠距離，從而評(píng)估個(gè)體的優(yōu)劣。

(3)設(shè)計(jì)了一種多樣性種群進(jìn)化更新方式以消除相同/相似功能編碼，避免傳統(tǒng)GP容易陷入局部最優(yōu)的問(wèn)題，提高了算法的搜索能力和泛化能力。

下一步研究可將該方法應(yīng)用在動(dòng)態(tài)RCPSP類(lèi)問(wèn)題下求解并結(jié)合魯棒性性能分析，使其獲得更廣泛的應(yīng)用和達(dá)到更全面的快速求解。