基于混合遺傳算法的柔性作業車間調度優化

文/段明躍，三明學院機電工程學院

基于混合遺傳算法的柔性作業車間調度優化

文/段明躍，三明學院機電工程學院

本文摘要：針對傳統作業車間調度問題的模糊性，結合實際生產流程，提出柔性作業車間調度模型，加入了隨機選定原則，在遺傳算法原有的基礎上優化。通過隨機選定，并進行交叉與變異，避免了局部最優問題同時是算法結果更加精確，收斂速度增強。最后通過實例仿真驗證了算法的有效性。

混合遺傳算法；多目標優化；柔性作業車間調度

就目前對調度問題的研究方法歸納來看，優化調度方法和啟發式算法是目前最常見的方法。優化調度主要是從全局出發，考慮在各個調度約束條件下目標函數的最優解。這類方法由于模型的解析過于復雜，且實際計算中不一定能得到最優解，所以在調度問題上無法得到滿意的答案。作業車間調度問題本質上是一個大范圍的組合優化問題，而遺傳算法本質上是一種并行的算法，與傳統數學規劃或算法相比搜索效率高，同時因為其采用的是隨機搜索，能夠克服局部最優問題，增大了算法的正確性。而且這類算法不需要很多的專業知識，所以實用范圍廣，可實現性高。

1 相關的問題假設

柔性作業車間調度主要是指在一個生產系統中，有一個需要加工完成的作業集，在這個加工集合中有個需要加工的零件，集合可以表示為。同時有一個加工機床集合,其中共有臺機床可用，集合可以表示為,每一個需要加工的零件都需要經過若干加工工序才可以完成。目標函數為求得最大完工時間的最小值。

針對該模型進行相應的假設：

（1）每一臺機床每次只能加工一個工件；

（2）每個工件在同一時刻只能在一臺機床上加工；

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

（4）在模型的初始時刻，所有工件都可以進行加工；

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

（6）每一種工序在機床上所需加工時間是確定好的；

2 模型變量定義

表1 模型變量定義表

3 基于混合遺傳算法的FJSP優化

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

將兩種編碼方式結合為一個二維矩陣，矩陣如下所示：

在矩陣(11)中，第一行表示所有加工工藝的序列，第二行表示每一道工序所對應的機床序號。

表2 一種柔性車間加工調度情況

表2是一個4個工件，3道工序，5臺加工機床的加工調度情況，則以此為舉例列寫出相應的二維矩陣。假設（1,2,4,3,2,4,3,2,1,4,1）為該情況下的一種可行方案，根據上述編碼方式可得到，

對應的操作和加工機床為：

步驟1 通過初始種群確定種群的規模大小，通過對時間取到將問題轉化為求最大值問題，即適應度函數。構建一個概率模型，利用比例于個體的適應度概率決定子孫的遺傳可行性。個體的概率選定后，產生隨機數決定下一步操作。

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

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

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

[1]王萬良, 趙澄, 熊婧,等. 基于改進蟻群算法的柔性作業車間調度問題的求解方法[J]. 系統仿真學報, 2008, 20(16):4326-4329.

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

[3]張騰飛, 馬躍, 李力,等. 柔性作業車間調度問題的改進遺傳算法[J].小型微型計算機系統, 2017, 38(1):129-132.