基于混合遺傳算法的柔性作業(yè)車間調(diào)度優(yōu)化

文/段明躍，三明學(xué)院機(jī)電工程學(xué)院

基于混合遺傳算法的柔性作業(yè)車間調(diào)度優(yōu)化

文/段明躍，三明學(xué)院機(jī)電工程學(xué)院

本文摘要：針對(duì)傳統(tǒng)作業(yè)車間調(diào)度問題的模糊性，結(jié)合實(shí)際生產(chǎn)流程，提出柔性作業(yè)車間調(diào)度模型，加入了隨機(jī)選定原則，在遺傳算法原有的基礎(chǔ)上優(yōu)化。通過隨機(jī)選定，并進(jìn)行交叉與變異，避免了局部最優(yōu)問題同時(shí)是算法結(jié)果更加精確，收斂速度增強(qiáng)。最后通過實(shí)例仿真驗(yàn)證了算法的有效性。

混合遺傳算法；多目標(biāo)優(yōu)化；柔性作業(yè)車間調(diào)度

就目前對(duì)調(diào)度問題的研究方法歸納來看，優(yōu)化調(diào)度方法和啟發(fā)式算法是目前最常見的方法。優(yōu)化調(diào)度主要是從全局出發(fā)，考慮在各個(gè)調(diào)度約束條件下目標(biāo)函數(shù)的最優(yōu)解。這類方法由于模型的解析過于復(fù)雜，且實(shí)際計(jì)算中不一定能得到最優(yōu)解，所以在調(diào)度問題上無法得到滿意的答案。作業(yè)車間調(diào)度問題本質(zhì)上是一個(gè)大范圍的組合優(yōu)化問題，而遺傳算法本質(zhì)上是一種并行的算法，與傳統(tǒng)數(shù)學(xué)規(guī)劃或算法相比搜索效率高，同時(shí)因?yàn)槠洳捎玫氖请S機(jī)搜索，能夠克服局部最優(yōu)問題，增大了算法的正確性。而且這類算法不需要很多的專業(yè)知識(shí)，所以實(shí)用范圍廣，可實(shí)現(xiàn)性高。

1 相關(guān)的問題假設(shè)

柔性作業(yè)車間調(diào)度主要是指在一個(gè)生產(chǎn)系統(tǒng)中，有一個(gè)需要加工完成的作業(yè)集，在這個(gè)加工集合中有個(gè)需要加工的零件，集合可以表示為。同時(shí)有一個(gè)加工機(jī)床集合,其中共有臺(tái)機(jī)床可用，集合可以表示為,每一個(gè)需要加工的零件都需要經(jīng)過若干加工工序才可以完成。目標(biāo)函數(shù)為求得最大完工時(shí)間的最小值。

針對(duì)該模型進(jìn)行相應(yīng)的假設(shè)：

（1）每一臺(tái)機(jī)床每次只能加工一個(gè)工件；

（2）每個(gè)工件在同一時(shí)刻只能在一臺(tái)機(jī)床上加工；

（3）工件的加工過程是連續(xù)的，中途不能中斷；

（4）在模型的初始時(shí)刻，所有工件都可以進(jìn)行加工；

（5）工件的工藝流程是預(yù)先確定好的；

（6）每一種工序在機(jī)床上所需加工時(shí)間是確定好的；

2 模型變量定義

表1 模型變量定義表

3 基于混合遺傳算法的FJSP優(yōu)化

在加工過程中，工件的每一道工序都可以選擇一臺(tái)或多臺(tái)機(jī)床進(jìn)行加工，單一采用基于工序的遺傳算法，在染色體的信息中無法表達(dá)出來，所以在原有算法的基礎(chǔ)上進(jìn)行優(yōu)化，將工序信息與機(jī)床信息相融合，形成一個(gè)二維矩陣，增加了機(jī)床的信息。在這個(gè)二維矩陣中，第一行為加工工序信息，而第二行為加入機(jī)床序號(hào)的補(bǔ)充信息，工序與機(jī)床都用每個(gè)染色體上的基因進(jìn)行編碼。遺傳算法存在過早收斂的問題，通過改進(jìn)使其可以得到更加優(yōu)秀的解。

將兩種編碼方式結(jié)合為一個(gè)二維矩陣，矩陣如下所示：

在矩陣(11)中，第一行表示所有加工工藝的序列，第二行表示每一道工序所對(duì)應(yīng)的機(jī)床序號(hào)。

表2 一種柔性車間加工調(diào)度情況

表2是一個(gè)4個(gè)工件，3道工序，5臺(tái)加工機(jī)床的加工調(diào)度情況，則以此為舉例列寫出相應(yīng)的二維矩陣。假設(shè)（1,2,4,3,2,4,3,2,1,4,1）為該情況下的一種可行方案，根據(jù)上述編碼方式可得到，

對(duì)應(yīng)的操作和加工機(jī)床為：

步驟1 通過初始種群確定種群的規(guī)模大小，通過對(duì)時(shí)間取到將問題轉(zhuǎn)化為求最大值問題，即適應(yīng)度函數(shù)。構(gòu)建一個(gè)概率模型，利用比例于個(gè)體的適應(yīng)度概率決定子孫的遺傳可行性。個(gè)體的概率選定后，產(chǎn)生隨機(jī)數(shù)決定下一步操作。

步驟2 在概率P的作用下，隨機(jī)的選擇矩陣中第二行的機(jī)床中非空值，將其隨機(jī)改變?yōu)?到工序范圍的數(shù)。這樣就可以得到同一工件同一步驟在不同機(jī)床上的信息。

步驟3 隨機(jī)選取兩個(gè)交叉點(diǎn)，然后將這兩個(gè)基因的信息相互交換，搜索交叉完畢之后產(chǎn)生的新的基因序列，找出新增和遺失的工件號(hào)，并在染色體中隨機(jī)篩選出多的基因，將其換為遺失的基因，則通過如此得到一個(gè)可行解。同時(shí)還需要保證原有染色體中的每道工序的相關(guān)信息不變。在變異過程中，在保證變異前后工件所可選擇的機(jī)床是保持不變的，為了改進(jìn)傳統(tǒng)遺傳算法，采用插入的變異方式，即在染色體中隨機(jī)選擇一個(gè)變異位置，然后將點(diǎn)插入在此位置之前。若本次最優(yōu)解使得適應(yīng)度函數(shù)大于歷代值則替換最優(yōu)解，繼續(xù)下一個(gè)隨機(jī)數(shù)組進(jìn)行計(jì)算。

步驟4 輸出最佳加工路線，算法結(jié)束。

[1]王萬良, 趙澄, 熊婧,等. 基于改進(jìn)蟻群算法的柔性作業(yè)車間調(diào)度問題的求解方法[J]. 系統(tǒng)仿真學(xué)報(bào), 2008, 20(16):4326-4329.

[2]王小蓉, 李蓓智, 周亞勤,等. 基于混合遺傳算法的柔性作業(yè)車間調(diào)度研究[J]. 現(xiàn)代制造工程, 2015(5):39-42.

[3]張騰飛, 馬躍, 李力,等. 柔性作業(yè)車間調(diào)度問題的改進(jìn)遺傳算法[J].小型微型計(jì)算機(jī)系統(tǒng), 2017, 38(1):129-132.