改進(jìn)粒子群算法在柔性作業(yè)加工時(shí)間問題研究

曲鵬舉

(貴州理工學(xué)院工程訓(xùn)練中心，貴州 貴陽 550003)

0 引言

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

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

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

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

1 問題描述及模型構(gòu)建

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

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

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

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

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

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

d.Tk為k號(hào)機(jī)器實(shí)際運(yùn)行時(shí)間，F(xiàn)max為所有工件的全部工序完成的最后結(jié)束時(shí)間。

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

minFmax=min{maxTk}

(1)

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

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

Fijk-Fi(j-1)k≥Cijk1

(2)

Fabk-Fijm≥Cabk

(3)

Fijm≥Cijk

(4)

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

2 改進(jìn)的粒子群算法

2.1 標(biāo)準(zhǔn)粒子群算法

粒子群優(yōu)化算法(particle swarm optimization，PSO)是一種典型的群體智能優(yōu)化算法。該算法因?yàn)榫幊毯唵?、參?shù)且時(shí)間復(fù)雜度低而廣泛應(yīng)用于眾多領(lǐng)域。標(biāo)準(zhǔn)的粒子群優(yōu)化算法位置和速度狀態(tài)屬性為：

(5)

(6)

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

2.2.1 粒子群算法慣性權(quán)重的改進(jìn)

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

(7)

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

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

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

(8)

(9)

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

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

(10)

(11)

2.3 改進(jìn)粒子群算法流程

改進(jìn)粒子群算法流程如圖1所示：

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

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

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

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

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

圖1 改進(jìn)粒子群算法流程

3 仿真分析與案例驗(yàn)證

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

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

表1 Kacem算例加工時(shí)間對(duì)比

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

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

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

4 結(jié)束語

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