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

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

1 引言

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

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

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

2 問題描述

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

2.1 車間加工情況描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 算法設(shè)計

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

3.1 染色體編碼

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

表1 三道工序編碼

每個工件都要依次在配粉、球磨、干燥工序上任選一臺設(shè)備上進(jìn)行加工。默認(rèn)經(jīng)驗排產(chǎn)是按加工時長優(yōu)先排時長小的設(shè)備。實際生產(chǎn)按默認(rèn)經(jīng)驗順序進(jìn)行排產(chǎn)，第一個工件加工設(shè)備依次為配粉工位1-球磨機1-噴霧干燥塔1，第二個工件加工設(shè)備依次為配粉工位2-球磨機2-噴霧干燥塔2，依次類推。以經(jīng)驗排產(chǎn)方案為例，該方案編碼后對應(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ì)量對遺傳算法在整個搜索空間中的搜索速度與質(zhì)量有著十分重要的關(guān)系。已有研究通常采用隨機或其他單一初始化的方法，因而所得到的解的質(zhì)量偏低。本文提出改進(jìn)多種群遺傳算法在產(chǎn)生初始種群時引入多個初始種群同時進(jìn)行優(yōu)化搜索，各初始種群間通過移民算子通信，從而實現(xiàn)多種群的協(xié)同進(jìn)化，得到各種群進(jìn)化的綜合結(jié)果。

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

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

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

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

3.4 選擇算子

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

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

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

3.5 交叉算子

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

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

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

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

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

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

圖2 PBX具體操作示意圖

3.6 變異算子

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

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

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

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

圖3 MPGA操作示意圖

4 仿真實例分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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