黃宗南 張博凡 信寧寧

(上海大學(xué)機(jī)電工程與自動(dòng)化學(xué)院，上海200072)

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

混合流水車間排序問題也是研究熱點(diǎn)之一［1－4］，本文在前期的研究基礎(chǔ)上，將提出的改進(jìn)型單點(diǎn)交叉算子［5］擴(kuò)展應(yīng)用到混合流水車間排序問題中，并測(cè)試該算子的求解性能。

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

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

符號(hào)和變量定義為:

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

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

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

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

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

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

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

式(4)和(5)表達(dá)了同一工序同一機(jī)器上不同工件加工順序約束，保證一臺(tái)機(jī)器在同一時(shí)刻只能加工一個(gè)工件;

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

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

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

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

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

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

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

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

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

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

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

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

2.2 改進(jìn)型交叉算子

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

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

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

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

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

3 實(shí)驗(yàn)分析

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

表1 工件在每臺(tái)機(jī)床上的加工時(shí)間

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

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

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

為了進(jìn)一步確認(rèn)算法的有效性，與兩個(gè)文獻(xiàn)中該案例的實(shí)驗(yàn)結(jié)果進(jìn)行比較，實(shí)驗(yàn)結(jié)果見表2。

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

表2 實(shí)驗(yàn)結(jié)果統(tǒng)計(jì)(10次運(yùn)算)

4 結(jié)語

將改進(jìn)型單點(diǎn)交叉算子擴(kuò)展應(yīng)用到混合流水車間排序問題中，并對(duì)其求解性能進(jìn)行測(cè)試。結(jié)果表明算法求解性能良好。

［1］唐立新，吳亞萍.混合流水車間調(diào)度的遺傳下降算法［J］.自動(dòng)化學(xué)報(bào)，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)仿真學(xué)報(bào)，2002，14(7):863 －869.

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

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

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

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

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