方 恒,朱建鴻

(江南大學(xué)輕工過(guò)程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室,無(wú)錫 214122)

0 引言

調(diào)度優(yōu)化問(wèn)題可以描述為將有限的資源合理的分配給若干任務(wù),調(diào)度結(jié)果的優(yōu)劣將直接影響企業(yè)的生產(chǎn)效益。柔性作業(yè)車間調(diào)度問(wèn)題(flexible job-shop scheduling problem,FJSP)是常見(jiàn)的調(diào)度優(yōu)化問(wèn)題之一,相比較于經(jīng)典作業(yè)車間問(wèn)題(job-shop scheduling problem,JSP),其至少有一道工序可在多臺(tái)機(jī)器上加工,且加工時(shí)間不同。FJSP這種特性使得其更加貼合實(shí)際生產(chǎn),求解難度也大幅增加[1-2]。

隨著研究的深入和問(wèn)題規(guī)模的擴(kuò)大,相較于精確算法而言,群智能算法原理簡(jiǎn)單、易于實(shí)現(xiàn),能夠在較短的時(shí)間內(nèi)求得問(wèn)題的近優(yōu)解,目前已有多種群智能算法被提出[3-4],并在求解FJSP時(shí)取得了較為優(yōu)越的結(jié)果。王玉芳等[5]提出了一種自適應(yīng)灰狼算法求解FJSP,并融合基于關(guān)鍵路徑和負(fù)載均衡兩種鄰域結(jié)構(gòu)的變鄰域搜索,以提高算法的性能。ALI等[6]為求解FJSP,引入了基于膜計(jì)算的并行框架來(lái)改進(jìn)和聲搜索算法。DING等[7]提出了一種改進(jìn)的粒子群優(yōu)化算法求解FJSP,并設(shè)計(jì)了一種新穎的鏈?zhǔn)骄幋a方案和相對(duì)應(yīng)的有效解碼方案,增強(qiáng)了算法的搜索能力。張博等[8]同時(shí)以最大完工時(shí)間、總加工成本、總加工質(zhì)量、總能耗和負(fù)載平衡為目標(biāo),提出了一種改進(jìn)多目標(biāo)粒子群算法。

多元宇宙優(yōu)化算法(multiverse optimizer,MVO)是MIRJALILI等[9]提出的一種群智能優(yōu)化算法,通過(guò)多元宇宙中白洞、黑洞和蟲(chóng)洞的相互作用來(lái)建立數(shù)學(xué)模型。MVO算法由于具有原理簡(jiǎn)單、易于實(shí)現(xiàn)、調(diào)整參數(shù)少、搜索效率高等優(yōu)點(diǎn),得到廣泛關(guān)注。MAUSAM等[10]將MVO算法與變分模式分解相結(jié)合,應(yīng)用于彩色圖像分解中。吳忠強(qiáng)等[11]將改進(jìn)的MVO算法應(yīng)用于光伏系統(tǒng)最大功率點(diǎn)的跟蹤中。於萬(wàn)里等[12]通過(guò)Levy飛行對(duì)MVO算法進(jìn)行改進(jìn),解決了氨糖發(fā)酵過(guò)程的工藝參數(shù)優(yōu)化問(wèn)題?；綧VO算法是針對(duì)連續(xù)優(yōu)化問(wèn)題而設(shè)計(jì),無(wú)法直接求解離散的FJSP。

基于上述問(wèn)題,本文提出一種離散多元宇宙優(yōu)化算法(discrete multi verse optimizer,DMVO)。采用兩段式整數(shù)編碼表示宇宙?zhèn)€體,并使用貪婪插入解碼提高解空間的搜索能力;利用混合策略初始化宇宙種群;在基本MVO算法基礎(chǔ)上,改進(jìn)了白洞選擇機(jī)制和離散的更新策略;最后通過(guò)基準(zhǔn)算例與其他算法進(jìn)行對(duì)比仿真實(shí)驗(yàn),驗(yàn)證了DMVO算法求解FJSP的有效性和可行性。

1 FJSP描述與建模

1.1 問(wèn)題描述

FJSP可描述為:車間中有多個(gè)工件需要加工,每個(gè)工件包含有多道工序,每道工序至少有一臺(tái)機(jī)器可以選擇,調(diào)度的目標(biāo)是為每道工序安排加工機(jī)器和為每臺(tái)機(jī)器上的加工工序進(jìn)行排序使得最大完工時(shí)間最小。FJSP需考慮如下假設(shè):

(1)每一臺(tái)機(jī)器在相同時(shí)刻僅能加工某個(gè)工件的某道工序;

(2)每個(gè)工件在相同時(shí)刻僅能在一臺(tái)機(jī)器上加工;

(3)不同工件的工序之間不存在優(yōu)先級(jí)的差別,同一工件的不同工序存在先后順序;

(4)每道工序加工過(guò)程中不可中斷;

(5)忽略工件在不同機(jī)器上的轉(zhuǎn)運(yùn)時(shí)間,且所有工件在初始時(shí)刻都可以被加工。

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

在FJSP中,J={1,2,…,n}為工件集合;M={1,2,…,m}為機(jī)器集合;Qi={1,2,…,qi}為工件i的工序集合,i∈J;Oij為工件i的第j道工序,j∈Qi;Mij為工序Oij可加工的機(jī)器集合;Tijh為工序Oij在機(jī)器h上的加工時(shí)間,h∈Mij;Sij為工序Oij加工的開(kāi)工時(shí)間;Eij為工序Oij加工的結(jié)束時(shí)間;Ci為工件i的完工時(shí)間;Yijz為0-1變量,工序Oij在機(jī)器z上加工則值為1,z∈M;Gijvw為0-1變量,工序Oij先于工序Ovw加工則值為1;R為一個(gè)大的正實(shí)數(shù)。

FJSP具體的數(shù)學(xué)模型[13]如下:

min(Cmax)=max(Ci)

(1)

s.t.

Eij-Sij=Tijz,?i,j,z

(2)

Eij≤Sik,?i,j

(3)

Sij+TijzYijz≤Eij,?i,j,z

(4)

(5)

Ci≤Cmax,?i

(6)

EvwYvwz+R(Gvwij-1)≤SijYijz,?i,j,v,w,z

(7)

Sij≥0,Tijz≥0,Eij≥0,?i,j,z

(8)

式(1)表示目標(biāo)函數(shù)是最大完工時(shí)間的最小化;式(2)表示所有工序加工過(guò)程中不可中斷;式(3)表示同一工件的不同工序間加工先后約束;式(4)表示所有工序加工的開(kāi)工時(shí)間不大于結(jié)束時(shí)間;式(5)表示所有工序只在機(jī)器上加工一次;式(6)表示任意工件完工時(shí)間不大于最大完工時(shí)間;式(7)表示每臺(tái)機(jī)器在同一時(shí)刻僅能加工一道工序;式(8)表示所有工序開(kāi)工、加工、結(jié)束時(shí)間非負(fù)。

2 基本多元宇宙優(yōu)化算法

MVO算法基于物理學(xué)中的多元宇宙理論,模擬宇宙種群在黑洞、白洞和蟲(chóng)洞三者的相互作用下不斷激發(fā)宇宙膨脹率,黑洞從外部吸收任何物質(zhì),白洞則從內(nèi)部向外輻射出物質(zhì)和能量,蟲(chóng)洞是連接兩個(gè)遙遠(yuǎn)時(shí)空的隧道,通過(guò)它可以穿越到平行宇宙進(jìn)行物質(zhì)傳輸。

首先產(chǎn)生初始宇宙種群:

(9)

MVO算法在每次迭代時(shí),首先根據(jù)宇宙種群的膨脹率(在本文FJSP中,定義膨脹率為最大完工時(shí)間的倒數(shù))進(jìn)行排序,遍歷宇宙作為黑洞,通過(guò)輪盤賭原則選擇一個(gè)宇宙作為白洞與之進(jìn)行物質(zhì)傳輸,公式如下:

(10)

式中:Ub是通過(guò)輪盤賭原則選擇的宇宙b,NI(Ui)是宇宙i的歸一化膨脹率,r1是[0,1]間的隨機(jī)數(shù)。

為了保證宇宙種群的多樣性,各個(gè)宇宙會(huì)不斷的向最優(yōu)宇宙移動(dòng),公式為:

(11)

T=1-l1/p/L1/p

(12)

WEP=WEPmin+l×(WEPmax-WEPmin)/L

(13)

式中:Ug是當(dāng)前最優(yōu)宇宙,r2、r3、r4是[0,1]間的隨機(jī)數(shù),T是旅行距離率,WEP是蟲(chóng)洞存在概率,WEPmin=0.2,WEPmax=1,l是當(dāng)前迭代次數(shù),L是最大迭代次數(shù),p是開(kāi)采精度,一般取值為6。

3 離散多元宇宙優(yōu)化算法

基本MVO算法只適用于求解連續(xù)函數(shù)優(yōu)化問(wèn)題,而FJSP是一類離散組合優(yōu)化問(wèn)題,需要將MVO進(jìn)行合理的離散化,避免算法陷入局部最優(yōu)、過(guò)早收斂。

3.1 編碼與解碼

FJSP包含機(jī)器選擇和工序排序兩個(gè)子問(wèn)題,采用機(jī)器層編碼MS和工序?qū)泳幋aOS構(gòu)成的兩段式整數(shù)編碼來(lái)表示一個(gè)調(diào)度解,編碼長(zhǎng)度為總工序數(shù),編碼方式如圖1所示。

圖1 雙層編碼方式

圖1中,共3個(gè)工件總計(jì)8道工序。機(jī)器層編碼MS各位置分量代表該位置所對(duì)應(yīng)的工序選擇加工的機(jī)器編號(hào),如工序O21可供選擇加工的機(jī)器有M1、M3和M4,編碼處選擇機(jī)器M3進(jìn)行加工;工序?qū)泳幋aOS各位置分量表示工件號(hào),加工順序從左至右,出現(xiàn)的次數(shù)表示對(duì)應(yīng)工件的第幾道工序,圖1工序?qū)泳幋a表示的加工順序?yàn)?O11、O21、O12、O31、O22、O13、O23、O32。

解碼時(shí),根據(jù)MS編碼為各道工序安排加工機(jī)器,遍歷OS編碼求解各道工序開(kāi)工時(shí)間和結(jié)束時(shí)間進(jìn)而求得最大完工時(shí)間,工序開(kāi)工時(shí)間為同一機(jī)器的上一道工序結(jié)束時(shí)間和同一工件的上一道工序結(jié)束時(shí)間的最大值。本文采用貪婪插入解碼方法[14],確保解碼后產(chǎn)生活動(dòng)調(diào)度,在不推遲已安排好的工序開(kāi)工時(shí)間以及滿足工件工序加工順序約束的條件下,將工序插入到當(dāng)前機(jī)器的空閑時(shí)間里。

3.2 宇宙種群初始化

一個(gè)具有多樣性和高質(zhì)量解的初始宇宙種群能夠給算法提供一個(gè)優(yōu)質(zhì)的起點(diǎn)。本文OS編碼采用完全隨機(jī)方式生成,再根據(jù)生成的OS編碼,采用全局、局部隨機(jī)混合兩種策略生成MS編碼,比例為1:1,生成方式為:

(1)全局策略:遍歷OS編碼,考慮各個(gè)機(jī)器的加工負(fù)載,在當(dāng)前工序加工可選機(jī)器集中選擇當(dāng)前工序完工時(shí)間最短的機(jī)器。

(2)局部隨機(jī)混合策略:遍歷OS編碼,僅考慮當(dāng)前工序的加工時(shí)間長(zhǎng)短,以0.5的概率選擇加工時(shí)間最短的機(jī)器,否則隨機(jī)選擇加工機(jī)器。

3.3 白洞選擇機(jī)制

在基本MVO算法中,白洞選擇依靠輪盤賭機(jī)制進(jìn)行選擇,而FJSP的各個(gè)解之間往往相差不懸殊,導(dǎo)致白洞大多集中在中間一部分宇宙,對(duì)于前一部分和后一部分宇宙來(lái)說(shuō),均難以選擇優(yōu)質(zhì)、多樣的白洞進(jìn)行物質(zhì)傳輸,算法容易陷入早熟。因此,本文對(duì)白洞選擇機(jī)制進(jìn)行改進(jìn),在迭代過(guò)程中,從膨脹率比當(dāng)前宇宙高的宇宙?zhèn)€體中隨機(jī)選擇一個(gè)宇宙作為白洞。

3.4 白洞黑洞傳輸機(jī)制

MS編碼每個(gè)位置代表一個(gè)工序的加工機(jī)器選擇,各位置間互不沖突,按式(10)進(jìn)行更新,對(duì)于宇宙Ui的MS編碼第j維變量,如果隨機(jī)數(shù)r1大于等于宇宙Ui的歸一化膨脹率,則將白洞Ub的MS編碼第j維變量傳輸至Ui的MS編碼第j維位置上。但這種更新方式對(duì)OS編碼更新會(huì)產(chǎn)生非法解,因?yàn)槊總€(gè)工件的總工序數(shù)是確定不變的。為了確保解的合法性,在進(jìn)行OS編碼的黑洞白洞傳輸時(shí),先找到Ub的OS編碼第j維變量所代表工序在Ui的OS編碼的位置,再將其插入到Ui的OS編碼第j維位置上,中間OS編碼左移或右移,具體操作如圖2所示。

圖2 OS編碼更新

3.5 向最優(yōu)宇宙移動(dòng)機(jī)制

在基本MVO算法中,個(gè)體在經(jīng)過(guò)黑洞白洞傳輸后通過(guò)在最優(yōu)宇宙鄰域內(nèi)進(jìn)行搜索,來(lái)改善種群的多樣性、激發(fā)宇宙膨脹率。對(duì)于FJSP這類離散問(wèn)題,基本MVO算法中的實(shí)數(shù)移動(dòng)鄰域概念不再適用,FJSP調(diào)度解的鄰域解可由交換、插入、變異等鄰域結(jié)構(gòu)定義產(chǎn)生,不同調(diào)度方案的個(gè)體經(jīng)過(guò)鄰域搜索后均有得到改善的潛力。因此,將向最優(yōu)宇宙移動(dòng)機(jī)制定義為基于關(guān)鍵路徑[15]的變鄰域搜索,如果隨機(jī)數(shù)r4

在FJSP中,每道工序的最早開(kāi)工時(shí)間從初始時(shí)刻依次計(jì)算,每道工序的最晚開(kāi)工時(shí)間從完工時(shí)刻逆序計(jì)算。最早開(kāi)工時(shí)間和最晚開(kāi)工時(shí)間相等的工序稱作為關(guān)鍵工序,同一臺(tái)機(jī)器上相鄰的幾個(gè)關(guān)鍵工序的組合稱為關(guān)鍵塊,多個(gè)關(guān)鍵塊組成一條關(guān)鍵路徑,對(duì)關(guān)鍵路徑進(jìn)行擾動(dòng)一定會(huì)改變最大完工時(shí)間。圖3為圖一編碼對(duì)應(yīng)的調(diào)度甘特圖,虛線內(nèi)為關(guān)鍵塊。

圖3 調(diào)度甘特圖

本文使用基于關(guān)鍵路徑的鄰域結(jié)構(gòu)為:

(1)鄰域結(jié)構(gòu)N1:隨機(jī)選取關(guān)鍵工序不少于兩個(gè)的關(guān)鍵塊,在關(guān)鍵塊上隨機(jī)選取兩道不同工件的工序,將兩者所在OS編碼位置元素交換。

(2)鄰域結(jié)構(gòu)N2:隨機(jī)選取關(guān)鍵工序不少于3個(gè)的關(guān)鍵塊,在關(guān)鍵塊上隨機(jī)選取兩道工序,將后一個(gè)工序所在OS編碼位置元素插入到前一個(gè)工序所在OS編碼位置,中間OS編碼后移。

(3)鄰域結(jié)構(gòu)N3:隨機(jī)選取一個(gè)可選機(jī)器不少于一臺(tái)的關(guān)鍵工序,隨機(jī)選擇一臺(tái)不同的機(jī)器加工,改變MS編碼。

3.6 算法步驟

步驟1:參數(shù)設(shè)置。設(shè)置工件數(shù)n,機(jī)器數(shù)m,最大迭代次數(shù)MaxIter,宇宙種群規(guī)模POP,蟲(chóng)洞存在概率WEPmin、WEPmax等。

步驟2:初始化宇宙種群。計(jì)算每個(gè)宇宙?zhèn)€體Ui的膨脹率Fit(Ui)和歸一化膨脹率NI(Ui),記錄最優(yōu)個(gè)體及其膨脹率為Ubest、Fitbest。

步驟3:開(kāi)始第l次迭代。

步驟4:白洞黑洞傳輸。使用3.3節(jié)白洞選擇機(jī)制和3.4節(jié)黑洞白洞傳輸對(duì)每一個(gè)宇宙?zhèn)€體Ui進(jìn)行更新,產(chǎn)生新的個(gè)體Unew,若Fit(Unew)≥Fit(Ui),則將Unew替代Ui。

步驟5:向最優(yōu)宇宙移動(dòng)。按式(13)更新WEP,遍歷宇宙種群,若r4

步驟6:若第l代最優(yōu)宇宙?zhèn)€體Ul膨脹率Fit(Ul)≥Fitbest,則更新Ubest、Fitbest。

步驟7:l=l+1,若l>MaxIter,輸出Ubest,否則進(jìn)入下一次迭代。

4 仿真實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)配置

本文提出的DMVO算法采用python3.6編程實(shí)現(xiàn),計(jì)算機(jī)配置為:AMD R7-4800H(2.9 GHz)、16 G內(nèi)存,Windows 10操作系統(tǒng)。選取KACEM[16]基準(zhǔn)算例集(Kacem01-Kacem05)和BRANDIMARTE[17]基準(zhǔn)算例集(MK01-MK10)共計(jì)15個(gè)算例進(jìn)行仿真實(shí)驗(yàn),n為工件數(shù)目,m為機(jī)器數(shù)目,兩者乘積n×m表示算例的規(guī)模,UB為已有算法求得算例的最優(yōu)解,所有算例均無(wú)量綱。DMVO算法設(shè)置的參數(shù)為:種群規(guī)模為100,WEPmin=0,WEPmax=0.5,最大迭代次數(shù)為200。

4.2 改進(jìn)機(jī)制有效性分析

為了驗(yàn)證本文所提出的幾種改進(jìn)機(jī)制的有效性,選取Brandimarte基準(zhǔn)算例集中的MK04算例(15×8)對(duì)DMVO1、DMVO2、DMVO3和DMVO算法進(jìn)行對(duì)比實(shí)驗(yàn),其中,DMVO1為只包含離散黑洞白洞傳輸?shù)腗VO算法,DMVO2為在DMVO1基礎(chǔ)上加入改進(jìn)初始化種群機(jī)制,DMVO3為在DMVO2基礎(chǔ)上加入改進(jìn)白洞選擇機(jī)制,DMVO為本文所提算法。各算法獨(dú)立運(yùn)行5次,其平均迭代收斂曲線如圖4所示。

圖4 MK04測(cè)試平均迭代收斂曲線圖

從圖4可以看出,離散化黑洞白洞傳輸機(jī)制可以有效的求解FJSP;初始化種群機(jī)制的加入使得算法初始解的質(zhì)量大大提高,加快了算法的收斂;DMVO3由于加入了改進(jìn)的白洞選擇機(jī)制,很好的利用了其他優(yōu)質(zhì)宇宙的信息,相比較于DMVO2算法尋優(yōu)能力得到提高;離散向最優(yōu)宇宙移動(dòng)機(jī)制的變鄰域搜索策略也使得算法能夠在后期跳出局部最優(yōu)值。

4.3 與其他算法的對(duì)比分析

為了驗(yàn)證所提DMVO算法求解FJSP的有效性和穩(wěn)定性,對(duì)上述15個(gè)基準(zhǔn)算例進(jìn)行10次求解,記錄最大完工時(shí)間的最優(yōu)值和平均值并分別與DAPSO算法[18]、HGWO算法[19]和GATS-HM算法[20]進(jìn)行對(duì)比,對(duì)比結(jié)果如表1所示。

表1 基準(zhǔn)算例計(jì)算結(jié)果對(duì)比

在表1中,Best為算法求解得到的最優(yōu)值;Avg為算法求解10次得到的平均值;MPDR為算法求得15個(gè)基準(zhǔn)算例的最優(yōu)解與UB間相對(duì)百分比偏差的平均值,用以衡量算法的求解性能,相對(duì)百分比偏差PDR由公式PDR=100×[(Best-UB)/UB]求解得到。

由表1的數(shù)據(jù)可以看出,雖然本文提出的DMVO算法在Kacem05、MK05算例上的效果不如GATS-HM算法,但在15個(gè)基準(zhǔn)算例中求得最優(yōu)解的個(gè)數(shù)為10個(gè),優(yōu)于GATS-HM算法(8個(gè))、DAPSO算法(7個(gè))和HGWO算法(7個(gè))。從與目前最優(yōu)解的偏差來(lái)看,DMVO算法在15個(gè)基準(zhǔn)算例上的MPRD值為2.40,明顯優(yōu)于DAPSO算法(4.09)和HGWO算法(8.13),較優(yōu)于GATS-HM算法(2.99),說(shuō)明所提DMVO算法在求解FJSP上具有一定的優(yōu)越性。此外,各基準(zhǔn)算例10次求解的平均值與最優(yōu)值相差較小,表明DMVO算法求解FJSP具有較好的穩(wěn)定性。

圖5為DMVO算法求解MK04算例的最優(yōu)調(diào)度甘特圖,最大完工時(shí)間為60,圖5中工序塊內(nèi)數(shù)字為工件號(hào),出現(xiàn)的次數(shù)代表則代表該工件第幾道工序。

圖5 MK04最優(yōu)調(diào)度甘特圖

5 結(jié)論

本文針對(duì)以最大完工時(shí)間為目標(biāo)的FJSP,提出了一種離散化的多元宇宙優(yōu)化算法。采用兩段式整數(shù)編碼和貪婪插入解碼,建立算法與調(diào)度解之間的聯(lián)系;設(shè)計(jì)一種初始化方法為算法提供一個(gè)優(yōu)質(zhì)的起點(diǎn);針對(duì)多元宇宙算法在FJSP上的應(yīng)用,設(shè)計(jì)新的白洞選擇、白洞黑洞轉(zhuǎn)移和向最優(yōu)宇宙移動(dòng)機(jī)制,以提高算法的性能。對(duì)15個(gè)著名的基準(zhǔn)算例進(jìn)行仿真實(shí)驗(yàn),結(jié)果驗(yàn)證了所提算法的有效性和穩(wěn)定性。在實(shí)際生產(chǎn)過(guò)程中,還需綜合考慮總機(jī)器負(fù)荷、機(jī)器總能耗等優(yōu)化目標(biāo),所以下一步工作中將繼續(xù)研究多元宇宙算法在多目標(biāo)FJSP上的應(yīng)用。