基于改進(jìn)混合作用力微粒群算法的液壓閥塊加工車間調(diào)度優(yōu)化

陳東寧， 彭曉靜， 姚成玉3， 張曉磊3， 楊曉榮

(1. 燕山大學(xué)河北省重型機(jī)械流體動(dòng)力傳輸與控制重點(diǎn)實(shí)驗(yàn)室， 河北秦皇島 066004; 2. 先進(jìn)鍛壓成形技術(shù)與科學(xué)教育部重點(diǎn)實(shí)驗(yàn)室(燕山大學(xué))， 河北秦皇島 066004; 3. 燕山大學(xué)河北省工業(yè)計(jì)算機(jī)控制工程重點(diǎn)實(shí)驗(yàn)室， 河北秦皇島 066004)

引言

車間調(diào)度是先進(jìn)制造系統(tǒng)的重要環(huán)節(jié)，直接影響企業(yè)的效益和競(jìng)爭(zhēng)力。車間調(diào)度指產(chǎn)品加工過(guò)程中，在最大限度滿足各種約束條件下，通過(guò)合理地安排各種資源及加工的先后順序，減少零件完工時(shí)間，從而提高企業(yè)車間的生產(chǎn)效率[1]。車間生產(chǎn)中，不合理的作業(yè)生產(chǎn)安排會(huì)導(dǎo)致不必要的生產(chǎn)能耗，因此，制定合理的調(diào)度方案顯得尤為重要[2]。近年來(lái)，微粒群算法在解決車間調(diào)度問(wèn)題中取得了較好的效果。微粒群(Particle Swarm Optimization, PSO)算法[3]作為一種高效智能優(yōu)化算法，憑借結(jié)構(gòu)簡(jiǎn)單、收斂速度快、參數(shù)設(shè)置少等優(yōu)點(diǎn)，成功應(yīng)用于各種復(fù)雜優(yōu)化問(wèn)題。例如，文獻(xiàn)[4]將提出的多作用力微粒群算法用于求解液壓閥塊加工車間調(diào)度問(wèn)題；文獻(xiàn)[5]利用改進(jìn)的二階微粒群算法優(yōu)化了具有空閑時(shí)間的車間調(diào)度問(wèn)題；文獻(xiàn)[6]針對(duì)柔性作業(yè)車間調(diào)度問(wèn)題，提出一種骨干雙粒子群算法。

PSO算法已成功解決各種車間調(diào)度問(wèn)題，但在作用力規(guī)則方面，標(biāo)準(zhǔn)PSO算法中僅考慮個(gè)體最優(yōu)微粒和全局最優(yōu)微粒的引力作用，易使算法陷入局部最優(yōu)。為此，許多學(xué)者從作用力方面對(duì)PSO算法進(jìn)行了改進(jìn)研究。例如，文獻(xiàn)[7]將微粒群分為多個(gè)子群，每個(gè)子群中適應(yīng)度最差的2個(gè)微粒與其他子群的微粒學(xué)習(xí)交流；文獻(xiàn)[8]算法初期充分發(fā)揮全局最優(yōu)解的領(lǐng)導(dǎo)能力，中后期利用隨機(jī)化均勻擾動(dòng)粒子改變?nèi)后w的作用力規(guī)則；文獻(xiàn)[9]將微粒僅受其他微粒吸引的作用方式，擴(kuò)展為微粒受比自身適應(yīng)值優(yōu)的微粒的吸引，同時(shí)受比自身適應(yīng)值劣的微粒的排斥；文獻(xiàn)[10]通過(guò)引入中間適應(yīng)度微粒的引力作用，為微粒逃離局部最優(yōu)解提供動(dòng)力。

綜上可見(jiàn)，上述改進(jìn)的PSO算法從避免算法早熟收斂、保證種群多樣性和提高收斂速度等某些側(cè)面進(jìn)行改進(jìn)，但這些算法僅考慮到單種的作用力規(guī)則，不能同時(shí)滿足種群多樣性和收斂速度的要求。為此，針對(duì)在不同的搜索階段采用不同的作用力規(guī)則，平衡算法全局探索性搜索和局部趨化性搜索能力，提出改進(jìn)混合多作用力微粒群(Improved Hybrid Force PSO,IHFPSO)算法，進(jìn)而將其用于液壓閥塊加工車間調(diào)度問(wèn)題，由所提算法優(yōu)化得到的閥塊加工順序和每道工序機(jī)器的分配情況，確定最佳的調(diào)度方案，解決基于人工排序產(chǎn)生的原有調(diào)度方案時(shí)間長(zhǎng)的問(wèn)題。

1 改進(jìn)的混合多作用力微粒群算法

IHFPSO算法的思想是：算法采用階段性搜索策略，將算法的搜索過(guò)程分為前期和后期2個(gè)搜索階段。在前期搜索階段，微粒受到所有個(gè)體最優(yōu)解的影響，同時(shí)考慮微粒受到的“吸引”和“排斥”作用，構(gòu)建微粒間作用的引斥力規(guī)則；在后期搜索階段，改變當(dāng)前微粒的學(xué)習(xí)對(duì)象，引入全局最優(yōu)解、個(gè)體最優(yōu)解的平均值對(duì)當(dāng)前微粒的吸引作用，同時(shí)構(gòu)造基于動(dòng)力加速度的引力規(guī)則，使微粒在雙作用力和引力提供的加速度的作用下進(jìn)行速度和位置的更新，滿足種群多樣性和收斂速度的要求，平衡算法的全局探索和局部搜索能力。

IHFPSO算法的速度和位置的更新公式為：

β(wx×[pavg-xid(t)]+(1-wx)×

cgrg[pgd(t)-xid(t)])

(1)

(2)

式中，vid(t+1)，vid(t)為微粒i第t+1代與第t代的第d維速度；xid(t+1)，xid(t)為微粒i第t+1代與第t代的第d維位置；pjd(t)為微粒j第t代個(gè)體最優(yōu)解的第d維位置；pgd(t)為第t代全局最優(yōu)微粒g的第d維位置；pavg為比微粒i適應(yīng)值好的個(gè)體最優(yōu)解的平均值；B(i)為個(gè)體最優(yōu)解比微粒i適應(yīng)值好的集合；W(i)為個(gè)體最優(yōu)解比微粒i適應(yīng)值差的集合；aid(t)為微粒i第t代第d維的動(dòng)力加速度；cj，cg為加速常數(shù)；rj，rg為(0, 1)區(qū)間內(nèi)相互獨(dú)立的隨機(jī)數(shù)；α，β為前、后期的切換系數(shù)；w為慣性權(quán)重；wx為動(dòng)態(tài)權(quán)重。

個(gè)體最優(yōu)解的平均值可由式(3)求得：

(3)

式中，pkd為微粒i鄰域微粒k的第d維的位置；K為微粒i鄰域微粒的個(gè)數(shù)；N(i)為微粒i鄰域微粒的集合。

在標(biāo)準(zhǔn)PSO算法中，微粒在個(gè)體經(jīng)驗(yàn)和群體經(jīng)驗(yàn)的指導(dǎo)下向更好的位置移動(dòng)，將速度更新公式中的個(gè)體認(rèn)知項(xiàng)和社會(huì)認(rèn)知項(xiàng)看作加速度項(xiàng)，為微粒的搜索提供動(dòng)力，則當(dāng)前微粒i第d維的動(dòng)力加速度aid(t)定義為：

aid(t)=rj(pid(t)-xid(t))+

rg(pgd(t)-xid(t))

(4)

慣性權(quán)重w可由式(5)求得：

(5)

式中，wmax為慣性權(quán)重值上限；wmin為慣性權(quán)重值下限；tmax為最大迭代次數(shù)。

算法前期、后期兩搜索階段的切換系數(shù)α，β可分別由式(6)、式(7)求得：

(6)

(7)

式中，γ為記錄搜索前期算法進(jìn)化停滯的次數(shù)；γmax為設(shè)置的算法進(jìn)化停滯次數(shù)閾值。

算法進(jìn)化停滯是指全局最優(yōu)微粒的適應(yīng)度在連續(xù)若干代內(nèi)不發(fā)生變化，γ由式(8)計(jì)算得到：

(8)

動(dòng)態(tài)權(quán)重wx可由式(9)求得：

(9)

式中，tx為算法前期向后期切換的迭代次數(shù)。

在算法搜索后期，隨著迭代次數(shù)的增大，動(dòng)態(tài)權(quán)重wx線性遞減，全局最優(yōu)解的吸引作用線性增大，既強(qiáng)化了算法的局部搜索能力，又能有效降低微粒陷入局部最優(yōu)的概率。

2 液壓閥塊加工車間調(diào)度優(yōu)化

2.1 液壓閥塊加工車間介紹

某公司液壓閥塊加工車間主要為動(dòng)力站中的泵站單元和閥臺(tái)單元提供用于安裝各種液壓元件并實(shí)現(xiàn)各元件油路連通的閥塊。該閥塊加工車間第1道工序有1臺(tái)鋸床，用于完成坯料的落料；第2道工序由兩臺(tái)銑床來(lái)完成各加工面的粗銑；第3道工序有1個(gè)臥式數(shù)控加工中心，能夠完成批量閥塊的所有閥孔和孔道的加工，有3臺(tái)搖臂鉆床，能夠完成劃線和除特殊閥孔以外的閥孔加工；第4道工序有2臺(tái)去刺機(jī)，可完成各閥孔棱角倒鈍、去毛刺的工作；第5道工序有1個(gè)立式數(shù)控加工中心對(duì)閥塊的安裝面進(jìn)行精銑；第6道工序有2臺(tái)打碼機(jī)，可完成閥塊出口處打鋼印的工作。

該調(diào)度方案依據(jù)各機(jī)器的加工能力和現(xiàn)場(chǎng)經(jīng)驗(yàn)，采用人工排序的方法產(chǎn)生，其調(diào)度指標(biāo)(最大完成時(shí)間)Cmax=525 min。

2.2 閥塊加工車間調(diào)度優(yōu)化模型

由上述車間介紹可知，該液壓閥塊加工車間調(diào)度問(wèn)題屬于混合流水車間調(diào)度問(wèn)題(Hybrid Flow-shop Scheduling Problem,HFSP)，HFSP可描述為：n個(gè)工件要經(jīng)過(guò)S道工序以完成加工，每道工序至少有1臺(tái)機(jī)器進(jìn)行加工且至少有1道工序存在并行機(jī)，同1道工序上各機(jī)器的處理性能有所不同，工件要經(jīng)過(guò)所有工序的加工，但各工件的每道工序可在任意1臺(tái)并行的機(jī)器上加工，已知工件在各工序相應(yīng)機(jī)器上的處理時(shí)間，確定工件的加工順序和每道工序機(jī)器的分配，使得調(diào)度指標(biāo)最小。

這里假設(shè)：工件一旦開(kāi)始加工便不可中斷；1臺(tái)機(jī)器同一時(shí)刻只能加工1個(gè)閥塊；1個(gè)閥塊同一時(shí)刻只能在1臺(tái)機(jī)器上加工?？紤]各機(jī)器的調(diào)機(jī)時(shí)間，以完成n個(gè)閥塊加工的最大完成時(shí)間最小為目標(biāo)，給出該閥塊加工車間調(diào)度優(yōu)化模型為：

minCmax=max{C1,C2, …,Cn}

(10)

約束條件由式(11)～式(16)給出：

(11)

(12)

(13)

eijk≤sij+1k′

i=1, 2, …,n;j=1, 2, …,S-1;

k=1, 2, …,mj;k′=1, 2, …,mj+1

(14)

i=1, 2, …,n;l=1, 2,…,n-1;

k=1, 2,…,m1

(15)

l1,l2=1, 2,…,n;l1≤l2;

j=1, 2, …,S;k,k′=1, 2, …,mj

(16)

閥塊i第j道工序在第k臺(tái)機(jī)器上的完成加工時(shí)間eijk與處理時(shí)間tijk可由式(17)、式(18)求得：

eijk=sijk+tijk

(17)

tijk=stijk+ptijk

(18)

式(10)～式(18)中，Ci為閥塊i的加工完畢時(shí)間；n為閥塊總數(shù)；Cmax為完成n個(gè)閥塊加工的最大完成時(shí)間；xil為取值為1或0的常數(shù)，若閥塊i在第l個(gè)位置上加工為1，否則為0；yijk為取值為1或0的常數(shù)，若閥塊i的工序j在k臺(tái)機(jī)器上為1，否則為0；mj為階段j的機(jī)器數(shù)；S為階段總數(shù)；sijk為閥塊i第j道工序在第k臺(tái)機(jī)器上的開(kāi)始加工時(shí)間；stijk為閥塊i第j道工序在第k臺(tái)機(jī)器上的調(diào)機(jī)時(shí)間;ptijk為閥塊i第j道工序在第k臺(tái)機(jī)器上的加工時(shí)間。

上述調(diào)度優(yōu)化模型中，式(11)、式(12)確保了同一時(shí)刻機(jī)器與閥塊間的一一對(duì)應(yīng)；式(13)使得每道工序每個(gè)閥塊只能在1臺(tái)機(jī)器上加工；式(14)表示同一閥塊不同工序間的先后制約關(guān)系；式(15)完成了第1道工序上調(diào)度排列中排位越前的閥塊開(kāi)始加工時(shí)間越早；式(16)實(shí)現(xiàn)了分配在同一機(jī)器上的閥塊排位靠后的必須等靠前的加工完畢才可進(jìn)行加工，當(dāng)處于不同位置的閥塊不在同道工序的同一機(jī)器上加工時(shí)，L為數(shù)值較大的常數(shù)以保證不等式恒成立。

2.3 液壓閥塊加工車間調(diào)度IHFPSO優(yōu)化

采用IHFPSO算法求解液壓閥塊加工車間調(diào)度問(wèn)題。首先，利用矩陣變量來(lái)處理約束條件，對(duì)微粒進(jìn)行編碼；然后，利用IHFPSO算法不斷地搜索并更新全局最優(yōu)解；最后，對(duì)微粒進(jìn)行解碼，求得最優(yōu)的調(diào)度方案。

現(xiàn)有8個(gè)閥塊要加工，每個(gè)閥塊均需經(jīng)過(guò)6道工序：落料、粗銑、鉆、去毛刺、精銑、打鋼印，閥塊在各機(jī)器上的加工時(shí)間如表1所示。

1) 微粒編碼

利用矩陣對(duì)微粒進(jìn)行編碼，矩陣的元素來(lái)表示機(jī)器，矩陣元素的位置關(guān)系來(lái)表示優(yōu)化模型中工序間的約束關(guān)系，為了擴(kuò)大微粒的搜索空間，采取隨機(jī)產(chǎn)生實(shí)數(shù)的編碼方法，以均等的機(jī)會(huì)選擇機(jī)器。

假設(shè)加工需要S道工序的n個(gè)閥塊，每道工序的機(jī)器數(shù)為mj(j=1, 2, …,S)，對(duì)所有機(jī)器按照加工工序依次排序編號(hào)，可構(gòu)造一個(gè)編碼矩陣AS×n為：

(19)

表1 閥塊在各個(gè)機(jī)器上的加工時(shí)間 min

對(duì)微粒進(jìn)行編碼：每個(gè)微粒由S個(gè)小段組成，每個(gè)小段包括n個(gè)數(shù)值，每個(gè)微粒對(duì)應(yīng)一個(gè)可行的調(diào)度方案。采用圖示的方式描述自變量aji與位置矢量Xi的元素之間的對(duì)應(yīng)關(guān)系，如圖1所示。

圖1 微粒編碼圖示

根據(jù)上述微粒編碼方法，對(duì)于該液壓閥塊加工車間調(diào)度優(yōu)化問(wèn)題，自變量aij與位置矢量Xi的元素之間的對(duì)應(yīng)關(guān)系如圖2所示。

圖2 該液壓閥塊微粒編碼圖示

采用IHFPSO算法求解該液壓閥塊加工車間調(diào)度問(wèn)題，其參數(shù)設(shè)置為：種群規(guī)模N=20、函數(shù)維數(shù)n=8×6=48、最大迭代次數(shù)tmax=500、慣性權(quán)重w=0.9～0.4、加速常數(shù)cj=cg=1.49。則微粒i經(jīng)過(guò)500代搜索后得到一個(gè)編碼矩陣A為：

(20)

2) 微粒解碼

采用矩陣的解碼方式，得到選擇機(jī)器矩陣；然后將液壓閥塊在各機(jī)器上的加工時(shí)間生成加工時(shí)間矩陣，按照閥塊的加工排序規(guī)則，得到完成時(shí)間矩陣。對(duì)式(20)的編碼矩陣A進(jìn)行解碼。

(1) 將編碼矩陣A中各個(gè)元素分別向下取整得矩陣B為：

(21)

由矩陣B可得到各閥塊與機(jī)器的對(duì)應(yīng)關(guān)系，例如，閥塊1的6道工序分別在機(jī)器1、3、4、8、10、11上加工；閥塊2的6道工序分別在機(jī)器1、3、6、8、10、12上加工。

將6×8的矩陣B擴(kuò)充為12×8的選擇機(jī)器矩陣S，基于各閥塊選擇機(jī)器的情況，置相應(yīng)行(表示機(jī)器)的元素為0或1，0表示沒(méi)有選擇該機(jī)器，1表示選擇該機(jī)器。由此可得到選擇機(jī)器矩陣S為：

(22)

(2) 為表示閥塊在其對(duì)應(yīng)加工機(jī)器上的使用時(shí)間，根據(jù)選擇機(jī)器矩陣S，結(jié)合表1中各閥塊在各機(jī)器上的加工時(shí)間，得到加工時(shí)間矩陣Tt，它表示各閥塊的各道工序在其選擇的機(jī)器上的加工時(shí)間：

(23)

(3) 根據(jù)閥塊加工順序規(guī)則，由加工時(shí)間矩陣可確定同一機(jī)器上閥塊的加工先后順序。機(jī)器1加工閥塊8、6、7、2、1、5、3、4的第1道工序；機(jī)器2加工閥塊6、7、5、4的第2道工序；機(jī)器3加工閥塊8、2、1、3的第2道工序；機(jī)器4加工閥塊1的第3道工序；機(jī)器5加工閥塊6、3的第3道工序；機(jī)器6加工閥塊8、2、5的第3道工序；機(jī)器7加工閥塊7、4的第3道工序；機(jī)器8加工閥塊6、2、7、1、5、4的第4道工序；機(jī)器9加工閥塊8、3的第4道工序；機(jī)器10加工閥塊6、8、2、7、1、5、4、3的第5道工序；機(jī)器11加工閥塊8、7、1、3的第6道工序；機(jī)器12加工閥塊6、2、5、4的第6道工序。

根據(jù)閥塊加工順序規(guī)則和加工時(shí)間矩陣Tt生成各閥塊在所選機(jī)器上的完工時(shí)間矩陣Tz：

(24)

矩陣Tz中元素表示的是相應(yīng)閥塊各道工序在所選機(jī)器上完成加工的時(shí)間，所以矩陣中元素最大的數(shù)即為微粒所表示調(diào)度方法的最大完成時(shí)間，即Cmax=414 min。

3) 結(jié)果對(duì)比與分析

將IHFPSO算法用于求解該液壓閥塊加工車間調(diào)度問(wèn)題，并與車間原有調(diào)度方案以及PSO算法、MPSO(中值導(dǎo)向微粒群)算法[10]、EPSO(擴(kuò)展微粒群)算法[9]、MFPSO(多作用力微粒群)算法[4]的運(yùn)行結(jié)果進(jìn)行對(duì)比，以驗(yàn)證所提算法的有效性。令PSO算法、MPSO算法、EPSO算法與IHFPSO算法的參數(shù)設(shè)置相同，MFPSO算法的參數(shù)設(shè)置中，切換因子t1為50、t2為350，其余參數(shù)與IHFPSO算法的參數(shù)設(shè)置相同。上述5種算法獨(dú)立運(yùn)行10次的優(yōu)化曲線見(jiàn)圖3，所得優(yōu)化結(jié)果見(jiàn)表2。

圖3 5種算法的優(yōu)化結(jié)果曲線

由圖3和表2可知，IHFPSO算法所得結(jié)果最優(yōu)，所得的最優(yōu)調(diào)度方案縮短了最大完成時(shí)間，故所提的IHFPSO算法是有效、可行的，在車間加工時(shí)采用該調(diào)度方案，根據(jù)閥塊的加工順序和每道工序機(jī)器的分配情況，對(duì)各閥塊進(jìn)行加工，可提高液壓閥塊加工車間的生產(chǎn)效率，也有助于實(shí)現(xiàn)節(jié)能減排、節(jié)約成本。

表2 優(yōu)化結(jié)果(最大完成時(shí)間)對(duì)比 min

3 結(jié)論

為平衡算法的全局和局部搜索能力，提出了改進(jìn)混合多作用力微粒群(IHFPSO)算法，采用階段性搜索策略，將算法的搜索過(guò)程分為2個(gè)搜索階段。在搜索前期，同時(shí)考慮微粒受到的“吸引”和“排斥”作用，構(gòu)建微粒間作用的引斥力規(guī)則。在搜索后期，引入全局最優(yōu)解、個(gè)體最優(yōu)解的平均值對(duì)當(dāng)前微粒的吸引作用，同時(shí)構(gòu)造基于動(dòng)力加速度的引力規(guī)則，滿足搜索后期收斂速度的要求，提高算法的尋優(yōu)能力。將IHFPSO算法用于求解液壓閥塊加工車間調(diào)度問(wèn)題，并與車間原有調(diào)度方案以及標(biāo)準(zhǔn)微粒群、中值導(dǎo)向微粒群、擴(kuò)展微粒群、多作用力微粒群算法進(jìn)行了對(duì)比，結(jié)果表明，提出的IHFPSO算法結(jié)果最優(yōu)，實(shí)現(xiàn)液壓閥塊加工車間調(diào)度優(yōu)化。