改進遺傳算法解決帶有機器惡化效應的柔性作業(yè)車間調度問題

安璐,張鵬,聶宇晨

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

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

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

1 問題描述及模型建立

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

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

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

決策變量說明：

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

(1)

(2)最小化總成本

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

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

(4)

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

對于客戶滿意度，本文主要研究交貨期的問題，當工件提前完工時，會存在存儲，即會產(chǎn)生懲罰成本；當在交貨期內進行完工時，既提高了客戶滿意度，也未增加倉儲成本，但當不屬于交貨期窗口中時，則產(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)表示目標函數(shù)為最小化最大完工時間；式(4)表示目標函數(shù)為最小化總成本；式(5)表示目標函數(shù)為最大化滿意度；式(6)為約束，同一工件的工序具有前后順序約束；式(7)表明同一時刻，一個工件的一道工序只能在一臺機器上加工；式(8)表明同一時刻，同一機器上只能加工一個工件的一道工序.

2 算法求解

對于多目標的柔性作業(yè)車間調度問題研究，確立了權重系數(shù)，利用多目標具體的權重系數(shù)，將多目標問題轉化為單目標問題，即其公式可以表達為：

(9)

2.1 適應度計算操作

此處適應度計算引入了模擬退火算法，利用其概率突跳特性，適當?shù)卦黾訉τ诹咏獾慕邮埽鰪娏怂惴ǖ娜炙阉髂芰?

2.2 改進交叉、變異操作

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

改進的交叉算子如下：

改進的變異算子如下：

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

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

2.3 選擇操作

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

IGSA步驟如下：

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

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

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

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

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

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

3 仿真實驗及分析

以6×6的FJSP為例，使用IGSA進行橫向對比.

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

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

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

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

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

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

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

表1 不同算法的Kacem算例結果比較

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

4 結論

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