李永湘,姚錫凡

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

0 引言

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

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

上述研究從不同角度改進(jìn)了遺傳算法的交叉算子和變異算子等,但文獻(xiàn)所提出的交叉算子產(chǎn)生的子代個(gè)體與父代個(gè)體之間相似程度高,全局搜索能力受限,對(duì)多峰函數(shù)易陷入早熟現(xiàn)象;優(yōu)化過程中缺少對(duì)車間物流和調(diào)度復(fù)雜度的考慮等。本文將調(diào)度熵引入MFJSP模型計(jì)算調(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個(gè)工件(J1,J2,J3,…,JN)需在Q臺(tái)機(jī)器(M1,M2,M3,…,MQ)上加工,每個(gè)工件的制造過程包含1道及其以上數(shù)量的工序;各工件的每道工序都有1臺(tái)及其以上數(shù)量的可選加工機(jī)器;每道工序一旦開始加工就不可被中斷;每道工序在不同機(jī)器上的加工時(shí)間可不同;每個(gè)工件的所有工序之間加工順序是固定的;不同的工件之間加工無耦合關(guān)系,相互獨(dú)立,加工優(yōu)先級(jí)相同。因此,MFJSP中主要需考慮工序使用的機(jī)器和不同工件在同一機(jī)器上的加工順序。MFJSP約束關(guān)系數(shù)學(xué)模型表示為:

(1)

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

(2)

(3)

(4)

(5)

(6)

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

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

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

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

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

(7)

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

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

(8)

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

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

(9)

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

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

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

(10)

式中:SEj是第j個(gè)工件生產(chǎn)過程的調(diào)度熵,JSTjk是第j個(gè)工件在第k個(gè)狀態(tài)下的持續(xù)時(shí)間,工件的狀態(tài)主要包括從第一道工序開始至最后一道工序結(jié)束期間該工件的所有工序加工狀態(tài)和相鄰兩個(gè)工序之間的等待狀態(tài);JMTj是第j個(gè)工件從第一道工序開始至最后一道工序結(jié)束所用的總時(shí)間,SNj是第j個(gè)工件從第一道工序開始至最后一道工序結(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ù)雜度最小值計(jì)算公式為:

(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)度問題中,一個(gè)工件Jj的加工過程由Hj個(gè)工序組成,每個(gè)工序Pjh可分配到Qjh個(gè)可選加工機(jī)器中的某臺(tái)機(jī)器上完成。一個(gè)調(diào)度方案可以表示為具有N個(gè)染色體的染色體鏈,為基因種群中的一個(gè)個(gè)體。每個(gè)染色體對(duì)應(yīng)一個(gè)工件。每個(gè)染色體具有Hj個(gè)基因片段。每個(gè)基因片段對(duì)應(yīng)一個(gè)工序?；蚱沃械拿總€(gè)基因表示可以完成該工序的候選加工機(jī)器。第j個(gè)染色體的第h個(gè)基因片段對(duì)應(yīng)于第j個(gè)工件的第h個(gè)工序Pjh。每個(gè)基因片段本質(zhì)是一個(gè)候選加工機(jī)器集M,它包含對(duì)應(yīng)工序的多個(gè)候選加工機(jī)器?；蛑禐?時(shí)表示選擇由該基因映射的加工機(jī)器來完成與其基因片段相對(duì)應(yīng)的工序;基因值為0時(shí)表示未選擇該加工機(jī)器。圖1展示了一個(gè)MFJSP調(diào)度方案的ECGA基因編碼,其中每個(gè)工件的加工被分解為若干個(gè)工序,每個(gè)工序?qū)?yīng)一個(gè)候選加工機(jī)器集。

圖1 基因編碼示意圖

2.2 選擇操作

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

(12)

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

(13)

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

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

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

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

2.3 交叉操作

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

(14)

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

圖2 切牌式交叉操作

2.4 變異操作

變異概率計(jì)算公式為:

(15)

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

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

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

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

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

(16)

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

(17)

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

2.6 ECGA算法步驟

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

圖4 ECGA算法流程圖

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

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

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

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

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

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

3 應(yīng)用案例

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

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

選用MATLAB R2019a編寫并運(yùn)行ECGA算法程序。設(shè)定最大完工時(shí)間閾值PETthreshold為72 h,種群規(guī)模PS為80,最大進(jìn)化代數(shù)MG為300,Г=99。4個(gè)目標(biāo)函數(shù)的權(quán)重系數(shù)分別設(shè)置為δ1=δ3=0.3,δ2=δ4=0.2。運(yùn)行ECGA算法程序10次,取其中最優(yōu)調(diào)度方案如圖5所示,其最大完工時(shí)間為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è)置如下:粒子群個(gè)數(shù)為80個(gè),迭代次數(shù)為300,個(gè)體學(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臺(tái)～第8臺(tái)機(jī)器的加工順序。4種算法所求調(diào)度方案的機(jī)器總負(fù)荷值接近相等。但與SGA、PSO、ABC所求調(diào)度方案相比,ECGA求得的調(diào)度方案具有更小的最大完工時(shí)間、最大機(jī)器負(fù)荷差和更好的適應(yīng)度值。與其它3者比較,ECGA所求調(diào)度方案的調(diào)度復(fù)雜度較大,說明在降低調(diào)度方案的最大完工時(shí)間和最大機(jī)器負(fù)荷差時(shí),會(huì)增大調(diào)度復(fù)雜度。追求最優(yōu)綜合調(diào)度質(zhì)量不可兼得各個(gè)單目標(biāo)函數(shù)的最優(yōu)值。實(shí)驗(yàn)結(jié)果表明,對(duì)于解決柔性作業(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é)模型及其求解算法。首先建立了考慮最大完工時(shí)間、最大機(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)度方案的最大完工時(shí)間和最大機(jī)器負(fù)荷差時(shí),會(huì)增大調(diào)度復(fù)雜度,追求最優(yōu)綜合調(diào)度質(zhì)量不可兼得所有單目標(biāo)函數(shù)的最優(yōu)值,說明MFJSP優(yōu)化模型具有重要的應(yīng)用價(jià)值。