陳東寧　張瑞星　姚成玉　茜彥輝

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

求解液壓閥塊加工車間調(diào)度的多作用力微粒群算法

陳東寧1,2張瑞星1,2姚成玉3茜彥輝1,2

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

為有效地解決液壓閥塊加工車間調(diào)度問題，考慮工序間和機器間的約束關(guān)系,以最大完成時間最小為目標(biāo)，給出了液壓閥塊加工車間調(diào)度優(yōu)化模型。為平衡算法的全局和局部搜索能力,提出了多作用力微粒群(MFPSO)算法，采用多作用力階段性搜索策略，將搜索過程劃分為前期、中期、后期3個階段,并對應(yīng)構(gòu)造單一斥力、平衡引斥力、單一引力3種作用力規(guī)則,在不同搜索階段采用不同的作用力規(guī)則,提高了算法的搜索機制和尋優(yōu)性能。將MFPSO算法用于求解液壓閥塊加工車間調(diào)度問題,利用矩陣變量來處理約束條件,給出了一種基于矩陣的微粒編碼、解碼方法。通過液壓閥塊加工車間調(diào)度優(yōu)化實例，將MFPSO算法與微粒群算法、中值導(dǎo)向微粒群算法、擴展微粒群算法、蟻群算法進行了對比,結(jié)果表明,提出的MFPSO算法結(jié)果最優(yōu)，從而驗證了該算法的有效性。

液壓閥塊加工車間調(diào)度;微粒群算法;作用力規(guī)則;MFPSO算法

0　引言

生產(chǎn)調(diào)度本質(zhì)上屬于復(fù)雜的優(yōu)化問題,具有大規(guī)模、非線性、強約束、多極值、多目標(biāo)等復(fù)雜性。高效的優(yōu)化技術(shù)與調(diào)度方法的研究與應(yīng)用,是提高生產(chǎn)效率和經(jīng)濟效益的核心環(huán)節(jié)。優(yōu)化技術(shù)與調(diào)度方法可以歸結(jié)為3種類型:精確求解算法[1]、啟發(fā)式方法[2]和基于人工智能的方法[3]。

近年來基于人工智能的方法憑借其漸進式尋優(yōu)、并行式搜索、適者生存式進化、通用性強、易于與其他算法結(jié)合等優(yōu)勢，備受學(xué)者的青睞,并被應(yīng)用于解決調(diào)度問題，其中常用的智能算法包括蟻群(ant colony optimization,ACO)算法[4]、微粒群(particle swam optimization,PSO)算法[5]、遺傳算法[6]、差分進化算法[7]等。其中,PSO算法作為一種高效的群體智能優(yōu)化算法,已成功應(yīng)用于求解各種生產(chǎn)調(diào)度問題,但它存在易陷入局部最優(yōu)、出現(xiàn)早熟等不足。

微粒間的作用力決定了微粒速度的方向和大小，是平衡微粒全局和局部搜索的關(guān)鍵因素。標(biāo)準(zhǔn)PSO算法的作用力規(guī)則中僅考慮個體最優(yōu)微粒和全局最優(yōu)微粒對當(dāng)前微粒的引力,這是導(dǎo)致算法陷入局部最優(yōu)的內(nèi)在缺陷,因此,一些學(xué)者從以下4個側(cè)面對PSO算法的作用力規(guī)則進行了改進:①調(diào)整引力大小。例如，采用線性遞減的慣性權(quán)重策略、基于模糊規(guī)則動態(tài)調(diào)整慣性權(quán)重的策略來調(diào)整微粒間引力大小[8]；引入收縮因子概念，根據(jù)微粒適應(yīng)度來動態(tài)改變收縮因子大小，從而改變當(dāng)前微粒所受的引力大小[9]；動態(tài)調(diào)整加速因子[10];將自適應(yīng)理論與PSO算法結(jié)合,自適應(yīng)地調(diào)整慣性權(quán)重,從而調(diào)整個體最優(yōu)微粒和全局最優(yōu)微粒對當(dāng)前微粒的引力大小[11]。②增添引力。例如，同時考慮個體最優(yōu)微粒和具有壽命周期的全局最優(yōu)微粒對當(dāng)前微粒的引力[12];添加當(dāng)代最優(yōu)微粒對當(dāng)前微粒的引力[13];考慮中間適應(yīng)度微粒對當(dāng)前微粒引力的中值導(dǎo)向PSO(median-oriented PSO,MPSO)算法[14];考慮距離當(dāng)前微粒最近的微粒的引力[15];將標(biāo)準(zhǔn)PSO算法中個別微粒對當(dāng)前微粒的引力擴展為所有個體最優(yōu)微粒的引力[16]。③增添斥力。例如,引入種群多樣性函數(shù)[17];根據(jù)種群多樣性自適應(yīng)改變?nèi)肿顑?yōu)微粒的引力和斥力[18];考慮適應(yīng)度變差的微粒對當(dāng)前微粒的斥力[19]。④增添引力和斥力。例如,擴展PSO(extended PSO,EPSO)算法將個體最優(yōu)和全局最優(yōu)微粒對當(dāng)前微粒的引力擴展為所有微粒對當(dāng)前微粒的引力、斥力[20]。

上述算法可從避免算法早熟收斂、保證種群多樣性、提高收斂速度和搜索精度等某些側(cè)面改進PSO算法的性能，但這些算法僅考慮單種作用力規(guī)則，使微粒間的作用機制相對單一，不能同時兼顧對算法的種群多樣性、收斂速度等性能要求。為此,本文考慮在不同搜索階段采用不同的作用力規(guī)則，豐富微粒間的作用力，平衡算法的全局和局部搜索能力,提出多作用力PSO(multi force PSO,MFPSO)算法，進而將其用于求解液壓閥塊加工車間調(diào)度問題，以尋找最佳的調(diào)度方案。

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

1.1液壓閥塊加工工藝

某公司液壓閥塊加工車間主要為動力站中的泵站單元和閥臺單元提供用于安裝各種液壓元件并實現(xiàn)各元件油路連通的閥塊，這些動力站廣泛應(yīng)用于生產(chǎn)加工和制造業(yè)中,如冶金、礦山、船廠等重工業(yè)設(shè)備，垃圾回收及處理設(shè)備，機床、壓力機、水利工程、紙漿和造紙機械等。為整套設(shè)備提供動力源的液壓動力站能夠安全平穩(wěn)地工作，是這些設(shè)備安全、可靠運行的基礎(chǔ),因此對動力站中液壓閥塊的加工質(zhì)量和工藝控制有較高的要求。該加工車間有鋸床1臺、銑床3臺(含數(shù)控銑床1臺)、鉆床4臺(含數(shù)控鉆床1臺)、去刺機2臺、打碼機2臺。為實現(xiàn)上述液壓閥塊的加工工藝性要求，該公司制訂了其特有的液壓閥塊加工工藝流程，每個閥塊均需經(jīng)過6道工序加工：落料、粗銑、鉆、去毛刺、精銑、打鋼印，如圖1所示。

圖1　液壓閥塊加工工藝流程

該車間還設(shè)有專門的液壓閥塊裝配區(qū)域,從而形成了液壓閥塊從加工到裝配的生產(chǎn)流水線。該車間加工的液壓閥塊最長達2500 mm，最重達5 t,并能夠保證液壓閥塊所需的加工工藝要求。

1.2調(diào)度優(yōu)化模型

該液壓閥塊加工車間調(diào)度問題具有流水作業(yè)特征,同時工序2、3、4、6上存在并行機加工的特點,由此可見,該問題屬于混合流水車間調(diào)度問題(hybrid flow-shop scheduling problem,HFSP)。HFSP可描述為：nM個工件要經(jīng)過s道工序以完成加工,每道工序至少有一臺機器進行加工且至少有一道工序存在并行機器，同一道工序上各機器的處理性能可相同也可不同，各工件的每道工序可在任意一臺并行的機器上加工，已知工件在各工序相應(yīng)機器上的處理時間，要求確定所有工件的排序以及每道工序上機器的分配情況，使得調(diào)度指標(biāo)(這里取為最大完成時間)最小。

結(jié)合現(xiàn)場工藝作如下假設(shè)：工件一旦開始加工便不可中斷；一臺機器同一時刻只能加工一個閥塊；一個閥塊同一時刻只能在一臺機器上加工；在并行加工工藝階段，閥塊可在并行機器的任意一臺機器上加工?？紤]各機器的調(diào)機時間，以完成nM個閥塊加工的最大完成時間最小為目標(biāo),給出該閥塊加工車間調(diào)度優(yōu)化模型如下：

(1)

(2)

(3)

(4)

u=1,2，…,s

(5)

v=1,2,…,nM;u=1,2,…,s-1

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

(6)

v=1,2,…,nM;l=1,2,…,nM-1;k=1,2,…,m1

(7)

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

u=1,2,…,s;k,k′=1,2,…,mu

其中

(8)

(9)

(10)

(11)

上述調(diào)度優(yōu)化模型中,式(2)和式(3)確保了每個優(yōu)先級位置與閥塊間一一對應(yīng);式(4)使得對于每道工序每個閥塊只能在一臺機器上加工；式(5)表示了同一閥塊不同工序間的先后制約關(guān)系；式(6)表示第一道工序上調(diào)度排列中排位越前的閥塊開始加工時間越早；式(7)實現(xiàn)了同道工序分配在同一機器上的閥塊排位靠后的必須等靠前的加工完成后才可進行加工,當(dāng)處于不同位置的閥塊不在同道工序的同一機器上加工時，L數(shù)值較大以保證不等式恒成立。

2　多作用力微粒群算法

多作用力微粒群(MFPSO)算法的基本思想如下:采用多作用力階段性搜索策略，將搜索過程劃分為前期、中期、后期3個階段，考慮微粒間作用力，借鑒擬態(tài)物理學(xué)中的引斥力思想，分別構(gòu)造單一斥力、平衡引斥力、單一引力3種作用力規(guī)則，在不同搜索階段采用不同的作用力規(guī)則，通過計算當(dāng)前微粒所受的作用力，更新微粒的速度和位置，根據(jù)微粒的適應(yīng)度更新個體最優(yōu)微粒和全局最優(yōu)微粒。

前期,考慮微粒間的排斥作用，構(gòu)造單一斥力的作用力規(guī)則，使微粒受所有微粒的斥力作用，以增強微粒群的種群多樣性，提高算法的全局搜索能力；中期，同時考慮微粒間的吸引和排斥作用，構(gòu)造平衡引斥力的作用力規(guī)則，使微粒受到比其適應(yīng)度好的個體最優(yōu)微粒的引力和比其適應(yīng)度差的個體最優(yōu)微粒的斥力作用,以保持微粒群的種群多樣性，平衡算法的全局和局部搜索能力；后期，考慮全局最優(yōu)微粒的吸引作用,構(gòu)造單一引力的作用力規(guī)則，使微粒向全局最優(yōu)微?？拷?，以增強算法的局部搜索能力，提高收斂速度。

2.13種作用力規(guī)則的構(gòu)造

假設(shè)在n維搜索空間中,微粒群的種群規(guī)模為N,對于任意微粒i(i=1,2,…,N),第t代微粒i的位置矢量為Xi(t)=(xi1(t),xi2(t),…,xi n(t)),速度矢量為Vi(t)=(vi1(t),vi2(t),…,vi n(t)),其個體最優(yōu)微粒的位置矢量為Pi(t)=(pi1(t),pi2(t),…,pi n(t));對于整個微粒群,第t代全局最優(yōu)微粒g的位置矢量為Pg(t)=(pg1(t),pg2(t),…,pg n(t))。

(1)單一斥力的作用力規(guī)則。微粒j對微粒i的斥力為

xi d(t)-xj d(t)j∈N

(2)平衡引斥力的作用力規(guī)則。比微粒i適應(yīng)度好的個體最優(yōu)微粒對微粒i的引力為

pj d(t)-xi d(t)j∈Bi(t)

比微粒i適應(yīng)度差的個體最優(yōu)微粒對微粒i的斥力為

xid(t)-pjd(t)j∈Wi(t)

其中

Bi(t)={j|f(Pj(t))

Wi(t)={j|f(Pj(t))≥f(Xi(t))?j∈N}

(3)單一引力的作用力規(guī)則。全局最優(yōu)微粒g對微粒i的引力為

pg d(t)-xid(t)

上述相關(guān)變量中,xj d(t)為第t代微粒j的第d維位置;pj d(t)為第t代微粒j的個體最優(yōu)微粒的第d維位置;Bi(t)為第t代比微粒i適應(yīng)度好的個體最優(yōu)微粒的集合;Wi(t)為第t代比微粒i適應(yīng)度差的個體最優(yōu)微粒的集合;f(·)為適應(yīng)度函數(shù);pgd(t)為第t代全局最優(yōu)微粒g的第d維位置。

2.2微粒的速度和位置更新

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

(12)

xid(t+1)=xid(t)+vid(t+1)

(13)

式中,vid(t)為第t代微粒i的第d維速度;w為慣性權(quán)重;α、β、γ為前期、中期、后期3階段搜索的切換系數(shù)；cj、cg為加速常數(shù);rj、rg為(0,1)區(qū)間互相獨立的隨機數(shù)。

慣性權(quán)重w可由下式求得:

(14)

式中,wmax為慣性權(quán)重的最大值;wmin為慣性權(quán)重的最小值;tmax為最大迭代次數(shù)。

前期、中期、后期3個階段搜索的切換系數(shù)α、β、γ可分別由下式求得：

(15)

(16)

(17)

式中,t1為前期向中期搜索切換時的切換因子;t2為中期向后期搜索切換時的切換因子。

(a)基于單一斥力的前期搜索

(b)基于平衡引斥力的中期搜索

(c)基于單一引力的后期搜索圖2　MFPSO算法微粒迭代更新的過程

圖2對MFPSO算法中微粒迭代更新的過程進行了形象的描述。圖2a～圖2c分別為MFPSO算法結(jié)合微粒速度更新公式(式(12))和位置更新公式(式(13))進行前期、中期、后期搜索的加權(quán)求和示意圖。微粒的移動方向由兩部分組成：①微粒i自身原有的速度Vi(t),并由慣性權(quán)重w決定其相對重要性;②其他微粒j(j=1,2,…,i-1,i+1,…,N)對微粒i的作用力:基于單一斥力的前期搜索時,微粒i受到的作用力為其他微粒j的斥力Xi(t)-Xj(t)的矢量和;基于平衡引斥力的中期搜索時,微粒i受到的作用力為比自身適應(yīng)度好的個體最優(yōu)微粒j(j∈Bi(t))的引力Pj(t)-Xi(t)和比自身適應(yīng)度差的個體最優(yōu)微粒j(j∈Wi(t))的斥力Xi(t)-Pj(t)的矢量和;基于單一引力的后期搜索時,微粒i受到的作用力為全局最優(yōu)微粒g的引力Pg(t)-Xi(t)。作用力的相對重要性由對應(yīng)的加速常數(shù)c和隨機數(shù)r決定。

2.3切換因子對MFPSO算法的影響

由于本文所提的MFPSO算法的特征是基于不同作用力規(guī)則的階段性搜索,因此,不同的切換因子t1和t2會影響各作用力在算法的整個搜索過程中所占比重，進而影響算法的尋優(yōu)性能。為尋求一組較好的切換因子，首先，測試每一種作用力單獨作用下，算法出現(xiàn)進化停滯時的迭代次數(shù)；然后,根據(jù)上述測試出的迭代次數(shù)t與最大迭代次數(shù)tmax的關(guān)系來設(shè)置幾組切換因子,通過測試分析來確定一組相對最佳的切換因子。

本文選取表1所示的8個被廣泛應(yīng)用于評價優(yōu)化算法性能的標(biāo)準(zhǔn)測試函數(shù)，測試每一種作用力規(guī)則單獨作用下算法的尋優(yōu)能力，參數(shù)設(shè)置如表2所示，在每種作用力下算法獨立運行30次。測試發(fā)現(xiàn)，基于單一斥力規(guī)則、平衡引斥力規(guī)則、單一引力規(guī)則，算法分別在t=0.1tmax、t=0.3tmax、t=0.3tmax代時進化已出現(xiàn)停滯現(xiàn)象。為使3個搜索階段能夠充分發(fā)揮作用,選取3組切換因子t1、t2進行測試:①t1=0.4tmax、t2=0.7tmax,加強前期搜索作用,增強種群多樣性;②t1=0.1tmax、t2=0.7tmax,加強中期搜索作用,平衡全局和局部搜索;③t1=0.1tmax、t2=0.4tmax,加強后期搜索作用,提高收斂速度。再次進行標(biāo)準(zhǔn)測試函數(shù)測試,算法運行30次求平均值和標(biāo)準(zhǔn)差,3組切換因子下MFPSO算法的優(yōu)化結(jié)果如表1所示,表中數(shù)字右上方標(biāo)有“*”的數(shù)值為對應(yīng)數(shù)據(jù)的最優(yōu)值。由表1可知,t1=0.1tmax、t2=0.7tmax時,對于大多數(shù)測試函數(shù)而言,MFPSO算法所得的結(jié)果相對最優(yōu)。這表明，在考慮到前期、后期搜索作用的同時增強中期搜索，可以使MFPSO算法性能較優(yōu)。

表1　不同切換因子下MFPSO算法的優(yōu)化結(jié)果

表2　參數(shù)設(shè)置

2.4MFPSO算法的執(zhí)行步驟

MFPSO算法的流程如圖3所示。

(1)初始化微粒群。隨機初始化微粒的速度和位置,即微粒群中每個微粒的每一維速度和位置分別在[vmin,vmax]和[xmin，xmax]區(qū)間內(nèi)隨機產(chǎn)生;計算微粒的適應(yīng)度;確定任意微粒j(?j∈N)的個體最優(yōu)微粒和全局最優(yōu)微粒g。

(2)基于單一斥力的前期搜索。計算所有微粒對當(dāng)前微粒i的斥力,利用式(6)和式(7)更新微粒的速度和位置;計算微粒的適應(yīng)度;更新任意微粒j的個體最優(yōu)微粒和全局最優(yōu)微粒g。

(3)判斷前期搜索是否結(jié)束,若迭代次數(shù)t

(4)基于平衡引斥力的中期搜索。計算比微粒i適應(yīng)度好的個體最優(yōu)微粒對當(dāng)前微粒i的引力和比微粒i適應(yīng)度差的個體最優(yōu)微粒對當(dāng)前微粒i的斥力，利用式(6)和式(7)更新微粒的速度和位置;計算微粒的適應(yīng)度；更新任意微粒j的個體最優(yōu)微粒和全局最優(yōu)微粒g。

(5)判斷中期搜索是否結(jié)束,若迭代次數(shù)t

(6)基于單一引力的后期搜索。計算全局最優(yōu)微粒g對當(dāng)前微粒i的引力,利用式(6)和式(7)更新微粒的速度和位置;計算微粒的適應(yīng)度;更新任意微粒j的個體最優(yōu)微粒和全局最優(yōu)微粒g。

(7)判斷終止條件,若t=tmax,則執(zhí)行(8),否則返回(6)。

(8)輸出優(yōu)化結(jié)果。

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

采用MFPSO算法求解液壓閥塊加工車間調(diào)度問題。首先,利用矩陣變量來處理約束條件，對微粒進行編碼；然后,利用MFPSO算法不斷地搜索并更新全局最優(yōu)解;最后,對微粒進行解碼,求得最優(yōu)的調(diào)度方案。編碼，即微粒位置的表示方式，本文利用矩陣來對微粒進行編碼，用列表示液壓閥塊，用行表示工序，利用矩陣的元素來表示機器,利用矩陣元素的位置關(guān)系來表示工序間的約束關(guān)系，為了擴大微粒的搜索空間以求得最優(yōu)解，采取隨機產(chǎn)生實數(shù)的編碼方法，以均等的機會選擇機器。由于微粒在速度-位置的迭代過程中是連續(xù)的，為避免產(chǎn)生非法解，本文采取了一種特殊的解碼方式，得到選擇機器矩陣，然后利用液壓閥塊在各機器上加工時間的數(shù)據(jù)表生成加工時間矩陣，按照一定的加工排序規(guī)則，得到完成時間矩陣。利用PSO算法以最大完成時間為適應(yīng)度函數(shù)，進行迭代尋優(yōu)最終產(chǎn)生使得該流水線加工完成時間最短的調(diào)度方案及其甘特圖。

3.1問題描述

現(xiàn)有8個液壓閥塊要加工，每個閥塊均需經(jīng)過6道工序加工：落料、粗銑、鉆、去毛刺、精銑、打鋼印，各機器按照工序順序依次編號，液壓閥塊在各機器上的加工時間見表3。采用MFPSO算法求解,以合理地分配每道工序的機器,確定同一臺機器上各閥塊加工的順序，尋求完成所有閥塊加工的最大完成時間最小的最優(yōu)調(diào)度方案。

表3　液壓閥塊在各機器上的加工時間　min

3.2編碼矩陣A

假設(shè)要加工nM個閥塊,每個閥塊都要依次經(jīng)過s道加工工序,每道工序的機器數(shù)為mu(u=1,2,…,s),對所有機器按照加工工序依次排序編號,可構(gòu)造一個s×nM維的編碼矩陣A：

(18)

根據(jù)上述編碼方法對微粒進行編碼:每個微粒由s個小段組成,每個小段包括nM個數(shù)值,每個微粒的長度為s×nM,從而形成了nM個閥塊完成s道工序的一個調(diào)度方案。以元素au v為自變量,微粒i的位置矢量Xi可表示為

Xi=(x1,x2,…,xnM,xnM+1,xnM+2,…,x2nM,…,

x(s-1)nM+1,x(s-1)nM+2,…,xsnM)=

(a11,a12,…,a1nM,a21,a22,…,

a2nM,…,as1,as2,…,asnM)

它對應(yīng)著一個編碼矩陣A,代表了一個可行的調(diào)度方案。

采用圖示的方式描述微粒編碼中自變量auv與位置矢量Xi的元素xi之間的對應(yīng)關(guān)系，如圖4所示。

圖4　微粒編碼圖示

對于上述液壓閥塊加工車間調(diào)度問題,采用MFPSO算法進行求解,其參數(shù)設(shè)置如下:種群規(guī)模N=20,函數(shù)維數(shù)n=8×6=48,最大迭代次數(shù)tmax=500,切換因子t1=50、t2=350,慣性權(quán)重wmin=0.4、wmax=0.9,加速常數(shù)cj=cg=1.49。微粒不斷地搜索并更新全局最優(yōu)解,則經(jīng)過500代搜索后得到全局最優(yōu)解,其編碼矩陣A如下：

(19)

有編碼必有解碼,要得到最優(yōu)的調(diào)度方案,需對上述編碼矩陣A進行解碼,解碼過程分為兩步:首先,對編碼矩陣A取整,并生成選擇機器矩陣S;其次,按照先來先加工的規(guī)則，確定閥塊的加工順序，并生成完成時間矩陣TC。

3.3選擇機器矩陣S

對式(19)的編碼矩陣A中各個元素au v分別向下取整,得到矩陣B：

(20)

由編碼矩陣A可知,矩陣B中的行表示各工序,列表示要加工的閥塊,根據(jù)各工序上的機器編號規(guī)則,由矩陣B的列可得到各閥塊與機器的對應(yīng)關(guān)系,例如,第1列的含義為：閥塊1的6道工序分別在機器1、2、5、8、10、11上加工;第2列的含義為：閥塊2的6道工序分別在機器1、2、6、9、10、12上加工。然后，將6行(6道工序)8列(8個閥塊)的矩陣B按列擴展成12行(12個機器)8列的選擇機器矩陣S,根據(jù)各閥塊在相應(yīng)工序是否選擇了該機器置矩陣中相應(yīng)元素的值為1或0,1表示選取該機器,0表示未選取,例如，根據(jù)矩陣B的第1列,將選擇機器矩陣S第1列的第1、2、5、8、10、11行取1,其余各行取0,依次類推,得到選擇機器矩陣S:

(21)

3.4完成時間矩陣的生成

3.4.1加工時間矩陣TP

將表3閥塊在各機器上的加工時間表示為矩陣T:

(22)

為提取各閥塊在其實際使用機器上的加工時間,屏蔽沒有實際使用的機器,將矩陣T與選擇機器矩陣S點乘得到加工時間矩陣TP:

(23)

它表示了各閥塊的各道工序在其選擇的機器上的加工時間。

3.4.2確定閥塊的加工順序

按照先來先加工的規(guī)則,確定閥塊的加工順序。當(dāng)出現(xiàn)int(au v)=int(au z)且v≠z時,表明閥塊v和z在同一臺機器上加工同一道工序u,這時,如果是第一道工序(u=1),則按照元素a1v的升序來加工閥塊;如果不是第一道工序(u>1),則根據(jù)每個閥塊的前一道工序完成時間的早晚來確定其加工順序，前一道工序先完成的閥塊先加工;如果完成時間相同,則也按照au v的升序來加工。

根據(jù)上述閥塊加工順序規(guī)則,可確定同一機器上閥塊的加工先后順序如下：機器1加工閥塊6、8、2、7、4、5、1、3的第1道工序；機器2加工閥塊8、2、5、1的第2道工序；機器3加工閥塊6、7、4、3的第2道工序；機器4加工閥塊7、5的第3道工序；機器5加工閥塊8、4、1的第3道工序；機器6加工閥塊6、2的第3道工序；機器7加工閥塊3的第3道工序；機器8加工閥塊6、7、1、3的第4道工序;機器9加工閥塊8、2、4、5的第4道工序；機器10加工閥塊6、8、2、7、4、5、1、3的第5道工序；機器11加工閥塊6、8、4、5、1的第6道工序；機器12加工閥塊2、7、3的第6道工序。

3.4.3完成時間矩陣TC

根據(jù)閥塊加工順序規(guī)則，結(jié)合式(23)所示的加工時間矩陣TP，生成閥塊在所選機器上完成相應(yīng)工序加工的完成時間矩陣TC：

(24)

3.5結(jié)果對比

將MFPSO算法用于求解該液壓閥塊加工車間調(diào)度問題,并與車間實際調(diào)度方案(依據(jù)現(xiàn)場實際經(jīng)驗排序)以及PSO算法、MPSO算法[14]、EPSO算法[20]、ACO算法進行對比,以驗證所提算法的有效性。

令PSO算法、MPSO算法、EPSO算法的參數(shù)設(shè)置與MFPSO算法相同:種群規(guī)模N=20,函數(shù)維數(shù)n=8×6=48,最大迭代次數(shù)tmax=500,慣性權(quán)重wmin=0.4、wmax=0.9,加速常數(shù)c1=c2=cj=1.49;令A(yù)CO算法的種群規(guī)模N=20,信息素?fù)]發(fā)系數(shù)ρ=0.5,固定概率P0設(shè)置為[0,1]之間的隨機數(shù)。上述5種算法獨立運行10次的最優(yōu)優(yōu)化結(jié)果見圖5,所得優(yōu)化結(jié)果的平均值見表4。

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

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

由圖5和表4可知,MFPSO算法所得結(jié)果最優(yōu),其中,與圖5所對應(yīng)的最優(yōu)調(diào)度方案的甘特圖如圖6所示。

圖6　MFPSO算法最優(yōu)調(diào)度方案的甘特圖

由圖6可知,MFPSO算法所得的最優(yōu)調(diào)度方案中各機器上的作業(yè)量比較均衡,符合實際需求,同時縮短了最大完成時間,故本文所提的MFPSO算法是有效、可行的，采用該調(diào)度方案可提高液壓閥塊加工車間的生產(chǎn)效率，也有助于實現(xiàn)節(jié)能減排、節(jié)約成本。

4　結(jié)語

(1)為平衡算法的全局和局部搜索能力,提出了多作用力微粒群(MFPSO)算法,采用多作用力階段性搜索策略，將搜索過程劃分為前期、中期、后期3個階段,并對應(yīng)構(gòu)造單一斥力、平衡引斥力、單一引力3種作用力規(guī)則，在不同搜索階段采用不同的作用力規(guī)則，豐富了微粒間的作用力，兼顧了對算法種群多樣性和收斂速度的要求，提高了算法的搜索機制和尋優(yōu)性能。

(2)為解決液壓閥塊加工車間調(diào)度問題,考慮工序間和機器間的約束關(guān)系,以最大完成時間最小為目標(biāo)，給出了液壓閥塊加工車間調(diào)度優(yōu)化模型。利用矩陣變量來處理約束條件，給出了一種基于矩陣的微粒編碼、解碼方法。將MFPSO算法用于求解液壓閥塊加工車間調(diào)度問題，并與車間實際調(diào)度方案以及微粒群(PSO)算法、中值導(dǎo)向微粒群(MPSO)算法、擴展微粒群(EPSO)算法、蟻群(ACO)算法進行了對比，結(jié)果表明，本文提出的MFPSO算法結(jié)果最優(yōu)，從而驗證了該算法的有效性。

(3)液壓技術(shù)是衡量機械制造業(yè)水平的最重要的基礎(chǔ)技術(shù)之一，本文從工藝流程控制的角度對其進行了研究,針對液壓閥塊加工車間調(diào)度問題,提出MFPSO算法以尋求最優(yōu)調(diào)度方案，為解決液壓閥塊加工車間調(diào)度問題提供了一條新的途徑。MFPSO算法采用前期、中期、后期3個階段的搜索策略,需要對以下問題進行進一步的研究:搜索階段的數(shù)目劃分與動態(tài)混合以進一步提高優(yōu)化性能;不同搜索階段的高效切換策略以適應(yīng)在線尋優(yōu)問題。

[1]Haouari M,Hidri L,Gharbi A.Optimal Scheduling of a Two-stage Hybrid Flow Shop[J].Mathematical Methods of Operations Research,2006,64(1):107-124.[2]黎展滔,陳慶新,毛寧.具有前成組約束的兩階段柔性流水車間的啟發(fā)式算法[J].機械工程學(xué)報,2012,48(22):189-198.

Li Zhantao,Chen Qingxin,Mao Ning.Heuristic Algorithms for Two-stage Flexible Flow Shop Scheduling with Head Group Constraint[J].Journal of Mechanical Engineering,2012,48(22):189-198.

[3]張國軍,李嬋娟,朱海平,等.不確定信息條件下Job-shop調(diào)度的混合智能算法[J].中國機械工程,2007,18(16):1939-1942.

Zhang Guojun,Li Chanjuan,Zhu Haiping,et al.A Hybrid Intelligent Algorithm for Job-shop Scheduling under Uncertain Information Environment[J].China Mechanical Engineering,2007,18(16):1939-1942.

[4]張潔, 張朋, 劉國寶. 基于兩階段蟻群算法的帶非等效并行機的作業(yè)車間調(diào)度[J].機械工程學(xué)報,2013,49(6):136-144.

Zhang Jie, Zhang Peng, Liu Guobao. Two-stage Ant Colony Algorithm Based Job Shop Scheduling with Unrelated Parallel Machines[J].Journal of Mechanical Engineering,2013,49(6):136-144.

[5]周輝仁,唐萬生,魏穎輝.基于微粒群算法的柔性流水車間調(diào)度優(yōu)化[J].中國機械工程,2010,21(9):1053-1057.

Zhou Huiren,Tang Wansheng,Wei Yinghui.PSO-based Optimization of Flexible Flow-shop Scheduling[J].China Mechanical Engineering,2010,21(9):1053-1057.

[6]趙詩奎,方水良.基于工序編碼和鄰域搜索策略的遺傳算法優(yōu)化作業(yè)車間調(diào)度[J].機械工程學(xué)報,2013,49(16):160-169.

Zhao Shikui,Fang Shuiliang.Operation-based Encoding and Neighborhood Search Genetic Algorithm for Job Shop Scheduling Optimization[J].Journal of Mechanical Engineering,2013,49(16):160-169.

[7]Xu Ye,Wang Ling.Differential Evolution Algorithm for Hybrid Flow-shop Scheduling Problems[J].Journal of Systems Engineering and Electronics,2011,22(5):794-798.

[8]Shi Y,Eberhart R C.Fuzzy Adaptive Particle Swarm Optimization[C]//IEEE Congress on Evolutionary Computation, May, 2001.Piscataway, New Jersey, USA: IEEE, 2001:101-106.[9]Bratton D,Kennedy J.Defining a Standard for Particle Swarm Optimization[C]//The 2007 IEEE Swarm Intelligence Symposium(SIS 2007),April 1-5.Honolulu, HI,USA:IEEE,2007:120-127.

[10]葉南海,戚一男,陳凱,等.基于改進PSO的可靠性穩(wěn)健優(yōu)化計算方法[J].中國機械工程,2012,23(5):551-555.

Ye Hainan,Qi Yinan,Chen Kai,et al.A Computational Method on Reliability Robust Optimization Based on Improved PSO[J]. China Mechanical Engineering, 2012, 23(5): 551-555.

[11]韓江洪,李正榮,魏振春.一種自適應(yīng)粒子群優(yōu)化算法及其仿真研究[J].系統(tǒng)仿真學(xué)報,2006,18(10):2969-2971.

Han Jianghong,Li Zhengrong,Wei Zhenchun.Adaptive Particle Swarm Optimization Algorithm and Simulation[J].Journal of System Simulation,2006,18(10):2969-2971.

[12]Chen W N, Zhang J, Lin Y, et al. Particle Swarm Optimization with an Aging Leader and Challengers[J]. IEEE Transactions on Evolutionary Computation, 2013, 17(2): 241-258.[13]劉朝華, 張英杰, 章兢,等.一種雙態(tài)免疫微粒群算法[J].控制理論與應(yīng)用,2011,28(1):65-72.

Liu Zhaohua,Zhang Yingjie,Zhang Jing,et al.A Novel Binary-state Immune Particle Swarm Optimization Algorithm[J].Control Theory & Applications,2011,28(1):65-72.[14]Beheshti Z, Shamsuddin S M H, Hasan S. MPSO: Median-oriented Particle Swarm Optimization[J].Applied Mathematics and Computation, 2013, 219(11): 5817-5836.[15]Qu B Y,Suganthan P N,Das S.A Distance-based Locally Informed Particle Swarm Model for Multimodal Optimization[J].IEEE Transactions on Evolutionary Computation,2013,17(3):387-402.[16]Mendes R,Kennedy J,Neves J.The Fully Informed Particle Swarm:Simpler,Maybe Better[J].IEEE Transactions on Evolutionary Computation,2004,8(3):204-210.[17]陳保娣,曾建潮.改進的吸引擴散微粒群算法[J].控制理論與應(yīng)用,2010,27(4):451-456.

Chen Baodi,Zeng Jianchao.Modified Attractive and Repulsive Particle Swarm Optimization[J].Control Theory & Applications,2010,27(4):451-456.

[18]韓飛,楊春生,劉清.一種改進的基于梯度搜索的微粒群優(yōu)化算法[J].南京大學(xué)學(xué)報(自然科學(xué)),2013,49(2):196-201.

Han Fei, Yang Chunsheng, Liu Qing. An Improved Particle Swarm Optimization Based on Gradient Search[J].Journal of Nanjing University(Natural Sciences), 2013, 49(2): 196-201.

[19]Huang T, Mohan A S. A Microparticle Swarm Optimizer for the Reconstruction of Microwave Images[J].IEEE Transactions on Antennas and Propagation, 2007, 55(3): 568-576.[20]莫思敏, 曾建潮, 謝麗萍. 擴展的微粒群算法[J].控制理論與應(yīng)用, 2012, 29(6): 811-816.

Mo Simin,Zeng Jianchao, Xie Liping. Extended Particle-swarm Optimization Algorithm[J].Control Theory & Applications,2012,29(6):811-816.

(編輯蘇衛(wèi)國)

A MFPSO Algorithm for Solving Hydraulic Manifold Processing Shop Scheduling

Chen Dongning1,2Zhang Ruixing1,2Yao Chengyu3Qian Yanhui1,2

1.Hebei Provincial Key Laboratory of Heavy Machinery Fluid Power Transmission and Control,Yanshan University,Qinhuangdao,Hebei,066004 2.Key Laboratory of Advanced Forging & Stamping Technology and Science(Yanshan University),Ministry of Education of China,Qinhuangdao,Hebei,066004 3.Key Laboratory of Industrial Computer Control Engineering of Hebei Province,Yanshan University,Qinhuangdao,Hebei,066004

Considering the constraints between processes and machines,an optimization model with the objective of minimizing the maximum completion time or makespan was put forward to solve manifold processing shop scheduling problem effectively.To balance the ability of global and local search of the algorithm,a MFPSO algorithm was proposed,which used staged search strategy of multi forces.The search process was divided into three stages:earlier-stage,medium-stage and later-stage,and three kinds of force rules,were correspondingly constructed,which were single repulsion force rule,balanced attraction and repulsion force rule and single attraction force rule.Different force rules were adopted in different search stages so as to improve the search mechanism and search performance of the algorithm.The MFPSO algorithm was applied in solving manifold processing shop scheduling problem. A particle encoding and decoding method was presented based on matrix, which made use of matrix variables to deal with the constraints of the problem. Finally, the MFPSO algorithm presented herein shows better performance compared with PSO algorithm,median-oriented PSO algorithm,extended PSO algorithm and ant colony optimization algorithm in optimizing manifold processing shop scheduling problem,thus its effectiveness was verified.

manifold processing shop scheduling;particle swarm optimization(PSO) algorithm;force rule;multi force PSO(MFPSO) algorithm

2014-08-29

國家自然科學(xué)基金資助項目(51405426);河北省自然科學(xué)基金資助項目(E2012203015)；河北省教育廳資助科研項目(ZH2012062)

TP18;TH173DOI：10.3969/j.issn.1004-132X.2015.03.015

陳東寧,女,1978年生。燕山大學(xué)機械工程學(xué)院副教授、博士。主要研究方向為系統(tǒng)可靠性及智能優(yōu)化。獲國家科技進步二等獎1項。出版專著2部,發(fā)表論文38篇。張瑞星,女,1987年生。燕山大學(xué)機械工程學(xué)院碩士研究生。姚成玉,男,1975年生。燕山大學(xué)電氣工程學(xué)院教授、博士。茜彥輝,男,1988年生。燕山大學(xué)機械工程學(xué)院碩士研究生。