景會成，王 穎

(華北理工大學 電氣工程學院，河北 唐山 063210 )

E-mail ：925683837@qq.com

1 引 言

柔性流水車間調(diào)度問題(Flexible Flow Shop scheduling，F(xiàn)FSP)是數(shù)字化車間首要解決的問題，是大量實際生產(chǎn)調(diào)度問題中最常見的簡化模型，是一類重要的組合優(yōu)化問題，已經(jīng)成為先進制造技術(shù)實踐的關(guān)鍵[1].FFSP問題可以被描述為一批工件需要經(jīng)過n道工序在m臺數(shù)控機床上進行加工，其中n道工序有一定的先后順序，m臺數(shù)控機床存在并行情況.由于實際生產(chǎn)過程中n、m的數(shù)值往往比較大，F(xiàn)FSP問題成為典型的NP-hard問題.目前針對于FFSP問題的解決方法有很多.韓忠華[2]等采用最優(yōu)個體集和自適應位置更新對蝙蝠算法進行優(yōu)化的方法對FFSP問題求解.畢孝儒[3]等采用混沌算子對人工群峰算法進行優(yōu)化的方法對FFSP問題求解.張海月[4]提出了模擬退火擾動(SADA)算法與NEH貪婪搜索算法結(jié)合后對粒子群算法進行優(yōu)化的方法對FFSP問題求解，上述文章都對經(jīng)典的算法進行了優(yōu)化，但依然存在著一個局部最優(yōu)和收斂速度之間的對立，若過于追求收斂速度，則可能限于局部最優(yōu)，為了防止局部最優(yōu)，必然會影響到收斂速度.本文針對FFSP問題提出了一種改進的遺傳算法，針對于傳統(tǒng)遺傳算法收斂速度慢的問題對未能直接進入下一代種群的剩余個體采用粒子群算法(PSO)，該算法能夠加快收斂速度.針對于傳統(tǒng)遺傳算法局部搜索能力弱容易限于局部最優(yōu)的問題在迭代過程引入模擬退火算法(SA)，該算法能夠概率性的跳出局部最優(yōu)解并最終趨于全局最優(yōu).改進后的遺傳算法能快速、高效的解決FFSP問題.

2 車間數(shù)學模型

車間共有m臺機床，機床號集M={M1，M2，M3，…，Mm}，令i∈{1，2，3，…，m}，則Mi表示機床號為i的機床.有n個待工件，待加工工件集N={N1，N2，N3，…，Nn}，令j∈{1，2，3，…，n}，則Nj表示第j個未加工工件.工藝路線集L={L1，L2，L3，…，Ll}，其中l(wèi)∈R.Nj可以在不同的Mi上加工，并且一旦開始加工便不能停止.Nj需要Oj道加工工序，工序順序集P={Pj1，Pj2，Pj3，…，PjOj}，令k∈{1，2，3，…，Oj}則Pjk表示Nj在第k道工序加工，Tjk記為Nj在第k道工序加工對應的加工時間，Sjk記為Nj在第k道工序加工對應的加工時間，STik記為Mi在第k道工序的起始加工時間，ETik記為Mi在第k道工序的加工結(jié)束時間.Cmax為車間排產(chǎn)調(diào)度的最大完成時間，Cj記為Nj所有工序加工完成時間.Cjk記為Nj在第k道工序的總完成時間.Cj的具體表達式：

(1)

其中

Cjk=Sjk+Tjk

(2)

目標函數(shù)

f=min{Cmax}=min{max(Cj)}j∈{1，2，3，…，n}

(3)

約束條件

Tj(k-1)≤Tjk(k≥1)

(4)

STik≥ETi(k-1)(k≥1)

(5)

公式(3)中f為最小完工時間，使Cmax達到最小即找出最優(yōu)的加工方案使總加工時間最小.k-1道工序的結(jié)束時間先于第k道工序的起始時間，保證工序的先后順序不變.Mi在第k-1道工序的加工結(jié)束時間先于Mi在第k道工序的起始加工時間，保證一臺機床只能加工一個工件.

3 PSO-GA算法改進

粒子群優(yōu)化算法最初是由Eberhart和Kennedy在1995 年提出的，是基于迭代的優(yōu)化方法，可用對復雜問題優(yōu)化求解[5]，粒子群里的個體(即粒子)代表問題的一個可能解，每個粒子具有位置和速度兩個特征，粒子通過位置來決定自身的適應度各個粒子記憶并追隨當前的最優(yōu)解.

把規(guī)定了行為規(guī)則的粒子作為個體，多個個體組合成為一個復雜的群體，便可用來對FFSP問題求最優(yōu)解.Xi=(xi1，xi1，…，xiD)記為第i個粒子的位置；Vi=(vi1，vi1，…，viD)記為第i個粒子的速度；Pg(k)=(pg1(k)，pg2(k)，…，pgD(k))記為經(jīng)過k次迭代后的粒子i的最優(yōu)位置；Pg(k)=(pg1(k)，pg2(k)，…，pgD(k))記為次迭代后的最優(yōu)粒子的位置.

vid(k+1)=ω·vid(k)+c1·r1·[pid(k)-xid(k)]+

c2·r2·[pgd(k)-xid(k)]

(6)

(7)

xid(k+1)=xid(k)+vid(k+1)

(8)

其中c1、c2為加速因子，ω為慣性因子，r1∈[0，1]、r2∈[0，1]、d∈[1，D]，D表示粒子群搜索空間的維數(shù).從上述公式可以看出PSO在迭代中期的收斂速度快、搜索效率高、精度高但在其他時期搜索效率低，在迭代后期更新速度幾乎趨近于0，容易陷于局部極值.最初由美國Michigan大學Holland教授于1975年首先提出來的遺傳算法(Genetic Algorithm，GA)，是通過對自然進化過程進行模擬來實現(xiàn)搜尋最優(yōu)解的一種方法[6].遺傳算法具有很強全局尋優(yōu)能力，尤其在迭代前期進化速度很快.這對于兩者的優(yōu)缺點很多學者提出了粒子群優(yōu)化遺傳算法對兩種算法進行優(yōu)勢互補.本文對文獻[7]中提出的PSO優(yōu)化遺傳算法進行了改進.

3.1 染色體編碼

在黃志清[8]等提出的雙層編碼的思路上，對工藝路線的工序數(shù)進行定量后對染色體進行編碼.基因Njlk表示工件Nj的l條工藝路線的k道工序.假設(shè)車間有4條工藝路線L1、L2、L3、L4，8個工件N1、N2、N3、N4、N5、N6、N7、N8進行加工.第一層編碼4-2-1-1-3-1-4-3，第二層編碼為1-1-3-5-3-8-1-7-8-5-2-4-2-6-2-8-6-2-4-3-7-8-5-2-8-5-5-4-2-6，其中工藝路線L1擁有3道工序，L2擁有6道工序、L3擁有5道工序、擁有2道工序.最終編碼為：

N141-N311-N531-N312-N831-N142-N741-N832-N532-N221-N411-N222-N611-N223-N833-N612-N224-N412-N313-N742-N834-N533-N225-N835-N534-N535-N413-N226-N613

3.2 適應度函數(shù)及選擇操作

適應度函數(shù)的選擇的原則是，適應度函數(shù)大于等于0，同向于優(yōu)化方向，并且一般在目標函數(shù)的基礎(chǔ)上進行變換.對完成時間進行去量綱處理后得到最大完工時間CTmax最小完工時間CTmin.適應度函數(shù)如公式(9)所示：

(9)

采用輪盤賭局的方式，根據(jù)Fit函數(shù)對個體的適應度進行計算，然后按照適應度值對應的選擇概率進行隨機選取，一直到選出滿足設(shè)定數(shù)量的個體數(shù)[9,10].

3.3 交叉和變異操作

交叉和變異操作的目的是產(chǎn)生新的個體保證種群的多樣性，其中遺傳算法的全局搜索能力由交叉操作控制，局部搜索能由變異操作決定.

交叉操作是對父代個體配對進行基因交換重組，產(chǎn)生新的個體，從而使更優(yōu)個體出現(xiàn)成為可能[11]，交叉因子pc1的取值對遺傳算法的收斂性有很大的影響，若pc1取值過小，進化緩慢不利于個體的優(yōu)勝劣汰，若pc1取值過大，新個體產(chǎn)生的速度加快但同時增大了個體迅速被破壞的風險.所以此次采用了自適應交叉因子.

保證最大適應度值與平均適應度值不相等時的基礎(chǔ)上，當前適應度值Fit(x)高于平均適應度值Fitavg時給pc0乘上一個小于1的數(shù)，減小交叉因子pc1的數(shù)值使優(yōu)秀個體能夠進入下一代.

(11)

變異操作是通過對個體內(nèi)部基因的更改產(chǎn)生新的個體，自適應變異操作公式與交叉操作類似.

4 模擬退火算法

模擬退火算法(Simulated Annealing，SA)最早的思想是由N.Metropolis[12]，通過賦予搜索過程一種時變且最終趨于0的概率突跳性，來有效的避免陷于局部極小并最終趨于全局最優(yōu)的串行結(jié)構(gòu)的優(yōu)化算法.將模擬退火算法應用于遺傳算法的迭代過程中加入SA判斷函數(shù)用來確定是否執(zhí)行SA操作，SA算法的步驟如下：

1)初始化參數(shù)設(shè)置：初始解S、初始溫度T、迭代次數(shù)L、循環(huán)計數(shù)器K；

2)Metropolis準則.增量ΔT=C(S′)-C(S)，C(S)為評價函數(shù)；

3)ΔT判斷.若T<0，S′變?yōu)楫斍敖猓籀≥0以概率exp(-ΔT/T)接受S′變?yōu)楫斍敖?

4)終止條件判定：根據(jù)經(jīng)驗若連續(xù)K個新解都沒有被選擇，那么當前解為最優(yōu)解輸出并結(jié)束.如果不滿足終止條件那么進行降溫操作.降溫公式為：

tW=γtW-1

(12)

5)重復上述步驟，完成對所有個體抽樣.

5 SA優(yōu)化改進PSO-GA算法

前期利用遺傳算法前期搜索效率高的優(yōu)勢產(chǎn)生初始種群，前期迭代次數(shù)所占總次數(shù)的百分比為GAΦ，中期利用粒子群算法收斂速度快的特點進行中期迭代，中期迭代次數(shù)所占總次數(shù)的百分比為PSOΦ，后期利用模擬退火算法來避免PSO-GA后期容易陷入局部極值的問題，后期迭代次數(shù)百分比為SAΦ，且PSOΦ+GAΦ+SAΦ=1.參數(shù)初始化時需要根據(jù)經(jīng)驗設(shè)定了GAΦ、PSOΦ、SAΦ的值.SA優(yōu)化PSO-GA算法以下簡稱SA-PSO-GA算法流程圖如圖1所示.

圖1 SA-PSO-GA算法流程圖

首先進行參數(shù)初始化設(shè)置并由遺傳算法產(chǎn)生一個初始種群，計算適應度函數(shù)對滿足條件的直接進入下一步，不滿足的通過PSO優(yōu)化之后進入下代種群.中期對種群選擇、交叉、操作等操作進行迭代，后期對符合SA判斷函數(shù)條件的進行模擬退火操作，不滿足的通過對舊種群與新種群合并成新的種群的再判斷是否滿足SA判斷函數(shù).進行適應值判斷后保存每代進化的最優(yōu)解直到輸出最終的最優(yōu)解.

6 生產(chǎn)車間調(diào)度實例仿真

贛州某機器人生產(chǎn)車間負責對6kg、8kg、12kg、20kg等多種型號的工業(yè)機器人本體件的加工工作.工業(yè)機器人本體由大臂、小臂、轉(zhuǎn)座、腕部、手部等組成.采用該公司提供的8kg機器人本體件，6個工件每個工件6道工序的數(shù)據(jù)進行排產(chǎn)實驗.定義8kg機器人型號對應的工藝路線l為0.表1所示為該公司應用案例中各工件加工時間.

表1 工業(yè)機器人本體加工車間部分工件加工時間(h)

對改進PSO-GA算法進行排產(chǎn)的初始粒子數(shù)為50、迭代次數(shù)150、pc0為0.85、pm0為0.35、γ為0.95.SA優(yōu)化PSO-GA算法進行排產(chǎn)的初始粒子數(shù)、迭代次數(shù)、pc0、pm0不變，模擬退火初始值500、模擬退火終值0，兩種算法對應甘特圖分別如圖2、圖3所示.甘特圖用jlk表示Njlk.

圖2 傳統(tǒng)PSO-GA算法對應甘特圖

圖3 SA-PSO-GA算法對應甘特圖

通過圖2和圖3可以看出，傳統(tǒng)PSO-GA算法甘特圖排產(chǎn)結(jié)果顯示48個小時可完成6個工件的生產(chǎn)，GA-PSO-SA算法甘特圖排產(chǎn)結(jié)果顯示46個小時即可完成生產(chǎn)任務，說明GA-PSO-SA算法排產(chǎn)實際效果優(yōu)于傳統(tǒng)PSO-GA算法.兩種算法的進化曲線圖如圖4所示.

圖4 進化曲線圖

從進化曲線圖可以看出傳統(tǒng)PSO-GA算法陷于局部最優(yōu)，所輸出的最優(yōu)解并不是實際的最優(yōu)解.并且運行結(jié)果顯示傳統(tǒng)PSO-GA算法運算時間一般為24-20S，SA-PSO-GA運算時間一般為19-16S.SA-PSO-GA算法達到預期效果，優(yōu)于傳統(tǒng)PSO-GA算法.

7 結(jié) 語

本文通過對通過對柔性流水車間調(diào)度的分析和模型的建立后，提出了一種新的SA-PSO-GA算法.SA-PSO-GA算法在迭代前期繼承GA算法前期搜索效率高的特點，在中期繼承PSO算法精度、搜索效率高的特點，在后期繼承SA算法的概率突跳性跳出局部極值的特點，最終達到快速、高效地得到全局最優(yōu)解的要求.通過實驗仿真比較，驗證了SA-PSO-GA算法的優(yōu)勢.