曹 睿 侯向盼 金巳婷

（1.大連交通大學(xué) 大連 116028）（2.中車青島四方機(jī)車車輛股份有限公司 青島 266031）（3.沈陽鐵路局通信段 沈陽 110001）

1 引言

在柔性車間調(diào)度問題中，每一個(gè)部件中的每一道工序不止固定在一臺(tái)機(jī)器上，可根據(jù)具體情況選擇不同的機(jī)器加工，并且不同機(jī)器加工的時(shí)間有所不同，與傳統(tǒng)的車間調(diào)度相比更具有靈活性［1］。本次設(shè)計(jì)利用改進(jìn)的遺傳算法對(duì)柔性車間部件生產(chǎn)完工最大時(shí)間最短作為性能指標(biāo)，確立為目標(biāo)函數(shù)，對(duì)種群初始化和交叉變異部分進(jìn)行改進(jìn)，提高全局的搜索效率，通過實(shí)例說明改進(jìn)的遺傳算法對(duì)柔性車間的調(diào)度優(yōu)化問題有所改善［2］。

2 柔性作業(yè)車間調(diào)度問題及參數(shù)描述

多目標(biāo)柔性作業(yè)車間調(diào)度是指生產(chǎn)車間中在m臺(tái)設(shè)備｛M1，…Mn｝上加工n個(gè)工件｛1,…N｝，每個(gè)工件包含ni個(gè)事先確定加工順序的工序，每道工序可以在多臺(tái)設(shè)備上加工，每道工序不同的機(jī)器加工加工時(shí)間有所不同。本文主要考慮最大完工時(shí)間最短的性能指標(biāo)［3］，其目標(biāo)函數(shù)的建立如下：

調(diào)度目標(biāo)是為每道工序選擇合適的機(jī)器、確定每臺(tái)機(jī)器上各個(gè)工件工序的最佳加工順序以及開工時(shí)間，使得工件的最大生產(chǎn)周期最短。除此之外，在工件加工過程中還需要滿足下面的幾個(gè)約束條件：1）工件i在機(jī)器j上的加工時(shí)間需要大于0；2）工件i的加工時(shí)間必須在規(guī)定時(shí)間范圍內(nèi)；3）對(duì)于特定的工件i，機(jī)器j必須先于機(jī)器m對(duì)其進(jìn)行加工；4）任意工件的加工過程必須是連續(xù)封閉的［15］。

一個(gè)包含3個(gè)工件、5臺(tái)機(jī)器的FJSP的問題描述如表1所示。

表1 3個(gè)工件、5臺(tái)機(jī)器的柔性車間調(diào)度問題

3 算法設(shè)計(jì)

3.1 染色體編碼

柔性作業(yè)車間調(diào)度編碼由兩部分組成：一部分是基于機(jī)器分配的編碼，對(duì)應(yīng)機(jī)器選擇子問題，確定所選擇的加工機(jī)器；另一部分是基于工序的編碼，對(duì)應(yīng)工序先后加工的排序子問題，確定工序的先后加工順序［4］。

以3×5柔性車間調(diào)度問題為例說明，第一層對(duì)工序順序進(jìn)行編碼得到的加工序列：O11→O31→O21→O12→O22→O32→O23→O13，第二層編碼是基于機(jī)器的編碼可以獲得工序?qū)?yīng)的加工機(jī)器序列：M1→M3→M2→M3→M4→M5→M1→M2。

第一部分是所有工件加工時(shí)間

第二部分是機(jī)器在加工工件時(shí)的準(zhǔn)備時(shí)間

表示上一工件結(jié)束加工時(shí)的拖延時(shí)間

3.2 種群初始化

根據(jù)車間的具體情況，在M個(gè)可用機(jī)器中選擇k臺(tái)性能優(yōu)良、加工時(shí)間相對(duì)較短的機(jī)器作為一個(gè)小規(guī)模的初始群體，求出這k臺(tái)機(jī)器的平均加工時(shí)間tA，將剩下的( M-K)臺(tái)機(jī)器的加工時(shí)間tP與tA相比較，為保證初始種群的數(shù)量，根據(jù)實(shí)際情況設(shè)置一個(gè)tP與tA的差異范圍Q，即若 |tA-tP|∈Q，則保留，否則，該機(jī)器淘汰，這樣可以保證初始種群的適應(yīng)度，提高搜索效率。流程圖如圖1。

圖1 初始化流程圖

3.3 適應(yīng)值函數(shù)

在遺傳算法中，適應(yīng)度越高，被選擇的幾率就越大［8］。在本次設(shè)計(jì)中，將適應(yīng)度函數(shù)表示成目標(biāo)函數(shù)倒數(shù)的形式，即

其中min T表示目標(biāo)函數(shù)，即最小生產(chǎn)周期，這樣，當(dāng)生產(chǎn)周期T最小時(shí)，適應(yīng)度函數(shù)值最大，就表示這條加工路線的時(shí)間最短［6］。

3.4 選擇操作

首先將種群內(nèi)個(gè)體按適應(yīng)度大小從高至低排序，利用最優(yōu)個(gè)體保存法將父代中的最優(yōu)個(gè)體即適應(yīng)度最高的個(gè)體直接保留進(jìn)入到下一代［7］。

3.5 交叉操作

針對(duì)FJSP本文提出了兩種交叉操作，第一種是POX交叉操作［11］，用于染色體中工序的加工順序的交叉；第二種是節(jié)點(diǎn)交叉操作用于染色體工序分配的機(jī)器的交叉。

工序染色體的交叉過程：

P1和P2為父代，交叉后產(chǎn)生子代C1和C2。首先將所有的工件分成兩個(gè)集合J1和J2，子一代的染色體C1/C2繼承父代中J1/J2內(nèi)的工件對(duì)應(yīng)的基因，子一代剩余的部分基因由父代剔除了C1/C2中剩余的基因來補(bǔ)充［9］。

機(jī)器染色體的交叉過程：

采用節(jié)點(diǎn)交叉法，即將整個(gè)染色體的基因串均勻分成三部分，這樣在染色體上就會(huì)產(chǎn)生兩個(gè)基因位點(diǎn)，選取每個(gè)基因位點(diǎn)兩側(cè)相鄰的字符組成一個(gè)基因段進(jìn)行交叉，這樣既避免了基因交叉分布的不均勻性，又能提高全局搜索效率［14］。

3.6 變異操作

第一部分變異時(shí)，在機(jī)器染色體基因串中隨機(jī)選擇一個(gè)位置，在此工序的機(jī)器集中隨機(jī)選擇一個(gè)與它不相等的整數(shù)，替換當(dāng)前的基因［10］，這樣確保得到的解是可行解。

第二部分采用相鄰交換變異法，以一定的概率隨機(jī)選取兩個(gè)位置的相鄰基因串進(jìn)行交換，與交叉操作類似［13］。

3.7 終止條件

本次設(shè)計(jì)中，根據(jù)實(shí)際情況，采用設(shè)置最大迭代次數(shù)的方式來終止算法的執(zhí)行［12］。

4 仿真結(jié)果分析

表2是以6×6的柔性作業(yè)車間各工件不同工序加工時(shí)間表為例。

表2 6×6柔性作業(yè)車間各工件不同工序加工時(shí)間

圖2 問題收斂曲線圖

圖3 GA-A迭代曲線圖

圖4 GA-B迭代曲線圖

5 結(jié)語

通過圖2兩種遺傳算法GA-A與GA-B適應(yīng)度函數(shù)的收斂曲線圖可知，本次所設(shè)計(jì)的遺傳算法相對(duì)于傳統(tǒng)算法而言，能夠快速收斂，迅速搜索到最優(yōu)解，且能夠克服早熟現(xiàn)象，搜索有效穩(wěn)定；通過對(duì)

遺傳算法運(yùn)行的參數(shù)設(shè)置如下：種群初始規(guī)模S=60，交叉概率Pc=0.8，變異概率Pm=0.01，最大進(jìn)化代數(shù)X=50。將最小生產(chǎn)周期作為適應(yīng)度函數(shù)，并按上述所設(shè)置的控制參數(shù)，分別基于傳統(tǒng)遺傳算法（GA-A）與本次所設(shè)計(jì)的遺傳算法（GA-B）對(duì)上述實(shí)例進(jìn)行仿真，經(jīng)過Matlab多次運(yùn)行仿真后，仿真結(jié)果如圖2～4所示。比分析圖3GA-A與圖4GA-B兩種算法的迭代仿真圖像可知，本次所設(shè)計(jì)的遺傳算法GA-B在30代以內(nèi)便可收斂至最優(yōu)解，而傳統(tǒng)遺傳算法GA-A迭代至70代時(shí)才收斂至最優(yōu)解，說明算法GA-B在解決車間實(shí)際生產(chǎn)調(diào)度問題時(shí)更加有效。