改進的粒子群算法在多目標(biāo)車間調(diào)度的應(yīng)用

李　浩　畢　利　靳彬鋒

(寧夏大學(xué)　寧夏 銀川 750021)

0　引　言

車間調(diào)度問題(JSP)在生產(chǎn)管理和組合優(yōu)化等領(lǐng)域一向都是熱門問題[1]。車間調(diào)度問題在數(shù)學(xué)上已被證明是NP困難問題[2]。目前解決NP問題的方法主要有兩種：利用數(shù)學(xué)方法求最優(yōu)解，往往有整數(shù)規(guī)劃、動態(tài)規(guī)劃、分支定界法和回溯剪枝法等非智能算法；利用智能算法求解其近似解(如：遺傳算法、hopfield神經(jīng)網(wǎng)絡(luò)、禁忌搜索、模擬退火、蟻群算法和粒子群算法等[3])。求解JSP的方法通常是求解一組工件的工序在一組機器上的分派[4]，而FJSP一般指的是機器選擇問題和工序調(diào)度問題這兩個問題的集合，是JSP的一個擴展[5]。因為加入了機器選擇的考慮，因此FJSP較之JSP更加困難。在實際的生產(chǎn)環(huán)境下，F(xiàn)JSP更具有普適性，故FJSP具有重要的理論意義和研究意義。

近些年來，多目標(biāo)FJSP因為更切合制造業(yè)實際生產(chǎn)中的需求而引起眾多學(xué)者的關(guān)注，并衍生了多種用于處理FJSP的智能算法[6]。目前解決FJSP的方法有加權(quán)法和利用pareto優(yōu)化策略求解非劣解集。前者的處理過程是將不同的目標(biāo)函數(shù)賦值以不同的權(quán)重，從而使得多目標(biāo)問題轉(zhuǎn)換為單目標(biāo)問題后來進行求解；后者是在一組多個目標(biāo)之間折衷的均衡解，也就是非劣解，求解多目標(biāo)問題的關(guān)鍵就是找到數(shù)量足夠多的且分布均勻的又具有代表性的非劣解集[7-8]。Rim等[7]在針對FJSP時提出了分布式和并行的處理方式，并且得到了較好的實驗結(jié)果。Manas等[8]通過對粒子的不確定性來避免算法早熟，并證明QPSO算法的優(yōu)越性。

隨著時代的發(fā)展，離散車間制造業(yè)已逐漸轉(zhuǎn)型，向半自動和全自動發(fā)展，但是到目前為止，眾多學(xué)者在考慮離散制造業(yè)的車間調(diào)度問題時，還是會忽略加工工件的過程中的運輸時間，即不考慮加工機器到下一個加工機器的運輸時間問題。本文引入小車的概念，針對當(dāng)前離散車間制造業(yè)半自動化(或者自動化)的特點，用來描述離散車間制造業(yè)中的半成品運輸問題。

與遺傳算法[9]相比，二者都需要進行種群的初始化和選擇合適的適應(yīng)度函數(shù)來評價系統(tǒng)，但粒子群算法是根據(jù)自己的速度來決定搜索方向的，只和pbest和gbest有關(guān)。整個搜索過程是跟隨著當(dāng)前最優(yōu)解移動的過程，并且收斂于最優(yōu)解的速度更快[10]。與hopfield神經(jīng)網(wǎng)絡(luò)算法[11]相比，二者都有參數(shù)需要調(diào)整，但是PSO的結(jié)構(gòu)和參數(shù)更加簡單，因為參數(shù)數(shù)量少，所以調(diào)參更加容易。但是如果參數(shù)設(shè)置不合理會導(dǎo)致PSO收斂速度過慢或者在最優(yōu)解附近來回震蕩導(dǎo)致算法不收斂。同時PSO算法也存在著容易陷入局部最優(yōu)解和早熟等的不足。因此，本文采用變參數(shù)策略、交叉變異機制，提出基于變參的交叉變異粒子群算法CAPSO(Cross and Aberrance Particle Swarm Optimization)，來避免陷入局部最優(yōu)和早熟等問題。

1　FJSP多目標(biāo)優(yōu)化

1.1　FJSP描述

FJSP可以描述為：N個待加工工件在M臺機器上加工，每個待加工工件有多步工序，每道工序可以在多臺機器上加工，但是工序的前后順序有要求，每臺機器可以加工不同工件的不同工序，調(diào)度的目標(biāo)就是把待加工工件的加工工序合理地分配到各個機器上去，在滿足某些特定的約束條件的情況下使得車間調(diào)度的性能指標(biāo)最優(yōu)。

1.2　FJSP多目標(biāo)優(yōu)化模型

首先，F(xiàn)JSP需要滿足如下條件：

(1) 系統(tǒng)開始運行時，每臺機器都可以被使用。

(2) 系統(tǒng)開始運行時，任一待加工工件的第一步都可以被加工。

(3) 每種待加工工件的任一工序在可用機器上的加工時間是確定的。

(4) 每種待加工工件的加工工序是有先后順序的。

(5) 工件的加工時間應(yīng)當(dāng)包括該工件在機器上的準(zhǔn)備時間和加工時間。

(6) 在相同時間內(nèi)，每個待加工工件有且僅能在一臺可用機器上加工。

(7) 在相同時間內(nèi)，可用機器要么繼續(xù)閑置，要么最多只能加工待加工工件的一道工序。

(8) 從前一個加工機器運輸?shù)较乱粋€加工機器的運輸時間是確定的。

(9) 每個待加工工件的任何一道工序有且只有在前一道工序加工結(jié)束并且運輸?shù)较乱粋€機器上后，這一道工序才可以在可用機器上進行加工。

本文選取的三個目標(biāo)為：最大完工時間、最小成本和機器最大負荷。

(1) 最大完工時間：

minF1=min{max{maxcj}+cartime}

(1)

(2) 最小成本:

(2)

(3) 最大負荷：

(3)

其中：

F1：工件的完工時間；

F2：加工成本；

F3：機器負荷；

Cj：工件j的完工時間；

cartime：小車運輸時間;

CV:機器運轉(zhuǎn)成本;

CS:機器閑置成本;

tijk:工件i的第j道工序在機器k上的加工時間;

Xijk: 決策變量，表示工件J的第i道工序是否選擇在機器K上進行加工；Xijk=1表示機器k被選中，在機器K上進行加工；Xijk=0表示機器k未被選中；

T*:多次實驗獲得的完工時間的值；

FDK: 第K臺機器的動態(tài)耗費率；

FSk: 第K臺機器的靜態(tài)耗費率。

對最大完工時間、最小成本和最大負荷這三個目標(biāo)函數(shù)進行量綱歸一化處理：

(4)

(5)

1.3　約束條件

(1) 時間約束：

tijk≥0且ti0k=0

(6)

Stijk>0且Sti0k=0

(7)

Stij>0且Sti0=0

(8)

(2) 資源約束:

(9)

(3) 工序約束:

(10)

1≤j≤nj

(11)

1≤i≤n

(12)

1≤k≤m

(13)

(4) 費用約束:

FDk>0且FD0=0

(14)

FSk>0且FS0=0

(15)

2　CAPSO算法

2.1　編碼和解碼

本文采用工序和機器分別編碼的方式進行編碼[12]，例如:

Xi=[2 1 3 2 1 3 1 2 3 2 3 2 3 4 1 2 1 3 2 4]

即等價于：

Xprocess=[2 1 3 2 1 3 1 2 3]

Xmachine=[2 3 4 1 2 1 3 2 4]

式中：Xprocess代表的是加工工序，Xmachine代表的是對應(yīng)工序中所選擇的機器；Xprocess中“1”出現(xiàn)三次，表示工件1的加工工序一共有三步， “1”、“2”、“3”、“4”四個不同的數(shù)字出現(xiàn)表示一共有四種工件需要進行加工；Xprocess中“1”出現(xiàn)兩次，表示選擇機器1作為加工機器的工序一共有兩道；Xprocess中第一次出現(xiàn)的“1”表示工件1的第一道工序，對應(yīng)到Xmachine中的“3”，表示工件1的第一道工序選擇在機器3上進行加工，Xprocess中第二次出現(xiàn)的“1”表示工件1的第二道工序，對應(yīng)到Xmachine中的“2”，表示工件1的第二道工序選擇在機器2上進行加工，以此類推。

2.2　位置和速度的更新

在標(biāo)準(zhǔn)的PSO算法中，粒子在空間中搜索的速度和位置由式(16)和式(17)確定：

vt+1=w×vt+r1×rand()×(Pt-xt)+

r2×rand()×(Gt-xt)

(16)

xt+1=xt+vt

(17)

式中：w為慣性權(quán)重；r1、r2為加速常數(shù)；rand()為區(qū)間[0,1]上均勻分布的偽隨機數(shù)；Pt和Gt分別為t時刻粒子的自身最好位置和全局最好位置。Pt為粒子群自身飛過的最好位置，而Gt為粒子所對應(yīng)的全局最好位置，它是整個群體所經(jīng)歷的最好位置。Xt=(xt1,xt2,…,xtn)與Vt=(vt1,vt2,…,vtn)為時刻t的位置和速度。

2.3　算法的改進

粒子群算法的運行過程是由信息傳遞的作用導(dǎo)致的粒子運動位置的變化。在該過程中，粒子的搜索能力，包括全局搜索能力和局部搜索能力是由慣性權(quán)重w、加速常數(shù)r1和r2以及最大速度Vmax三種參數(shù)共同作用的結(jié)果。其中慣性權(quán)重w使粒子擁有慣性運動，從而使其有能力搜索未知的求解區(qū)域。最大速度Vmax決定當(dāng)前位置的解的效果的精度:若Vmax過大，粒子可能會飛過最優(yōu)解的范圍而來回震蕩；若Vmax過小，粒子不能跳出局部較好區(qū)間，導(dǎo)致其陷入局部最優(yōu)值。另外，加速常數(shù)r1和r2代表每個粒子靠近Pt和Gt位置的統(tǒng)計加速項的權(quán)重，若值過低會讓粒子的迭代速度過慢，容易進入局部最優(yōu)從而無法進入最優(yōu)解區(qū)域，反之則粒子有可能突然沖向或越過最優(yōu)解區(qū)域。因此，為了防止粒子陷入局部最優(yōu)，本文利用交叉算子令粒子可以跳出局部最優(yōu)。為了防止粒子沖過目標(biāo)區(qū)域，每迭代一定次數(shù)，將設(shè)置r1和r2縮小一定的倍數(shù)來使得粒子的步長降低，同時設(shè)置最大速度限制，若粒子速度超過最大速度則重新設(shè)置速度。

2.4　CAPSO算法流程圖及流程

圖1為CAPSO算法的流程圖。

圖1　CAPSO算法流程圖

具體步驟如下：

Step1初始化粒子群種群即隨機產(chǎn)生所有粒子的位置和速度并確定其pbest和gbest。

Step2將每個粒子的當(dāng)前位置與pbest進行比較，取較優(yōu)解作為新的gbest。

Step3將每個粒子的當(dāng)前位置與gbest進行比較，取較優(yōu)解作為新的gbest。

Step4若滿足變異條件則執(zhí)行變異操作，否則執(zhí)行Step5。

Step5更新粒子的速度和位置。

Step6判斷是否滿足終止條件，若滿足則終止算法，gbest為最優(yōu)解，若不滿足則返回Step2。

3　實驗結(jié)果

本文利用8×8的8工件8機器3工序的部分多目標(biāo)FJSP例子加以描述。具體加工時間見表1。

表1　8×8F JSP車間調(diào)度

同時給出小車在不同機器上的運輸時間，由于從自身到自身不需要運輸時間，為了方便表示，故對從自身到自身的運輸時間均為0。具體見表2。

表2　小車在8個機器間的運輸時間

我們得出的實驗結(jié)果見表3。從表3可以看出，CAPSO算法在解決離散車間制造業(yè)中多目標(biāo)車間調(diào)度問題時，其產(chǎn)生的非劣解集中解的個數(shù)明顯多于PSO算法和ACO算法。同時該算法在最大完工時間、最小成本和最大負荷均優(yōu)于PSO算法和ACO算法。

表3　不同算法結(jié)果的比較

觀察圖2-圖4，可以看出，CAPSO算法的非劣解相較之PSO算法和ACO算法來說，解的分布較集中、數(shù)量較多并且質(zhì)量高。

圖2　CAPSO算法的非劣解集

圖3　PSO算法的非劣解集

圖4　ACO算法的非劣解

4　結(jié)　語

隨著社會的發(fā)展和進步，離散車間制造業(yè)的自動化已是必然趨勢。本文正是基于此提出了“FJSP+小車”的思路來解決離散車間制造業(yè)自動化的實際問題。在傳統(tǒng)的PSO算法中引入了交叉變異因子來降低粒子陷入局部最優(yōu)的概率，同時通過對最大速度的限制和步長周期性的降低來使得粒子降低震蕩的頻率，并給出了CAPSO算法求解多目標(biāo)柔性車間調(diào)度的算法步驟和流程圖。經(jīng)過仿真實驗測試，驗證了本算法在FJSP中的有效性。

[1] 熊銳, 吳澄. 車間生產(chǎn)調(diào)度問題的技術(shù)現(xiàn)狀與發(fā)展趨勢[J]. 清華大學(xué)學(xué)報(自然科學(xué)版), 1998(10):55-60.

[2] 徐俊剛, 戴國忠, 王宏安. 生產(chǎn)調(diào)度理論和方法研究綜述[J]. 計算機研究與發(fā)展, 2004, 41(2):257-267.

[3] 楊開兵, 劉曉冰. 一種求解多目標(biāo)組合優(yōu)化的遺傳局部搜索算法[J]. 計算機應(yīng)用與軟件, 2009, 26(8):16-17,119.

[4] 何霆, 劉飛, 馬玉林,等. 車間生產(chǎn)調(diào)度問題研究[J]. 機械工程學(xué)報, 2000, 36(5):97-102.

[5] 侯曉莉, 劉永, 江來臻,等. 多目標(biāo)FJSP的一維編碼粒子群優(yōu)化求解方法[J]. 計算機工程與應(yīng)用, 2015, 51(13):47-51,71.

[6] 劉麗琴, 張學(xué)良, 謝黎明,等. 多目標(biāo)柔性作業(yè)車間調(diào)度的Pareto混合粒子群算法[J]. 中北大學(xué)學(xué)報(自然科學(xué)版), 2013(2):48-53.

[7] Zarrouk R, Ettouil M, Bennour I, et al. Towards an Embedded Distributed Implementations of PSO Solutions for the Flexible Job Shop Problem[J]. Procedia Computer Science, 2015, 73:146-153.

[8] Singh M R, Mahapatra S S． A quantum behaved particle swarm optimization for flexible job shopscheduling[J]． Computers and Industrial Engineering, 2016,93(C)：36-44.

[9] 張靜, 王萬良, 徐新黎,等. 混合粒子群算法求解多目標(biāo)柔性作業(yè)車間調(diào)調(diào)度度問題[J]. 控制理論與應(yīng)用, 2012, 29(6):715-722.

[10] 魏巍, 譚建榮, 馮毅雄,等. 柔性工作車間調(diào)度問題的多目標(biāo)優(yōu)化方法研究[J]. 計算機集成制造系統(tǒng), 2009, 15(8):1592-1598.

[11] 劉曉冰, 焦璇, 寧濤,等. 基于雙鏈量子遺傳算法的柔性作業(yè)車間調(diào)度[J]. 計算機集成制造系統(tǒng), 2015, 21(2):495-502.

[12] 彭建剛, 劉明周, 張璽,等. 基于Pareto優(yōu)化的離散自由搜索算法求解多目標(biāo)柔性作業(yè)車間調(diào)度問題[J]. 中國機械工程, 2015, 26(5):620-626.

[13] 王萬良, 吳啟迪. 基于Hopfield神經(jīng)網(wǎng)絡(luò)求解作業(yè)車間調(diào)度問題的新方法[J]. 計算機集成制造系統(tǒng), 2001, 7(12):7-12.

[14] 劉勝, 于海強. 基于改進遺傳算法的多目標(biāo)FJSP問題研究[J]. 控制工程, 2016, 23(6):816-822.