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

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

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

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

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

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

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

0　引言

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

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

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

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

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

1.1液壓閥塊加工工藝

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

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

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

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

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

結(jié)合現(xiàn)場(chǎng)工藝作如下假設(shè)：工件一旦開(kāi)始加工便不可中斷；一臺(tái)機(jī)器同一時(shí)刻只能加工一個(gè)閥塊；一個(gè)閥塊同一時(shí)刻只能在一臺(tái)機(jī)器上加工；在并行加工工藝階段，閥塊可在并行機(jī)器的任意一臺(tái)機(jī)器上加工?？紤]各機(jī)器的調(diào)機(jī)時(shí)間，以完成nM個(gè)閥塊加工的最大完成時(shí)間最小為目標(biāo),給出該閥塊加工車(chē)間調(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)確保了每個(gè)優(yōu)先級(jí)位置與閥塊間一一對(duì)應(yīng);式(4)使得對(duì)于每道工序每個(gè)閥塊只能在一臺(tái)機(jī)器上加工；式(5)表示了同一閥塊不同工序間的先后制約關(guān)系；式(6)表示第一道工序上調(diào)度排列中排位越前的閥塊開(kāi)始加工時(shí)間越早；式(7)實(shí)現(xiàn)了同道工序分配在同一機(jī)器上的閥塊排位靠后的必須等靠前的加工完成后才可進(jìn)行加工,當(dāng)處于不同位置的閥塊不在同道工序的同一機(jī)器上加工時(shí)，L數(shù)值較大以保證不等式恒成立。

2　多作用力微粒群算法

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

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

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

假設(shè)在n維搜索空間中,微粒群的種群規(guī)模為N,對(duì)于任意微粒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)),其個(gè)體最優(yōu)微粒的位置矢量為Pi(t)=(pi1(t),pi2(t),…,pi n(t));對(duì)于整個(gè)微粒群,第t代全局最優(yōu)微粒g的位置矢量為Pg(t)=(pg1(t),pg2(t),…,pg n(t))。

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

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

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

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

比微粒i適應(yīng)度差的個(gè)體最優(yōu)微粒對(duì)微粒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對(duì)微粒i的引力為

pg d(t)-xid(t)

上述相關(guān)變量中,xj d(t)為第t代微粒j的第d維位置;pj d(t)為第t代微粒j的個(gè)體最優(yōu)微粒的第d維位置;Bi(t)為第t代比微粒i適應(yīng)度好的個(gè)體最優(yōu)微粒的集合;Wi(t)為第t代比微粒i適應(yīng)度差的個(gè)體最優(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ū)間互相獨(dú)立的隨機(jī)數(shù)。

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

(14)

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

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

(15)

(16)

(17)

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

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

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

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

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

2.3切換因子對(duì)MFPSO算法的影響

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1問(wèn)題描述

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

表3　液壓閥塊在各機(jī)器上的加工時(shí)間　min

3.2編碼矩陣A

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

(18)

根據(jù)上述編碼方法對(duì)微粒進(jìn)行編碼:每個(gè)微粒由s個(gè)小段組成,每個(gè)小段包括nM個(gè)數(shù)值,每個(gè)微粒的長(zhǎng)度為s×nM,從而形成了nM個(gè)閥塊完成s道工序的一個(gè)調(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)

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

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

圖4　微粒編碼圖示

對(duì)于上述液壓閥塊加工車(chē)間調(diào)度問(wèn)題,采用MFPSO算法進(jìn)行求解,其參數(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)過(guò)500代搜索后得到全局最優(yōu)解,其編碼矩陣A如下：

(19)

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

3.3選擇機(jī)器矩陣S

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

(20)

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

(21)

3.4完成時(shí)間矩陣的生成

3.4.1加工時(shí)間矩陣TP

將表3閥塊在各機(jī)器上的加工時(shí)間表示為矩陣T:

(22)

為提取各閥塊在其實(shí)際使用機(jī)器上的加工時(shí)間,屏蔽沒(méi)有實(shí)際使用的機(jī)器,將矩陣T與選擇機(jī)器矩陣S點(diǎn)乘得到加工時(shí)間矩陣TP:

(23)

它表示了各閥塊的各道工序在其選擇的機(jī)器上的加工時(shí)間。

3.4.2確定閥塊的加工順序

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

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

3.4.3完成時(shí)間矩陣TC

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

(24)

3.5結(jié)果對(duì)比

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

令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]之間的隨機(jī)數(shù)。上述5種算法獨(dú)立運(yùn)行10次的最優(yōu)優(yōu)化結(jié)果見(jiàn)圖5,所得優(yōu)化結(jié)果的平均值見(jiàn)表4。

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

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

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

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

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

4　結(jié)語(yǔ)

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

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

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

[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]黎展滔,陳慶新,毛寧.具有前成組約束的兩階段柔性流水車(chē)間的啟發(fā)式算法[J].機(jī)械工程學(xué)報(bào),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]張國(guó)軍,李嬋娟,朱海平,等.不確定信息條件下Job-shop調(diào)度的混合智能算法[J].中國(guó)機(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]張潔, 張朋, 劉國(guó)寶. 基于兩階段蟻群算法的帶非等效并行機(jī)的作業(yè)車(chē)間調(diào)度[J].機(jī)械工程學(xué)報(bào),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]周輝仁,唐萬(wàn)生,魏穎輝.基于微粒群算法的柔性流水車(chē)間調(diào)度優(yōu)化[J].中國(guó)機(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]趙詩(shī)奎,方水良.基于工序編碼和鄰域搜索策略的遺傳算法優(yōu)化作業(yè)車(chē)間調(diào)度[J].機(jī)械工程學(xué)報(bào),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]葉南海,戚一男,陳凱,等.基于改進(jìn)PSO的可靠性穩(wěn)健優(yōu)化計(jì)算方法[J].中國(guó)機(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é)報(bào),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ìn)的吸引擴(kuò)散微粒群算法[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]韓飛,楊春生,劉清.一種改進(jìn)的基于梯度搜索的微粒群優(yōu)化算法[J].南京大學(xué)學(xué)報(bào)(自然科學(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]莫思敏, 曾建潮, 謝麗萍. 擴(kuò)展的微粒群算法[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)國(guó))

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

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

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

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