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

于 蒙 劉德漢

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

0 引 言

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

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

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

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

1.1 模型描述

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

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

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

1.2 模型評價(jià)指標(biāo)確立

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

(6)

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

(7)

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

(8)

綜合目標(biāo)評價(jià)函數(shù)f為

f=w1f1+w2f2

(9)

2 改進(jìn)PSO-GA算法設(shè)計(jì)

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

圖2 改進(jìn)PSO-GA算法流程圖

2.1 染色體編碼與解碼操作

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

2.2 適應(yīng)度計(jì)算

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

(10)

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

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

(11)

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

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

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

(12)

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

(13)

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

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

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

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

(14)

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

采用高斯變異法進(jìn)行變異操作，同樣仿照交叉過程設(shè)置自適應(yīng)變異因子.

(15)

2.5 非法解修正

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

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

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

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

3 實(shí)例驗(yàn)證及算法對比

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

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

為了更好的研究分析本文所設(shè)計(jì)的算法性能，進(jìn)行了遺傳算法、粒子群算法及改進(jìn)PSO-GA算法的仿真實(shí)驗(yàn).

3.1 參數(shù)設(shè)置

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

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

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

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

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

表4 不同算法評價(jià)指標(biāo)表

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

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

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

圖4 綜合目標(biāo)函數(shù)隨訓(xùn)練代數(shù)進(jìn)化圖

4 結(jié) 束 語

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

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