基于改進型交叉算子的混合流水車間排序求解

黃宗南 張博凡 信寧寧

(上海大學機電工程與自動化學院，上海200072)

混合流水車間是指一批工件在流水線上進行多個階段的加工，每一階段至少有一臺并行機器;在每一階段各工件均要完成一道工序，各工件的每道工序可以在相應階段上的任意一臺機器上加工。這種形式的車間在制造業(yè)中比較常見，其作業(yè)排序比置換型車間更復雜。因此，為了提高企業(yè)設備的使用效率，科學合理的作業(yè)排序方法非常重要。

混合流水車間排序問題也是研究熱點之一［1－4］，本文在前期的研究基礎上，將提出的改進型單點交叉算子［5］擴展應用到混合流水車間排序問題中，并測試該算子的求解性能。

1 混合流水車間排序的數(shù)學模型

混合流水車間排序問題的數(shù)學描述如下:

符號和變量定義為:

N為工件數(shù);S為加工階段數(shù)(工序數(shù));

M(k)為第k道加工工序的并行機器數(shù)量;Pik為工件i在第k道工序的加工時間;

Cik為工件i在第k道工序的完工時間;PN為足夠大的正整數(shù);

Yikm=1，表示工件i分配到第k道工序m機器上加工，否則Yikm=0;Xijk=1，表示工件i在第k道工序領先工件j加工，否則Xijk=0。

式(1)表示排序的目標函數(shù)，即要求工件加工最大完工時間最小化，也叫Makespan指標;

式(2)表示各工件在每一道工序只能分配一臺機器加工;

式(3)表示每一工件須經(jīng)S道工序加工;

式(4)和(5)表達了同一工序同一機器上不同工件加工順序約束，保證一臺機器在同一時刻只能加工一個工件;

式(6)描述了每一工件須依次在不同工序加工的順序要求，保證一個工件同時只能在一個工序加工;

式(7)和(8)為決策變量和參數(shù)取值約束。

2 混合流水車間排序問題求解

2.1 遺傳尋優(yōu)流程

圖1是求解混合流水車間排序問題的遺傳算法操作流程。

第一步，隨機生成N個個體組成初始種群。其中，每個個體表示染色體的基因編碼，對于混合流水車間排序問題，常用的編碼方式有矩陣編碼、復合編碼和置換編碼等。本文采用置換編碼。例如，對于5個工件的混合流水車間排序問題，假設一條染色體為［2 4 1 5 3］，則表示工件進入流水線的順序為“工件2→工件4→工件1→工件5→工件3”。

第二步，解碼。對于采用置換編碼的混合流水車間排序問題，需要同時安排設備的分配和工件的排序。本文采用基于 FIFO(先進先出)［6］的解碼方式。例如，設有m個工件，S道工序，每道工序有M(s)臺并行機器，并且已知工件在每臺機器上的加工時間，解碼的操作流程為:把前工序最早完工的工件依次分配給當前工序的機器上，空閑的機器數(shù)由每道工序的并行機數(shù)量以及當前已分配任務情況決定，一臺機器同一時刻只能加工一個工件，按這樣的操作從第一道工序直至最后一道工序進行解碼，確定各工件在機器上的加工順序。

第三步，計算個體的適應度。根據(jù)遺傳算法目標函數(shù)的方向與適應度值變化方向相同的原則，本次采用的適應度函數(shù)為式(1)目標函數(shù)的倒數(shù)。

第四步，進行遺傳操作，即進化尋優(yōu)。

①選擇操作。本文采用與生物自然選擇最相似的輪盤賭選擇算子，用正比于個體適應度值的概率來選擇個體。

②交叉操作。采用改進型單點交叉算子，此操作方法在下節(jié)中展開。

③變異操作。常用的變異方法有交換變異、倒位變異、插入變異等。本文采用交換變異。例如一條染色體為［2 4 1 5 3］，隨機選取第2和第4位置，則交換變異的結(jié)果是［2 5 1 4 3］。

2.2 改進型交叉算子

由前期研究可知，改進型單點交叉算子性能良好［5］，故將該算子擴展應用到混合流水車間排序問題。以兩個父代［9 7 4 1 8 6 5 3 2］和［9 6 1 4 3 8 5 7 2］為例，改進型單點交叉算子的操作過程如圖2。

(1)產(chǎn)生一隨機數(shù)(rand)，當隨機數(shù)大于0.5時，把兩父代交叉點前的基因復制給子代，然后從父代2(或1)中找出子代1(或2)中缺失的基因，并將其按順序復制給子代交叉點后的位置。得到的子代見圖2b。

(2)當隨機數(shù)小于等于0.5時，把兩父代交叉點后的基因復制給子代，其余操作與步驟1類似。得到的子代見圖2c。

從上述操作結(jié)果可知，對于二進制編碼，改進型單點交叉保留交叉點前或交叉點后的基因所得到的子代是相同的;而對于符號編碼，由于染色體中會出現(xiàn)重復基因是非法的，故需要對重復基因進行替換，所以保留交叉點前或交叉點后的基因所得到的子代是不同的。與典型單點交叉相比，改進型單點交叉擴大了染色體基因的改變范圍，增大了搜索空間。

根據(jù)計算流程用Matlab語言編制了求解該問題的遺傳算法程序，實現(xiàn)混合流水車間排序問題的求解。

3 實驗分析

實驗采用文獻［7］中的案例。某汽車發(fā)動機廠加工車間要加工12個工件，每個工件有車、刨、磨3道工序，現(xiàn)有3臺車床完成工序1，2臺刨床完成工序2，4臺磨床完成工序3，每臺機床的加工能力不同，具體加工時間如表1所示［7］。

表1 工件在每臺機床上的加工時間

在計算實驗時，遺傳參數(shù)設置與文獻中相同:種群個數(shù)30，交叉率0.8，變異率0.05，進化代數(shù)100。經(jīng)過多次運算，［4 11 6 1 12 2 3 10 5 9 8 7］是得到的最好的染色體之一，其進化歷程圖如圖3所示。同時，與典型單點交叉算子進行比較，典型單點交叉算子的進化歷程圖如圖4。

從以上兩個進化歷程圖可以看出，進化前期兩個算子的平均適應度都在增加、進化，但改進型單點交叉算子比典型單點交叉算子速度更快;進化的后期雖然都逐漸趨于收斂，但改進型單點交叉算子更穩(wěn)定。觀察最大適應度曲線，改進型單點交叉算子能夠更快找到最優(yōu)解。由此可知，改進型單點交叉算子的整體尋優(yōu)過程更好。

據(jù)此，最優(yōu)排序的甘特圖如圖5，該方案的最大流程時間為25個單位。圖中的線段表示工件的加工時間，線段上方的第一位數(shù)字代表工序號，第二位數(shù)字代表工件號。從圖中排序結(jié)果可以看出，各并行機器被分配的加工任務比較均勻，且各機器在加工時間上基本保持連續(xù)，機器的空閑時間少，使完工時間減少。

為了進一步確認算法的有效性，與兩個文獻中該案例的實驗結(jié)果進行比較，實驗結(jié)果見表2。

由表中數(shù)據(jù)可知，本方法所求得的最好解為25，好于文獻［7］中的29和文獻［8］中的26;平均值為26，同樣優(yōu)于文獻［7］中的29.4和文獻［8］中的27.2;說明本研究采用的變形遺傳算法求解性能良好。

表2 實驗結(jié)果統(tǒng)計(10次運算)

4 結(jié)語

將改進型單點交叉算子擴展應用到混合流水車間排序問題中，并對其求解性能進行測試。結(jié)果表明算法求解性能良好。

［1］唐立新，吳亞萍.混合流水車間調(diào)度的遺傳下降算法［J］.自動化學報，2002，28(4):637 －641.

［2］Bassem Jarboui，Mansour Eddaly，Patrick Siarry.A hybrid genetic algorithm for solving no－ wait flowshop［J］.Intermational Journal of Advanced Manufacturing Technolgy，2010(11):472－478.

［3］王萬良，姚明海，吳云高，等.基于遺傳算法的混合Flow－shop調(diào)度方法［J］.系統(tǒng)仿真學報，2002，14(7):863 －869.

［4］胡燕海，嚴雋琪，葉飛帆.基于遺傳算法的混合流水車間構(gòu)建方法［J］.中國機械工程，2005，16(10):888 －891.

［5］張博凡，黃宗南.基于變形遺傳算法交叉算子的Flow－Shop問題求解［J］.制造業(yè)自動化，2011，33(10):27 －29.

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

［7］吳云高.基于遺傳算法的車間調(diào)度方法及其應用［D］.杭州:浙江工業(yè)大學，2002.

［8］周輝仁，唐完生，魏穎輝.基于微粒群算法的柔性流水車間調(diào)度優(yōu)化［J］.中國機械工程，2010，21(9):1053 －1057.