改進PSO-GA算法求解混合流水車間調(diào)度問題

于 蒙 劉德漢

(武漢理工大學物流工程學院 武漢 430063)

0 引 言

隨著現(xiàn)代制造企業(yè)生產(chǎn)規(guī)模和生產(chǎn)水平的不斷提高，帶了一系列的調(diào)度難題.如何通過科學而高效的手段安排生產(chǎn)計劃、利用現(xiàn)有資源提高工廠產(chǎn)能成為企業(yè)關(guān)注的熱點問題.混合流水車間調(diào)度(hybrid flow shop problem,HFSP)是車間調(diào)度領域中一個經(jīng)典問題，其廣泛存在于各流水式生產(chǎn)線.HFSP要求在每道工序加工機器不定的情況下，工件在加工之前就確定加工順序，這使得該問題比傳統(tǒng)的流水車間調(diào)度問題(flow shop problem,FSP)具有更高的復雜度.同時在調(diào)度過程中，企業(yè)不同的部門從各自的需求出發(fā)，對生產(chǎn)調(diào)度決策目標會有多樣化的要求，因此需要結(jié)合實際的生產(chǎn)情況和不同的需求，同時考慮多個目標進行優(yōu)化.

目前對多目標HFSP問題的研究主要集中在采用啟發(fā)式算法、元啟發(fā)式算法或多個元啟發(fā)式算法的混合算法求解不同的目標上.Arroyo等[1]較早的針對多目標流水車間調(diào)度問題提出了一種遺傳局部搜索算法；Kachitvichyanukul等[2]提出了一種兩階段的遺傳算法來求解多目標車間調(diào)度問題；張超勇等[3]基于遺傳算法對非支配排序進行了改進，并將算法應用于柔性流水車間優(yōu)化問題的求解；陳園園等[4]將PSO優(yōu)化GA算法應用到離散型流水車間調(diào)度的求解.HFSP領域的大量文獻表明當前該問題仍需針對不同的求解目標在算法上進行改進，而求解過程中，算法收斂速度與跳出局部最優(yōu)之間存在對立.

文中通過對汽車制造生產(chǎn)線進行調(diào)度優(yōu)化，將制約成本指標的機器負荷及制約效率指標的交貨拖期時間最短作為優(yōu)化目標建立了多目標優(yōu)化數(shù)學模型，并通過改進型PSO-GA算法作為全局優(yōu)化算法對一條典型汽車生產(chǎn)線進行了優(yōu)化，該算法提高了收斂速度并有著較好的跳出局部最優(yōu)的能力.

1 多目標混合流水車間調(diào)度模型建立

1.1 模型描述

混合流水車間是一類常見的制造環(huán)境，其模型示意見圖1，n個工件(J1,J2,…,Jn)需要在m道工序(Z1,Z2,…,Zm)上順序進行加工，每個工序有若干個并行的同速加工工位，工件在每個工位上加工時間不一定相同，工序間緩沖區(qū)無庫存限制，要求確定工件加工順序及其在并行機上是如何進行分配的，最終目標是使得模型滿足實際生產(chǎn)需求.

對混合流水車間做以下假設：①一臺機器同一時刻只對應一個工件的加工過程；②一個工件同一時刻不能在不同機器上加工；③每個工序的準備時間與順序無關(guān)，且直接計入加工時間中；④不考慮急件和故障等非確定因素.

圖1 混合流水車間示意圖

模型中涉及到的參數(shù)見表1.

表1 模型參數(shù)表

建立0-1混合整數(shù)規(guī)劃模型，主要約束條件如下.

i=1,2,…,n;j=1,2,…,m

(1)

i=1,2,…n;j=1,2,…m;r=l+1

(2)

Cij≤Biv

i=1,2,…n;j=1,2,…m-1;v=j+1 (3)

(4)

i,p=1,2,…,n;j=1,2,…,m;r=p+1 (5)

式(1)表示工件的一道工序只能由唯一一臺機器完成；式(2)表示工序不可中斷；式(3)表示工件下一工序的開始時間大于等于當前工序的結(jié)束時間；式(4)表示約束機器能力，確保任意時間在某工序加工的工件數(shù)不超過該工序并行機器數(shù)；式(5)表示一個工件選擇完機器后，下一個工件才能選擇.

1.2 模型評價指標確立

主要考慮的調(diào)度性能指標為機器負荷及總拖期時間.將每個工位的總加工時間與所在工序各機器平均總加工時間做方差，以此作為衡量機器負荷平衡的指標f1.

(6)

使用總拖期最小來代表交貨期的時間最短，作為另一個目標函數(shù)f2.

(7)

通過權(quán)向量w將多目標問題轉(zhuǎn)換為單目標，取

(8)

綜合目標評價函數(shù)f為

f=w1f1+w2f2

(9)

2 改進PSO-GA算法設計

遺傳算法(genetic algorithm,GA)是參照自然界優(yōu)勝劣汰進化法則而誕生的一種進化算法.遺傳算法的優(yōu)點在于優(yōu)良的全局搜索與并行搜索能力，對于大型復雜問題常常有很好的求解效果.粒子群算法(particle swarm optimization,PSO)是模仿自然界中鳥類尋找食物的過程而產(chǎn)生的一種算法，粒子群算法常常由于其粒子更新達到停滯狀態(tài)而容易陷入局部最優(yōu).遺傳算法在搜索精度與信息保留問題上有較多改善空間，且算法后期收斂速度上常常比較緩慢.為了克服兩者的缺點，利用粒子群算法收斂速度快、效率高的特點進行初步尋優(yōu)，再利用遺傳算法全局搜索的優(yōu)勢進行種群的篩選，并通過在遺傳算法的基礎上引入新參數(shù),動態(tài)地控制迭代交叉變異比，進而達到提高群體多樣性的目的.算法流程圖見圖2.

圖2 改進PSO-GA算法流程圖

2.1 染色體編碼與解碼操作

HSF問題常采用基于工序和機器的編碼方式，本文采用編碼的前半段確定工件加工的順序，比如,對于一個三個工件的FSP問題，13212132中第h(0

2.2 適應度計算

為了設計適應度函數(shù)，通過權(quán)向量將多目標問題轉(zhuǎn)換為單目標，并進行無量綱化處理.

(10)

式中：fi為不同目標函數(shù)，i為1或2時分別對應機器負荷指標及總拖期時間指標；fimin、fimax分別為初始種群中當前目標函數(shù)的最大與最小值.

適應度函數(shù)應同向于優(yōu)化方向，機器負荷越不均衡、總拖期時間越長時，均與優(yōu)化方向相反，故適應度函數(shù)設置為

(11)

2.3 粒子群尋優(yōu)操作

采用標準粒子群算法進行初步的搜索，粒子的速度更新、位置更新規(guī)則如下

vid(t+1)=w×vid(t)+c1×r1×

(12)

xid(t+1)=xid(t)+vid(t+1)

(13)

粒子群每次更新都舍棄不可行解，將部分較優(yōu)解保留并替代原種群中對應數(shù)目的較劣解.這一更新種群的方式稱為遷移，借鑒了生態(tài)學的概念[5].

2.4 遺傳算法尋優(yōu)操作

使用輪盤賭方式進行選擇操作，使Fit值越大的染色體保留的概率越大，隨機選取一定數(shù)量的染色體作為新的父代.同時引入精英保留策略，使一定比例的優(yōu)質(zhì)解直接進入下一代的迭代過程，以加快種群的收斂.

采用算數(shù)交叉法進行交叉操作，為了盡可能的避免交叉過程中進化速度過快或過慢導致的負面效應，定義自適應交叉因子.當適應度變化過大時，改變交叉因子的大小以保證整體進化的質(zhì)量.定義自適應交叉因子如式.

(14)

式中：Fitmax和Fitavg分別為群體的最大和平均個體適應度;Fit為父代兩個體適應度較大[6].

采用高斯變異法進行變異操作，同樣仿照交叉過程設置自適應變異因子.

(15)

2.5 非法解修正

基于工序編碼常常會帶來非法解，因此一次尋優(yōu)操作完成后后需要對更新后的粒子進行調(diào)整，設計了一種非法解的修正方法.步驟如下.

步驟1對編碼向下取整數(shù).

步驟2移除編碼中仍不合理的粒子

步驟3根據(jù)編碼規(guī)則對步驟二得到的編碼進行補完，隨機填入空白處得到修正后的最終編碼.

3 實例驗證及算法對比

為驗證本文改進PSO-GA算法性能，對某整車廠焊裝車間車前門線體數(shù)據(jù)進行了仿真測試.該條柔性流水線可以生產(chǎn)6種不同的車門，不同車型對應車門制造的標準工時有所差異，線體符合典型FSP模型，根據(jù)本文模型，以設備負荷均衡水平及總拖期時間為優(yōu)化指標進行實驗.線體共6個工序，每個工序有2～3個并行機.現(xiàn)對一批共6個不同的工件進行仿真實驗，工件加工工時見表2.

表2 工件加工時間表 單位:s

為了更好的研究分析本文所設計的算法性能，進行了遺傳算法、粒子群算法及改進PSO-GA算法的仿真實驗.

3.1 參數(shù)設置

參數(shù)的設置合理與否與問題規(guī)模有關(guān)，而且會對實驗結(jié)果有較大影響.遺傳算法與粒子群算法的參數(shù)設計見表3.

表3 改進PSO-GA算法參數(shù)表

結(jié)合大量仿真實驗結(jié)論[7]，本文所提出的改進粒子群-遺傳算法與基本遺傳算法、粒子群算法采用基本相同的參數(shù)，但是配置了不同的交叉因子和變異因子.交叉概率Pc取[0.6，0.9]，變異概率Pm取[0.05，0.1]，并根據(jù)改進粒子群-遺傳算法參數(shù)的取值范圍，重新配置了交叉因子、變異因子的自適應調(diào)整范圍—將精英種群的交叉因子、變異因子采用更小的調(diào)整范圍，以更好的保持優(yōu)秀個體.

3.2 實仿真結(jié)果分析

仿真實驗環(huán)境使用Matlab R2018a仿真軟件，lntel(R) Core(TM) i5-8400,2.80 GHz處理器，內(nèi)存為8.00 GB.共進行了20組實驗，實驗數(shù)據(jù)見表4，表中數(shù)據(jù)均已采用文獻[8]中的方法進行了無量綱歸一化處理.實驗中綜合目標函數(shù)考慮拖期時間與機器負荷均衡，其中拖期時間權(quán)重設置為0.7，機器負荷均衡權(quán)重設置為0.3.表中數(shù)據(jù)表明基本粒子群算法與遺傳算法均過早的收斂，所輸出的最優(yōu)解為局部最優(yōu)解.改進PSO-GA算法得到的為更優(yōu)解，相較于粒子群算法，綜合目標評價函數(shù)f的平均值改善了13.6%，相較于粒子群算法，綜合目標評價函數(shù)f平均值改善了10.9%.且改進PSO-GA算法的最差解與最優(yōu)解結(jié)果都好于另外兩種算法.

表4 不同算法評價指標表

粒子群算法及遺傳算法最優(yōu)解計算后所得到的工序分別為[3,5,2,6,4,1]及[2,5,3,6,4,1]，改進PSO-GA算法得到最優(yōu)解的加工順序為[4,5,2,6,3,1].通過圖3的改進PSO-GA算法最優(yōu)解甘特圖展示了機器分配情況，可以看到機器負荷較為均衡，其中工序1～6中各臺機器運轉(zhuǎn)負荷率為100%、100%、86.7%、90.0%、100%、97.4%、94.3%、89.7%、85.8%、100%、90.6%，各機器負荷差距較小且負荷率均超過75%時可以認為此生產(chǎn)線負荷較為合理.

圖3 實例調(diào)度結(jié)果甘特圖

三種算法最優(yōu)解的收斂曲線見圖4.通過收斂曲線可以看出，在達到收斂時，改進PSO-GA算法不僅在綜合評價指標上較優(yōu)，所需代數(shù)顯著少于其他兩種算法.

圖4 綜合目標函數(shù)隨訓練代數(shù)進化圖

4 結(jié) 束 語

本文通過對雙目標柔性流水車間調(diào)度問題進行建模與分析，對遺傳-粒子群算法進行了改進，算法在繼承了粒子群算法搜索速度快，效率高的特點，同時也具有遺傳算法全局搜索能力強的特點，并且在引入動態(tài)交叉變異參數(shù)后，能較好的提高種群多樣性，避免陷入局部極值的情況.

由于本文所使用的算例規(guī)模較小，當問題規(guī)模擴大時，改進PSO-GA算法收斂速度與精度還有待進一步驗證與提高.