改進(jìn)鯨魚優(yōu)化算法及其在混流U型裝配線平衡問題的應(yīng)用

張凌波, 周劍揚(yáng)

(華東理工大學(xué)信息科學(xué)與工程學(xué)院, 上海 200237)

鯨魚優(yōu)化算法(whale optimization algorithm,WOA)具有收斂速度快,性能穩(wěn)定等優(yōu)勢(shì),自從提出以來廣泛應(yīng)用于故障診斷[1]、參數(shù)調(diào)優(yōu)[2]、水資源配置[3]和模型優(yōu)化[4]。但同其他的智能優(yōu)化算法一樣,存在收斂精度較低,易于陷入局部最優(yōu)等問題,已有許多學(xué)者對(duì)其進(jìn)行了研究和改進(jìn)。黃元春等[5]提出一種偽反向?qū)W習(xí)和高斯-柯西混合變異策略的改進(jìn)鯨魚算法,改善了算法的收斂速度和精度;吳坤等[6]將灰狼優(yōu)化算法中的等級(jí)制度和微分進(jìn)化算法中的貪婪策略引入鯨魚優(yōu)化算法,提升了算法的全局搜索能力;Jiang等[7]將差分算法和鯨魚優(yōu)化算法結(jié)合,并引入云自適應(yīng)慣性權(quán)重,有效平衡全局和局部搜索。上述改進(jìn)雖然改善了WOA的性能,但是在尋優(yōu)精度和算法穩(wěn)定性方面還存在不足,仍有改進(jìn)空間。

裝配線是由一些物料搬運(yùn)設(shè)備連接起來連續(xù)生產(chǎn)線,由多個(gè)工位組成,每個(gè)工位完成整個(gè)裝配過程的幾個(gè)環(huán)節(jié)。由于任務(wù)分配的不合理,裝配線各工位的負(fù)載并不均衡,就會(huì)出現(xiàn)“瓶頸工序”,造成資源的浪費(fèi)和生產(chǎn)效率低下。裝配是生產(chǎn)過程的重要環(huán)節(jié)之一,據(jù)調(diào)查,裝配占用總生產(chǎn)時(shí)間的50%和總生產(chǎn)成本的20%。

裝配線平衡問題(assembly line balancing problem,ALBP)是指根據(jù)裝配線的已知信息,合理地將各工序分配至各個(gè)工作站,優(yōu)化裝配線某些指標(biāo)的一系列復(fù)雜問題。常見的裝配線平衡問題主要可以分為3類,即第1類裝配線平衡問題(ALBP-Ⅰ)、第2類裝配線平衡問題(ALBP-Ⅱ)、E類裝配線平衡問題[8](ALBP-E)。ALBP-Ⅰ是已知裝配線的節(jié)拍時(shí)間,最小化裝配線的工作站數(shù)量;ALBP-Ⅱ是已知裝配線的工作站數(shù)量,最小化裝配線的節(jié)拍時(shí)間;ALBP-E是最小化工作站數(shù)量和節(jié)拍時(shí)間,提高裝配線效率。裝配線根據(jù)類型,可以分為直型線、U型線和并行線;根據(jù)生產(chǎn)產(chǎn)品的類型,又可分為單模、多模和混模。隨著市場(chǎng)變化和精益生產(chǎn)的發(fā)展,越來越多的企業(yè)采用靈活性更好的混流U型線代替?zhèn)鹘y(tǒng)的單模直型線,這使得混流U型線的平衡問題(mixed model U-shaped assembly line balancing problem,MMUALBP)成為近幾年的研究重點(diǎn);彭運(yùn)芳等[9]針對(duì)第2類混流U型裝配線的平衡問題,構(gòu)建了其混合整數(shù)規(guī)劃模型,并提出了一種改進(jìn)的遺傳算法,采用3種工序分配方法,并通過實(shí)驗(yàn)驗(yàn)證了算法的有效性;劉佳楠等[10]針對(duì)直型線和U型線的混流裝配線平衡問題,提出多目標(biāo)的平衡方法,并采用改進(jìn)的遺傳算法進(jìn)行優(yōu)化;原丕業(yè)等[11]的研究兼顧工作站的平均和瞬時(shí)負(fù)荷,建立了混流U型裝配線的多目標(biāo)數(shù)學(xué)模型,并設(shè)計(jì)了一種自適應(yīng)遺傳算法求解;Aufy等[12]針對(duì)混流直型和U型線的裝配線平衡問題,設(shè)計(jì)了一種工人-任務(wù)分配的啟發(fā)式模型,并通過實(shí)例驗(yàn)證其模型的有效性;Zhang等[13]以最小化混流U型裝配線的能源消耗和生產(chǎn)效率為目標(biāo)建立了多目標(biāo)模型,并設(shè)計(jì)了一種改進(jìn)的多目標(biāo)蜻蜓優(yōu)化算法求解;Zheng等[14]基于任務(wù)選擇因子的編碼方式,提出一種混合交叉熵算法,用于解決混流U型線的平衡問題。如何合理地分配工序和更精準(zhǔn)的求解,是混流U型裝配線目前需要解決的問題。

針對(duì)鯨魚優(yōu)化算法在實(shí)際應(yīng)用中存在尋優(yōu)能力不足、求解效果不穩(wěn)定和易于陷入局部最優(yōu)等問題,現(xiàn)提出一種改進(jìn)的鯨魚優(yōu)化算法(improve whale optimization algorithm,IWOA),并將其應(yīng)用到求解混流U型裝配線平衡問題。在WOA的基礎(chǔ)上,現(xiàn)引入均勻設(shè)計(jì)方法進(jìn)行初始種群的生成,提高初始種群的質(zhì)量;融合NEWUOA算法,增強(qiáng)鯨魚優(yōu)化算法的局部搜索能力;提出一種新的越界處理方法,降低算法陷入局部最優(yōu)的可能;引入非線性收斂因子和自適應(yīng)權(quán)重,平衡算法的局部和全局搜索,增加算法的搜索精細(xì)度。通過7個(gè)基準(zhǔn)測(cè)試函數(shù),驗(yàn)證IWOA在尋優(yōu)效果和求解穩(wěn)定性方面的優(yōu)越性。針對(duì)混流U型裝配線平衡問題,以裝配線節(jié)拍時(shí)間為優(yōu)化目標(biāo),設(shè)計(jì)帶閾值的工序分配方法。最后通過21個(gè)混流裝配線標(biāo)準(zhǔn)算例,進(jìn)一步驗(yàn)證本文提出的IWOA的有效性。

1 標(biāo)準(zhǔn)的鯨魚優(yōu)化算法

WOA是Mirjalili等[15]通過對(duì)座頭鯨特有的氣泡網(wǎng)狩獵方式進(jìn)行研究和模擬,建立數(shù)學(xué)模型,而后提出的一種智能優(yōu)化算法。該算法包括包圍獵物、氣泡網(wǎng)攻擊和搜索獵物3個(gè)階段。

1.1 包圍獵物

WOA通過假定當(dāng)前的最優(yōu)個(gè)體所處的位置即為獵物或者最接近獵物的位置,以此吸引其他個(gè)體向著最優(yōu)個(gè)體移動(dòng),完成對(duì)獵物的包圍,其過程可以描述為

D1=|CX*(t)-X(t)|

(1)

X(t+1)=X*(t)-AD1

(2)

式中:D1為中間變量;t為當(dāng)前的迭代次數(shù);X*為最佳鯨魚個(gè)體的位置;X為當(dāng)前鯨魚個(gè)體的位置;A和C為系數(shù),定義為

A=2ar-a

(3)

C=2r

(4)

式中:r為[0,1]的隨機(jī)數(shù);隨著迭代次數(shù)的增加,收斂因子a線性地從2減至0。

1.2 氣泡網(wǎng)攻擊

鯨魚個(gè)體根據(jù)自身和獵物之間的距離,通過一種對(duì)數(shù)螺旋方程更新位置,其過程可以描述為

X(t+1)=D2eblcos(2πl(wèi))+X*(t)

(5)

式(5)中:D2=|X*(t)-X(t)|為當(dāng)前鯨魚個(gè)體和獵物之間的距離;e為自然常數(shù);b為螺旋對(duì)數(shù)方程常數(shù);l為[-1,1]的隨機(jī)數(shù)。

為了更好地模擬座頭鯨的這種獨(dú)特捕食行為,WOA設(shè)置了一個(gè)概率閾值,用于在包圍和螺旋更新兩種行為之間進(jìn)行選擇,通常情況下,兩種行為的概率都為50%,其數(shù)學(xué)模型為

(6)

式(6)中:p1為[0,1]的隨機(jī)數(shù)。

1.3 搜索獵物

WOA會(huì)根據(jù)系數(shù)A的值來決定是靠近最優(yōu)個(gè)體進(jìn)行包圍獵物或螺旋更新,還是遠(yuǎn)離最優(yōu)個(gè)體進(jìn)行隨機(jī)搜索。當(dāng)|A|>1時(shí),WOA將隨機(jī)選擇參考個(gè)體Xrand,執(zhí)行全局搜索,而不再是以最優(yōu)個(gè)體為參考。過程可以描述為

D3=|CXrand(t)-X(t)|

(7)

X(t+1)=Xrand(t)-AD3

(8)

2 改進(jìn)的鯨魚優(yōu)化算法

WOA具有實(shí)現(xiàn)簡(jiǎn)單、可調(diào)參數(shù)少和收斂速度快等優(yōu)點(diǎn),廣泛應(yīng)用于工程問題優(yōu)化,但在實(shí)際應(yīng)用中發(fā)現(xiàn),WOA存在尋優(yōu)精度不足、易于陷入局部最優(yōu)等缺點(diǎn)。針對(duì)上述問題,在WOA的種群初始化、局部搜索、越界修正和收斂因子方面提出了幾點(diǎn)改進(jìn)措施,具體如下。

2.1 基于均勻設(shè)計(jì)的種群初始化策略

一般的智能優(yōu)化算法使用隨機(jī)方式進(jìn)行初始種群的生成,這樣的初始種群只具有一定的隨機(jī)性,而不能保證有較好均勻性。均勻試驗(yàn)設(shè)計(jì),簡(jiǎn)稱均勻設(shè)計(jì),是由Fang等[16]提出的一種試驗(yàn)設(shè)計(jì)方法,用于將試驗(yàn)點(diǎn)均勻的散布在試驗(yàn)區(qū)域內(nèi),盡可能地減少試驗(yàn)次數(shù)。以往采用均勻設(shè)計(jì)的智能優(yōu)化算法[17-18]大多使用好格子點(diǎn)法進(jìn)行均勻設(shè)計(jì)表的生成,但是好格子點(diǎn)法要求試驗(yàn)次數(shù)n和因子個(gè)數(shù)s滿足式(9)的限制:

(9)

式(9)中:φ(?)為歐拉函數(shù)。

這要求優(yōu)化算法的種群數(shù)量要足夠大,但對(duì)于群智能優(yōu)化算法,過大的種群數(shù)量意味著算法運(yùn)行時(shí)間的增多。切割法[19]的思想是從一個(gè)較大的均勻設(shè)計(jì)中切割出一個(gè)符合條件的偏差最小的均勻設(shè)計(jì)作為近似均勻設(shè)計(jì)。相較于好格子點(diǎn)法,切割法只要求較大的均勻設(shè)計(jì)的試驗(yàn)次數(shù)p或p+1為素?cái)?shù),可用于算法求解高維復(fù)雜問題時(shí)初始種群的生成。IWOA采用基于切割法的均勻設(shè)計(jì)種群初始化方法,并使用方冪好格子法作為切割法的初始設(shè)計(jì),混合偏差作為均勻性度量,混合偏差的公式為

(10)

式中:zij為第i個(gè)點(diǎn)的第j維坐標(biāo)。

2.2 基于NEWUOA的局部搜索算子

NEWUOA是一種無導(dǎo)數(shù)優(yōu)化方法[20],用于求解求導(dǎo)困難、無約束的黑箱問題。NEWUOA是一種基于信賴域的確定性優(yōu)化算法,采用二次逼近的方式,不需要計(jì)算目標(biāo)優(yōu)化函數(shù)的導(dǎo)數(shù)。因此,NEWUOA和智能優(yōu)化算法具有很好的契合度。NEWUOA的流程可以描述如下。

步驟1選擇初始插值點(diǎn)xi,計(jì)算F(xi)中的最優(yōu)值,設(shè)定最優(yōu)值對(duì)應(yīng)的xi為xopt。構(gòu)建初始的二次模型Qinit,設(shè)定參數(shù)ρ=ρbeg,Δ=ρbeg。

步驟2計(jì)算‖d‖≤Δ條件下Q(xopt+d)的近似最小值,其中d為信賴域子問題的近似解。如果‖d‖<Δ,則將參數(shù)CRVMIN的值設(shè)置為二次模型Q的最小曲率值。

步驟3如果‖d‖>ρ/2,則計(jì)算F(xopt+d),設(shè)定參數(shù)RATIO為[F(xopt)-F(xopt+d)]/[Q(xopt)-Q(xopt+d)],并在參數(shù)Δ≥ρ條件下調(diào)整ρ的值。將參數(shù)MOVE設(shè)置為0或者下次迭代過程中要舍去的插值點(diǎn)的索引。如果‖d‖<ρ/2,則跳至步驟11。

步驟4如果MOVE>0,則更新二次模型Q,將xMOVE替換為xopt+d。如果F(xopt+d)

步驟5如果RATIO≥0.1,則跳轉(zhuǎn)至步驟2。

步驟6將xMOVE設(shè)置為當(dāng)前迭代中使得距離參數(shù)DIST=‖xMOVE-xopt‖最大的插值點(diǎn)。

步驟7如果DIST≥2Δ,跳至步驟10。

步驟8如果參數(shù)d、Δ、RATIO滿足‖d‖≤ρ,Δ≤ρ,RATIO≤0,轉(zhuǎn)至步驟9;反之,轉(zhuǎn)至步驟2。

步驟9如果ρ=ρend,轉(zhuǎn)至步驟13;反之,轉(zhuǎn)至步驟10。

步驟10將參數(shù)ρ在滿足約束ρ≥ρend下縮小10倍,并將Δ設(shè)置為max{ρold/2,ρnew},跳至步驟2。

步驟11使用參數(shù)CRVMIN測(cè)試‖d‖的最近3個(gè)值和F-Q是否足夠小,如果是,則轉(zhuǎn)至步驟9,反之跳至步驟12。

步驟12設(shè)置參數(shù)ρ為原來的1/10且不低于其下界值,RATIO=-1,轉(zhuǎn)至步驟6。

步驟13如果||d||<ρ/2,則計(jì)算F(xopt+d)后,算法終止;否則,直接終止算法。

NEWUOA具有優(yōu)越的局部搜索能力,初始點(diǎn)的選取影響著優(yōu)化結(jié)果,而WOA的種群更新依賴于引導(dǎo)個(gè)體,優(yōu)秀的引導(dǎo)個(gè)體可以更好地引導(dǎo)種群的搜索方向。通過融合NEWUOA,由WOA提供全局最優(yōu)個(gè)體作為NEWUOA的初始點(diǎn),同時(shí)WOA借助NEWUOA進(jìn)行更好的局部搜索,優(yōu)化引導(dǎo)個(gè)體,從而提高自身的尋優(yōu)能力。在算法初始運(yùn)行時(shí),對(duì)種群中最優(yōu)個(gè)體執(zhí)行一次NEWUOA,如果種群最優(yōu)值發(fā)生變化,則繼續(xù)對(duì)種群最優(yōu)個(gè)體執(zhí)行NEWUOA,反之,則停止執(zhí)行NEWUOA,直到累計(jì)30次迭代,種群最優(yōu)值都沒有發(fā)生變化,則繼續(xù)啟用NEWUOA,重復(fù)上述過程。

2.3 基于環(huán)形區(qū)間和隨機(jī)波動(dòng)越界修正策略

大部分智能優(yōu)化算法在處理越界問題上一般會(huì)舍棄越界個(gè)體或直接將越界個(gè)體修正至邊界,這樣可能會(huì)導(dǎo)致該個(gè)體頻繁越界,致使算法陷入局部最優(yōu)。采用一種基于環(huán)形區(qū)間和隨機(jī)波動(dòng)的越界修正策略,公式為

(11)

式(11)中:mod(n1,n2)為修正的按模運(yùn)算,假設(shè)n1=pnn2+re,pn為正整數(shù),re為余數(shù),當(dāng)re>0時(shí), mod(n1,n2)=re;當(dāng)re=0時(shí),mod(n1,n2)=n2;p2和rand(0,1)為[0,1]的隨機(jī)數(shù);lb和ub分別為算法搜索區(qū)域的下界和上界;Xi(t)為個(gè)體第i維的坐標(biāo)。

2.4 非線性收斂因子和自適應(yīng)權(quán)重系數(shù)

A是控制WOA進(jìn)行全局搜索和局部搜索的關(guān)鍵參數(shù),其變化受到a的影響。根據(jù)文獻(xiàn)[5]中的研究,a不同變化趨勢(shì)對(duì)算法的全局搜索和局部搜索存在一定程度的影響。為均衡算法的全局和局部搜索,引入的非線性收斂因子a的計(jì)算公式為

(12)

式(12)中:Max_iter為最大迭代次數(shù)。

經(jīng)式(12)改進(jìn)后,a在算法迭代過程中的變化趨勢(shì)為先緩后急,增加了算法全局搜索所占用的迭代次數(shù)比例,增強(qiáng)了算法的全局搜索能力。此外,為進(jìn)一步增加算法的搜索精細(xì)度,設(shè)計(jì)了一種自適用權(quán)重ω,隨著迭代進(jìn)程的推進(jìn),ω可以使得種群在最優(yōu)個(gè)體附近進(jìn)行更加精細(xì)的搜索,其計(jì)算公式為

(13)

X(t+1)=ωX*(t)-AD1

(14)

X(t+1)=D2eblcos(2πl(wèi))+ωX*(t)

(15)

2.5 IWOA步驟

本文提出的IWOA偽代碼如下。

注:T為迭代次數(shù);Tmax為最大迭代次數(shù)。

圖1給出了IWOA更加直觀的流程圖。

2.6 算法復(fù)雜度分析

3 仿真實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證IWOA的性能,選擇7個(gè)基準(zhǔn)測(cè)試函數(shù),如表1所示,與幾種工程上常用的智能優(yōu)化算法以及其他的改進(jìn)鯨魚算法比較,包括遺傳算法(genetic algorithm, GA)、WOA、PWOA[5]、GWOA[6]、BWOA[21]、NWOA[22]和RWOA[23]。測(cè)試函數(shù)中,F1～F3為多模態(tài)函數(shù),F4為固定維度的多模態(tài)函數(shù),F5～F7為單模態(tài)函數(shù)。測(cè)試指標(biāo)包括最優(yōu)值、最差值、均值、標(biāo)準(zhǔn)差、和平均運(yùn)行時(shí)間。測(cè)試軟件為MATLAB2021b,測(cè)試環(huán)境為11th Gen Intel(R) Core(TM) i7-11800H @ 2.30 GHz,16 GB RAM。

表1 基準(zhǔn)測(cè)試函數(shù)

參與測(cè)試的算法參數(shù)設(shè)置如下:遺傳算法[24]的精英保留個(gè)數(shù)設(shè)置為2,交叉率0.7,變異率0.1;WOA和IWOA中參數(shù)b都遵循WOA,文獻(xiàn)[15]設(shè)置為1,其余改進(jìn)鯨魚優(yōu)化算法的參數(shù)設(shè)置均參考其原文獻(xiàn)。所有算法的種群大小設(shè)置為30,迭代次數(shù)上限為500次,算法終止條件為|f(x)-fmin|≤10-5或達(dá)到最大迭代次數(shù)。為避免隨機(jī)性,對(duì)每種算法獨(dú)立運(yùn)行1 000次。測(cè)試結(jié)果如表2所示。

表2 算法測(cè)試結(jié)果

由表2可知,在尋優(yōu)精度方面,相較于其他算法,IWOA在測(cè)試函數(shù)F1～F2和F4～F7上求得的結(jié)果最優(yōu),僅在F3上略差于其他算法,這得益于IWOA采用NEWUOA算法作為其局部搜索算子的一部分,增強(qiáng)了算法的搜索能力,并通過引入了自適應(yīng)參數(shù),增加算法的搜索精細(xì)度;在算法求解穩(wěn)定性方面,IWOA在7個(gè)測(cè)試函數(shù)中的最差值指標(biāo)均是最小的,此外,在F1～F2和F4～F7中的均值和標(biāo)準(zhǔn)差指標(biāo)也是最小的,即更接近最優(yōu)值的均值和更小的標(biāo)準(zhǔn)差,僅在F3中的均值和標(biāo)準(zhǔn)差指標(biāo)略差于PWOA,這表明在所有參與測(cè)試的算法中,IWOA在求解穩(wěn)定性方面具有一定的優(yōu)越性。

在平均運(yùn)行時(shí)間方面,IWOA在F1、F3、F4和F6上取得了最短的平均運(yùn)行時(shí)間,而在其余3個(gè)測(cè)試函數(shù)中要差于其他算法。圖2給出了所有算法在迭代500次的過程中最優(yōu)值的均值隨迭代次數(shù)的變化曲線。由圖2可知,IWOA在F2、F5和F7中的收斂曲線所表現(xiàn)出的特性為在迭代前期快速收斂,在中后期略慢于PWOA和GWOA,但最終仍可收斂至最優(yōu)值;在F1、F4和F6中,IWOA在收斂精度方面表現(xiàn)出顯著優(yōu)勢(shì),并且可以在較小的迭代次數(shù)內(nèi)快速收斂至最優(yōu)值或其附近,收斂曲線位于所有算法的下方;在F3中,IWOA同樣在前期有著最快的收斂速度,但其收斂精度要低于PWOA。

圖2 收斂曲線

綜合上述結(jié)果,相較于其他算法,IWOA具有更高求解精度和更好的求解穩(wěn)定性,雖然所提出的改進(jìn)措施對(duì)運(yùn)行時(shí)間存在一定的負(fù)面影響,但仍可在前期加快算法的收斂。

4 基于改進(jìn)鯨魚優(yōu)化算法的混流U型裝配線平衡優(yōu)化

4.1 問題描述

第2類混流U型裝配線平衡問題就是已知工作站的數(shù)量,在混合模型和U型裝配線的情況下,最小化裝配線的節(jié)拍時(shí)間。相較于一般的單模直線型裝配線平衡問題,混流U型裝配線平衡問題的復(fù)雜性更高,主要體現(xiàn)在:①單模的裝配線只生產(chǎn)單一品種的產(chǎn)品,其各個(gè)工序的裝配時(shí)間相對(duì)固定,而混流的裝配線生產(chǎn)多種工藝相似,品種不同的產(chǎn)品,不同產(chǎn)品相同工序的裝配時(shí)間存在差異;②直線型裝配線的工序分配只能按照工序的順序,例如從前往后或從后往前進(jìn)行,而U型線的工序分配更為靈活,可以同時(shí)從裝配線的前后進(jìn)行工序的分配。為了降低混流裝配線平衡問題的復(fù)雜度,一般采取的方式是根據(jù)各產(chǎn)品主生產(chǎn)計(jì)劃(master production schedule,MPS),構(gòu)建綜合工序優(yōu)先級(jí)圖[25],將“混流”轉(zhuǎn)換為“單?！眴栴},如圖3所示,模型A、B、C的MPS為1∶1∶1。本文所建立的數(shù)學(xué)模型基于以下假設(shè):①每中產(chǎn)品的工序所需的裝配時(shí)間是固定值,不受其他因素的影響;②所有模型的優(yōu)先級(jí)圖都可以構(gòu)成綜合優(yōu)先級(jí)圖;③不同產(chǎn)品的相同工序須分配到同一個(gè)工作站;④所有產(chǎn)品的工序優(yōu)先級(jí)相同。

圈中數(shù)字表示工序序號(hào);圈上數(shù)字表示工序時(shí)間

4.2 數(shù)學(xué)模型

針對(duì)第2類混流U型裝配線的平衡問題,優(yōu)化目標(biāo)定義為最小化節(jié)拍時(shí)間Ct,如式(16)所示。

minCt

(16)

模型同時(shí)需要滿足相關(guān)約束:

(17)

(18)

(19)

(20)

(21)

(22)

式中:M為模型數(shù)量;dm為模型m的需求;D為模型總需求;K為工作站數(shù)量;N為工序數(shù)量;tjm為模型m的工序j所需裝配時(shí)間;Tj為工序j的加權(quán)時(shí)間;P為工序優(yōu)先級(jí)集合;xjk和yjk為決策變量,分別為分配順序從前向后和從后向前時(shí),工序j是否分配給工作站k,是則為1,反之為0。

式(17)為裝配線上生產(chǎn)產(chǎn)品的總需求;式(18)為綜合優(yōu)先級(jí)圖中各工序根據(jù)MPS計(jì)算得出加權(quán)裝配時(shí)間;式(19)表示每一道工序都被分配至一個(gè)工作站;式(20)表示每個(gè)工作站的總裝配時(shí)間不得超過節(jié)拍時(shí)間;式(21)和式(22)表示向后和向前的工序分配需要滿足工序的優(yōu)先級(jí)約束。

4.3 編碼與解碼

采用優(yōu)先級(jí)權(quán)重的編碼方式,初始對(duì)每道工序賦予[0,1]的隨機(jī)數(shù),作為該工序的優(yōu)先級(jí)權(quán)重,以Jackson問題為例,其編碼如圖4所示。

圖4 Jackson優(yōu)先級(jí)權(quán)重編碼

解碼就是將種群個(gè)體的編碼信息解釋成工序分配信息,為更好地進(jìn)行工序分配,本文提出一種帶閾值的工序分配方法。根據(jù)影子約束關(guān)系[26],如圖5所示,從前后兩個(gè)方向進(jìn)行分配,具體步驟如下。

圖5 影子約束關(guān)系圖

步驟2根據(jù)P,同時(shí)向前向后搜索無約束的工序,將無緊前工序的工序(P列和為0)放入P1中,無緊后工序的工序(P行和為0)放入P2中。

步驟3分別P1和P2中選擇優(yōu)先級(jí)權(quán)重最大的工序a和b并比較其權(quán)重大小,如果a的權(quán)重大于等于b,轉(zhuǎn)至步驟4,否則轉(zhuǎn)至步驟5。

步驟4如果滿足|TSk+TSa-Ctbest|≤|Ctbest-TSk|且|TSk+TSa-Ctbest|≤B,則將工序a分配至工作站k,TSk=TSk+TSa,將P中工序a所在的行置為0并轉(zhuǎn)至步驟2;否則嘗試分配工序b,如果滿足|TSk+TSb-Ctbest|≤|Ctbest-TSk|且|TSk+TSb-Ctbest|≤B,則將工序b分配至工作站k,TSk=TSk+TSb,將P中工序b所在的列置為0并轉(zhuǎn)至步驟2,否則轉(zhuǎn)至步驟6。

步驟5如果滿足|TSk+TSb-Ctbest|≤|Ctbest-TSk|且|TSk+TSb-Ctbest|≤B,則將工序b分配至工作站k,TSk=TSk+TSb,將P中工序b所在的列置為0并轉(zhuǎn)至步驟2;否則嘗試分配工序a,如果滿足|TSk+TSa-Ctbest|≤|Ctbest-TSk|且|TSk+TSa-Ctbest|≤B,則將工序a分配至工作站k,TSk=TSk+TSa,將P中工序a所在的行置為0并轉(zhuǎn)至步驟2,否則轉(zhuǎn)至步驟6。

步驟6如果k=K-1,將剩余工序分配至工作站K,輸出分配結(jié)果,結(jié)束工序分配程序,否則k=k+1,轉(zhuǎn)至步驟2。

圖6給出了解碼的流程圖。

4.4 算例測(cè)試結(jié)果與分析

為了驗(yàn)證IWOA在求解裝配線平衡問題上的性能,采用網(wǎng)站(https://assembly-line-balancing.de/)[27]中的混流數(shù)據(jù)集作為測(cè)試算例,具體數(shù)據(jù)信息如表3所示,選擇與第3節(jié)中相同的算法作為對(duì)比算法。測(cè)試指標(biāo)為節(jié)拍時(shí)間和對(duì)應(yīng)的平衡率,平衡率RB的計(jì)算公式為

表3 混流裝配線測(cè)試算例

(23)

4.4.1 參數(shù)設(shè)置

針對(duì)Thom、Kim、Arcus三組問題,設(shè)定算法的迭代次數(shù)為500。為避免隨機(jī)性,對(duì)每種算法獨(dú)立運(yùn)行10次,取最優(yōu)值作為最終結(jié)果,并對(duì)表中結(jié)果的最優(yōu)值進(jìn)行加粗處理,其余參數(shù)設(shè)置和測(cè)試環(huán)境與第3節(jié)中保持一致。

4.4.2 結(jié)果和分析

表4給出了8種算法的對(duì)比結(jié)果。根據(jù)表4可知,在簡(jiǎn)單問題Thom1～Thom3上,所有算法均可以求得最佳的生產(chǎn)節(jié)拍;在6個(gè)中等規(guī)模的問題Kim1～Kim6中,IWOA在所有的算例中都能夠求得更小的節(jié)拍時(shí)間;在12個(gè)大規(guī)模的問題Arcus1～Arcus12中,IWOA在11個(gè)算例中求得了最小的節(jié)拍時(shí)間,這說明IWOA具有更好的尋優(yōu)能力。Arcus9～Arcus12因?yàn)榇嬖趩蝹€(gè)工序裝配時(shí)間超過工作站平均裝配時(shí)間的情況,所以無法達(dá)到100%的平衡率。

圖7給出了所有算法在部分用例中的收斂曲線圖。在簡(jiǎn)單算例Thom1中,所有算法都可以在前幾次迭代快速收斂至最優(yōu)值,而在中等算例Kim1和大規(guī)模算例Arcus3,IWOA雖然在前期的收斂速度要落后于其他算法,但仍可收斂至更優(yōu)的值。上述的實(shí)驗(yàn)結(jié)果驗(yàn)證了IWOA的有效性,能夠在復(fù)雜問題上求得更好的解。

圖7 部分算例的收斂曲線

5 結(jié)論

以最小節(jié)拍時(shí)間作為優(yōu)化目標(biāo),建立了第2類混流U型裝配線平衡問題的模型,并提出了一種改進(jìn)的鯨魚優(yōu)化算法IWOA進(jìn)行模型的求解。算法采用均勻設(shè)計(jì)作為初始種群的生成策略,提高初始種群的均勻性;采用NEWUOA算法作為IWOA的局部搜索算子,強(qiáng)化算法的局部搜索性能;在處理越界點(diǎn)時(shí)采用一種基于環(huán)形區(qū)間和隨機(jī)波動(dòng)的修正策略,降低算法陷入局部最優(yōu)的可能;最后引入了非線性收斂因子和自適應(yīng)權(quán)重系數(shù),平衡算法的全局和局部搜索,增強(qiáng)算法的搜索精細(xì)度。針對(duì)第2類混流U型裝配線平衡問題,IWOA的采用優(yōu)先級(jí)權(quán)重的編碼方式,并采用一種帶閾值的解碼方案,盡可能地得到更好的工序分配方案。通過7個(gè)基準(zhǔn)函數(shù)測(cè)試和21個(gè)裝配線標(biāo)準(zhǔn)算例測(cè)試表明IWOA在一般問題上的求解精度和穩(wěn)定性高于對(duì)比算法,同時(shí)在復(fù)雜問題的優(yōu)化效果也要優(yōu)于對(duì)比算法,驗(yàn)證了算法改進(jìn)的有效性,為工程中解決混流U型裝配線的平衡問題提供了可行的解決方案。