基于遺傳算法的模具電極調(diào)度問題求解

夏琴香 李凱 馬駿 程秀全 肖剛鋒

(1.華南理工大學(xué) 機(jī)械與汽車工程學(xué)院，廣東 廣州 510640；2.珠海格力精密模具有限公司，廣東 珠海 519070； 3.廣州民航職業(yè)技術(shù)學(xué)院 飛機(jī)維修工程學(xué)院，廣東 廣州 510403)

模具制造業(yè)廣泛使用電火花(EDM)加工技術(shù)對型腔形狀復(fù)雜的模具零件進(jìn)行加工，電極經(jīng)數(shù)控加工(CNC)后進(jìn)入到EDM車間對模具零件進(jìn)行放電加工，電極的生產(chǎn)將直接影響模具的制造周期[1]。由于模具屬于典型的單件小批量產(chǎn)品，生產(chǎn)按照訂單進(jìn)行組織，模具零件到達(dá)EDM車間的時間并不具有連續(xù)性，且一套模具往往對應(yīng)幾十個電極，所需電極數(shù)量龐大，協(xié)作關(guān)系復(fù)雜，因此電極的生產(chǎn)調(diào)度任務(wù)復(fù)雜艱巨。

傳統(tǒng)的模具電極調(diào)度人工參與度高，嚴(yán)重依賴個人經(jīng)驗，不可避免地出現(xiàn)電極未完成CNC加工，從而不能按時到達(dá)EDM單元耽誤模具零件加工，以及模具零件還沒有到達(dá)，而大量電極囤積在EDM車間的現(xiàn)象，嚴(yán)重影響模具零件的交貨期，企業(yè)資源和生產(chǎn)能力也無法充分發(fā)揮和利用。因此，有效利用生產(chǎn)資源，制定電極生產(chǎn)調(diào)度方案，對保證模具按時交貨和提高企業(yè)生產(chǎn)競爭力有重要意義。目前針對模具電極調(diào)度問題，孫吳勝等[2]將EDM階段電極和內(nèi)模的協(xié)同加工描述為后工序成組約束，以拖期量最小化為目標(biāo)建立了成組約束下的模具電極調(diào)度模型，并提出了基于加工時間最長(LPT)和加工時間最短(SPT)優(yōu)先規(guī)則的啟發(fā)式調(diào)度算法進(jìn)行求解；Li等[3]進(jìn)一步歸納了后成組約束，且基于交貨期最早(EDD)和LPT優(yōu)先規(guī)則提出了一種名為EL算法。以上研究中的模具電極調(diào)度模型的CNC階段僅限于單個電極加工，但目前模具企業(yè)為縮短電極加工時間，常在CNC階段對電極進(jìn)行批處理加工，上述算法難以適應(yīng)現(xiàn)代化生產(chǎn)模式的要求。

文中針對以上問題，建立了批處理下的模具電極調(diào)度模型，根據(jù)相關(guān)性原則設(shè)計相關(guān)性優(yōu)先分批算法以解決批處理問題，利用遺傳算法求解批調(diào)度問題，并設(shè)計相關(guān)算例驗證了該算法的有效性。

1 問題描述

1.1 模具電極生產(chǎn)流程

模具電極的生產(chǎn)流程包含CNC和EDM兩個階段[4]。接到模具訂單后，根據(jù)模具零件的工藝設(shè)計產(chǎn)生電極生產(chǎn)任務(wù)，電極經(jīng)過設(shè)計、編程并完成CNC工序后，進(jìn)入到EDM車間作為模具零件加工的刀具進(jìn)行放電加工。其中，CNC階段多個電極隨機(jī)組合，同時在批處理機(jī)上并行加工，具有批處理特征；EDM階段與同一模具零件對應(yīng)的所有電極在同一臺機(jī)器上串行加工，即一次只能有一個電極放電，且為提高加工精度，模具零件在所有電極放電完成后才能下機(jī)。

針對模具電極在EDM階段的生產(chǎn)特點(diǎn)，將多個電極加工一個模具零件的過程歸納為相關(guān)性特征：若模具零件在某一階段需要若干個電極進(jìn)行協(xié)同加工，稱對應(yīng)于同一個模具零件的電極具有相關(guān)性，具有相關(guān)性的電極需在同一臺機(jī)器上加工，不相關(guān)的各電極組在加工過程中遵循不可搶占性。

模具電極調(diào)度問題即確定為電極在CNC和EMD階段加工次序的優(yōu)化問題。通過對加工次序的優(yōu)化，使模具零件總拖期量最??；其中CNC階段具有批處理特征、EDM階段具有相關(guān)性特征，兩階段都具有多臺并行機(jī)同時進(jìn)行加工(如圖1所示)。

圖1 模具電極生產(chǎn)流程圖

1.2 問題描述及數(shù)學(xué)模型

模具電極調(diào)度問題可視作柔性流水車間調(diào)度問題(HFSP)的擴(kuò)展，HFSP最早由Johnson[5]在1954年發(fā)表的開創(chuàng)性論文里提出，在1978年被Garey等[6]證明為NP-hard問題，其特點(diǎn)是工件在流水線上進(jìn)行多個階段的加工，其中至少有一個階段存在并行機(jī)?？紤]到模具電極調(diào)度問題還存在批處理和相關(guān)性特征，將模具電極調(diào)度問題記為BCHFSP。

將電極記為a類工件、模具零件記為b類工件，BCHFSP問題描述為：有p個a類工件和q個b類工件，a類工件ai在流水線上進(jìn)行CNC和EDM兩個階段的加工，第1階段(CNC階段)有m1臺機(jī)器，第2階段(EDM階段)有m2臺機(jī)器。各階段有且只有一道工序，可以在任意一臺機(jī)器上加工；且第1階段具有批處理特征，第2階段具有相關(guān)性特征；a類工件在零時刻到達(dá)，b類工件分批等間隔到達(dá)。工件在加工過程中遵循不可搶占性，每個工件只能被一臺機(jī)器所加工，在滿足生產(chǎn)工藝約束條件下尋找一種調(diào)度策略，使所確定生產(chǎn)批量和相應(yīng)加工順序下的b類工件總拖期量最小。

BCHFSP的數(shù)學(xué)模型如下(模型相關(guān)參數(shù)及其定義見表1)：

(1)

(2)

(3)

(y=1,2,…,p)

(4)

(y=1,2,…,p)

(5)

Rai(d+1)=Faid=Said+Paid

(6)

(i=1,2,…，p;d=1,2)

Rbj2≥Aj,j=1,2,…,q

(7)

(8)

式(1)表示問題的目標(biāo)函數(shù)，ξ為某一調(diào)度方案；約束(2)表示工件bj的拖期量等于最后一個與bj協(xié)同加工工件的完工時刻減去bj的交貨期；約束(3)表示第1階段為批處理加工；約束(4)表示第2階段具有相關(guān)性的工件在同一機(jī)器上加工；約束(5)表示批處理加工時間為各電極加工時間之和；約束(6)表示同一階段工件加工就緒時刻、完工時刻和開始加工時刻的關(guān)系；約束(7)表示工件bj的加工就緒時刻大于等于到達(dá)時刻；約束(8)表示同一批次工件占用的總空間不能超過最大批處理容量。

1.3 數(shù)學(xué)模型的理論分析

由于不相關(guān)的各電極組在加工過程中遵循不可搶占性，那么當(dāng)相關(guān)電極在第2階段的加工不連續(xù)時，將產(chǎn)生機(jī)器空閑等待時間，使當(dāng)前工件以及后續(xù)工件的拖期量增加[3]。為獲得模型中目標(biāo)函數(shù)(1)的最優(yōu)解，對如何實現(xiàn)加工連續(xù)性進(jìn)行理論分析。假設(shè)一調(diào)度方案ξ已經(jīng)確定a類工件的Rauj2，則有以下結(jié)論：

表1 模具電極調(diào)度模型參數(shù)及定義

①存在最小的b類工件Rbj2使具有相關(guān)性的a類工件在EDM階段的加工連續(xù);

②最小Rbj2可以被找到。

對于結(jié)論②，令Rbj2=Aj，通過Rauj2和Pauj2計算并判斷加工過程是否中斷，若中斷則令Rbj2增加單位時間，因最小Rbj2存在且區(qū)間固定，只要重復(fù)以上判斷必能找到最小Rbj2使加工連續(xù)，結(jié)論②得證。當(dāng)加工連續(xù)時，b類工件的加工時間可按式(9)計算：

(9)

2 模具電極調(diào)度算法

2.1 算法總體框架

根據(jù)上述調(diào)度模型，將模具電極調(diào)度問題的求解分解為兩個層次：第1層考慮CNC階段的批處理特征，建立分批優(yōu)先規(guī)則對a類工件進(jìn)行分批，以及確定批次本身加工次序；第2層考慮EMD階段的相關(guān)性特征，需要確定Rbj2使相關(guān)電極加工連續(xù)，并確定各相關(guān)電極組加工次序。

目前調(diào)度算法主要為啟發(fā)式算法和智能優(yōu)化算法[7]，Dios等[8]基于NEH法求解了最小完工時間下的可跳過HFSP；Tasgetiren等[9]提出一種迭代貪婪算法，求解最小拖期量的帶阻塞HFSP；Engin等[10]基于交叉和變異機(jī)制的混合蟻群算法求解了無等待流水車間調(diào)度問題。由于啟發(fā)式算法依賴于建立的優(yōu)先規(guī)則，面對大規(guī)模的模具電極調(diào)度時規(guī)則匹配速度較慢，因此考慮使用智能優(yōu)化方法。遺傳算法(GA)是基于“適者生存”的一種高度并行、隨機(jī)和自適應(yīng)優(yōu)化算法，自Davis[11]將其引入到FSP中，GA的隱含并行性和全局解空間搜索使其在大規(guī)模調(diào)度領(lǐng)域展現(xiàn)出了極強(qiáng)的適應(yīng)性和生命力[12]。文中以GA算法框架為基礎(chǔ)，配合分批策略以及GA改進(jìn)策略完成模具電極兩層調(diào)度，算法總體框架如圖2所示。

圖2 模具電極調(diào)度算法框架

2.2 電極分批算法

根據(jù)模具電極加工的特點(diǎn)，CNC階段的電極分批考慮兩個原則[4]：第1個是同一批電極不能超過最大批處理容量；第2個考慮電極相關(guān)性特征，模具零件在EDM過程中遵循不可搶占性，即所有對應(yīng)電極加工完才能進(jìn)行下一模具零件的加工，若相關(guān)電極進(jìn)入第2階段時不連續(xù)，會不可避免地增加等待時間，因此將具有相關(guān)性的電極優(yōu)先劃分到同一批次，記為相關(guān)性優(yōu)先(CF)。

CF分批策略為：①按相關(guān)性對所有參與調(diào)度的電極進(jìn)行初步分組；②對于各組電極，選擇第一個電極加入批次，并按順序往批次中添加電極，若達(dá)到最大批處理容量，則下一電極添加到新的批次；③各組剩余電極任意組合，同樣不能超過最大批處理容量。

2.3 電極批調(diào)度遺傳算法

2.3.1 配種策略

傳統(tǒng)GA盡管在一定條件下具有全局收斂性，但選擇、交叉、變異等遺傳操作是在概率意義下隨機(jī)進(jìn)行的，在一定程度上會出現(xiàn)退化及長時間陷入局部最優(yōu)的情況，另一方面相較于GA強(qiáng)大的全局搜索能力，其局部搜索能力弱[13]。針對以上問題，文中從動物配種現(xiàn)象得到啟發(fā)，提出一種優(yōu)化策略。

動物配種是指挑選具有優(yōu)秀基因的雄性，與其余雌性進(jìn)行配種以期產(chǎn)生優(yōu)秀個體的過程，以人工干預(yù)的方式增加了優(yōu)秀個體出現(xiàn)的概率。文中將這一過程插入到遺傳算法中，提出一種基于動物配種的策略(如圖2中虛線框所示)，在此基礎(chǔ)上，對傳統(tǒng)遺傳GA進(jìn)行改進(jìn)，改進(jìn)后的遺傳算法記為Breed-GA。

具體步驟如下：

步驟1按GA進(jìn)行迭代，令停滯代數(shù)S=0，并設(shè)定臨界停滯代數(shù)Smax和鄰域搜索輪數(shù)k；

步驟2種群適應(yīng)度計算，并判斷進(jìn)化停滯狀態(tài)，即本次與上一輪迭代最優(yōu)解值是否相同，若相同則S=S+1，否則繼續(xù)迭代；

步驟3若S>Smax，則進(jìn)行配種:取出當(dāng)前最優(yōu)解，按隨機(jī)交換、中心對稱、向前插入、向后插入4個鄰域動作(如圖3所示)為一輪進(jìn)行k輪鄰域搜索，選取適應(yīng)度最高的染色體作為種染色體，將種染色體與種群中每一條染色體配種產(chǎn)生兩個子代，比較該染色體與子代適應(yīng)度，取最高者替代該染色體，S=0，返回步驟2，否則繼續(xù)迭代；

圖3 鄰域搜索動作

步驟4每一次迭代完成都進(jìn)行個體評價，若滿足停止準(zhǔn)則則輸出最優(yōu)解，否則重復(fù)以上步驟。

2.3.2 編碼與解碼

用所有批次的置換排列作為算法的染色體編碼方式，染色體基因為批次編號，長度等于批次數(shù)量。批次編號在染色體中的位置表示該批次進(jìn)入流水線的順序,譬如，nB=5時，染色體[2 3 5 1 4]表示所有批次進(jìn)入流水線的順序為“批次2—批次3—批次5—批次1—批次4”?；谌旧w轉(zhuǎn)化后的有序操作表，通過一定的啟發(fā)式方法進(jìn)行解碼，就可以產(chǎn)生調(diào)度方案。

解碼過程分為兩個階段，第1階段的解碼步驟如下。

(10)

步驟2將染色體中最靠前的未分配批次分配給釋放時刻最早的機(jī)器；

步驟3判斷是否所有批次都完成了機(jī)器分配。若已完成，則結(jié)束循環(huán)，進(jìn)入第2階段解碼，否則轉(zhuǎn)到步驟1；

第2階段的解碼步驟為

步驟1第1階段解碼完成并獲得a類工件的Rauj2，根據(jù)模型理論分析計算所有b類工件的加工就緒時刻Rbj2，按遞增排序，按式(9)計算b類工件的加工時間；

步驟2根據(jù)下式更新第2階段所有可用機(jī)器的釋放時刻，按從早到晚排序：

(11)

步驟3將加工就緒時刻最早且未分配的b類工件對應(yīng)的所有a類工件分配給釋放時刻最早的機(jī)器，加工就緒時刻相同則選加工時間長的工件，仍不能確定則隨機(jī)選取，即優(yōu)先級為加工就緒時刻→加工時間→隨機(jī)。由于保證了加工連續(xù)性，故a類工件可按任意順序加工；

步驟4判斷是否所有a類工件都完成了機(jī)器分配。若已完成，則結(jié)束循環(huán)，否則轉(zhuǎn)到步驟2。

2.3.3 遺傳操作

適應(yīng)度函數(shù)取模型目標(biāo)函數(shù)，適應(yīng)度值越小適應(yīng)度越高；選擇采用輪盤賭方法，適應(yīng)度值越小每條染色體被選取的概率越大；交叉操作采用POX交叉法；變異操作采用位置變異法。

3 算例仿真及結(jié)果分析

3.1 仿真算例設(shè)計

采用分割試驗思想[14]設(shè)計本文的仿真數(shù)據(jù)集，算例參數(shù)如下：b類工件交貨期、b類工件數(shù)量、協(xié)作工件數(shù)量、a類工件占用批處理空間、最大批處理容量、工件加工時間、工件到達(dá)時間、機(jī)器數(shù)量，各參數(shù)設(shè)置如表2所示。

表2 算例參數(shù)

其中b類工件交貨期采用TWK[15]方法：

(12)

式中:寬裕度系數(shù)取1和2，分別代表緊、松交貨期。U代表取范圍內(nèi)均勻離散分布；Vi矩陣第1行為占用批處理空間，第2行為相應(yīng)取值概率；工件到達(dá)時間指b類工件到達(dá)時間Aj，按起始時間/批次大小/間隔時間取10/5/5；(m1,m2)分別代表第1階段和第2階段的機(jī)器數(shù)量。

3.2 仿真實驗及結(jié)果分析

按3.1算例設(shè)計方法，選取主要參數(shù)：b類工件數(shù)量、最大批處理容量、機(jī)器數(shù)量以及不同的交貨期寬裕度系數(shù)得到參數(shù)配置四元組：{q,Vmax,(m1,m2),k}。通過四元組中每一個參數(shù)值的不同設(shè)置，得到24種仿真算例并對文中提出的Breed-GA和傳統(tǒng)GA進(jìn)行測試比較，目的包括：(1)驗證算法針對不同規(guī)模問題的有效性；(2)驗證配種策略能夠有效解決傳統(tǒng)GA進(jìn)化停滯時間過長以及局部搜索能力弱的問題。所有算法的參數(shù)設(shè)置均為種群規(guī)模Psize=50，交叉概率Pc=0.6，變異概率Pm=0.001，停止準(zhǔn)則為最大迭代次數(shù)imax=100，臨界停滯代數(shù)5，鄰域搜索輪數(shù)k=10，采用保優(yōu)策略。仿真測試軟件為Matlab2019a，處理器為Intel(R)Core(TM)i5-6300HQ，運(yùn)存RAM8GB。

表3為按每種四元組配置下分別按Breed-GA和GA進(jìn)行10次仿真試驗得到的最優(yōu)適應(yīng)度平均值及其進(jìn)化率?？梢钥闯?，文中提出的RF分批算法和Breed-GA對不同規(guī)模的BCHFSP均有效，且與傳統(tǒng)GA相比，Breed-GA求解得到的拖期量進(jìn)化率最高達(dá)到16.71%。在其它條件相同時，q=40的進(jìn)化率相較于q=20明顯提升，這說明隨著問題規(guī)模的擴(kuò)大，Breed-GA的優(yōu)勢也不斷擴(kuò)大。

表3 總拖期量

圖4為算法進(jìn)化迭代曲線，橫坐標(biāo)為迭代次數(shù)，縱坐標(biāo)為總拖期量。圖中總拖期量隨著迭代次數(shù)的增加，從21 411降到17 162，即算法有效減小了模具總拖期量，虛線框表明GA在前期收斂時處于長時間的進(jìn)化停滯狀態(tài)，散狀分布點(diǎn)則說明配種策略在長時間停滯時發(fā)揮了作用，增強(qiáng)了GA的局部搜索能力，跳出了局部最優(yōu)狀態(tài)，進(jìn)而提高整體迭代速度和迭代質(zhì)量。

圖4 算法進(jìn)化迭代曲線

圖5為最優(yōu)解分布圖，相同條件下每種算法循環(huán)仿真10次，記錄每一次循環(huán)下的最優(yōu)解。各點(diǎn)的離散程度表明Breed-GA的解較GA的解穩(wěn)定，這是由于配種策略加快了前期迭代速度，增加了相同最大迭代次數(shù)下算法收斂到最優(yōu)解的概率。

圖5 最優(yōu)解分布圖

圖6對比了不同算例參數(shù)配置下的算法平均運(yùn)行時間，右側(cè)為對應(yīng)配置信息，如“204331”表示{q=20,Vmax=4,(m1,m2)=(3,3),k=1}，以此類推。結(jié)果顯示，由于配種操作影響，經(jīng)配種策略改進(jìn)的遺傳算法運(yùn)行時間比傳統(tǒng)遺傳算法長1～2 s，但所耗時間均在可接受范圍內(nèi)。q從20增加到40時，運(yùn)行時間從10 s增加到24 s，其余參數(shù)影響不明顯，說明算法運(yùn)行時間主要和參與調(diào)度的工件數(shù)量有關(guān)。

圖7為一組小規(guī)模案例下的最終調(diào)度方案甘特圖，圖中橫軸為加工時間，縱軸為機(jī)器編號，“B”表示批次，“b”表示b類工件，“1，2，…，10”為各電極編號，具體案例信息見表4和表5，機(jī)器配置為(2,2)。甘特圖顯示，CNC階段批次1和5在CNC1機(jī)床上加工，批次2、4、3依次在CNC2機(jī)床上加工，EDM階段工件1、4和相關(guān)電極在EDM1機(jī)床上加工，工件2、3和相關(guān)電極在EDM2機(jī)床上加工。

圖6 算法運(yùn)行時間對比

圖7 調(diào)度甘特圖

表4 模具零件信息

表5 電極信息

4 結(jié)論

文中針對模具電極CNC和EDM兩階段調(diào)度問題，建立了以最小拖期量為目標(biāo)的數(shù)學(xué)模型。設(shè)計了相關(guān)性原則下的CF分批算法以及基于配種策略的改進(jìn)GA進(jìn)行求解。在24種算例下進(jìn)行循環(huán)仿真實驗，得到以下結(jié)論：

(1)針對模具電極生產(chǎn)特點(diǎn)建立了具有批處理和相關(guān)性特征的調(diào)度數(shù)學(xué)模型，能夠準(zhǔn)確描述模具電極調(diào)度問題。

(2)所設(shè)計的相關(guān)性優(yōu)先分批算法和提出的改進(jìn)遺傳算法能夠有效解決模具電極調(diào)度問題，可自動實現(xiàn)對模具電極進(jìn)行批處理，以及對CNC和EDM階段加工次序進(jìn)行批調(diào)度。

(3)所提出的配種策略提高了傳統(tǒng)遺傳算法的鄰域搜索能力并加快了算法的收斂速度，使樣本內(nèi)的模具零件拖期量最多減少16.71%。