曲鵬舉

(貴州理工學院工程訓練中心，貴州 貴陽 550003)

0 引言

近年來，柔性作業(yè)加工已經在微電子、小批量零件等領域得到廣泛應用，柔性作業(yè)車間生產問題(flexible job-shop processing problem，F(xiàn)JPP) 也成為了制造領域重點研究的問題之一，柔性作業(yè)加工時間問題就是其中的關鍵。

粒子群算法由于參數(shù)少，操作簡單，已經廣泛應用于柔性加工問題中。顧幸生等[1]對柔性作業(yè)車間調度問題中的多個性能評價指標進行研究后，提出了改進博弈粒子群算法；Ismayilov等[2]為解決工作流多目標優(yōu)化問題，提出了一種基于預測的動態(tài)多目標進化算法；馬學森等[3]針對傳統(tǒng)粒子群算法求解云計算多目標任務調度的收斂速度慢、精度低的缺陷，提出一種優(yōu)化多目標任務調度粒子群算法(MOTS-PSO)；崔航浩等[4]針對以最小化最大完工時間為目標的MRC-FJSP，提出了一種帶隨機網絡的多種群粒子群優(yōu)化算法；張聞強等[5]針對多目標FJSP求解過程復雜、算法易陷入局部最優(yōu)的問題，提出了一種基于多區(qū)域采樣策略的混合粒子群優(yōu)化算法；張立果等[6]針對大多數(shù)算法求解多目標柔性作業(yè)車間調度問題時，所存在的穩(wěn)定性差、搜索深度不夠、無法對多目標中單一目標進行深入搜索的問題，對傳統(tǒng)遺傳算法做出改進，提出了一種求解多目標問題的雙層遺傳算法；Dong等[7]為解決傳統(tǒng)粒子群優(yōu)化(PSO)中的早熟收斂問題，提出了基于對立策略的的自適應變異粒子群優(yōu)化(AMOPSO)；胡志剛等[8]針對有效解決云環(huán)境中任務分配問題從而有效降低能耗，提出了一種改進的粒子群優(yōu)化算法。

貝塔分布作為統(tǒng)計學上的概率分布，在粒子群算法的優(yōu)化問題中的應用也逐漸增加。胡棠清等[9]為解決粒子群優(yōu)化算法中存在的早熟收斂、易陷入局部尋優(yōu)等問題，提出一種對慣性權重的非線性改進策略，構造了一種基于指數(shù)函數(shù)的慣性權重，并加入服從貝塔分布的隨機調整數(shù)，以實現(xiàn)對其動態(tài)調整；周蓉等[10]針對粒子群算法(PSO)易早熟收斂、逃離局部最優(yōu)能力差、精度低等缺點，提出一種基于灰狼優(yōu)化的反向學習粒子群算法，該算法非最優(yōu)粒子采用貝塔分布，提高其搜索效率和開采性能;黃洋等[11]提出了一種動態(tài)調整慣性權重的簡化均值粒子群優(yōu)化算法(DSMPSO)，該算法構造了一種基于余弦函數(shù)的慣性權重，并加入服從貝塔分布的隨機調整策略，以實現(xiàn)對慣性權重的動態(tài)調整，從而更好地平衡算法的全局和局部搜索能力；王勇亮等[12]在收斂因子和種群位置更新公式中引入三角函數(shù)和貝塔分布,提高了算法后期的收斂速度。

為了減少柔性作業(yè)加工時長，本文提出一種改進粒子群算法(β-PSO)。

1 問題描述及模型構建

1.1 柔性作業(yè)加工問題模型

柔性作業(yè)加工問題定義：已知有n個待加工工件，在m臺可用機器設備上進行加工，每個工件有m道工序需要加工，每個工件的加工工序以及加工耗時已知，在符合柔性作業(yè)加工時間問題約束條件下，使總體加工時間最短。

柔性作業(yè)加工時間問題模型描述如下：

a.待加工的工件集J={J1,J2,J3,…,Jn}，車間加工可使用機器集M={M1,M2,M3,…,Mm}，其中最大工件數(shù)為n，最大可用機器數(shù)為m。

b.每個工件加工工序不同、加工順序固定，工序集合P={Pi|P1,P2,P3,…,Pn}，{i|i=1,2,3,…,n}，Pi為編號為i的工件的所有工序，Pij為編號為i的工件的第j個工序。

c.STijk、Fijk、Cijk分別為工件i的第j道工序在k號機器的加工起始時間、加工結束時間與加工持續(xù)時間，其中{k|k=1,2,3,…,m}。

d.Tk為k號機器實際運行時間，F(xiàn)max為所有工件的全部工序完成的最后結束時間。

柔性作業(yè)加工時間的優(yōu)化目標是在接近實際生產的環(huán)境下，盡可能把各種機器、所有工件和所有工序做到合理分配，使Fmax全部工序完成的最后結束時間最短，確定的加工時間目標函數(shù)為

minFmax=min{maxTk}

(1)

1.2 柔性作業(yè)加工時間問題約束條件

在全部工序加工過程中，加工可使用機器可以為任意待加工工序提供支持。根據(jù)機器加工的工藝流程以及實際加工中各項工序的完成順序，特定的機器按照工藝流程、工藝卡片，同一時間只能進行某種工序的加工。在保證緊前工序完成之后，才能進行下一個加工時間的確立。因此，加工的約束必須滿足下列條件，即：

Fijk-Fi(j-1)k≥Cijk1

(2)

Fabk-Fijm≥Cabk

(3)

Fijm≥Cijk

(4)

式(2)表示所有工件的工序都需要消耗時間，必須按照特定的順序完成；式(3)表示機器不重復占用原則，任意1臺機器不能在同一時間內完成多個工序；式(4)表示加工持續(xù)時間的約束。

2 改進的粒子群算法

2.1 標準粒子群算法

粒子群優(yōu)化算法(particle swarm optimization，PSO)是一種典型的群體智能優(yōu)化算法。該算法因為編程簡單、參數(shù)且時間復雜度低而廣泛應用于眾多領域。標準的粒子群優(yōu)化算法位置和速度狀態(tài)屬性為：

(5)

(6)

2.2 粒子群算法參數(shù)的改進

2.2.1 粒子群算法慣性權重的改進

慣性權重對粒子群算法的收斂速度及收斂質量有重要影響，為了解決標準粒子群算法求解過程中收斂性緩慢、穩(wěn)定性低和易陷入局部最優(yōu)等缺點，慣性權重不應該是固定值，而應該隨著迭代次數(shù)的增加，前期有較大的慣性權重，加強全局尋優(yōu)能力，后期有較小的慣性權重，局部尋優(yōu)能力較強，所以本文提出慣性權重冪函數(shù)自適應調節(jié)方法，即

(7)

ωmax為慣性權重的最大值，ωmin為慣性權重的最小值，ωmax=0.95，ωmin=0.40；tmax為最大迭代次數(shù)；t為當前迭代次數(shù)。

2.2.2 粒子群算法隨機數(shù)的改進

標準粒子群算法中r1、r2為(0,1)內均勻分布的隨機數(shù)，而統(tǒng)計學中貝塔分布也是一個在[0,1]內連續(xù)分布的概率數(shù)，被廣泛應用于機器學習和數(shù)理統(tǒng)計學[13]。貝塔分布的概率密度函數(shù)為：

(8)

(9)

其中a>0,b>0。a、b取值不同，貝塔概率分布的圖像也不同。若a=b，函數(shù)關于x=0.5直線對稱；若a>b，圖像靠右側，相反靠左側。

根據(jù)式(7)、式(8)和式(9)改進后的粒子群算法公式為：

(10)

(11)

2.3 改進粒子群算法流程

改進粒子群算法流程如圖1所示：

a.按照柔性作業(yè)加工時間問題模型及約束條件式(1)～式(4)，構建數(shù)學模型。

b.初始改進粒子群算法迭代次數(shù)t=1，設定算法參數(shù)、位置邊界值和速度邊界值，包括粒子個數(shù)N、最大迭代次數(shù)tmax、初始粒子位置xi、初始粒子速度vi、位置邊界值xmax、速度邊界值vmax以及維數(shù)D。

c.按照粒子群算法慣性權重冪函數(shù)調節(jié)式(7)和貝塔分布隨機數(shù)式(8)、式(9)自適應改變參數(shù)ω(t)和r1、r2，根據(jù)速度公式(10)和位置式(11)進行迭代，計算粒子的適應度值，選出當前最優(yōu)解。

d.設定算法進化閾值k=10，若個體最優(yōu)值在一定迭代次數(shù)未發(fā)生變化，判定算法早熟，按照步驟c繼續(xù)進行更新。

e.判斷是否達到最大迭代次數(shù)tmax，若達到則輸出當前最優(yōu)值，若未達到，則迭代次數(shù)t+1，返回步驟c繼續(xù)迭代。

圖1 改進粒子群算法流程

3 仿真分析與案例驗證

為驗證改進粒子群算法(β-PSO)的性能，在Win7操作系統(tǒng)，配置計算機Intel(R) Core(TM) i5-3470 CPU @3.20 GHz，8 GB RAM，MATLAB(R2014a)環(huán)境下，選取Kacem算例[14],將β-PSO與標準粒子群算法(PSO)、余弦慣性權重改進粒子群算法(CPSO)[15]的仿真結果進行對比，結果如表1和表2所示。算法參數(shù)?。毫Ｗ尤毫Ｗ觽€數(shù)N=30，最大迭代次數(shù)tmax=600。最大時間差為各算例中，加工時間最長的算法與加工時間最短的算法的差值；最大偏差率為各算例中，最大時間差與最長加工時間的比值。最大時間差和最大偏差率反應了算法改進后的效果。

從表1 Kacem算例加工時間分析可知，隨著工件數(shù)n、機器數(shù)m的增加，加工時間隨之增長。標準PSO算法參數(shù)沒有進行改進，慣性權重采用固定值，隨機數(shù)采用(0,1)均勻分布，4個KACEM算例中,PSO算法的加工時間都是最長的，在第1個算例中，工件數(shù)n=6，機器數(shù)m=6，加工時間最長的是PSO算法，最短的是CPSO算法，最大時間差為4.2 s，β-PSO算法比加時間最短的CPSO算法多了0.2 s；在第2個算例中，工件數(shù)n=8，機器數(shù)m=8，加工時間最長的是PSO算法，最短的是β-PSO算法，最大時間差為6.7 s；在第3個算例中，工件數(shù)n=10，機器數(shù)m=10，加工時間最長的是PSO算法，加工時間為59.7 s，最短的是β-PSO算法，時間為47.4 s，最大時間差為12.3 s；在第4個算例中，工件數(shù)n=15，機器數(shù)m=10，加工時間最長的是PSO算法，加工時間為96.7 s，最短的是β-PSO算法，時間為74.2 s，最大時間差為22.5 s。在4個算例中，機器數(shù)與工件數(shù)較少的時候，β-PSO算法比CPSO算法加工時間略低，隨著機器數(shù)與工件數(shù)的增加，β-PSO算法在加工時間上相較其他2種算法的優(yōu)勢逐漸體現(xiàn)出來。

表1 Kacem算例加工時間對比

由表2可知，在Kacem03算例中，β-PSO算法最大偏差率為20.61%，CPSO算法最大偏差率為15.58%。β-PSO算法比CPSO算法降低了3 s，降低了5.95%。

表2 Kacem03算例各算法加工信息

β-PSO算法在迭代次數(shù)t=281次時尋得最優(yōu)解， 而CPSO在迭代次數(shù)t=376次、PSO在迭代次數(shù)t=484次時尋得最優(yōu)解，β-PSO算法與其他2種算法相比具有更好的尋優(yōu)性能。

4 結束語

針對柔性作業(yè)車間加工時間問題，本文提出β-PSO算法，該算法以最小加工時間為目標函數(shù)，慣性權重冪函數(shù)自適應調節(jié)，隨機數(shù)采用貝塔分布進行改進，提升算法的全局和局部搜索能力，可以有效改進標準粒子群算法求解過程中收斂速度慢、尋優(yōu)穩(wěn)定性差、易過早陷入局部最優(yōu)等。 選取Kacem經典調度算例，將β-PSO算法與PSO、CPSO算法仿真驗證，從最小加工時間、最大時間差和最大偏差率3個角度分析了β-PSO在求解Kacem算例的性能，驗證了β-PSO算法的在解決柔性作業(yè)車間加工時間問題上的優(yōu)越性。