基于混合遺傳算法的車間調(diào)度研究

馮世扣，鮑 敏 ，張 偉

(浙江理工大學(xué)機(jī)械與自動(dòng)控制學(xué)院，浙江杭州310018)

0 引 言

生產(chǎn)車間調(diào)度是離散制造系統(tǒng)中關(guān)鍵的一個(gè)環(huán)節(jié)，車間調(diào)度通過(guò)合理分配現(xiàn)有的資源、安排零件加工次序和加工時(shí)間，能夠有效的提高生產(chǎn)效率，對(duì)車間調(diào)度進(jìn)行研究具有深遠(yuǎn)的意義［1-2］。生產(chǎn)車間調(diào)度問(wèn)題種類繁多，本研究主要針對(duì)單件作業(yè)車間調(diào)度問(wèn)題(job shop problem，JSP)。在用遺傳算法求解JSP 問(wèn)題時(shí)，初期種群之間差異非常大，很容易造成整個(gè)種群過(guò)早收斂，算法后期種群趨于一致，個(gè)體之間優(yōu)勢(shì)不明顯，導(dǎo)致種群進(jìn)化停滯不前［3-5］。為了使調(diào)度方案更實(shí)用高效，遺傳算法得到不斷改進(jìn)和發(fā)展。Parviz Fatah［6］在求解過(guò)程中建立一個(gè)數(shù)學(xué)性規(guī)劃模型，用啟發(fā)式遺傳算法結(jié)合模擬退火算法求解;張超勇［7］設(shè)計(jì)了一個(gè)種基于工序和機(jī)器編碼的改進(jìn)遺傳算法，具有更好的遺傳特性;王萬(wàn)良等［8］提出了改進(jìn)自適應(yīng)遺傳算法，改進(jìn)自適應(yīng)遺傳算法提高了獲得最優(yōu)解的速度;Victor 等［9］改進(jìn)了混合遺傳算法的交叉操作，并將改進(jìn)的算法應(yīng)用與車間調(diào)度問(wèn)題中。

本研究針對(duì)遺傳算法搜索效率低，易于過(guò)早收斂等缺點(diǎn)，提出一種新的混合遺傳算法。這種算法核心在于:在每一代遺傳進(jìn)化過(guò)程中，引入退火思想，在迭代初期退火算法具有很高溫度，此時(shí)算法有很強(qiáng)的概率突跳性，有利于打破過(guò)早收斂問(wèn)題;引入自適應(yīng)交叉和變異概率，能使算法在優(yōu)化過(guò)程中自動(dòng)改變交叉和變異概率，避免盲目交叉，從而提高搜索效率;設(shè)計(jì)新型的交叉和變異算子，以避免交叉后產(chǎn)生不可行解，相對(duì)于傳統(tǒng)的算子新算子能夠使種群更加的多樣化，從而提高找到最優(yōu)解的概率。

1 JSP 問(wèn)題的數(shù)學(xué)模型

JSP 問(wèn)題主要研究n 個(gè)工件(J1J2…Jn)在M 個(gè)機(jī)器(M1M2…Mn)上完成加工，每個(gè)工件有k 個(gè)工序，每個(gè)工序在不同的機(jī)器上完成，相應(yīng)的完成時(shí)間也不同。JSP問(wèn)題的目標(biāo)就是通過(guò)優(yōu)化工件在機(jī)器上的加工順序，使加工完成的時(shí)間最短。通常JSP 問(wèn)題有以下假設(shè):

(1)不同工件的工序不存在先后順序的約束。

(2)各個(gè)工序一開(kāi)始加工就不能中斷。

(3)每臺(tái)機(jī)器可以加工不同工件的不同工序，但一臺(tái)機(jī)器不能同時(shí)加工多種工序。

(4)每一個(gè)工件只有當(dāng)前一個(gè)工序完成加工后，才能開(kāi)始加工該工件后一道工序。

(5)每一個(gè)工序的加工時(shí)間和加工機(jī)器都是預(yù)先給定的。

JSP 問(wèn)題的數(shù)學(xué)描述如下:

式(1)表示目標(biāo)函數(shù)。式中:Cik—工件i 在機(jī)器k上的完成時(shí)間;n—工件數(shù);m—機(jī)器數(shù)。

式(2)表示各工件的加工先后順序。式中:cjk，tik—工件j 在機(jī)器k 上的完成時(shí)間和加工時(shí)間;M—一個(gè)足夠大的正整數(shù)，如果工件j 比工件i 先在機(jī)器k 上加工，則xijk為1，反之為0。

式(3)表示工藝條件約束下各工件的加工順序。其中:如果機(jī)器h 優(yōu)先與機(jī)器k 加工工件i，則aijk為1，反之為0。

另外對(duì)一些符號(hào)作如下說(shuō)明:

(1)加工時(shí)間矩陣T。T(i，j)表示加工第i 個(gè)工件的第j 個(gè)工序所用的時(shí)間。

(2)機(jī)器順序矩陣J。J(i，j)表示加工第j 個(gè)工件的第j 個(gè)工序所用的機(jī)器號(hào)。

2 混合遺傳算法的設(shè)計(jì)

在用混合遺傳算法求解JSP 問(wèn)題的過(guò)程中，關(guān)鍵步驟包括設(shè)計(jì)編碼和解碼方式、確定目標(biāo)函數(shù)、設(shè)計(jì)遺傳算子、確定遺傳參數(shù)以及設(shè)計(jì)模擬退火過(guò)程等。

2．1 染色體編碼

編碼是遺傳算法求解調(diào)度問(wèn)題的關(guān)鍵，本研究采用基于工序的編碼方式，該編碼方式可以避免產(chǎn)生不可行解和死鎖現(xiàn)象。當(dāng)求解n 個(gè)工件在m 臺(tái)機(jī)器上加工的問(wèn)題時(shí)，染色體的基因數(shù)等于全部工序的數(shù)，為n·m 個(gè)。每一個(gè)工件的工序都用相應(yīng)的工件號(hào)表示，第i 次出現(xiàn)的工件號(hào)就表示加工該工件的第i 道工序。如個(gè)體［2 3 1 2 3 1 1 2 3］表示3 個(gè)工件在3 臺(tái)機(jī)器上加工，該染色體的加工順序?yàn)楣ぜ?，工件3，工件1，工件2，工件3，工件1，工件1，工件2，工件3。

2．2 染色體解碼

對(duì)于已有的染色體，結(jié)合機(jī)器順序矩陣，可以得到加工所有工序的機(jī)器序號(hào)，從而得到一個(gè)有效的生產(chǎn)調(diào)度。

2．3 適應(yīng)度值

適應(yīng)度值用來(lái)衡量個(gè)體適應(yīng)環(huán)境的能力，適應(yīng)度值越大越優(yōu)秀，遺傳到下一代概率越大［9］。對(duì)于車間調(diào)度問(wèn)題，適應(yīng)度值是加工完成所有工件的時(shí)間Cmax的最小值。

式中:Cmax—加工完成所有工件的時(shí)間。

2．4 選擇算子

選擇算子是選擇種群中高適應(yīng)度值的個(gè)體進(jìn)入下一代的操作。本研究采用比例選擇方式，即被選中個(gè)體的概率正比與個(gè)體的適應(yīng)度值:

式中:Pi—選擇的概率，F(xiàn)(xi)—個(gè)體適應(yīng)值。

2．5 交叉操作

種群通過(guò)交叉操作產(chǎn)生新個(gè)體，從而推動(dòng)種群進(jìn)化，因此交叉操作是最重要的操作。對(duì)于JSP 問(wèn)題，筆者采用傳統(tǒng)的交叉操作，產(chǎn)生的新染色體可能存在某個(gè)工序的多余或缺失，因此交叉操作的難點(diǎn)在于如何保證交叉產(chǎn)生的新染色體是可行解。本研究設(shè)計(jì)了基于工件序號(hào)的交叉操作，具體步驟如下:

步驟1:從父代中隨機(jī)選擇兩個(gè)個(gè)體P1P2，隨機(jī)產(chǎn)生兩個(gè)不同的隨機(jī)數(shù)i1和i2(0 ＜i1，i2＜n)，然后把P1P2中i1和i2都提取出來(lái)，保存在新的基因串A1A2中，并且保持這些基因相對(duì)位置不變，P1P2中相應(yīng)的基因位置用0 來(lái)代替。

步驟2:然后把A2的基因插入到P1中基因?yàn)? 的位置，產(chǎn)生子代B1，把A1的基因插入到P2中基因?yàn)?的位置產(chǎn)生子代B2。

步驟3:把子代B1所有基因向左移動(dòng)一位，子代B2向右移動(dòng)一位，分別得到最終個(gè)體C1C2。例如:

P1為:

P2為:

A1為:［4 3 4 3 3 4］

A2為:［3 4 4 3 4 3］

P1為:［0 2 0 1 1 0 2 0 1 0 2 0］

P2為:［0 2 0 0 1 2 2 0 0 1 1 0］

B1為:［3 2 4 1 1 4 2 3 1 4 2 3］

B2為:［4 2 3 4 1 2 2 3 3 1 1 4］

C1為:［2 3 1 1 4 2 3 1 4 2 3 3］

C2為:［4 4 2 3 4 1 2 2 3 3 1 1］

通過(guò)以上交叉產(chǎn)生的個(gè)體不存在某個(gè)基因多余或缺失的情況，都是可行解。步驟3 中將子代向左向右移動(dòng)，可以提高種群多樣性，避免遺傳算法早熟。

2．6 變異操作

種群通過(guò)變異操作，產(chǎn)生新個(gè)體，在保證種群多樣性的同時(shí)推動(dòng)種群向前進(jìn)化。本研究中變異操作具體步驟如下:首先隨機(jī)選擇一個(gè)個(gè)體，隨機(jī)產(chǎn)生兩個(gè)位置，將兩個(gè)位置之間的基因片段逆轉(zhuǎn)，獲得新的個(gè)體。例如P1為［4 2 3 1 1 4 2 3 1 3 2 4］，兩個(gè)交叉位置Pose1和Pose2分別為4，9，則兩個(gè)位置間的基因片段A1為:［1 1 4 2 3 1］，通過(guò)逆轉(zhuǎn)A1，得到新片段A2為:［1 3 2 4 1 1］，最后用A2替換A1，得到子代B1為:［4 2 3 1 3 2 4 1 1 3 2 4］。

2．7 初始參數(shù)確定

在遺傳算法中，交叉概率Pc和變異概率Pm會(huì)直接影響算法的收斂性。因此本研究對(duì)Pc和Pm進(jìn)行重新的設(shè)計(jì)，Pc和Pm會(huì)隨著適應(yīng)度值變化而變化，具體如下:當(dāng)個(gè)體的適應(yīng)度值大于種群的平均適應(yīng)度值時(shí)，該個(gè)體屬于優(yōu)良個(gè)體，應(yīng)盡力保留，故Pc和Pm應(yīng)該較小;反之，Pc和Pm應(yīng)取較大的值。具體計(jì)算公式如下:

式(6～7)中:fmax—當(dāng)代種群中最大適應(yīng)度值，favg—當(dāng)代種群適應(yīng)度值的平均值，f'—兩個(gè)交叉?zhèn)€體中較大個(gè)體的適應(yīng)度值，f—要變異個(gè)體的適應(yīng)度值。一般取Pc1=0．9，Pc2=0．6，Pm1=0．1，Pm2=0．001［10］。

2．8 模擬退火算法設(shè)計(jì)

本研究引入模擬退火算法中的Metropolis 接受準(zhǔn)則使算法跳出局部最優(yōu)解的“陷阱”。Metropolis 接受準(zhǔn)則是以一定的概率P 來(lái)接受比原個(gè)體差的新個(gè)體，由該準(zhǔn)則判斷進(jìn)過(guò)遺傳算子的新個(gè)體是否替代父代個(gè)體，具體公式如下:

式中:T—模擬退火算法中的溫度;Δf—經(jīng)過(guò)遺傳算子的新個(gè)體與原個(gè)體適應(yīng)度值之差，若Δf 大于0，則接受適應(yīng)值更高的新個(gè)體，否則產(chǎn)生一個(gè)［0，1］隨機(jī)數(shù)b，若P ＞b，用新個(gè)體代替舊個(gè)體。

本研究給定初始溫度T0，終止溫度Tend，以及降溫系數(shù)K，在每一次退溫過(guò)程中，用Metropolis 接受準(zhǔn)則決定最終的個(gè)體，直到達(dá)到溫度達(dá)到Tend。

2．9 算法流程圖

混合遺傳算法流程圖如圖1 所示。

圖1 算法流程圖

3 仿真結(jié)果與分析

在混合遺傳算法仿真實(shí)驗(yàn)中，筆者采用FT06 問(wèn)題作為仿真案例［11］，即6 個(gè)工件，6 臺(tái)機(jī)器的調(diào)度問(wèn)題。機(jī)器的順序矩陣J 和加工的時(shí)間矩陣T 如下所示:

Matlab 仿真試驗(yàn)中，采用的初始參數(shù)為Pc為0．9，Pm=0．1，Size=40，T0=10 000，Tend=0．1，K =0．9。用混合遺傳算法得到最佳個(gè)體為［3 3 2 6 1 1 3 2 6 4 2 4 5 3 4 6 2 1 1 1 5 4 5 2 3 6 5 2 3 4 5 5 6 1 6 4］，需要的加工時(shí)間為55 s，達(dá)到該問(wèn)題的最優(yōu)解。算法收斂曲線如圖2 所示，最佳個(gè)體的甘特圖如圖3 所示，即工件加工順序圖。

圖2 收斂曲線圖

為驗(yàn)證混合遺傳算法的可行性，在同樣的參數(shù)下，筆者分別用遺傳算法和模擬退火算法求解FT06 問(wèn)題，得到相應(yīng)的結(jié)果，3 種算法的收斂曲線對(duì)比圖如圖4 所示。

從圖2 中可以看到，混合遺傳算法進(jìn)過(guò)50 代完成了收斂，得到的最佳完工時(shí)間為55，與FT06 問(wèn)題的最優(yōu)解一致，表明混合算法具有一定的搜索精度和較高的效率。

圖3 生產(chǎn)順序圖

圖4 3 種算法收斂對(duì)比圖

從圖3 中可以看到，每臺(tái)機(jī)器加工工件的順序，例如機(jī)器1 的加工工序順序依次為工件1 第2 工序、工件4 第2 工序、工件3 第4 工序、工件6 第4 工序、第5工件第5 工序和第2 工件第5 工序。6 臺(tái)機(jī)器上加工順序包含了所有工件的所有工序，是一個(gè)完整的生產(chǎn)計(jì)劃，也證明混合遺傳算法編碼方式避免了交叉和變異后產(chǎn)生非法個(gè)體。

3 種算法收斂曲線對(duì)比圖如圖4 所示。對(duì)比SA和GASA 曲線，可以看到SA 曲線前期有很大的波動(dòng)，GASA 收斂更早，表明混合遺傳算法能在全局進(jìn)行搜索最優(yōu)解，能夠控制尋優(yōu)方向，相對(duì)于SA 具有更快的搜索速度。對(duì)比GA 和GASA 曲線，可以看到GA 曲線前期收斂的非常快，在求解復(fù)雜問(wèn)題時(shí)比較容易早熟，從而只求得局部解。GASA 曲線收斂較為平滑，能克服GA 容易早熟的缺點(diǎn)。

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

本研究描述了車間調(diào)度的數(shù)學(xué)模型，分析遺傳算法在求解車間調(diào)度問(wèn)題時(shí)存在的不足之處，重新設(shè)計(jì)基于工件編號(hào)的交叉算子和變異算子，優(yōu)化了交叉和變異過(guò)程，同時(shí)采用自適應(yīng)交叉和變異概率，避免遺傳算法在迭代后期出現(xiàn)停滯不前的現(xiàn)狀。同時(shí)筆者在優(yōu)化過(guò)程中引入模擬退火算法，克服算法容易早熟的缺點(diǎn)。仿真結(jié)果顯示混合遺傳算法能夠找到全局最優(yōu)解，很好的解決JSP 調(diào)度問(wèn)題。

本研究以產(chǎn)品的最小完工時(shí)間作為目標(biāo)函數(shù)，找到了全局最優(yōu)解，但實(shí)際生產(chǎn)過(guò)程中還應(yīng)考慮客戶滿意度、生產(chǎn)成本、交貨延期懲罰等其他指標(biāo)，下一階段應(yīng)考慮多目標(biāo)遺傳算法的實(shí)現(xiàn)，提高算法實(shí)用性。

［1］邵新宇，饒運(yùn)清．制造系統(tǒng)運(yùn)行優(yōu)化理論與方法［M］．北京:科學(xué)出版社，2010．

［2］王 凌．車間調(diào)度及其遺傳算法［M］．北京:清華大學(xué)出版社，2003．

［3］吳 君，張京娟．采用遺傳算法的多機(jī)自由飛行沖突解脫策略［J］．智能系統(tǒng)學(xué)報(bào)，2013，15(1):90-92．

［4］CHUN B T，LEE S H． An efficient workload redistrbution algorithm in grid computing systems using genetic information［J］．Convergence and Hybrid Information Technology Communications in Computer and Information Science，2012，310(2):164-171．

［5］ZHANG Jing-jie，XV Chong-hai，YI Ming-dong，et al． Design of nano composite ceramic tool and die material with back propagation neural network and genetic algorithms［J］．Journal of Materials Engineering and Performance，2012，21(4):463-470．

［6］FATTAHI P，MEHRABAD S M，JOLAI F． Mathematical modeling and heuristic approaches to flexible job shop scheduling problems［J］．Journal of Intelligent Manufacturing，2007(18):331-342．

［7］張超勇，饒運(yùn)清，李培根．柔性作業(yè)車間調(diào)度問(wèn)題的兩級(jí)遺傳算法［J］．機(jī)械工程學(xué)報(bào)，2007，43(7):119-124．

［8］王萬(wàn)良．人工智能及其應(yīng)用［M］．北京:高等教育出版社，2008．

［9］YAURIMA V，BURTSEVA L，TECRNYJH A． Hybrid Flow Shop with Unrelated Machines Sequence Dependent Setup Time and Availability Constrain:an Enhanced Crossover Operator for a Genetic Algorithm［C］//Proceedings of the 7th international conference on Parallel processing and applied mathematics． Gdansk:［s．n．］，2007:608-617．

［10］王萬(wàn)良，吳啟迪，宋 毅．求解作業(yè)車間調(diào)度問(wèn)題的改進(jìn)自適應(yīng)遺傳算法［J］． 系統(tǒng)工程理論與實(shí)踐，2004，20(2):80-83．

［11］王 凌．智能優(yōu)化算法及其應(yīng)用［M］．北京:清華大學(xué)出版社，2001．