基于離散多元宇宙算法的柔性作業(yè)車間調(diào)度*

方 恒,朱建鴻

(江南大學(xué)輕工過程先進控制教育部重點實驗室,無錫 214122)

0 引言

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

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

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

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

1 FJSP描述與建模

1.1 問題描述

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

(1)每一臺機器在相同時刻僅能加工某個工件的某道工序;

(2)每個工件在相同時刻僅能在一臺機器上加工;

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

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

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

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

在FJSP中,J={1,2,…,n}為工件集合;M={1,2,…,m}為機器集合;Qi={1,2,…,qi}為工件i的工序集合,i∈J;Oij為工件i的第j道工序,j∈Qi;Mij為工序Oij可加工的機器集合;Tijh為工序Oij在機器h上的加工時間,h∈Mij;Sij為工序Oij加工的開工時間;Eij為工序Oij加工的結(jié)束時間;Ci為工件i的完工時間;Yijz為0-1變量,工序Oij在機器z上加工則值為1,z∈M;Gijvw為0-1變量,工序Oij先于工序Ovw加工則值為1;R為一個大的正實數(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ù)是最大完工時間的最小化;式(2)表示所有工序加工過程中不可中斷;式(3)表示同一工件的不同工序間加工先后約束;式(4)表示所有工序加工的開工時間不大于結(jié)束時間;式(5)表示所有工序只在機器上加工一次;式(6)表示任意工件完工時間不大于最大完工時間;式(7)表示每臺機器在同一時刻僅能加工一道工序;式(8)表示所有工序開工、加工、結(jié)束時間非負(fù)。

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

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

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

(9)

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

(10)

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

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

(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]間的隨機數(shù),T是旅行距離率,WEP是蟲洞存在概率,WEPmin=0.2,WEPmax=1,l是當(dāng)前迭代次數(shù),L是最大迭代次數(shù),p是開采精度,一般取值為6。

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

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

3.1 編碼與解碼

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

圖1 雙層編碼方式

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

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

3.2 宇宙種群初始化

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

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

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

3.3 白洞選擇機制

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

3.4 白洞黑洞傳輸機制

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

圖2 OS編碼更新

3.5 向最優(yōu)宇宙移動機制

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

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

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

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

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

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

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

3.6 算法步驟

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

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

步驟3:開始第l次迭代。

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

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

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

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

4 仿真實驗與分析

4.1 實驗配置

本文提出的DMVO算法采用python3.6編程實現(xiàn),計算機配置為: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)共計15個算例進行仿真實驗,n為工件數(shù)目,m為機器數(shù)目,兩者乘積n×m表示算例的規(guī)模,UB為已有算法求得算例的最優(yōu)解,所有算例均無量綱。DMVO算法設(shè)置的參數(shù)為:種群規(guī)模為100,WEPmin=0,WEPmax=0.5,最大迭代次數(shù)為200。

4.2 改進機制有效性分析

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

圖4 MK04測試平均迭代收斂曲線圖

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

4.3 與其他算法的對比分析

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

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

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

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

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

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

5 結(jié)論

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