基于多種群遺傳算法與Plant Simulation的車間調(diào)度優(yōu)化

代禮奇，彭 可，崔 焱，劉 明

（湖南師范大學(xué) 工程與設(shè)計(jì)學(xué)院，湖南 長(zhǎng)沙 410081）

1 引言

隨著硬質(zhì)合金在現(xiàn)代工業(yè)中的廣泛應(yīng)用，對(duì)其混合料的質(zhì)量要求也越來(lái)越高。該生產(chǎn)線引進(jìn)的濕磨-噴霧干燥生產(chǎn)工藝滿足該質(zhì)量要求，但其設(shè)備多且復(fù)雜，按經(jīng)驗(yàn)進(jìn)行生產(chǎn)排產(chǎn)效率低下。因而需要一種科學(xué)的排產(chǎn)方法對(duì)該類多工序、多設(shè)備的生產(chǎn)線進(jìn)行合理排產(chǎn)。

硬質(zhì)合金混合料生產(chǎn)線調(diào)度問(wèn)題作為典型的混合流水車間調(diào)度問(wèn)題（HFSP），當(dāng)其工件種類、工序、設(shè)備數(shù)較少時(shí)，可用分支定界和線性規(guī)劃等精確方法求出最優(yōu)解；而當(dāng)其生產(chǎn)規(guī)模擴(kuò)大時(shí)，解空間會(huì)呈爆炸式增長(zhǎng)，精確求解方法很難在合理的時(shí)間內(nèi)求出最優(yōu)解。而以遺傳算法、模擬退火算法、禁忌搜索算法等為代表的啟發(fā)式算法，以其能在合理的計(jì)算時(shí)間內(nèi)求出高質(zhì)量的解的特點(diǎn)而被廣泛應(yīng)用于求解HFSP問(wèn)題。軒華等改變初始種群、交叉概率和變異概率提出一種防止陷入局部最優(yōu)的自適應(yīng)混合遺傳算法求解帶機(jī)器阻塞約束的HFSP問(wèn)題。耿凱峰等改進(jìn)編碼方式、交叉和變異算子提出一種改進(jìn)Memtic算法用于求解帶工序跳躍的綠色混合流水車間。孟磊磊等提出一種改進(jìn)的回溯搜索算法求解帶阻塞約束的不相關(guān)并行機(jī)HFSP問(wèn)題。鄭旭[設(shè)計(jì)兩種不同編碼方式的蟻群優(yōu)化算法求解考慮阻塞時(shí)間和工件差異約束的HFSP問(wèn)題。袁慶欣等分別采用NSGA-Ⅱ、NSGA-Ⅲ算法求解考慮有限緩沖區(qū)約束的HFSP問(wèn)題?，F(xiàn)有文獻(xiàn)的研究，對(duì)傳統(tǒng)啟發(fā)式算法的全局搜索能力進(jìn)行了改善，且在傳統(tǒng)HFSP問(wèn)題中加入了與實(shí)際車間更貼合的約束條件。最后，基于算例對(duì)算法的有效性進(jìn)行驗(yàn)證。

綜上，目前關(guān)于生產(chǎn)調(diào)度優(yōu)化的文獻(xiàn)對(duì)優(yōu)化后的方案僅在數(shù)值上進(jìn)行了驗(yàn)證。本文基于上述研究思路，提出一種多種群遺傳算法對(duì)該硬質(zhì)合金生產(chǎn)線進(jìn)行優(yōu)化，并引入Plant Simulation生產(chǎn)線仿真平臺(tái)對(duì)上述優(yōu)化方案進(jìn)行更實(shí)際地驗(yàn)證。

2 問(wèn)題描述

HFSP問(wèn)題可以描述為：n個(gè)工件在s（s≥2）道工序上連續(xù)加工，工序j含有m（m>0；j=1，2，…，s）臺(tái)設(shè)備，生產(chǎn)線共有m臺(tái)設(shè)備，且至少存在一個(gè)工序有多臺(tái)設(shè)備。因而，HFSP問(wèn)題通過(guò)改變工件加工順序及各工件設(shè)備分配來(lái)優(yōu)化。

2.1 車間加工情況描述

硬質(zhì)合金混合料生產(chǎn)線包含配粉、球磨、干燥三道工序，各工序中分別包含4臺(tái)、16臺(tái)、4臺(tái)設(shè)備，工序間通過(guò)AGV小車進(jìn)行物料運(yùn)輸。對(duì)該生產(chǎn)線作業(yè)調(diào)度問(wèn)題有如下描述：一批料24個(gè)工件分別要依次在3個(gè)工序上的一臺(tái)設(shè)備上完成加工，各工序加工時(shí)間及工序間AGV路線已知。由于設(shè)備加工時(shí)間較長(zhǎng)，同一批料出料時(shí)間相對(duì)比較集中，且同一工序的各設(shè)備加工時(shí)長(zhǎng)因運(yùn)輸距離及設(shè)備型號(hào)等因素有明顯差距。因此，調(diào)整三道工序中設(shè)備的使用順序，可有效提高該生產(chǎn)線的生產(chǎn)效率。該生產(chǎn)線生產(chǎn)流程示意圖如圖1所示。并對(duì)其約束條件做出如下假設(shè)。

圖1 硬質(zhì)合金混合料生產(chǎn)線生產(chǎn)流程示意圖

1）生產(chǎn)線各設(shè)備布局已確定，各設(shè)備間AGV的移動(dòng)路線確定且唯一。

2）各工序間物料運(yùn)輸?shù)腁GV型號(hào)相同，且執(zhí)行任務(wù)期間不能被其他任務(wù)打斷。

3）每個(gè)工件都要固定加工要求依次完成所有工序，完成每個(gè)工序時(shí)在該工序內(nèi)任一設(shè)備上完成即可。

4）每個(gè)工件都有固定的加工順序，不能任意打亂加工順序。

5）每臺(tái)設(shè)備同一時(shí)刻只能處理一個(gè)工件。

6）加工工藝要求不同工件在同一設(shè)備上的加工時(shí)間相同。

7）為方便計(jì)算，各設(shè)備加工時(shí)長(zhǎng)包括該設(shè)備加工基本時(shí)長(zhǎng)、AGV送料運(yùn)輸時(shí)長(zhǎng)、人工裝卸料時(shí)長(zhǎng)以及清洗攪拌等輔助工序時(shí)長(zhǎng)。

2.2 調(diào)度問(wèn)題建模

為方便后續(xù)描述，對(duì)以下參數(shù)進(jìn)行符號(hào)定義。

i：各加工工件序號(hào)；I：工件集；n：工件總數(shù)；j：工序序號(hào)；s：工序數(shù)；J：工序序號(hào)；O：工件i的第j道工序；k：設(shè)備序號(hào)；m：設(shè)備總數(shù)；m：工序j的設(shè)備數(shù)；K：車間設(shè)備集；K：工序j的設(shè)備集；M：值為無(wú)窮大的實(shí)數(shù)；P：工件i在設(shè)備k上的加工時(shí)間；B：工件i在設(shè)備k上開(kāi)始加工時(shí)間；E：工件i在設(shè)備k上加工完成時(shí)間。

優(yōu)化目標(biāo)函數(shù)為最小化最大加工完成時(shí)間為f=min（Emax）；約束條件為

式(3)表示同一工件在同一工序某一臺(tái)設(shè)備上加工即可；式(4)和式(5)表示每個(gè)工件都要依次完成s道工序；式(6)表示每個(gè)設(shè)備只能完成某一種工序；式(7)表示工件i在設(shè)備k上加工完成時(shí)間為開(kāi)始加工時(shí)間與加工時(shí)間之和；式(8)表示最大完工時(shí)間應(yīng)不小于任意工件的完工時(shí)間；式(9)表示不同工件在同一設(shè)備上的加工時(shí)間相同；式(10)表示考慮阻塞時(shí)設(shè)備k同一時(shí)刻只能處理一個(gè)工件。

3 算法設(shè)計(jì)

傳統(tǒng)遺傳算法的主要實(shí)現(xiàn)步驟為染色體編碼、種群初始化、設(shè)置適應(yīng)度函數(shù)、選擇、交叉、變異等算子，重復(fù)選擇、交叉、變異直至滿足終止條件后輸出結(jié)果。為改善遺傳算法的搜索鄰域，本文在傳統(tǒng)遺傳算法基礎(chǔ)上提出一種引入精英種群、移民算子和人工選擇算子的多種群遺傳算法，各種群間采用不同交叉概率和變異概率進(jìn)行協(xié)同進(jìn)化。

3.1 染色體編碼

遺傳算法的染色體編碼方式可以分為二進(jìn)制編碼、浮點(diǎn)編碼、符號(hào)編碼以及多參數(shù)級(jí)聯(lián)編碼等。本文以三道工序中的設(shè)備使用順序?yàn)闆Q策變量，各設(shè)備只能完成某一道工序。因此，本文采用多染色體實(shí)數(shù)編碼，即每個(gè)個(gè)體有三條染色體，分別代表配粉工序、球磨工序、干燥工序的設(shè)備投產(chǎn)順序。三道工序共24臺(tái)設(shè)備，具體編碼見(jiàn)表1。各工序編碼順序是按各設(shè)備在同工序設(shè)備中加工時(shí)間進(jìn)行遞增排列，即加工時(shí)長(zhǎng)越小，編碼號(hào)越小。

表1 三道工序編碼

每個(gè)工件都要依次在配粉、球磨、干燥工序上任選一臺(tái)設(shè)備上進(jìn)行加工。默認(rèn)經(jīng)驗(yàn)排產(chǎn)是按加工時(shí)長(zhǎng)優(yōu)先排時(shí)長(zhǎng)小的設(shè)備。實(shí)際生產(chǎn)按默認(rèn)經(jīng)驗(yàn)順序進(jìn)行排產(chǎn)，第一個(gè)工件加工設(shè)備依次為配粉工位1-球磨機(jī)1-噴霧干燥塔1，第二個(gè)工件加工設(shè)備依次為配粉工位2-球磨機(jī)2-噴霧干燥塔2，依次類推。以經(jīng)驗(yàn)排產(chǎn)方案為例，該方案編碼后對(duì)應(yīng)的三條染色體分別為[1,2,3,4]，[5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]，[21,22,23,24]。

3.2 種群初始化

初始化是遺傳算法中的關(guān)鍵一步，初始種群的質(zhì)量對(duì)遺傳算法在整個(gè)搜索空間中的搜索速度與質(zhì)量有著十分重要的關(guān)系。已有研究通常采用隨機(jī)或其他單一初始化的方法，因而所得到的解的質(zhì)量偏低。本文提出改進(jìn)多種群遺傳算法在產(chǎn)生初始種群時(shí)引入多個(gè)初始種群同時(shí)進(jìn)行優(yōu)化搜索，各初始種群間通過(guò)移民算子通信，從而實(shí)現(xiàn)多種群的協(xié)同進(jìn)化，得到各種群進(jìn)化的綜合結(jié)果。

3.3 適應(yīng)度函數(shù)

遺傳算法中適應(yīng)度函數(shù)是用來(lái)判別各基因遺傳到下一代的概率。如何使適應(yīng)度函數(shù)與求解對(duì)象有效匹配是檢驗(yàn)遺傳算法有效性的關(guān)鍵。本案例求解目的是一批工件總完成時(shí)間T的最小值，故以一批工件總完工時(shí)間T的倒數(shù)作為適應(yīng)度函數(shù)。T的計(jì)算公式為

式中，n為一批工件包含的工件數(shù)；T表示加工完工件i所需要的時(shí)間；t表示在加工工件i時(shí)，工件i+1已完成任務(wù)所節(jié)省的時(shí)間。

適應(yīng)度函數(shù)可以表示為

3.4 選擇算子

選擇算子是實(shí)現(xiàn)遺傳思想“適者生存”的核心步驟，本文案例中選擇算子采用輪盤賭選擇。輪盤賭選擇又稱為比例選擇方法，其基本思想是：各個(gè)個(gè)體被選中的概率與其適應(yīng)度大小成正比，即適應(yīng)度值越大的個(gè)體越容易被選中，對(duì)應(yīng)到本文案例中一批工件總完工時(shí)間T越小的基因組越容易被選中。其具體操作過(guò)程為∑f

1）計(jì)算整個(gè)群體中每個(gè)個(gè)體的適應(yīng)度，并將群里中所有個(gè)體的適應(yīng)度累加求和得到適應(yīng)度總和。

2）計(jì)算出群體中各個(gè)個(gè)體的相對(duì)適應(yīng)度f(wàn)/∑f，該相對(duì)適應(yīng)度值即為該個(gè)體遺傳到下一代群體的概率。

3.5 交叉算子

交叉運(yùn)算為遺傳算法中產(chǎn)生新個(gè)體的基本操作過(guò)程，指以一定的概率將一對(duì)父代基因的部分結(jié)構(gòu)互相替換重組生成一對(duì)新的子代基因的操作。由于實(shí)數(shù)編碼方式染色體上每個(gè)基因的唯一性，若采用簡(jiǎn)單交叉方式，會(huì)出現(xiàn)非法解。如一對(duì)父代染色體[1,2,3,4]，[2,3,4,1]，以單點(diǎn)交叉為例，交換后面兩個(gè)基因，得到子代為[1,2,4,1]，[2,3,3,4]。兩個(gè)子代中都有兩個(gè)相同設(shè)備，與該染色體實(shí)際意義沖突。為避免染色體交叉產(chǎn)生非法解，本案例采用基于位置的交叉（Position-based Crossover，PBX）。其具體操作步驟為

1）隨機(jī)選擇一條父代染色體中的幾個(gè)基因，選擇的基因可不連續(xù)；

2）生成一條子代染色體，使該染色體與1）中所述父代染色體選中位置基因相同；

3）先找出1）中選中基因在另一條父代染色體上的位置，再將其余基因按順序放入上一步生成的子代中得到一條子代染色體；

4）選擇另一條父代染色體重復(fù)以上步驟得到第二條子代染色體。

以球磨工序的染色體為例，其交叉操作過(guò)程如圖2所示。

圖2 PBX具體操作示意圖

3.6 變異算子

在遺傳算法中，變異算子的基本內(nèi)容是指對(duì)群體P（t）中的每一個(gè)個(gè)體，以某一概率改變某一個(gè)或某一些基因座上的基因值為其他的等位基因。常用操作方法有均勻變異、邊界變異、高斯變異、非均勻變異以及互聯(lián)變異等。本文中案例采用互聯(lián)變異方法，即先在父代染色體中隨機(jī)選擇兩個(gè)基因，再交換其位置得到子代染色體。如父代染色體為[1,2,3,4]，隨機(jī)選擇基因2、4，得到新的子代染色體為[1,4,3,2]。

3.7 移民算子與人工選擇算子

針對(duì)傳統(tǒng)遺傳算法容易過(guò)早收斂于局部鄰域空間的現(xiàn)象。多種群遺傳算法引入了移民算子和多個(gè)設(shè)有不同控制參數(shù)的初始種群，并定期通過(guò)移民算子將各種群中的最優(yōu)個(gè)體替換掉其余某種群中的最差個(gè)體，在迭代遺傳中實(shí)現(xiàn)種群間信息互換。

同時(shí)，多種群遺傳算法引入人工選擇算子和精華種群，在進(jìn)化的每一代中通過(guò)人工選擇算子將其他種群的最優(yōu)個(gè)體添加到精華種群中，精華種群不用進(jìn)行選擇、交叉、變異等遺傳操作，保證進(jìn)化過(guò)程中各種群產(chǎn)生的最優(yōu)個(gè)體不被破壞。其操作過(guò)程示意圖如圖3所示。

圖3 MPGA操作示意圖

4 仿真實(shí)例分析

4.1 Plant Simulation生產(chǎn)線建模

該硬質(zhì)合金生產(chǎn)線在仿真平臺(tái)中所建立模型如圖4所示，模型中包括倉(cāng)庫(kù)以及配粉、球磨、干燥三道工序。三道工序中分別包含4臺(tái)、16臺(tái)、4臺(tái)設(shè)備，工序間各設(shè)置有緩存區(qū)，工序間由AGV小車進(jìn)行物料調(diào)度。

圖4 基于Plant Simulation的生產(chǎn)線模型

按實(shí)際生產(chǎn)線布局在Plant Simulation平臺(tái)中選取“Source”對(duì)象設(shè)置間隔時(shí)間模擬出庫(kù)，模擬物料出入庫(kù)；在各工序間添加“Buffer”對(duì)象用于模擬緩存區(qū)；分別選取4臺(tái)、16臺(tái)、4臺(tái)“Singleproc”模擬配粉工序、球磨工序以及干燥工序的設(shè)備；分別建立“Track”、“Transporter”對(duì)象模擬AGV和AGV軌道。

4.2 調(diào)度方案優(yōu)化

為優(yōu)化本車間設(shè)備投產(chǎn)順序，本文基于Matlab R2018b工具分別利用傳統(tǒng)遺傳算法和多種群遺傳算法對(duì)設(shè)備投產(chǎn)順序進(jìn)行優(yōu)化，運(yùn)行環(huán)境為 Intel（R）Core（TM）i5-9300H 2.40 GHz，運(yùn)行內(nèi)存16GB。一批料共24個(gè)工件分別在設(shè)備數(shù)為4臺(tái)、16臺(tái)、4臺(tái)的工序上依次加工，且不同工件在同一設(shè)備上的加工時(shí)間相同。為了方便多種群遺傳算法與傳統(tǒng)遺傳算法對(duì)比，兩種算法設(shè)置相同的最大迭代數(shù)和種群規(guī)模，設(shè)置最大迭代數(shù)為30，種群規(guī)模為40。其中多種群遺傳算法隨機(jī)產(chǎn)生5個(gè)初始子種群，為保證MPGA算法的全局搜索能力和進(jìn)化種群的多樣性，各種群采用不同的交叉概率和變異概率。在0.7～0.9范圍內(nèi)隨機(jī)選擇交叉概率，在0.01～0.05范圍內(nèi)隨機(jī)選擇變異概率。

兩種算法優(yōu)化后的投產(chǎn)方案與經(jīng)驗(yàn)投產(chǎn)方案見(jiàn)表4。

表4 經(jīng)驗(yàn)方案與算法優(yōu)化方案染色體對(duì)比

MPGA與SGA算法迭代過(guò)程圖分別如圖5、圖6所示。

圖5中橫坐標(biāo)代表迭代種群代數(shù)，縱坐標(biāo)代表對(duì)應(yīng)加工一批料所需時(shí)長(zhǎng)。點(diǎn)畫線代表每一代個(gè)體中最優(yōu)的設(shè)備投產(chǎn)方案，虛線代表該代個(gè)體中最差的設(shè)備投產(chǎn)方案，“++”線為兩者的平均值。

如圖5所示，MPGA進(jìn)化到第22代后，最優(yōu)個(gè)體的目標(biāo)變量FINAL_TIME才收斂于最小值，對(duì)比最大時(shí)間和最小時(shí)間曲線發(fā)現(xiàn)整個(gè)進(jìn)化過(guò)程搜索鄰域較大；如圖6所示，SGA的進(jìn)化曲線在第16代就已收斂于其“最小值”，且其搜索領(lǐng)域相對(duì)局限；上述結(jié)果證明MPGA有效地改善了SGA搜索鄰域，且較好地克服了其“早熟”現(xiàn)象。

圖5 MPGA排優(yōu)迭代過(guò)程

圖6 SGA排優(yōu)迭代過(guò)程

4.3 調(diào)度方案驗(yàn)證

在前文所建立的生產(chǎn)線模型中建立三個(gè)Table對(duì)象分別存放所得到的優(yōu)化投產(chǎn)方案。建立一個(gè)全局變量FINAL_TIME，并在ENDSIM方法中將各投產(chǎn)方案得到的加工完成時(shí)間賦值給全局變量FINAL_TIME。建立Track、Track1、Track2對(duì)象，并各建立兩個(gè)Onsensor方法對(duì)象。Onsensor1控制AGV從緩存區(qū)取料，Onsensor2控制AGV將物料按table表分配到各工序的設(shè)備上。

最終的仿真結(jié)果顯示，MPGA相對(duì)傳統(tǒng)投產(chǎn)方案優(yōu)化了66 min；而SGA優(yōu)化時(shí)間僅為18 min。

5 結(jié)束語(yǔ)

1）為提高硬質(zhì)合金混合料生產(chǎn)效率，提出了一種改進(jìn)的多種群遺傳算法（MPGA）改善該硬質(zhì)合金混合料生產(chǎn)線的生產(chǎn)調(diào)度方案。