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

(1. 燕山大學河北省重型機械流體動力傳輸與控制重點實驗室， 河北秦皇島 066004; 2. 先進鍛壓成形技術與科學教育部重點實驗室(燕山大學)， 河北秦皇島 066004; 3. 燕山大學河北省工業(yè)計算機控制工程重點實驗室， 河北秦皇島 066004)

引言

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

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

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

1 改進的混合多作用力微粒群算法

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

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

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

(3)

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

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

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

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

(4)

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

(5)

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

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

(6)

(7)

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

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

(8)

動態(tài)權重wx可由式(9)求得：

(9)

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

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

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

2.1 液壓閥塊加工車間介紹

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

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

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

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

這里假設：工件一旦開始加工便不可中斷；1臺機器同一時刻只能加工1個閥塊；1個閥塊同一時刻只能在1臺機器上加工?？紤]各機器的調(diào)機時間，以完成n個閥塊加工的最大完成時間最小為目標，給出該閥塊加工車間調(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臺機器上的完成加工時間eijk與處理時間tijk可由式(17)、式(18)求得：

eijk=sijk+tijk

(17)

tijk=stijk+ptijk

(18)

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

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

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

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

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

1) 微粒編碼

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

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

(19)

表1 閥塊在各個機器上的加工時間 min

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

圖1 微粒編碼圖示

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

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

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

(20)

2) 微粒解碼

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

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

(21)

由矩陣B可得到各閥塊與機器的對應關系，例如，閥塊1的6道工序分別在機器1、3、4、8、10、11上加工；閥塊2的6道工序分別在機器1、3、6、8、10、12上加工。

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

(22)

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

(23)

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

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

(24)

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

3) 結果對比與分析

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

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

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

表2 優(yōu)化結果(最大完成時間)對比 min

3 結論

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