孫 浩，劉環(huán)宇，趙柏棟，張玉嘉，楊 振，王德權(quán)

(大連工業(yè)大學(xué)機(jī)械工程與自動(dòng)化學(xué)院，大連 116034)

0 引言

柔性生產(chǎn)調(diào)度問(wèn)題(flexible job shop scheduling problem,FJSP)是復(fù)雜的NP-hard問(wèn)題[1]，打破了傳統(tǒng)剛性大批量生產(chǎn)對(duì)設(shè)備唯一性的約束，使車間調(diào)度變得更加復(fù)雜多變。從調(diào)度目標(biāo)數(shù)量可將柔性作業(yè)車間調(diào)度分為：?jiǎn)文繕?biāo)和多目標(biāo)調(diào)度。

相比于單目標(biāo)調(diào)度問(wèn)題[2-3]，多目標(biāo)柔性作業(yè)車間調(diào)度問(wèn)題更為復(fù)雜。首先，難以保證在調(diào)度過(guò)程中多個(gè)目標(biāo)的優(yōu)化平衡。其次，多個(gè)目標(biāo)的參數(shù)和量綱存在差異?，F(xiàn)階段多目標(biāo)調(diào)度的研究思路分為兩種，其一，通過(guò)權(quán)重將多目標(biāo)轉(zhuǎn)化為單目標(biāo)[4-5]；其二，非劣解生成法，利用帕累托原理生成最優(yōu)解集[6-8]，此方法廣泛應(yīng)用于求解三目標(biāo)及以上問(wèn)題。在算法設(shè)計(jì)上需要對(duì)原始算法進(jìn)行改進(jìn)或者結(jié)合兩種不同算法的優(yōu)點(diǎn)，使算法能夠發(fā)揮更好的尋優(yōu)效果。DEB等[9]在NSGA基礎(chǔ)上提出了NSGA-Ⅱ算法，提高算法搜索效果和計(jì)算效率。CHEN等[10]提出混合算法MGSA- NSGA-Ⅲ，采取混沌變異策略，提高解空間分布的均勻性。LI等[11]在傳統(tǒng)NSGA-Ⅲ基礎(chǔ)上改進(jìn)了參考點(diǎn)生成策略和算子選擇機(jī)制，提高了算法計(jì)算效率。求解高維多目標(biāo)問(wèn)題時(shí)，常見(jiàn)的全局智能算法均存在著種群多樣性低、搜索效率差、容易陷入局部最優(yōu)等缺陷。

綜上所述，文章提出了一種改進(jìn)NSGA-Ⅲ算法，采取4種不同編碼方式共同生成初始化種群，并引入鄰域搜索策略，解決單一算法種群多樣性低、容易陷入局部最優(yōu)等問(wèn)題。

1 多目標(biāo)柔性作業(yè)車間調(diào)度模型建立

柔性作業(yè)車間的柔性表現(xiàn)在加工順序和設(shè)備選擇上的不確定性，使多目標(biāo)調(diào)度問(wèn)題更為復(fù)雜。假設(shè)，車間共有m臺(tái)設(shè)備和n個(gè)待加工工件，并且每個(gè)工件含有多道加工工序。工件必須按照工序的加工順序依次加工，工件的每道工序的加工設(shè)備選取須在指定的設(shè)備集中，可選設(shè)備集中的機(jī)器加工能力存在差異。因此，柔性車間調(diào)度的兩個(gè)主要任務(wù)：①確定工件的加工順序；②確定每道工序選擇的設(shè)備。參數(shù)符號(hào)含義如表1所示。

表1 參數(shù)符號(hào)含義

機(jī)器集合M={M1,M2,…,Mm}，共有m臺(tái)設(shè)備；工件集合P={P1,P2,…,Pn}，共有n個(gè)工件；工序集合J={J1,J2,…,Jn}，Ji={Ji1,Ji2,…,Jik}，Ji表示第i個(gè)工件加工的工序數(shù)。

(1)目標(biāo)函數(shù)。

①最大完工時(shí)間最?。?/p>

CM=min(max1≤i≤n(Ci))

(1)

②總設(shè)備負(fù)荷最??；

(2)

③車間總能耗最??；

(3)

(2)約束條件。

柔性作業(yè)車間調(diào)度問(wèn)題可描述成，n個(gè)工件在m臺(tái)設(shè)備上加工，且一個(gè)工件包含多道工序，每道工序可在一臺(tái)或多臺(tái)設(shè)備上加工，加工設(shè)備選擇不同，加工時(shí)間及加工功率不同。

①所有設(shè)備初始化均為待加工狀態(tài)。

(4)

②一個(gè)工件某一時(shí)刻只能加工一道工序。

(5)

式中，k′、k表示對(duì)應(yīng)加工設(shè)備編號(hào)

③一個(gè)工件的某一時(shí)刻只能在一臺(tái)設(shè)備上進(jìn)行加工。

Li,j,t1≠Li,j,t2→t1≠t2

(6)

式中，Li,j,t1為t1時(shí)刻執(zhí)行Oi,j的設(shè)備編號(hào)；Li,j,t2為t2時(shí)刻執(zhí)行Oi,j的設(shè)備編號(hào)。

④任意工件只要選定設(shè)備開(kāi)始加工，則過(guò)程中不能中斷。

(7)

⑤每個(gè)工件的每道工序需在特定的設(shè)備集中選取。

mi,j∈Mi,j

(8)

2 改進(jìn)NSGA-Ⅲ算法設(shè)計(jì)

遺傳算法在求解調(diào)度優(yōu)化問(wèn)題時(shí)具備魯棒性強(qiáng)特點(diǎn)。求解多目標(biāo)問(wèn)題時(shí)，NSGA-Ⅱ[12]和NSGA-Ⅲ被廣泛使用，為了進(jìn)一步提高算法的效率，避免陷入局部最優(yōu)，對(duì)NSGA-Ⅲ算法做出如下改進(jìn)。算法流程如圖1所示。

圖1 改進(jìn)NSGA-Ⅲ算法流程圖

基本步驟如下：

(1)種群初始化階段，為保證種群分布均勻并且縮小搜索的解空間大小。采取4種不同編碼的種群初始化方式；

(2)混合NSGA-Ⅱ基于擁擠度選擇和錦標(biāo)賽的方式，對(duì)初始化種群進(jìn)行篩選，使具有良好基因的個(gè)體參與到進(jìn)化當(dāng)中；

(3)利用NSGA-Ⅲ的全局搜索能力，對(duì)種群進(jìn)行搜索，選擇出下一代優(yōu)良個(gè)體；

(4)結(jié)合基于部分解的隨機(jī)鄰域搜索策略，對(duì)(3)選擇出的優(yōu)良個(gè)體進(jìn)行鄰域搜索，避免丟失更優(yōu)的個(gè)體；

(5)判斷算法是否終止，即算法是否迭代到指定代數(shù)，是則算法終止，否則繼續(xù)迭代。

2.1 染色體編碼設(shè)計(jì)

工件的加工工序順序和每道工序的設(shè)備分配是柔性作業(yè)車間調(diào)度中最基本的兩個(gè)方面。因此，在此類問(wèn)題上采取兩部分編碼方式。第一部分基于工序編碼，選取工件編號(hào)作為工序部分基因，第二部分基于設(shè)備編碼，選取設(shè)備集中的設(shè)備順序號(hào)作為基因。圖2以3個(gè)工件在3臺(tái)設(shè)備上加工為例來(lái)編碼。

圖2 染色體編碼

工序編碼表示為三個(gè)工件的加工順序，第一個(gè)1出現(xiàn)表示O1,1工序，第二個(gè)1出現(xiàn)表示O1,2工序。設(shè)備編碼表示完成某工序可用設(shè)備集中所選擇設(shè)備的順序號(hào)，例如，設(shè)備編碼中第一個(gè)2表示為完成O1,1工序，在m1,1中選擇第2個(gè)設(shè)備M2。

2.2 種群初始化設(shè)計(jì)

種群空間的均勻性是影響算法性能好壞的重要指標(biāo)。越是均勻的種群空間，算法的搜索結(jié)果往往更優(yōu)，不容易陷入局部最優(yōu)等問(wèn)題。因此，為使種群空間具有均勻性，采用4種不同的編碼方式共同生成初始化種群。

(1)采取最長(zhǎng)路徑(即加工工序最多)加工時(shí)間最短原則編碼。

(2)采取隨機(jī)加工工序的加工時(shí)間最短原則編碼。

(3)采取最長(zhǎng)路徑加工功率最小原則編碼。

(4)采取隨機(jī)加工工序的加工功率最小原則編碼。

2.3 初始化種群個(gè)體的選擇

錦標(biāo)賽選擇的方式是常見(jiàn)的選擇手段之一，而在解決高維多目標(biāo)問(wèn)題時(shí)，單一的選擇方式很難達(dá)到理想效果，需要更多的指標(biāo)來(lái)保證選取的合理性。綜合考慮算法的計(jì)算效率和選取結(jié)果的最優(yōu)程度，提出結(jié)合NSGA-Ⅱ中的快速非支配等級(jí)和基于擁擠度的選擇方式。

(1)計(jì)算種群個(gè)體的非支配等級(jí)和擁擠度大小。

(2)設(shè)置錦標(biāo)賽參賽數(shù)量，選擇出參賽的個(gè)體，再依據(jù)非支配排序等級(jí)，選出等級(jí)較高的個(gè)體。

(3)當(dāng)選擇的個(gè)體非支配排序等級(jí)一致時(shí)，選擇擁擠度較大的個(gè)體。

2.4 交叉與變異

(1)交叉操作。采用模擬二進(jìn)制交叉方式，分別對(duì)工序和設(shè)備進(jìn)行交叉。工序交叉如圖3所示，設(shè)備交叉如圖4所示。

圖3 工序交叉示意圖

將P1中工序2位置保留，再將P2中不屬于工序2 的位置順序插入到P1中得到子代個(gè)體C1,同理，得到C2。

圖4 設(shè)備交叉示意圖

確定父代個(gè)體中設(shè)備交叉位置，進(jìn)行交叉生成子代個(gè)體。再依據(jù)工序染色體對(duì)交叉后的設(shè)備染色體產(chǎn)生的非法基因按照設(shè)備加工時(shí)間最短原則進(jìn)行修正。

(2)變異操作。變異操作采取基于工序交叉和設(shè)備交叉的變異方式，利用隨機(jī)函數(shù)產(chǎn)生工序交叉位置，同時(shí)保證位置上點(diǎn)數(shù)值不同。交叉完成后，工序基因?qū)?yīng)的不合理設(shè)備基因，按照工序加工時(shí)間最短原則進(jìn)行修正，設(shè)備交叉與工序交叉同理。工序交叉變異過(guò)程如圖5所示。

圖5 基于工序交叉的變異圖

2.5 基于部分解的隨機(jī)鄰域搜索策略

NSGA-Ⅲ具有良好的全局搜索能力，但其對(duì)局部的搜索能力較差，因此算法在迭代過(guò)程中往往會(huì)出現(xiàn)局部最優(yōu)的問(wèn)題。基于此，采取鄰域搜索機(jī)制[13]與NSGA-Ⅲ算法混合的方式。

(1)首先，設(shè)置大小為K的鄰域搜索空間。

(2)選擇鄰域搜索個(gè)體，并在該個(gè)體中隨機(jī)選擇兩個(gè)工件的工序作為關(guān)鍵工序，對(duì)工件1中所有工序的設(shè)備進(jìn)行重新選擇：①當(dāng)最短加工時(shí)間設(shè)備唯一，選擇該設(shè)備加工。②當(dāng)最短加工時(shí)間設(shè)備不唯一，選擇所有設(shè)備中加工功率最小的設(shè)備。對(duì)工件2中所有工序的設(shè)備重新隨機(jī)選擇。

(3)滿足初始設(shè)定的K值時(shí)，結(jié)束鄰域搜索。

3 仿真驗(yàn)證

首先，驗(yàn)證改進(jìn)算法目標(biāo)迭代的收斂情況，再將所提出的改進(jìn)NSGA-Ⅲ算法與原始NSGA-Ⅲ 算法進(jìn)行對(duì)比驗(yàn)證，觀察兩個(gè)算法在相同實(shí)例下所得到的初始解空間的均勻性、大小和非支配解的數(shù)量。

算法基本參數(shù)如表2所示。

表2 算法基本參數(shù)

(1)初始化種群分布和最優(yōu)解的分布對(duì)比。對(duì)比NSGA-Ⅲ算法與所提出的改進(jìn)NSGA-Ⅲ算法在求解MK01算例時(shí)初始化種群的分布情況和最優(yōu)解分布情況，如圖6～圖8所示。

圖6 NSGA-Ⅲ初始 化種群分布圖7 改進(jìn)NSGA-Ⅲ 初始化種群分布

圖8 兩種算法最優(yōu)解的分布圖

由上述分布圖可知，改進(jìn)NSGA-Ⅲ算法的初始化種群分布更均勻，搜索的解空間更小，且搜索到的最優(yōu)解收斂更好，求解結(jié)果更優(yōu)。

(2)非支配解對(duì)比驗(yàn)證。對(duì)于非支配解的驗(yàn)證，采用10個(gè)BRdate[14]實(shí)例進(jìn)行仿真。兩種算法在10個(gè)BRdate實(shí)例上搜索到非支配解情況匯總?cè)缦拢浩渲蠳SD表示兩個(gè)算法搜索到的非支配解總數(shù)；～表示沒(méi)有搜到非支配解；n1|n2中n1代表對(duì)應(yīng)算法搜索到的非支配解數(shù)量，n2代表兩個(gè)算法搜索的非支配解總數(shù)。具體非支配解信息匯總?cè)绫?所示。

表3 兩種算法的非支配解

由上表可知，改進(jìn)NSGA-Ⅲ在10組BRdate算例中搜索到非支配解數(shù)占76%，而NSGA-Ⅲ搜索到非支配解數(shù)占24%，改進(jìn)NSGA-Ⅲ有效性得以驗(yàn)證。

4 總結(jié)

針對(duì)柔性作業(yè)車間調(diào)度問(wèn)題，建立以最小化完工時(shí)間，設(shè)備總負(fù)荷和車間總能耗為目標(biāo)的多目標(biāo)調(diào)度模型，并對(duì)求解多目標(biāo)問(wèn)題具有良好魯棒性的NSGA-Ⅲ算法做出改進(jìn)。首先，采取4種不同編碼方式的種群初始化策略，使得種群分布均勻的同時(shí)，縮小搜索的解空間大小。在進(jìn)化階段，混合了NSGA-Ⅱ基于擁擠度的父代種群選擇和基于部分解的鄰域搜索策略，防止算法在實(shí)現(xiàn)全局搜索時(shí)，陷入局部最優(yōu)。

最終，通過(guò)10個(gè)BRdate標(biāo)準(zhǔn)算例對(duì)所提出的改進(jìn)NSGA-Ⅲ算法與原始NSGA-Ⅲ算法進(jìn)行對(duì)比驗(yàn)證。依據(jù)初始化種群的均勻性、搜索解空間的大小和非支配解的數(shù)量等指標(biāo)來(lái)判斷算法的優(yōu)劣，證明所提出算法的有效性。