基于協(xié)同奔襲自適應(yīng)狼群算法的雙車間優(yōu)化調(diào)度

梁 迪, 薛 健, 趙伊諾

(沈陽大學(xué) 機(jī)械工程學(xué)院, 遼寧 沈陽 110044)

目前車間調(diào)度研究大多以單一車間為對象,而實(shí)際生產(chǎn)工件加工的開始時間往往與前一車間息息相關(guān),因此研究多車間的協(xié)同調(diào)度有助于使車間整體調(diào)度更優(yōu).已有眾多學(xué)者將智能啟發(fā)式算法應(yīng)用到協(xié)同調(diào)度問題上,馮霞等[1]用遺傳算法對機(jī)場的加油車和擺渡車協(xié)同調(diào)度問題進(jìn)行了分析改進(jìn),提高了機(jī)場的運(yùn)行效率.于大洋等[2]提出了電動汽車充電與風(fēng)電協(xié)同調(diào)度碳減排效益的測算模型,證明了協(xié)同調(diào)度是實(shí)現(xiàn)風(fēng)電和電動汽車規(guī)模化協(xié)調(diào)利用的一種有效手段,但目前針對生產(chǎn)車間協(xié)同調(diào)度方面的研究較少.狼群算法被國內(nèi)外眾多學(xué)者提出并改進(jìn),將其應(yīng)用于調(diào)度及路徑規(guī)劃等問題上.馮曉莉等[3]將狼群算法結(jié)合模擬退火算法,提高了算法的全局收斂性與計算魯棒性,并將其應(yīng)用于求解復(fù)雜的并聯(lián)泵站群優(yōu)化運(yùn)行模型上;周璟[4]提出了混沌狼群圍捕算法,在狼群圍捕算法基礎(chǔ)上,使用Tent混沌映射改進(jìn)了狼群初始化方法,使狼群初始分布更加均勻,提高了車間內(nèi)機(jī)器人導(dǎo)航規(guī)劃的實(shí)時性,減少了導(dǎo)航路徑長度;Seifi等[5]提出了灰狼和鯊魚氣味算法(GWO+SSO)的組合,并將其應(yīng)用于多個邊界約束下目標(biāo)函數(shù)優(yōu)化,實(shí)驗(yàn)結(jié)果證明該方法在全局極小值上具有較高的收斂性.以上學(xué)者在算法上的改進(jìn)皆是提高算法的有效性及準(zhǔn)確性,但在算法運(yùn)行速度與收斂速度上收效不明顯.

本文在已有學(xué)者提出的的三級領(lǐng)導(dǎo)式狼群算法[6]基礎(chǔ)上進(jìn)行改進(jìn):為了加快算法搜索效率,結(jié)合粒子群算法和細(xì)菌覓食算法,在“狼群圍攻”階段融入粒子群算法特點(diǎn),加入自適應(yīng)步長;為了提高算法后期收斂速度,在“強(qiáng)者生存”環(huán)節(jié)融入細(xì)菌算法特點(diǎn),淘汰適應(yīng)度最差的一半狼,并將剩余的一半狼復(fù)制.文中對案例企業(yè)車間調(diào)度問題進(jìn)行分析建模,并用MATLAB進(jìn)行求解.

1 協(xié)同奔襲策略的狼群優(yōu)化算法(CAWPA)

初始狼群算法(wolf pack algorithm,WPA)是學(xué)者模擬自然界狼群的圍捕獵物行為提出的,其中抽象出搜索行為、圍攻行為和更新行為[7].2013年吳虎勝等[8]提出了一種全新的狼群算法,更加細(xì)致地將狼群分成頭狼、探狼、猛狼3大類.

為了使算法搜索最優(yōu)值的范圍更加全面廣泛,將領(lǐng)導(dǎo)狼設(shè)置為3匹,讓它們分別帶領(lǐng)狼群搜索最佳解,這樣不僅避免了原始狼群算法易陷入最優(yōu)的問題,而且加快了全局的搜索速度和精確度.CAWPA算法的流程如圖1所示.

圖1 CAWPA算法流程圖Fig.1 Flow chart of CAWPA algorithm

1.1 初始化狼群

在搜索區(qū)域內(nèi),隨機(jī)將狼群的位置初始化,即

(1)

式中,1≤l≤L.

然后根據(jù)式(1)初始化第i匹狼在最初始迭代時的位置為

(2)

式中:xi為狼群的位置分布;xmax為狼群可活動的最大范圍;xmin為狼群可活動的最小范圍;e為一個隨機(jī)數(shù)值,取值在[0,1]之間.

1.2 “3匹頭狼”領(lǐng)導(dǎo)式奔襲行為

首先選取適應(yīng)度最大的狼作為頭狼,記為α狼,然后依次選取適應(yīng)度第2和第3的狼作為第2領(lǐng)導(dǎo)狼和第3領(lǐng)導(dǎo)狼,記為β狼和δ狼,其余狼群記為ω狼[9].

α狼、β狼和δ狼的適應(yīng)度分別記為fα、fβ、fδ,并記3匹狼的適應(yīng)度之和為f,即

f=fα+fβ+fδ.

(3)

2匹狼之間的距離采用歐式距離描述,Xi狼與α狼之間的距離公式為

(4)

(5)

Xi狼與δ狼之間的距離公式為

(6)

記3個距離之和為l,

l=lα+lβ+lδ.

(7)

因此,“3匹頭狼”領(lǐng)導(dǎo)的奔襲方式為

1.3 圍攻行為

算法后期,將頭狼位置示為獵物位置,圍攻過程公式為

(9)

1.4 “適者生存”策略

原算法中[10],在淘汰階段會淘汰適應(yīng)度比較差的R匹狼,重新隨機(jī)生成R匹狼,R為在范圍[N/ (2χ),N/χ]中的一個隨機(jī)正整數(shù),其中χ表示淘汰狼數(shù)的比例因子,這樣做增大了算法的計算時間[11].本文參考細(xì)菌覓食算法,把細(xì)菌覓食算法特點(diǎn)融入狼群算法,將適應(yīng)度較低的一半狼淘汰,然后直接將剩余的一半較強(qiáng)的狼復(fù)制[12].這樣不僅可以使算法在設(shè)置參數(shù)的過程中更簡單,而且也會保留多次迭代之后適應(yīng)度較高的狼.

2 實(shí)驗(yàn)仿真

金屬結(jié)構(gòu)件的制造屬于多品種、小批量的生產(chǎn)方式,生產(chǎn)過程中產(chǎn)生的中間零部件規(guī)格繁多[13].現(xiàn)有車間調(diào)度問題的研究主要是優(yōu)化單一車間的生產(chǎn)效率最優(yōu),缺少統(tǒng)一的協(xié)同調(diào)度[14],使上下游車間無法達(dá)到整體最優(yōu).因此,有必要進(jìn)行科學(xué)合理的協(xié)同生產(chǎn)調(diào)度,從而減少在制品庫存,縮短產(chǎn)品總完工時間,提高生產(chǎn)效率.

本文主要考慮切割車間與機(jī)械加工車間協(xié)同調(diào)度問題,切割車間是典型的并行機(jī)調(diào)度問題(parallel machine scheduling problem,PMSP),而機(jī)械加工車間的生產(chǎn)安排為流水線調(diào)度問題(flow scheduling problem,FSP).但是在同時考慮2個車間的生產(chǎn)時并不能簡單地將PMSP作為流水調(diào)度車間的一道工序,因?yàn)樵跈C(jī)械加工車間加工的零件在并行機(jī)部分是合并加工的,多個零件合并在一張板材上加工.因此切割車間與機(jī)械加工車間需要協(xié)同調(diào)度.

結(jié)構(gòu)件切割車間板材的切割過程分為準(zhǔn)備、加工與收件3個階段.準(zhǔn)備時間為切割之前將板材放到固定架上的時間;加工時間與設(shè)備切割的速度相關(guān),而切割速度則與板材材質(zhì)有關(guān);收件時間為完成切割之后,需要對切割得到的零件進(jìn)行收集整理的時間[15].每種板材的準(zhǔn)備時間和收件時間均與板材大小有關(guān),而且是固定值,所以加工時間由板材和切割設(shè)備共同決定.

經(jīng)過切割后得到的零件直接送往機(jī)械加工車間進(jìn)行加工,每個零件按相同順序經(jīng)過每個機(jī)械加工機(jī)器,每臺機(jī)器上各零件加工順序一致,工藝程序如圖2所示.

圖2 雙車間工藝程序Fig.2 Process of dual workshop

2.1 建立數(shù)學(xué)模型

2.1.1 切割階段

約束各板材完工時間為

(10)

式中:n為切割階段板材的數(shù)量;m為切割階段機(jī)器的數(shù)量;Cip代表板材i在機(jī)器p上的完工時間;Cgp代表板材g在機(jī)器p上的完工時間;g是板材i在機(jī)器p上的前序板材;STi為板材i在切割階段的準(zhǔn)備時間;Li為板材i的切割長度;vip為板材i在機(jī)器p上的切割速度;PTi為板材i在切割階段的收件時間.

2.1.2 加工階段

計算零件完工時間和最大完工時間.

(11)

式中:Cjq為零件j在機(jī)器q上的完工時間;n′為機(jī)械加工階段零件的數(shù)量;m′為機(jī)械加工階段機(jī)器的數(shù)量;j為機(jī)械加工階段零件的序號;q為機(jī)械加工階段機(jī)器的序號;Tjq為機(jī)械加工階段零件j在機(jī)器q上的加工時間.

最大完工時間Cmax≥Cjq.

2.2 實(shí)驗(yàn)設(shè)計與參數(shù)設(shè)置

板材的切割速度通過矩陣V隨機(jī)生成,

例如,同一種板材可以在第1列(切割機(jī)器1)上以速度1切割,也可以以速度2在第2列(切割機(jī)器2)上切割,但不能在第3列(切割機(jī)器3)上切割.板材的數(shù)量n設(shè)置為5、10、15,需加工的板材材質(zhì)設(shè)為3種,切割車間機(jī)器數(shù)量m設(shè)置為3,切割長度服從U[100,200]分布,準(zhǔn)備時間ST服從U[1,25]分布,收件時間PT服從U[1,25]分布.機(jī)械加工階段零件數(shù)量n′設(shè)置為20、40、60、80.機(jī)械加工流水車間機(jī)器數(shù)量設(shè)置為4,其中加工的準(zhǔn)備時間包含在加工時間內(nèi),加工時間服從U[1,40]分布的整數(shù),所有零件的加工時間一致.

基礎(chǔ)種群大小為100,迭代次數(shù)設(shè)置為10(n+n′),GA算法交叉概率為1,變異概率為0.1,CAWPA算法游走概率為1,奔襲概率為0.1.

2.3 實(shí)驗(yàn)結(jié)果及對比

為評價本文提出的CAWPA算法的表現(xiàn), 本文引入GA算法和GWO算法求解該問題. 3種算法獨(dú)立運(yùn)行20次, 選取運(yùn)算結(jié)果的平均值、最小值、相對百分比偏差和標(biāo)準(zhǔn)差4個指標(biāo)來評價算法的能力. 具體如表1～表4所示.

實(shí)驗(yàn)的運(yùn)行環(huán)境是Window 10系統(tǒng),Intel(R) Core(TM)i7-8750HCPU@ 2.20 GHz 2.21 GHz,運(yùn)行內(nèi)存16.0 GB.最優(yōu)結(jié)果用星號標(biāo)出.

表1 5、10、15個板材在不同零件數(shù)下算法運(yùn)行結(jié)果的平均值對比Table 1 Comparison of the average value of algorithm running results of 5, 10, and 15 plates with different parts numbers min

表2 5、10、15個板材在不同零件數(shù)下算法運(yùn)行結(jié)果的最小值對比Table 2 Comparison of the minimum value of algorithm running results of 5, 10, and 15 plates with different parts numbers min

表3 5、10、15個板材在不同零件數(shù)下算法運(yùn)行結(jié)果的相對百分比偏差對比Table 3 Comparison of relative percentage deviations of algorithm running results of 5, 10, and 15 plates with different parts numbers %

表4 5、10、15個板材在不同零件數(shù)下算法運(yùn)行結(jié)果的標(biāo)準(zhǔn)差對比Table 4 Comparison of the standard deviation of the algorithm running results of 5, 10, and 15 plates with different parts numbers

通過對表1～表4的數(shù)據(jù)對比分析可知,改進(jìn)后的CAWPA算法相較于GA算法與GWO算法更優(yōu)秀.在切割階段板材數(shù)量為5時,GWO算法也能取得與CAWPA算法相似的最優(yōu)解,但是隨著板材數(shù)量的增加,GWO算法也慢慢體現(xiàn)出后繼無力的感覺,這說明GWO算法對于求解協(xié)同調(diào)度問題十分有效,但隨著數(shù)據(jù)的增加,未作改進(jìn)的GWO算法在處理速度上明顯不盡人意.在平均解上CAWPA較其他2種算法更加穩(wěn)定,數(shù)據(jù)也更加準(zhǔn)確.

本文選取切割階段板材數(shù)量5、機(jī)械加工階段零件數(shù)量20為具體案例.迭代次數(shù)為10×(5+20)=250,得到雙車間協(xié)同調(diào)度甘特圖,如圖3所示,其中M-Q-1～M-Q-3表示切割車間的第1、2、3臺機(jī)器,M-G-1～M-G-4表示機(jī)械加工車間的第1、2、3、4臺機(jī)器;S1代表切割階段板材1,J1代表機(jī)械加工階段零件1,以此類推.圖中M-G-4為最后一個零件J16的完工時間,即為總加工時間,運(yùn)行結(jié)果得出總加工時間為737 min.

圖3 雙車間協(xié)同調(diào)度甘特圖Fig.3 Gantt chart for cooperative scheduling of dual workshop

圖4 各算法迭代進(jìn)化對比Fig.4 Comparison of iterative evolution of each algorithm

圖4為3個算法的迭代進(jìn)化對比圖,從圖中可以看出:在前20次迭代中,協(xié)同奔襲狼群算法在處理速度方面有明顯優(yōu)勢,求解速度更快,搜索到較優(yōu)解的時間更短,也更準(zhǔn)確;GA算法雖然前期較GWO算法進(jìn)化速度快,但容易陷入局部最優(yōu)解;隨著迭代次數(shù)的增加,通過將細(xì)菌覓食算法融入CAWPA算法的后期,使CAWPA算法能夠在短時間內(nèi)找到最優(yōu)解,且不易陷入局部最優(yōu),而GWO算法雖然搜索最優(yōu)解的能力較GA算法更強(qiáng),但相比CAWPA算法進(jìn)化速度比較慢.

3 結(jié) 論

本文提出了一種協(xié)同奔襲策略的狼群優(yōu)化算法(CAWPA),以改進(jìn)傳統(tǒng)狼群算法對數(shù)據(jù)處理不準(zhǔn)確且易陷入局部最優(yōu)的問題.在前期搜索階段,加入3匹頭狼協(xié)同領(lǐng)導(dǎo)策略:α,β和δ3匹領(lǐng)導(dǎo)狼,使算法具有更全面的搜索范圍,在游走行為加入交互策略以提高狼群溝通交互能力;在“猛狼圍攻”環(huán)節(jié),融入自適應(yīng)步長機(jī)制,使得算法具有更快的收斂速度;在后期“強(qiáng)者生存”環(huán)節(jié)中模仿細(xì)菌覓食算法,去除適應(yīng)度最差的2/N匹狼,復(fù)制剩余的2/N匹狼.將改進(jìn)后的狼群算法應(yīng)用在切割車間與機(jī)械加工車間協(xié)同調(diào)度問題上,選取了GA算法和GWO算法進(jìn)行比較,共進(jìn)行了4組實(shí)驗(yàn),比較了平均值、最小值、相對百分比偏差和標(biāo)準(zhǔn)差,并選取1組具體案例,對比3種算法的迭代速度和得到最優(yōu)解時間.實(shí)驗(yàn)結(jié)果證明CAWPA算法相比較于其他2種算法具有更準(zhǔn)確的計算結(jié)果和更穩(wěn)定的表現(xiàn).