宋 堯,仰燕蘭,葉 樺

1(東南大學(xué) 自動化學(xué)院,南京 210096)

2(復(fù)雜工程系統(tǒng)測量與控制教育部重點實驗室,南京 210096)

資源受限項目調(diào)度問題(Resource-Constrained Project Scheduling Problem,RCPSP)是一種典型的NPhard 問題[1],具有約束條件嚴(yán)苛、組合性強(qiáng)、求解范圍廣等特點,其基本目標(biāo)是在一定資源的約束下得到合理的調(diào)度方案,使得時間或者項目成本得到最優(yōu)化.多技能資源受限項目調(diào)度問題(Multi-Skilled Resource-Constrained Project Scheduling Problem,MS-RCPSP/MSPSP)是在其基礎(chǔ)上增加了技能約束的一種拓展性問題,因其在軟件開發(fā)、建筑工程、車間調(diào)度等方面的廣泛應(yīng)用而不斷受到越來越多的學(xué)者的關(guān)注,并衍生出許多求解方案.比如,任逸飛等人提出了一種包含雙層決策及局部優(yōu)化策略的混合算法對MSPSP 進(jìn)行求解,并結(jié)合基于關(guān)鍵鏈的局部搜索算法提高了求解質(zhì)量[2];Skowronski 等人先后用基于調(diào)度優(yōu)先級規(guī)則的元啟發(fā)式算法[3]、禁忌搜索算法[4]和進(jìn)化算法[5]研究MSPSP,并生成了一套專門針對MSPSP 的基準(zhǔn)數(shù)據(jù)集iMOPSE[6],為后世研究該問題提供了重要參考依據(jù).

總的來說,目前所使用的各種算法都僅能針對部分?jǐn)?shù)據(jù)對象而不斷靠近最優(yōu)解,如何提出合適的算法為MSPSP 求出更優(yōu)解是目前研究努力的一個方向.本文在對比了各種算法之后,考慮到發(fā)展已久的遺傳算法(Genetic Algorithm,GA)[7]在尋優(yōu)搜索能力、魯棒性和兼容性等方面的良好表現(xiàn),選擇其作為本文的基本算法.考慮到該算法存在早熟收斂和后期收斂速度慢的問題,學(xué)者們在其基礎(chǔ)上進(jìn)行了相關(guān)改進(jìn),并用于求解MSPSP 問題.比如,Laszczyk 等人在經(jīng)典的非支配遺傳算法的基礎(chǔ)上提出了一種新的選擇算子,提高了搜索效率[8];Lin 等人提出了一種遺傳規(guī)劃的超啟發(fā)式算法,將遺傳算法作為一種宏觀策略,統(tǒng)籌調(diào)度十種啟發(fā)式規(guī)則進(jìn)行求解[9].本文針對MSPSP 的特點,在細(xì)化遺傳算法的求解過程的基礎(chǔ)上,對其選擇、交叉和排序過程分別進(jìn)行了改進(jìn).

1 MSPSP 介紹

1.1 問題描述

MSPSP 的基本概念是:一個項目中涉及多個任務(wù),任務(wù)之間存在時間約束關(guān)系,項目中的各種資源都具備一種或多種技能,問題的目標(biāo)是在滿足各種約束的條件下合理調(diào)度和分配已有的資源和任務(wù),使得完成整個項目的總時間或總成本最小化.

一般而言,問題中的資源都指人力資源,以圖1為例,J1～J4 表示任務(wù),H1～H4 表示資源,以J1 為例,它需要具備技能S3 且技能等級達(dá)到3.2 的人員,在H1～H4 中只有H2 和H4 是滿足的,因此對于J1 來說H2 和H4 可以被分配給它.當(dāng)確定人力資源的可分配權(quán)后,再結(jié)合相關(guān)時間約束和資源約束,才能進(jìn)一步確定最終的分配情況.

圖1 MSPSP 示意圖

1.2 數(shù)學(xué)模型

為了便于描述MSPSP 的數(shù)學(xué)模型,首先引入如下符號定義:

J:任務(wù)集合,J={1,2,···,m};

H:資源集合,H={1,2,···,n};

S:技能集合;

dj:完成任務(wù)j的工期;

bj:任務(wù)j的開始時間;

fj:任務(wù)j的結(jié)束時間;

kjh:任務(wù)j所需要的資源h的數(shù)量;

Pj:任務(wù)j的前置任務(wù)集合;

Kh:資源h的數(shù)量;

wh:資源h的單位成本;

Sh:資源h所擁有的技能集合;

Jh:資源h可完成的任務(wù)集合;

ls:技能s的等級;

qs:技能s的類別;

α:優(yōu)化目標(biāo)的權(quán)重系數(shù);

T:工作持續(xù)時間;

Qjht:0-1 變量,資源h在t時刻作用于任務(wù)j時為1,否則為0.

MSPSP 的數(shù)學(xué)模型為:

目標(biāo)函數(shù):

其中,

約束條件:

式(1)中的Fτ和Fc分別表示工作的總時間和總成本,兩者是相互制約的關(guān)系,通過權(quán)重系數(shù) α關(guān)聯(lián)起來,構(gòu)成總的優(yōu)化目標(biāo)Fs.α的取值將決定優(yōu)化對象是單目標(biāo)還是多目標(biāo),α=0時 是成本優(yōu)化,α=1時是時間優(yōu)化,α ∈(0,1)是綜合考慮時間和成本的多目標(biāo)優(yōu)化.本文主要考慮單目標(biāo)優(yōu)化.式(4)和式(5)表示任務(wù)的時間約束.式(6)～式(8)是對人力資源的約束:式(6)要求每種人力資源至少具備一種技能;式(7)體現(xiàn)了人員成本的合理性;式(8)表示單個資源在同一時間內(nèi)只能使用一種技能去執(zhí)行一項任務(wù).式(9)是技能約束,規(guī)定了在為各個任務(wù)節(jié)點分配資源時,必須滿足該任務(wù)對資源的技能種類和技能等級的需求.式(10)的定義是為了方便計算成本消耗.

2 改進(jìn)遺傳算法

2.1 編解碼方案

根據(jù)問題選擇合適的染色體編碼方式是遺傳算法的第一步,鑒于MSPSP 是要尋找滿足約束條件的任務(wù)和資源的最佳排列,本文選擇基于優(yōu)先級數(shù)組的整數(shù)編碼,以更直觀地展示和表達(dá)調(diào)度結(jié)果.在遺傳算法中,每條染色體對應(yīng)一個任務(wù)鏈,以優(yōu)先級數(shù)組進(jìn)行表示時,數(shù)組中的元素(即染色體的基因)是任務(wù)的權(quán)重,數(shù)組的下標(biāo)表示任務(wù)編號,數(shù)組的長度等于任務(wù)總數(shù).

編碼之后還需要進(jìn)行解碼才能形成完整的調(diào)度方案.本文選擇串行調(diào)度機(jī)制[10]實行解碼操作,主要分為兩個部分:

(1)在不考慮技能約束的情況下,根據(jù)任務(wù)的權(quán)重生成任務(wù)序列,當(dāng)權(quán)重相等時,任務(wù)編號小的優(yōu)先;

(2)根據(jù)技能約束和資源約束對資源進(jìn)行分配,在此過程中如果發(fā)現(xiàn)資源分配沖突則需要對任務(wù)序列進(jìn)行調(diào)整,如果無法通過調(diào)整滿足需求則放棄該方案.

2.2 適應(yīng)度函數(shù)

遺傳算法一般會選擇問題的目標(biāo)函數(shù)作為適應(yīng)度函數(shù),但MSPSP 的目標(biāo)函數(shù)是最小化目標(biāo),不滿足適應(yīng)度函數(shù)的最大化需求,因此需要做一定轉(zhuǎn)化,最終的適應(yīng)度函數(shù)如式(11)所示.

其中,fg(ck)是個體ck的適應(yīng)度函數(shù),Fs是當(dāng)前個體的目標(biāo)值(即目標(biāo)函數(shù)值),Fs_max和Fs_min分別是當(dāng)前群體中的最大目標(biāo)值和最小目標(biāo)值.

2.3 基于群體共享的小生境選擇

得到種群的適應(yīng)度后,需要根據(jù)適應(yīng)度大小對種群中的個體進(jìn)行初步篩選,挑選出適應(yīng)度較好的一批個體,為后續(xù)的交叉和變異做準(zhǔn)備.傳統(tǒng)的直接通過比較個體適應(yīng)度大小來決定生存權(quán)的方式會帶來一些問題:

(1)算法搜索初期,適應(yīng)度很好的一批個體不但擁有更長的生存時間,而且易被視為優(yōu)良父代將本身的基因傳承下去,進(jìn)而影響整個種群的進(jìn)化方向,從而削弱了算法的全局搜索能力;

(2)算法搜索后期,經(jīng)過多代的進(jìn)化,個體間的差異變小,種群多樣性降低,演變成了近親繁殖,在此基礎(chǔ)上生成的后代也很難有新的變化,最終算法可能會陷入局部最優(yōu).

為了防止種群的多樣性被破壞,本文在遺傳算法的選擇階段融入基于群體共享的小生境技術(shù)[11].其基本過程是:首先將原始種群分為若干子種群,接著從中挑選出一個優(yōu)質(zhì)種群作為共享種群,然后在共享種群和普通種群內(nèi)部獨立進(jìn)行交叉、變異操作,生成新一代種群,并不斷重復(fù)這種操作,直到滿足終止條件為止.將小生境技術(shù)與遺傳算法相融合,能夠增強(qiáng)算法的全局搜索的能力,加快算法的收斂速度.

2.3.1 定義說明

為了實現(xiàn)上述算法,首先給出如下定義:

定義1.個體間距離

在基于群體共享機(jī)制的小生境方法中,可以利用海明距離來輔助判斷個體之間的相似程度,相似度不高的個體才能進(jìn)行交配,以保證種群的多樣性.為了方便計算海明距離,需要先將個體由實數(shù)編碼轉(zhuǎn)為二進(jìn)制編碼,然后再根據(jù)式(12)求得個體ci和cj之間的海明距離,其中,binLen表示染色體二進(jìn)制編碼的長度,G表示整個種群.

定義2.個體共享度

個體共享度是借助個體間海明距離來度量其相似程度的一種表達(dá),如式(13)所示,個體之間相似度越大,個體共享度就越大.

定義3.群體共享度

群體共享度是對個體在群體中的特異性的度量,是個體與群體中的其他個體間的個體共享度之和,如式(14)所示.

2.3.2 確定式采樣選擇

在各個子群體的進(jìn)化過程中,為了保證優(yōu)質(zhì)基因能夠遺傳下去,與文獻(xiàn)[11]不同的是,本文采用確定式采樣選擇法[12]進(jìn)行個體選擇,避開傳統(tǒng)輪盤賭方式帶來的統(tǒng)計誤差.具體操作過程是:

Step 1.計算各個子種群中的個體在下一代中的期望數(shù)目:

Step 3.根據(jù)Nexp(ci)的小數(shù)部分對所有個體進(jìn)行排序,選擇最大的個個體進(jìn)入到下一代種群中.

這種方式能夠確保每個子群體中適應(yīng)度較大的個體都能存活到下一代.

2.3.3 子種群適應(yīng)度和規(guī)模調(diào)整

為了減少算法中相似個體的不斷聚合,需要根據(jù)子群體的群體共享度不斷調(diào)整其適應(yīng)度和種群規(guī)模.

調(diào)整的基本規(guī)則是:

(1)根據(jù)共享種群的群體共享度占總?cè)后w共享度的比值,略微調(diào)高共享種群的適應(yīng)度;

(2)當(dāng)普通種群的群體共享度大于共享種群的群體共享度時,調(diào)低普通種群的適應(yīng)度,反之調(diào)高;

(3)在總的種群規(guī)模不變的情況下,根據(jù)種群的適應(yīng)度比例重新分配子種群的規(guī)模.

對于共享種群的適應(yīng)度調(diào)整:

對于普通種群的適應(yīng)度調(diào)整:

對于各個子種群規(guī)模的調(diào)整:

其中,sshare表示共享種群的群體共享度,subS ize(i)表示第i個子種群的規(guī)模,fg(i)表示第i個子種群的適應(yīng)度值.

2.4 基于修復(fù)機(jī)制的單點交叉

遺傳算法中的交叉操作能夠生成繼承了父代基因的新個體,提高算法的全局搜索能力,其中最常見的是單點交叉法.傳統(tǒng)的單點交叉的過程是:在父輩個體中隨機(jī)選擇一個交叉點,將該交叉點之后的基因互換,從而生成了兩個新的子個體.本文的染色體是任務(wù)時序鏈,使用基本的單點交叉后容易打破時序約束,且新生成的子個體中可能出現(xiàn)重復(fù)項和缺失項.為了保證子代個體的有效性,本文結(jié)合隨機(jī)生成的交叉概率Pc,在基本的單點操作基礎(chǔ)上增加了相關(guān)修復(fù)策略,如圖2所示.

具體的修復(fù)過程是:經(jīng)過基本的單點交叉后,首先找到子代個體中重復(fù)的編號,子代c1中是1 和3,c2中是4 和6;然后將c1交叉點前的重復(fù)編號與c2交叉點后的重復(fù)編號依次進(jìn)行交換,即c1中交叉點前的1 和3 分別與c2交叉點后的4 和6 交換,同理,也將c2交叉點前的重復(fù)編號與c1交叉點后的重復(fù)編號依次進(jìn)行交換,即c2中交叉點前的4 和6 分別與c1交叉點后的3 和1 交換;最后交換后的結(jié)果即為修復(fù)的子代個體,該子代個體都滿足任務(wù)的時序約束,且沒有重復(fù)項.

但是,交叉完后的子代個體的適應(yīng)度并不一定比父代強(qiáng),為了在交叉后盡量保留適應(yīng)度相對較好的個體,在此引入父子競爭機(jī)制來進(jìn)一步篩選出能夠進(jìn)入下一代繁殖的個體:對父代c1、c2和子代c1、c2四個個體的適應(yīng)度進(jìn)行排序,選擇適應(yīng)度最好的兩個作為最終的新生代個體進(jìn)入下一次繁殖和進(jìn)化.

圖2 基于修復(fù)機(jī)制的單點交叉示意圖

2.5 基于多重驗證的變異

除了交叉外,遺傳算法中的變異操作也能生成新的個體,輔助交叉操作維護(hù)種群的多樣性,增強(qiáng)算法的局部搜索能力.與交叉不同的是,變異是根據(jù)變異率Pm在單個染色體上對其部分基因進(jìn)行突變,從而產(chǎn)生新的個體.

對于MSPSP 問題而言,為了使變異后的個體仍舊滿足約束條件,在執(zhí)行傳統(tǒng)的變異操作后,還需對新個體進(jìn)行時序約束驗證,只有驗證通過的個體才能保留下來,否則變異失效.另外,如果變異后的個體適應(yīng)度太低,則表明該方案不太可取,且會影響整個子群體的適應(yīng)度,因此還需對新個體進(jìn)行適應(yīng)度檢驗.

本文設(shè)計的基于多重驗證的變異過程如下:

Step 1.隨機(jī)為子種群中的所有個體分配概率p(ci);

Step 2.選擇一個個體,判斷是否滿足p(ci)≤Pm,如果是則執(zhí)行變異操作,否則另選個體進(jìn)行判斷;

Step 3.在所選個體上隨機(jī)選擇兩個任務(wù)和進(jìn)行交換;

Step 4.判斷新個體是否滿足時序約束,且適應(yīng)度比舊個體高,如果都滿足則用新個體代替舊個體;否則拋棄新個體,保留舊個體;Step 5.判斷當(dāng)前種群中的所有個體是否都檢測完畢,如果是,則結(jié)束變異操作;否則轉(zhuǎn)到Step 2.

2.6 算法總流程

改進(jìn)遺傳算法的詳細(xì)步驟為:

Step 1.設(shè)置遺傳算法的相關(guān)參數(shù)(種群規(guī)模popS ize,變異概率Pm,最大迭代次數(shù)Niter),并用貪心算法初始化種群;

Step 2.劃分子種群;

Step 3.計算個體的適應(yīng)度,并在各個子種群內(nèi)獨立執(zhí)行進(jìn)化操作:首先按照確定式采樣規(guī)則進(jìn)行個體選擇,然后執(zhí)行基于修復(fù)機(jī)制的單點交叉操作,最后完成基于多重驗證的變異操作;

Step 4.判斷子群體進(jìn)化次數(shù)ksub是否達(dá)到上限值Ne,如果是則先將ksub清零,再轉(zhuǎn)到Step 5;否則轉(zhuǎn)到Step 3;

Step 5.計算子種群的平均適應(yīng)度,選擇適應(yīng)度值最高的作為共享種群;

Step 6.根據(jù)群體共享度和適應(yīng)度調(diào)整所有子種群的適應(yīng)度和規(guī)模;

Step 7.淘汰連續(xù)幾代表現(xiàn)最差的子群體,并產(chǎn)生相同規(guī)模的新群體進(jìn)行替換;

Step 8.判斷當(dāng)前迭代次數(shù)是否達(dá)到上限,或者連續(xù)幾代的求解結(jié)果偏差是否滿足收斂條件,如果滿足任意一條則結(jié)束算法,輸出結(jié)果;否則轉(zhuǎn)到Step 3.

算法的流程圖如圖3所示.

3 實驗分析

用Python 實現(xiàn)了針對MSPSP 的改進(jìn)遺傳算法后,為了驗證算法的性能,本文在iMOPSE[6]數(shù)據(jù)集上進(jìn)行了實驗,并與其他算法的求解結(jié)果進(jìn)行了對比.實驗中,算法的參數(shù)設(shè)置如表1所示.

在取相同參數(shù)的情況下,改進(jìn)遺傳算法和傳統(tǒng)遺傳算法在10_20_46_15 算例上的求解效果如圖4所示,可以看出,改進(jìn)算法的收斂速度更快,求解結(jié)果更優(yōu).

使用改進(jìn)遺傳算法對整個iMOPSE 數(shù)據(jù)集進(jìn)行求解,分別取α=1(時間最優(yōu))和α=0(成本最優(yōu)),每個實例運行20 次,將結(jié)果與文獻(xiàn)[13]中的混合蟻群算法的結(jié)果進(jìn)行對比,如表2所示.可以看出,不管是以時間最優(yōu)還是成本最優(yōu)為目標(biāo),改進(jìn)遺傳算法都能求得更優(yōu)的解,且從多次求解的標(biāo)準(zhǔn)差來看,大部分情況下改進(jìn)遺傳算法都更加穩(wěn)定.

圖3 改進(jìn)遺傳算法流程圖

表1 改進(jìn)遺傳算法參數(shù)設(shè)置

圖4 改進(jìn)GA 和傳統(tǒng)GA 在10_20_46_15 上的求解對比圖(α=1)

表2 改進(jìn)遺傳算法和混合蟻群算法在iMOPSE 上的求解結(jié)果對比

續(xù)表2

4 結(jié)束語

本文針對MSPSP 問題的特點,在傳統(tǒng)遺傳算法的基礎(chǔ)上,融入了基于群體共享的小生境技術(shù),提高了種群信息的利用率,并針對MSPSP 的時序約束,分別為交叉和變異操作增加了修復(fù)和驗證機(jī)制,進(jìn)一步確保了個體的合法性.經(jīng)實驗驗證分析可知,改進(jìn)后的遺傳算法相較于傳統(tǒng)遺傳算法和混合蟻群算法的收斂速度更快,求解結(jié)果更優(yōu),穩(wěn)定性更強(qiáng),且能在iMOPSE 數(shù)據(jù)集上取得良好效果,為研究相關(guān)實際問題提供了一定參考價值.