改進(jìn)遺傳算法解決帶有機(jī)器惡化效應(yīng)的柔性作業(yè)車間調(diào)度問題

安璐,張鵬,聶宇晨

(1.大連交通大學(xué) 軟件學(xué)院，遼寧 大連 116054;2.大連交通大學(xué) 創(chuàng)新創(chuàng)業(yè)教育學(xué)院，遼寧 大連 116028)*

柔性車間調(diào)度問題FJSP是經(jīng)典車間調(diào)度問題JSP的一種擴(kuò)展，是一種更復(fù)雜的NP難的問題.自從1990年Bucker首次提出FJSP概念之后[1]，大量智能優(yōu)化算法被應(yīng)用于解決此問題.當(dāng)然，由于遺傳算法的全局搜索能力較強(qiáng)的優(yōu)點(diǎn)，所以更被廣泛應(yīng)用于解決各種關(guān)于調(diào)度的問題.寧濤等[2]引入了MAGTD(多指標(biāo)加權(quán)灰靶決策模型)的基于混沌理論的量子粒子群算法來求解多目標(biāo)FJSP，使用算例驗(yàn)證算法的實(shí)用性；肖華軍等[3]提出了一種將化學(xué)反應(yīng)和禁忌搜索算法相結(jié)合的混合算法求解多目標(biāo)FJSP；姜天華等[4]提出了一種引入交叉和變異的基于變鄰域搜索的混合灰狼優(yōu)化算法求解多目標(biāo)FJSP；張垚等[5]提出了一種新型遺傳鄰域萬有引力算法，借鑒歐氏距離的染色體差距的概念和慣性質(zhì)量概念解決作業(yè)車間調(diào)度；翟所霞等[6]通過改進(jìn)自適應(yīng)遺傳算法的集成調(diào)度方法來求解柔性作業(yè)車間調(diào)度和動(dòng)態(tài)調(diào)度問題，并對(duì)緊急訂單插入和機(jī)器發(fā)生故障進(jìn)行重調(diào)度；付亞平等[7]針對(duì)帶有交貨期的FJSP問題，提出了一種使用三種不同鄰域模式的搜索方法的自適應(yīng)離散貓群優(yōu)化算法解決；曹如勝等[8]使用具有特定鄰域函數(shù)和多樣化結(jié)構(gòu)的禁忌搜索算法解決了具有序列依賴性的柔性作業(yè)車間調(diào)度問題；寧濤等[9]提出了一種從一維到三維的解碼方法的遺傳方法GA_JS來解決分布式FJSP；楊宇琪等[10]提出了一種新的免疫多智能體調(diào)度系統(tǒng)(NIMASS)來解決以完工時(shí)間為目標(biāo)的FJSP.

經(jīng)過前面研究可以發(fā)現(xiàn)，現(xiàn)在對(duì)于考慮機(jī)器惡化效應(yīng)的FJSP還是相對(duì)較少.因此，本文研究針對(duì)柔性作業(yè)生產(chǎn)調(diào)度過程中的關(guān)于機(jī)器的惡化效應(yīng)，以客戶滿意度，最大完工時(shí)間，總成本為多目標(biāo)，建立考慮機(jī)器惡化效應(yīng)的FJSP模型，在基本的GSA的基礎(chǔ)上[11]，使用一種IGSA進(jìn)行求解.

1 問題描述及模型建立

考慮機(jī)器惡化效應(yīng)的FJSP作為最符合實(shí)際生產(chǎn)需求的車間調(diào)度，是一個(gè)典型的NP難問題.本文從企業(yè)的角度，研究了多目標(biāo)FJSP，以最小化最大完工時(shí)間，最小總成本以及最大化客戶滿意度為目標(biāo)，建立了多目標(biāo)的考慮機(jī)器惡化效應(yīng)的FJSP模型.最小化完工時(shí)間有利于提高設(shè)備利用率，最小化成本有利于企業(yè)的最大利益，而客戶滿意度有利于企業(yè)聲譽(yù).多目標(biāo)FJSP描述如下：n個(gè)工件在m臺(tái)機(jī)器上加工，每個(gè)工件包含至少一道工序，每道工序可在可選機(jī)器集中任選一臺(tái)進(jìn)行加工，每臺(tái)機(jī)器上可以加工多道工序，工序在不同機(jī)器上加工時(shí)間不同.考慮機(jī)器惡化效應(yīng)的FJSP問題的約束：①同一時(shí)刻，每臺(tái)機(jī)器只能加工一個(gè)工件的一道工序;②同一時(shí)刻，一個(gè)工件的一道工序只能在一臺(tái)機(jī)器上加工;③同一工件中工序有先后順序約束;④各個(gè)工件加工優(yōu)先級(jí)相同且都在零時(shí)刻處于可用狀態(tài).

模型的參數(shù)說明及決策變量說明如下：

參數(shù)說明：工件集合為J={1,2,…，n}，n為工件數(shù)；機(jī)器集合為M={1,2,…，m},m為機(jī)器數(shù)；Oij為工件j的第i道工序；Mij為工序Oij的可選機(jī)器集；ni為 工件i的工序數(shù)；Rij為工件j的第i道工序的完工時(shí)間；mijk為工件j的第i道工序的可選機(jī)器集；Sijk為工件j的第i道工序在機(jī)器k上的開始加工時(shí)間；Eijk為機(jī)器惡化時(shí)工件j的第i道工序在機(jī)器k上的完工時(shí)間；Rijk為工件j的第i道工序是否在機(jī)器k上加工；Tijk為靜態(tài)環(huán)境下工件j的第i道工序在機(jī)器k的加工時(shí)間；Ci為工件i的完工時(shí)間；?k為機(jī)器k的惡化效應(yīng)；?ij為工件j在機(jī)器i上的惡化系數(shù)；Uk為機(jī)器k的使用時(shí)間；Ak為機(jī)器k的機(jī)齡；[Tj,T2j]為工件j的交貨期窗口；T1j={0,Cj-Tj}為工件j的拖期時(shí)間；Ej={0,Tj-Cj}為工件j的提早時(shí)間；tj為工件j單位時(shí)間內(nèi)的拖期懲罰成本；ej為工件j單位時(shí)間內(nèi)的倉(cāng)儲(chǔ)成本；pijk為工件j第i道工序在機(jī)器k單位時(shí)間內(nèi)加工成本.

決策變量說明：

(1)最小化最大完工時(shí)間f1

(1)

(2)最小化總成本

總成本主要包括加工成本和交貨期早期/拖期成本懲罰和.

機(jī)器惡化系數(shù)為機(jī)器使用時(shí)間與機(jī)齡之比

(4)

(3)最大化客戶滿意度f3

對(duì)于客戶滿意度，本文主要研究交貨期的問題，當(dāng)工件提前完工時(shí)，會(huì)存在存儲(chǔ)，即會(huì)產(chǎn)生懲罰成本；當(dāng)在交貨期內(nèi)進(jìn)行完工時(shí)，既提高了客戶滿意度，也未增加倉(cāng)儲(chǔ)成本，但當(dāng)不屬于交貨期窗口中時(shí)，則產(chǎn)生拖期懲罰成本，然后根據(jù)拖期懲罰成本來衡量客戶滿意度.衡量公式如下：

(5)

變量約束：s.t

Eijk≤S(i+1)jkj=1,…,n，

i=1,…,nj-1，k=1,…,m

(6)

k=1,…,m

(7)

if?Rijk=1,Rxyz≠1,j≠yori≠x

(8)

式(1)～式(3)表示目標(biāo)函數(shù)為最小化最大完工時(shí)間；式(4)表示目標(biāo)函數(shù)為最小化總成本；式(5)表示目標(biāo)函數(shù)為最大化滿意度；式(6)為約束，同一工件的工序具有前后順序約束；式(7)表明同一時(shí)刻，一個(gè)工件的一道工序只能在一臺(tái)機(jī)器上加工；式(8)表明同一時(shí)刻，同一機(jī)器上只能加工一個(gè)工件的一道工序.

2 算法求解

對(duì)于多目標(biāo)的柔性作業(yè)車間調(diào)度問題研究，確立了權(quán)重系數(shù)，利用多目標(biāo)具體的權(quán)重系數(shù)，將多目標(biāo)問題轉(zhuǎn)化為單目標(biāo)問題，即其公式可以表達(dá)為：

(9)

2.1 適應(yīng)度計(jì)算操作

此處適應(yīng)度計(jì)算引入了模擬退火算法，利用其概率突跳特性，適當(dāng)?shù)卦黾訉?duì)于劣解的接受，增強(qiáng)了算法的全局搜索能力.

2.2 改進(jìn)交叉、變異操作

交叉操作兩交叉?zhèn)€體加入相似度閾值，利用海明相似度，設(shè)定相似度閾值來考慮是否要進(jìn)行交叉操作，如果相似度小于相似度閾值，不進(jìn)行交叉操作，這樣可以加快算法運(yùn)行速率，然后加入正態(tài)云模型，利用其云滴的隨機(jī)性和穩(wěn)定傾向性，使用X云條件發(fā)生器根據(jù)種群的適應(yīng)度進(jìn)行自適應(yīng)產(chǎn)生交叉、變異概率，彌補(bǔ)了傳統(tǒng)的自適應(yīng)算法易陷入局部最優(yōu)的缺陷，然后根據(jù)其交叉、變異概率，在進(jìn)行交叉、變異操作.

改進(jìn)的交叉算子如下：

改進(jìn)的變異算子如下：

其中，t1,t2,t3,t4為常數(shù)，F(xiàn)v為種群的平均適應(yīng)度值，f=max(fa,fb)，f為兩交叉?zhèn)€體中適應(yīng)度值較大者；Ex=(fa+fb)/2，Ex為兩交叉?zhèn)€體的均值，En=(Fmax-Ex)/C1，En為熵，是不確定性度量，C1為控制參數(shù)，F(xiàn)max,Fmin分別為適應(yīng)度的最大值和最小值；He為熵的不確定性度量，He=En/C2，C2為控制參數(shù)，En1是以En為期望，以He為標(biāo)準(zhǔn)差的正態(tài)隨機(jī)數(shù).

正態(tài)云模型中，參數(shù)Ex，En分別表示云模型的水平位置和陡峭程度，且He和云滴的離散程度呈正比，確定度與之呈反比，即He越大，離散程度越大，確定度越小.根據(jù)“3En”規(guī)則，進(jìn)行設(shè)置t1-t4為0-1的常數(shù)，且根據(jù)本文的設(shè)置，t1=t2=0.8，t3=t4=0.6，而C1是控制云模型的陡峭程度，設(shè)定為3會(huì)比較好，C2控制云層的厚度，設(shè)定為10比較適宜[12].

2.3 選擇操作

使用遺傳算法中常用的輪盤賭和精英保留策略相結(jié)合的方式，輪盤賭選擇最好的染色體，通過適應(yīng)度值在種群總的適應(yīng)度值占的比例進(jìn)行選擇操作，通過目標(biāo)函數(shù)的約束，找到最優(yōu)解，同時(shí)使用精英保留策略，把適應(yīng)度較好的染色體保留下來，方便尋找最優(yōu)解.

IGSA步驟如下：

步驟1：種群初始化，隨機(jī)生成規(guī)模為n的初始種群.

步驟2：計(jì)算初始種群中每個(gè)個(gè)體的適應(yīng)度值，引入模擬退火算法，利用其概率突跳性，跳出局部最優(yōu)解，加強(qiáng)了得到全局最優(yōu)解的可能.

步驟3：交叉，先判斷兩交叉?zhèn)€體相似度之差，若相差小于相似度閾值，不使用交叉操作，因?yàn)樾庐a(chǎn)生個(gè)體與原始個(gè)體相差不大；否則，使用正態(tài)云發(fā)生器自適應(yīng)產(chǎn)生交叉概率.

步驟4：變異，使用正態(tài)云發(fā)生器自適應(yīng)產(chǎn)生變異概率.

步驟5：選擇，使用輪盤賭方法和精英保留策略相結(jié)合的方式選擇.

步驟6：判斷是否滿足終止條件，如果滿足，輸出；不滿足，轉(zhuǎn)步驟2.

3 仿真實(shí)驗(yàn)及分析

以6×6的FJSP為例，使用IGSA進(jìn)行橫向?qū)Ρ?

遺傳算法參數(shù)設(shè)置如下：

種群初始規(guī)模NIND=40，種群最大進(jìn)化代數(shù)MAXGEN=50，交叉概率Pc=0.8，變異概率Pm=0.6,目標(biāo)函數(shù)最小完成時(shí)間，最小成本和最大滿意度，根據(jù)設(shè)置的權(quán)重系數(shù)分別為0.5,0.2，0.3，進(jìn)行集成調(diào)度.根據(jù)所設(shè)置的參數(shù)，分 別 基于GSA和IGSA對(duì)上述實(shí)例進(jìn)行仿真，經(jīng)過matlab仿真多次得到結(jié)果圖如圖1、圖2.

圖2對(duì)圖1進(jìn)行了改進(jìn)，改進(jìn)交叉操作，設(shè)置交叉位置和標(biāo)準(zhǔn)位置，增加了全局搜索能力，由圖中GSA和IGSA的對(duì)比可知，IGSA得到的最優(yōu)解更好.交叉操作加入海明相似度，進(jìn)行相似度對(duì)比，增加了算法的收斂速度和運(yùn)行效率，由上圖可知，IGSA增加了算法的收斂速度和運(yùn)行效率.

改變一下初始的遺傳算法參數(shù)設(shè)置，將種群初始規(guī)模NIND=100,最大進(jìn)化代數(shù)MAXGEN=100,在進(jìn)行仿真實(shí)驗(yàn)，測(cè)試改進(jìn)云自適應(yīng)遺傳退火算法的有效性，如圖3、圖4.

改進(jìn)初始參數(shù)后，IGSA的最優(yōu)解，收斂速度，運(yùn)行效率比GSA更好.

為驗(yàn)證本文所提出的帶有機(jī)器惡化效應(yīng)的柔性作業(yè)車間調(diào)度管理方法，選擇經(jīng)典的Kacem[13]算例，在Matlab7.0 支持環(huán)境下用IGSA算法針對(duì)兩種規(guī)模的標(biāo)準(zhǔn)問題(4工件×6機(jī)器、8工件×8機(jī)器)獨(dú)立執(zhí)行30次，同時(shí)與已普遍使用的HS[14]、DCSO[15]和AIA[16]算法進(jìn)行對(duì)比分析，從而檢驗(yàn)所提出方法的有效性.

表1中S1、S2、S3和S4分別表示算法獲得的不同解；Vbest表示機(jī)器的最大完工時(shí)間最優(yōu)解；Vavg表示進(jìn)行十次調(diào)度后的平均解；Time表示調(diào)度時(shí)間(單位：min).使用不同算法求解Kacem算例的結(jié)果如表1所示，可以看出本文提出的IGSA不但能獲得更多的非支配解(Pareto最優(yōu)解)，而且在算例中都能獲得當(dāng)前最優(yōu)解.同等參數(shù)下，IGSA有更強(qiáng)的尋優(yōu)能力.以8×8問題為例，雖然AIA算法和IGSA算法均獲得了2個(gè)非支配解，但是AIA算法獲得的解(8,44,7)被IGSA算法獲得的解(8,43,7) 所支配，QPSO算法獲得的解(10,42,8)被IQBFO算法獲得的解(9,42,7)所支配.

表1 不同算法的Kacem算例結(jié)果比較

由表1可以看出，本文算法與其他算法相比有一定優(yōu)勢(shì)，在Kacem基準(zhǔn)測(cè)試用例4×6中，與改進(jìn)后的HS對(duì)比，最優(yōu)解和平均解都要優(yōu)于改進(jìn)后的HS；在Kacem基準(zhǔn)測(cè)試用例8×8中，與改進(jìn)后的HS對(duì)比，其平均解與它相差不大，而與DCSO對(duì)比，其運(yùn)行速度比其更優(yōu).由此測(cè)試可得到本文算法對(duì)于FJSP的可行性.

4 結(jié)論

通過上述仿真實(shí)驗(yàn)可知，本次設(shè)計(jì)的遺傳算法相比于傳統(tǒng)的遺傳算法來說，更能加快收斂速度，收斂到最優(yōu)解，加入海明相似度，進(jìn)行相似度閾值比較，更能加快算法運(yùn)行效率，同時(shí)利用正態(tài)云模型其云滴的隨機(jī)性和穩(wěn)定傾向性，使用X條件云發(fā)生器自適應(yīng)產(chǎn)生交叉和變異概率，同時(shí)利用模擬退火算法的概率突跳性，使其能跳出局部最優(yōu)，找到全局最優(yōu)解，同時(shí)也避免了傳統(tǒng)遺傳算法易早熟收斂這一缺點(diǎn)，但是此算法針對(duì)小規(guī)模的FJSP會(huì)更好.