基于熵增強(qiáng)混沌遺傳算法的柔性作業(yè)車間調(diào)度*

李永湘,姚錫凡

(1.貴州工程應(yīng)用技術(shù)學(xué)院機(jī)械工程學(xué)院,畢節(jié) 551700;2.華南理工大學(xué)機(jī)械與汽車工程學(xué)院,廣州 510640)

0 引言

優(yōu)質(zhì)的作業(yè)車間調(diào)度是提高制造企業(yè)生產(chǎn)效率和競爭力的重要途徑?，F(xiàn)代制造企業(yè)的多目標(biāo)柔性作業(yè)車間調(diào)度問題(multi-objective flexible job-shop scheduling problem,MFJSP)突破了傳統(tǒng)作業(yè)車間調(diào)度問題(job-shop scheduling problem,JSP)中工序?qū)?yīng)制造資源的唯一性約束[1]。在MFJSP加工任務(wù)中工件擁有多個備選加工路線,每道工序可有多個備選加工設(shè)備,且每道工序在不同加工設(shè)備上的加工時間可以是不相同的[2]。為了實(shí)現(xiàn)最優(yōu)化作業(yè)車間調(diào)度,需要根據(jù)市場變化需求和企業(yè)生產(chǎn)實(shí)際情況,動態(tài)調(diào)整工件各道工序由哪臺機(jī)器處理,達(dá)成多目標(biāo)綜合調(diào)度質(zhì)量最優(yōu)[3]。MFJSP問題模型更符合現(xiàn)代制造企業(yè)生產(chǎn)實(shí)踐,但也擴(kuò)大了可行解空間,已被證明是一個NP難題[4]。柔性制造生產(chǎn)實(shí)踐過程復(fù)雜,給加工車間制定最優(yōu)調(diào)度方案并有效組織生產(chǎn)提出了更高要求。為了在當(dāng)前逆全球化復(fù)雜環(huán)境下存活并發(fā)展下去,如何以最低成本、最少時間和最低生產(chǎn)組織復(fù)雜度完成工件加工任務(wù)成為眾多制造企業(yè)追求的目標(biāo)。

國內(nèi)外學(xué)者先后應(yīng)用遺傳算法、粒子群優(yōu)化算法等智能算法求解JSP問題,取得了許多成果。其中,遺傳算法求解復(fù)雜車間調(diào)度問題時潛力巨大,各種改進(jìn)遺傳算法為柔性作業(yè)車間調(diào)度優(yōu)化提供了新思路。謝志強(qiáng)等[5]應(yīng)用基于分枝定界和遺傳算法相結(jié)合的混合優(yōu)化策略實(shí)現(xiàn)多車間動態(tài)重調(diào)度。胡瑞淇等[6]研究了二進(jìn)制編碼遺傳算法求解順序柔性車間調(diào)度最優(yōu)解。王佳怡、李博宇等[7-9]研究了不同的交叉變異算法。MARJAN等[10]設(shè)計了新的選擇準(zhǔn)則和基于機(jī)器的新交叉算子以解決算法早熟問題。XU等[11]提出了一種基于個體相似度的自適應(yīng)交叉和變異操作。ATTIA、DANIAL等[12-14]研究了基于柯西變異、頻率分析等基因種群改進(jìn)法以提高遺傳算法搜索能力。

上述研究從不同角度改進(jìn)了遺傳算法的交叉算子和變異算子等,但文獻(xiàn)所提出的交叉算子產(chǎn)生的子代個體與父代個體之間相似程度高,全局搜索能力受限,對多峰函數(shù)易陷入早熟現(xiàn)象;優(yōu)化過程中缺少對車間物流和調(diào)度復(fù)雜度的考慮等。本文將調(diào)度熵引入MFJSP模型計算調(diào)度復(fù)雜度,提高車間調(diào)度方案的綜合調(diào)度質(zhì)量,并提出熵增強(qiáng)混沌遺傳算法求解MFJSP模型,用伯努利混沌映射和高斯云模型改進(jìn)遺傳算法鄰域搜索功能,提高算法執(zhí)行效率,最后通過應(yīng)用案例和仿真實(shí)驗(yàn)驗(yàn)證所提出模型和算法的有效性。

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

1.1 約束條件

MFJSP調(diào)度問題描述如下:N個工件(J1,J2,J3,…,JN)需在Q臺機(jī)器(M1,M2,M3,…,MQ)上加工,每個工件的制造過程包含1道及其以上數(shù)量的工序;各工件的每道工序都有1臺及其以上數(shù)量的可選加工機(jī)器;每道工序一旦開始加工就不可被中斷;每道工序在不同機(jī)器上的加工時間可不同;每個工件的所有工序之間加工順序是固定的;不同的工件之間加工無耦合關(guān)系,相互獨(dú)立,加工優(yōu)先級相同。因此,MFJSP中主要需考慮工序使用的機(jī)器和不同工件在同一機(jī)器上的加工順序。MFJSP約束關(guān)系數(shù)學(xué)模型表示為:

(1)

PETjh+PWTj(h,h+1)≤PSTj(h+1)

(2)

(3)

(4)

(5)

(6)

式中:i表示機(jī)器編號,i=1,2,3,…,Q;Q表示總機(jī)器數(shù)目,Qjh表示第j個工件的第h道工序的候選機(jī)器總數(shù),且Qjh≥1;j表示工件編號,j=1,2,3,…,N;N表示總工件數(shù)目,Pjh表示第j個工件的第h道工序,h表示工序編號,h=1,2,3,…,H;H表示總工序數(shù)目,Hj表示第j個工件的總工序數(shù)目,PSTjh表示第j個工件的第h道工序開始加工的時間,PETjh表示第j個工件的第h道工序加工結(jié)束時間,PETthreshold表示最大完工時間閾值,PWTj(h,h+1)為第j個工件的第h道工序與第h+1道工序之間的等待時間,MPTijh表示第j個工件的第h道工序在第i臺機(jī)器上的加工時間,σijh為開關(guān)變量。

式(1)和式(2)表示同一工件的工序約束關(guān)系,只能在上一道工序完成后才能開始下一道工序。式(3)表示工件的完工時間約束關(guān)系,所有工件的最大完工時間不能超過調(diào)度方案的最大完工時間閾值。式(4)表示機(jī)器約束關(guān)系,同一個工件的同一道工序只能被一臺機(jī)器加工。式(5)表示每個工件的制造過程包含1道及其以上數(shù)量的工序。

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

為獲得綜合調(diào)度質(zhì)量最優(yōu)的調(diào)度方案,本文設(shè)定了4個目標(biāo)函數(shù)為:

目標(biāo)函數(shù)1:求最大完工時間的最小值。

(7)

各個工件最后一道工序的結(jié)束時間稱為該工件的完工時間。調(diào)度方案中各個工件完工時間的最大值稱為該調(diào)度方案的最大完工時間。最大完工時間越小可確保工件交貨期,提高企業(yè)響應(yīng)市場需求的敏捷度。

目標(biāo)函數(shù)2:求最大機(jī)器負(fù)荷差的最小值。

(8)

不同調(diào)度方案中各個機(jī)器的加工負(fù)荷各不相同。機(jī)器之間負(fù)荷差越小,則各機(jī)器負(fù)荷越均衡。機(jī)器負(fù)荷均衡有利于充分發(fā)揮所有機(jī)器的效能,并方便機(jī)器的統(tǒng)一維護(hù)管理。

目標(biāo)函數(shù)3:求機(jī)器總負(fù)荷的最小值。

(9)

不同的調(diào)度方案中工序選擇不同機(jī)器加工工件所用時間不同,導(dǎo)致機(jī)器總負(fù)荷不同。加工成本往往與總加工時間成正比關(guān)系,盡量減小調(diào)度方案的機(jī)器總負(fù)荷,有利于節(jié)省成本,降低能耗。

目標(biāo)函數(shù)4:求調(diào)度復(fù)雜度的最小值。

調(diào)度復(fù)雜度通過調(diào)度熵來衡量。調(diào)度方案中單個工件的調(diào)度熵計算如下:

(10)

式中:SEj是第j個工件生產(chǎn)過程的調(diào)度熵,JSTjk是第j個工件在第k個狀態(tài)下的持續(xù)時間,工件的狀態(tài)主要包括從第一道工序開始至最后一道工序結(jié)束期間該工件的所有工序加工狀態(tài)和相鄰兩個工序之間的等待狀態(tài);JMTj是第j個工件從第一道工序開始至最后一道工序結(jié)束所用的總時間,SNj是第j個工件從第一道工序開始至最后一道工序結(jié)束期間所經(jīng)歷的總狀態(tài)數(shù)目。柔性作業(yè)車間調(diào)度復(fù)雜度等于調(diào)度方案中所有工件的調(diào)度熵之和,即總調(diào)度熵?？傉{(diào)度熵越小,則調(diào)度復(fù)雜度越小,工件制造可靠性越高,成功完成工件制造任務(wù)的概率越大。調(diào)度復(fù)雜度最小值計算公式為:

(11)

式中:SC表示調(diào)度復(fù)雜度,N表示調(diào)度方案中的總工件數(shù)目。

2 熵增強(qiáng)混沌遺傳算法

為提高M(jìn)FJSP調(diào)度問題尋優(yōu)質(zhì)量,克服傳統(tǒng)遺傳算法易過早陷入局部極值的問題,本文提出一種熵增強(qiáng)混沌遺傳算法(entropy-enhanced chaotic genetic algorithm,ECGA)求解MFJSP模型。將伯努利混沌映射引入遺傳算法,利用混沌運(yùn)算的隨機(jī)性、遍歷性、非線性特點(diǎn),改進(jìn)選擇算子,優(yōu)化算法鄰域搜索功能,應(yīng)用高斯云模型改進(jìn)交叉算子和變異算子,避免尋優(yōu)過程陷入局部極值,提高算法執(zhí)行效率。

2.1 基因編碼

ECGA算法采用二進(jìn)制編碼方法建立遺傳基因與調(diào)度方案的映射關(guān)系。在MFJSP調(diào)度問題中,一個工件Jj的加工過程由Hj個工序組成,每個工序Pjh可分配到Qjh個可選加工機(jī)器中的某臺機(jī)器上完成。一個調(diào)度方案可以表示為具有N個染色體的染色體鏈,為基因種群中的一個個體。每個染色體對應(yīng)一個工件。每個染色體具有Hj個基因片段。每個基因片段對應(yīng)一個工序?；蚱沃械拿總€基因表示可以完成該工序的候選加工機(jī)器。第j個染色體的第h個基因片段對應(yīng)于第j個工件的第h個工序Pjh。每個基因片段本質(zhì)是一個候選加工機(jī)器集M,它包含對應(yīng)工序的多個候選加工機(jī)器?；蛑禐?時表示選擇由該基因映射的加工機(jī)器來完成與其基因片段相對應(yīng)的工序;基因值為0時表示未選擇該加工機(jī)器。圖1展示了一個MFJSP調(diào)度方案的ECGA基因編碼,其中每個工件的加工被分解為若干個工序,每個工序?qū)?yīng)一個候選加工機(jī)器集。

圖1 基因編碼示意圖

2.2 選擇操作

為了獲得比傳統(tǒng)遺傳算法更好的優(yōu)化效果,在選擇操作中引入伯努利混沌映射公式,如式(12)所示。

(12)

C(t)=int(PS×B(t))+1

(13)

式中:λ為控制參數(shù),PS為種群中的個體總數(shù),B(t)表示第t次迭代后生成的伯努利混沌映射隨機(jī)數(shù),C(t)表示選擇操作種群個體序號,int()為取整函數(shù)。伯努利混沌映射初始值設(shè)置為(0,1)區(qū)間內(nèi)的均勻隨機(jī)數(shù)。

ECGA采用二元隨機(jī)錦標(biāo)賽模式進(jìn)行選擇操作,步驟為:

步驟1:根據(jù)伯努利混沌映射公式生成2個隨機(jī)數(shù),從種群中選擇對應(yīng)序號的2個個體,比較其適應(yīng)度,并將適應(yīng)度最高的個體遺傳給下一代種群;

步驟2:重復(fù)步驟1PS次,獲得下一代種群的PS個個體。

2.3 交叉操作

ECGA引入高斯云模型改進(jìn)交叉算子和變異算子,避免尋優(yōu)過程陷入局部極值,提高算法執(zhí)行效率。高斯云模型促使ECGA早期階段有較大的交叉概率和變異概率來提高精英個體的出現(xiàn)概率,而在ECGA后期階段有較小的交叉概率和變異概率,盡可能保持種群中的精英個體以加快全局收斂速度。交叉概率計算公式為:

(14)

根據(jù)式(14)計算交叉概率Pc并執(zhí)行交叉操作。如圖2所示,ECGA使用切牌式交叉操作,擴(kuò)展搜索空間,提高種群基因的多樣性。切牌式交叉操作時,兩個父代個體沿著位于相同位置的任意相鄰兩個基因片段之間的間隙被分成兩個部分。第1個父代個體的前半部分與第2個父代個體的后半部分依序組合在一起形成新的子代個體;同時第2個父代個體的前半部分與第1個父代個體的后半部分依序組合在一起構(gòu)成另一個新的子代個體。

圖2 切牌式交叉操作

2.4 變異操作

變異概率計算公式為:

(15)

式中:Pm是變異個體的變異概率,Pmmax是種群的最大變異概率,Pmmin是最小變異概率,Φ′是變異個體的適應(yīng)度值,η3和η4是區(qū)間[0,1]中的常數(shù),取η3=0.4,η4=0.8。

根據(jù)式(15)計算變異概率Pm并執(zhí)行變異操作。如圖3所示,ECGA使用兩基因片段式變異操作方法,隨機(jī)選擇父代個體中的兩個基因片段,將所選基因片段中的一個基因編碼置1,其它基因編碼置0,從而產(chǎn)生一個新的子代個體。

圖3 兩基因片段式變異操作

2.5 適應(yīng)度函數(shù)構(gòu)建

ECGA采用加權(quán)相對偏差來評估調(diào)度方案綜合性能,并構(gòu)建適應(yīng)度函數(shù)。加權(quán)相對偏差是所有目標(biāo)函數(shù)相對偏差的加權(quán)和,其計算公式為:

(16)

加權(quán)相對偏差越小,調(diào)度方案綜合調(diào)度質(zhì)量越好。根據(jù)式(16)設(shè)計ECGA適應(yīng)度函數(shù)如下:

(17)

式中:f(j)是種群中第j個個體的適應(yīng)度函數(shù),Γ是足夠大的正數(shù)。適應(yīng)度函數(shù)越大,調(diào)度方案綜合性能越好。

2.6 ECGA算法步驟

ECGA算法流程如圖4所示,具體步驟為:

圖4 ECGA算法流程圖

步驟2:計算種群個體對應(yīng)調(diào)度方案的4個目標(biāo)函數(shù)值:最大完工時間、最大機(jī)器負(fù)荷差、機(jī)器總負(fù)荷和調(diào)度復(fù)雜度;

步驟3:計算種群中所有個體的加權(quán)相對偏差、適應(yīng)度值,并計算最大適應(yīng)度值、最小適應(yīng)度值和平均適應(yīng)度值。判斷每個個體是否滿足約束條件式(1)～式(5),如果滿足約束條件,返回是,否則返回否;

步驟4:將種群中滿足約束條件的每個個體適應(yīng)度值f(j)與全局最優(yōu)適應(yīng)度值f(GOS)進(jìn)行比較。如果f(j)>f(GOS),則用f(j)替換f(GOS),并用第j個個體替換全局最優(yōu)個體GOS,從而得到新的全局最優(yōu)個體和全局最優(yōu)適應(yīng)度值;

步驟5:計算伯努利混沌映射隨機(jī)數(shù),應(yīng)用二元隨機(jī)錦標(biāo)賽模式進(jìn)行選擇操作;計算高斯云模型的期望值、云熵、超熵和標(biāo)準(zhǔn)差,求出不同個體的交叉概率和變異概率,并執(zhí)行切牌式交叉操作和兩基因片段式變異操作;

步驟6:檢查算法是否達(dá)到終止條件。如果進(jìn)化代數(shù)達(dá)到所設(shè)定的最大值或滿足算法的其它結(jié)束條件,則停止算法迭代操作并輸出結(jié)果;否則,轉(zhuǎn)到算法步驟2。

上述算法中,步驟1功能是初始化種群,步驟2計算種群個體對應(yīng)調(diào)度方案的4個目標(biāo)函數(shù)值,其時間復(fù)雜度為T1=O(n);步驟2～步驟6實(shí)現(xiàn)算法循環(huán)迭代,當(dāng)作業(yè)車間調(diào)度規(guī)模足夠大時,忽略其它低次冪項(xiàng)式,可得總的算法時間復(fù)雜度為T2=O(n2)。

3 應(yīng)用案例

以12個工件、3道工序、8臺機(jī)器所構(gòu)成的柔性作業(yè)車間調(diào)度問題M8J12P3[10]為例說明MFJSP模型和ECGA算法應(yīng)用過程。用戶選擇在8臺機(jī)器上加工12個零件,每個工件有3道工序,且需遵循工序先后順序加工。8臺機(jī)器分別表示為M1、M2、M3、…、M8,12個工件加工任務(wù)分別表示為J1、J2、J3、…、J12,Pj,h其表示第j個工件的第h道工序,各工序在機(jī)器上的加工時間(單位:h)如表1所示。

表1 M8J12P3加工參數(shù)表

選用MATLAB R2019a編寫并運(yùn)行ECGA算法程序。設(shè)定最大完工時間閾值PETthreshold為72 h,種群規(guī)模PS為80,最大進(jìn)化代數(shù)MG為300,Г=99。4個目標(biāo)函數(shù)的權(quán)重系數(shù)分別設(shè)置為δ1=δ3=0.3,δ2=δ4=0.2。運(yùn)行ECGA算法程序10次,取其中最優(yōu)調(diào)度方案如圖5所示,其最大完工時間為15 h,最大機(jī)器負(fù)荷差為1 h,機(jī)器總負(fù)荷為113 h,調(diào)度復(fù)雜度為15.928。機(jī)器M1上的加工順序?yàn)?P12,1、P12,2、P4,2、P4,3、P7,3;機(jī)器M2上的加工順序?yàn)?P3,1、P11,2、P8,2、P1,3、P10,3;機(jī)器M3上的加工順序?yàn)?P2,1、P6,1、P11,1、P12,3、P1,2、P10,2;機(jī)器M4上的加工順序?yàn)?P9,1、P5,1、P5,3、P6,3、P8,3;機(jī)器M5上的加工順序?yàn)?P8,1、P6,2、P7,2、P2,3;機(jī)器M6上的加工順序?yàn)?P10,1、P5,2、P9,2、P11,3;機(jī)器M7上的加工順序?yàn)?P4,1、P2,2、P9,3;機(jī)器M8上的加工順序?yàn)?P7,1、P1,1、P3,2、P3,3。

4 算法比較分析

在相同最大進(jìn)化代數(shù)的情況下,將ECGA算法、粒子群優(yōu)化算法(PSO)[15]、人工蜂群算法(ABC)[16]和標(biāo)準(zhǔn)遺傳算法(SGA)[17]用于解決相同的柔性作業(yè)車間調(diào)度問題M8J12P3。SGA算法的參數(shù)設(shè)置與ECGA算法相同:種群規(guī)模為80,最大進(jìn)化代數(shù)為300。PSO算法的參數(shù)設(shè)置如下:粒子群個數(shù)為80個,迭代次數(shù)為300,個體學(xué)習(xí)因子和群體學(xué)習(xí)因子各取值為2,慣性因子取值為0.2。ABC算法的參數(shù)設(shè)置如下:種群規(guī)模為80,迭代次數(shù)為300。上述4種算法各運(yùn)行10次取最優(yōu)值,得到的結(jié)果如表2所示。調(diào)度方案矩陣中第1行～第8行依次表示第1臺～第8臺機(jī)器的加工順序。4種算法所求調(diào)度方案的機(jī)器總負(fù)荷值接近相等。但與SGA、PSO、ABC所求調(diào)度方案相比,ECGA求得的調(diào)度方案具有更小的最大完工時間、最大機(jī)器負(fù)荷差和更好的適應(yīng)度值。與其它3者比較,ECGA所求調(diào)度方案的調(diào)度復(fù)雜度較大,說明在降低調(diào)度方案的最大完工時間和最大機(jī)器負(fù)荷差時,會增大調(diào)度復(fù)雜度。追求最優(yōu)綜合調(diào)度質(zhì)量不可兼得各個單目標(biāo)函數(shù)的最優(yōu)值。實(shí)驗(yàn)結(jié)果表明,對于解決柔性作業(yè)車間調(diào)度問題,ECGA比SGA、PSO和ABC具有更快的收斂速度和更好的全局搜索能力,如圖6所示。ECGA優(yōu)化結(jié)果具有最佳的綜合調(diào)度質(zhì)量,有助于企業(yè)提高生產(chǎn)效率和降低成本。

表2 幾種算法的M8J12P3調(diào)度問題尋優(yōu)結(jié)果比較

圖6 幾種算法的M8J12P3調(diào)度問題尋優(yōu)迭代曲線

5 結(jié)論

研究了多目標(biāo)柔性作業(yè)車間調(diào)度數(shù)學(xué)模型及其求解算法。首先建立了考慮最大完工時間、最大機(jī)器負(fù)荷差、機(jī)器總負(fù)荷和調(diào)度復(fù)雜度的 MFJSP優(yōu)化模型。然后提出一種改進(jìn)的熵增強(qiáng)混沌遺產(chǎn)算法求解MFJSP模型。應(yīng)用伯努利混沌映射改進(jìn)選擇操作,用高斯云模型改進(jìn)變異算子和交叉算子,提高了算法全局尋優(yōu)能力和搜索效率,使用切牌式交叉操作和兩基因片段式變異操作來擴(kuò)展搜索空間,提高種群基因的多樣性,避免了傳統(tǒng)遺傳算法易早熟缺陷。最后以M8J12P3調(diào)度問題為例驗(yàn)證了ECGA算法的有效性。與SGA、PSO和ABC相比,ECGA具有更快的收斂速度和更好的全局搜索能力,有助于企業(yè)獲得綜合調(diào)度質(zhì)量最優(yōu)的車間調(diào)度方案,提高生產(chǎn)效率和降低成本。案例研究結(jié)果顯示在降低調(diào)度方案的最大完工時間和最大機(jī)器負(fù)荷差時,會增大調(diào)度復(fù)雜度,追求最優(yōu)綜合調(diào)度質(zhì)量不可兼得所有單目標(biāo)函數(shù)的最優(yōu)值,說明MFJSP優(yōu)化模型具有重要的應(yīng)用價值。