基于改進(jìn)果蠅算法的第一類(lèi)裝配線平衡率優(yōu)化*

杜利珍，張亞軍，董 理，徐 杰

(武漢紡織大學(xué)a.機(jī)械工程與自動(dòng)化學(xué)院；b.紡織科學(xué)與工程學(xué)院，武漢 430073)

0 引言

在制造領(lǐng)域中，裝配線平衡問(wèn)題(assembly line balancing problem，ALBP)[1]是一項(xiàng)十分重要的課題，裝配線是否平衡對(duì)企業(yè)的生產(chǎn)效率和經(jīng)濟(jì)收益有著直接的影響。裝配線平衡問(wèn)題的研究有很多，如潘志豪等[2]結(jié)合非支配排序遺傳算法、布谷鳥(niǎo)搜索算法和動(dòng)態(tài)搜索算法三種算法，解決多目標(biāo)約束的E類(lèi)飛機(jī)總裝脈動(dòng)生產(chǎn)線平衡問(wèn)題；MASOOD等[3]提出一種改進(jìn)的帶變量鄰域搜索的遺傳算法，求解第一類(lèi)生產(chǎn)線平衡問(wèn)題；方喜峰等[4]設(shè)計(jì)了一種結(jié)合遺傳算法、蟻群算法的混合優(yōu)化算法去求解結(jié)合了第一類(lèi)和第三類(lèi)的生產(chǎn)線平衡問(wèn)題。

已知裝配線平衡問(wèn)題屬于NP-hard問(wèn)題[5]，智能算法在裝配線平衡研究中應(yīng)用較多，常見(jiàn)的有遺傳算法(genetic algorithm，GA)[6]、粒子群算法(particle swarm optimization，PSO)[7]和差分進(jìn)化算法(differential evolution，DE)[8]等，GA是一種自適應(yīng)全局優(yōu)化搜索算法，具有自適應(yīng)、自學(xué)習(xí)和自組織的特點(diǎn)；PSO是一種隨機(jī)搜索算法，具有快速的計(jì)算速度和較好的全局搜索能力；DE是一種基于群體的自適應(yīng)全局優(yōu)化算法，具有自適應(yīng)能力強(qiáng)、魯棒性強(qiáng)等特點(diǎn)。

果蠅算法(fruit fly optimization algorithm，F(xiàn)OA)[9]也是智能算法的一種，已經(jīng)在多個(gè)領(lǐng)域運(yùn)用[10-11]。FOA 擁有更好的自適應(yīng)能力，具有迭代過(guò)程簡(jiǎn)單，全局收斂性強(qiáng)，算法執(zhí)行時(shí)間短的特點(diǎn)，同時(shí)FOA也容易過(guò)早收斂、陷入局部最優(yōu)?？紤]到模擬退火算法局部搜索能力強(qiáng)的特點(diǎn)，將退火機(jī)制融入FOA的算法迭代當(dāng)中，幫助FOA跳出局部最解，增加了算法的搜索性，使結(jié)果更趨近于全局最優(yōu)解。本文對(duì)空調(diào)外機(jī)裝配線平衡問(wèn)題展開(kāi)研究，建立以最小工作站數(shù)為目標(biāo)函數(shù)的數(shù)學(xué)模型，綜合考慮實(shí)際市場(chǎng)需求和作業(yè)優(yōu)先關(guān)系，采用改進(jìn)FOA對(duì)空調(diào)外機(jī)裝配線生產(chǎn)實(shí)例求解，求出最小工作站數(shù)和工序在工作站中的分布情況，并對(duì)結(jié)果進(jìn)行分析。

1 問(wèn)題描述

本文是在市場(chǎng)需求和生產(chǎn)節(jié)拍已知的情況下，以空調(diào)裝配線為研究對(duì)象，進(jìn)行裝配線平衡研究，該問(wèn)題屬于第一類(lèi)裝配線平衡問(wèn)題[5]，即裝配線的生產(chǎn)節(jié)拍已定，在生產(chǎn)約束條件的約束下，按照合適的規(guī)則分配作業(yè)元素到工作站中去，得出最小工作站數(shù)。在生產(chǎn)過(guò)程中，生產(chǎn)節(jié)拍受到工藝、場(chǎng)地、物料配送等條件的約束，因此在解決該類(lèi)問(wèn)題時(shí)需要考慮作業(yè)優(yōu)先關(guān)系等問(wèn)題[12]。如何在滿足生產(chǎn)約束條件情況下，對(duì)作業(yè)元素進(jìn)行分配，使工作站的數(shù)量最少并且工作站保持一個(gè)均衡的作業(yè)負(fù)荷，這是本次研究的關(guān)鍵所在。

對(duì)ALBP-Ⅰ進(jìn)行數(shù)學(xué)建模，定義以下符號(hào)和參數(shù)：E為裝配線上任務(wù)的集合，E={1,2,…,n}；CT為裝配線生產(chǎn)節(jié)拍；m為裝配線工作站數(shù)量；ti為完成作業(yè)i所需要的時(shí)間；Sk為分配到第k個(gè)工作站的任務(wù)集合；p=(pij)n×n為裝配作業(yè)優(yōu)先關(guān)系矩陣，若作業(yè)i是作業(yè)j的緊前工序，則pij=1，否則，pij=0；t(Sk)為第k個(gè)工作站的總作業(yè)時(shí)間。

ALBP-Ⅰ可以用如下數(shù)學(xué)模型來(lái)表示[13]：

F1=minm

(1)

s.t.Sx∩Sy=?,x,y=1,2,…,m

(2)

(3)

x≤y,?i∈Sx,j∈Sy,且pij=1

(4)

t(Sk)≤TT,?k=1,2,…,m

(5)

式(1)表示目標(biāo)函數(shù)，表示工作站數(shù)的最小值；式(2)表示作業(yè)分配時(shí)的限制條件，每個(gè)作業(yè)都要被分配到一個(gè)工作站中，并且同一個(gè)作業(yè)不能同時(shí)分配到兩個(gè)及以上個(gè)工作站中；式(3)表示所有工作站中的作業(yè)的集合與裝配線上的任務(wù)集合相等；式(4)表示作業(yè)優(yōu)先關(guān)系，保證作業(yè)分配時(shí)滿足作業(yè)優(yōu)先關(guān)系，確保緊后工序不會(huì)被分配在緊前工序前面的工作站中；式(5)確保每一個(gè)工作站的時(shí)間小于等于生產(chǎn)節(jié)拍。裝配線平衡問(wèn)題的衡量指標(biāo)如表1所示。

表1 計(jì)算公式

TT為理論生產(chǎn)節(jié)拍；T為每天的作業(yè)時(shí)間；Q為日產(chǎn)量；α為裝配線平衡率。

2 改進(jìn)果蠅算法設(shè)計(jì)

2.1 果蠅算法原理介紹

果蠅算法是一種尋求全局優(yōu)化的群體智能算法，它的基本思想主要來(lái)源于果蠅的覓食行為。果蠅通過(guò)嗅覺(jué)搜索食物源，最遠(yuǎn)可達(dá)40 km遠(yuǎn)的距離，當(dāng)果蠅距離食物比較近的時(shí)候，果蠅通過(guò)敏感的視覺(jué)系統(tǒng)繼續(xù)進(jìn)行搜索，并在最后找到食物。根據(jù)果蠅群體的覓食行為的特點(diǎn)，將標(biāo)準(zhǔn)的果蠅優(yōu)化算法分成以下步驟[14]：

步驟1：初始化果蠅群體的位置；

步驟2：給出每個(gè)果蠅嗅覺(jué)搜索時(shí)隨機(jī)方向和距離；

步驟3：因?yàn)橐婚_(kāi)始食物的位置是未知的，因此在計(jì)算味道濃度判定值時(shí)，需要先計(jì)算每個(gè)果蠅與原點(diǎn)之間的距離Dist，再來(lái)計(jì)算味道濃度判定值Di；

步驟4：根據(jù)味道濃度判定函數(shù)(Fitnessfunction)，代入味道濃度判定值Di，求出每個(gè)果蠅個(gè)體的位置相對(duì)應(yīng)的味道濃度Smell；

步驟5：果蠅群體中每個(gè)果蠅都有一個(gè)味道濃度值，找出味道濃度值最大的果蠅，即求出極大值；

步驟6：保留味道濃度值最大的果蠅的味道濃度值和相對(duì)應(yīng)的x、y坐標(biāo)，此時(shí)，果蠅群體利用視覺(jué)系統(tǒng)向味道濃度值最高的果蠅個(gè)體的位置飛去；

步驟7：進(jìn)入到迭代尋優(yōu)步驟，重復(fù)操作步驟2～步驟5，并判斷迭代次數(shù)是否滿足迭代終止條件，若滿足條件，則輸出最優(yōu)結(jié)果。

2.2 改進(jìn)的混合果蠅算法

果蠅算法的每次迭代是以最優(yōu)果蠅個(gè)體為中心，展開(kāi)局部搜索，因此具有結(jié)構(gòu)簡(jiǎn)單、可操作性強(qiáng)、全局尋優(yōu)快的特點(diǎn)，但該算法容易過(guò)早收斂，陷入局部最優(yōu)[15]。針對(duì)該算法的不足之處，本文提出一種混合果蠅算法(hybrid fruit fly optimization algorithm，HFOA)，把果蠅算法與模擬退火算法相結(jié)合，擴(kuò)大種群的搜索范圍。

模擬退火算法(simulated annealing algorithm，SA)具有搜索能力強(qiáng)、操作簡(jiǎn)單、求解速度快的優(yōu)點(diǎn)，因此，可以在果蠅算法的種群迭代過(guò)程中，引入模擬退火操作。如圖1所示，在果蠅算法中設(shè)置一個(gè)判斷機(jī)制，若多次迭代最優(yōu)果蠅個(gè)體位置未更新，則將最優(yōu)果蠅個(gè)體位置進(jìn)行退火操作，保證了混合果蠅算法解的全局性。

圖1 混合果蠅算法流程圖

2.3 工序編碼規(guī)則

本文采用基于權(quán)重的編碼方式[16]，將離散問(wèn)題轉(zhuǎn)化為連續(xù)問(wèn)題進(jìn)行求解。給每一道工序進(jìn)行編號(hào)，同時(shí)，每一道工序?qū)?yīng)著一個(gè)隨機(jī)權(quán)重系數(shù)，這種編碼方式對(duì)種群的更新有一定的促進(jìn)作用。根據(jù)作業(yè)優(yōu)先關(guān)系圖和權(quán)重系數(shù)得到作業(yè)序列，根據(jù)作業(yè)優(yōu)先關(guān)系圖，得到每個(gè)工序的入度，入度是指在有向圖中某點(diǎn)作為邊的終點(diǎn)的次數(shù)之和，得到入度為0的工序，入度為0表示該工序不存在緊前工序，將入度為0的工序組合在一起形成集合V，在集合V中找出權(quán)重系數(shù)最大的向量j，將向量j放到作業(yè)序列PS中，在原有的作業(yè)優(yōu)先關(guān)系矩陣中抹除工序j，重復(fù)操作，直到所有工序都被安排。

以圖2為例，每個(gè)工序的編號(hào)分別是[1,2,3,4,5,6,7,8,9,10,11]，工序?qū)?yīng)的隨機(jī)權(quán)重為[3.52,6.26,3.43,1.99,7.53,1.85,4.92,5.28,6.84,9.40,4.64]，得到工站劃分情況如圖3所示。

圖2 Jackson問(wèn)題作業(yè)優(yōu)先關(guān)系圖 圖3 Jackson問(wèn)題工站山積圖

2.4 自適應(yīng)增長(zhǎng)的權(quán)重更新策略

選取初始種群中最優(yōu)果蠅個(gè)體作為下一代種群的中心果蠅個(gè)體，其它果蠅個(gè)體向中心果蠅靠近，以此來(lái)進(jìn)行種群的更新。果蠅個(gè)體權(quán)重變化采用自適應(yīng)增長(zhǎng)的權(quán)重更新策略，如圖4所示，根據(jù)隨機(jī)函數(shù)產(chǎn)生一個(gè)與矩陣Qbest相同維度的矩陣Ry，矩陣Ry的選取范圍是根據(jù)矩陣Qbest的平均值來(lái)定的，可表示為：對(duì)于矩陣Ry中任意元素ry，都有：

圖4 果蠅個(gè)體權(quán)重變化圖

(8)

式中，Qbest為上一代果蠅種群中最優(yōu)個(gè)體權(quán)重；n為矩陣Qbest中元素個(gè)數(shù)；qk為矩陣Qbest中各元素；rand為0～1之間的隨機(jī)數(shù)。每一次迭代，果蠅個(gè)體權(quán)重都在不斷累加，采用自適應(yīng)增長(zhǎng)的權(quán)重更新策略可以保證果蠅種群的搜索步長(zhǎng)，避免算法過(guò)早收斂。因此，果蠅種群可以表示為X(i)=Qbest+Ry，對(duì)種群中的每個(gè)個(gè)體X(i)，以工作站數(shù)最小作為評(píng)價(jià)指標(biāo)來(lái)進(jìn)行計(jì)算，適應(yīng)度函數(shù)如式(1)所示。

3 算法性能驗(yàn)證

為檢驗(yàn)混合果蠅算法求解第一類(lèi)生產(chǎn)線平衡問(wèn)題的有效性，該算法運(yùn)用MATLAB 2016a編程，在配備8 G內(nèi)存、3.00 GHzCPU的計(jì)算機(jī)上運(yùn)行。為了便于比較，分別對(duì)FOA、SA進(jìn)行編程。

3.1 案例測(cè)試

測(cè)試案例由文獻(xiàn)[17]提供，測(cè)試案例數(shù)據(jù)可在網(wǎng)站http://alb.mansci.de/上獲取，分別使用FOA、SA、HFOA對(duì)這些案例進(jìn)行求解，每個(gè)案例求解10次，記錄求得的最優(yōu)的解以及求得最優(yōu)解的次數(shù)。算法運(yùn)行參數(shù)設(shè)置如下：種群規(guī)模Sizepop=50，最大迭代次數(shù)Maxgen=100，初始溫度T=800，Markov鏈長(zhǎng)度L=50，溫度衰減參數(shù)K=0.95。各測(cè)試案例運(yùn)行結(jié)果如表2所示。

表2 測(cè)試案例運(yùn)行結(jié)果

3.2 算法性能分析

為了更直觀地顯示各算法性能優(yōu)劣的比較結(jié)果，本文采用相對(duì)偏差率(relative percentage deviation，RPD)來(lái)評(píng)估各算法性能[18]。

(9)

(10)

3.3 測(cè)試結(jié)果分析

3種算法對(duì)這22個(gè)標(biāo)準(zhǔn)案例的求解結(jié)果如表2所示，每個(gè)測(cè)試案例求解10次，結(jié)果顯示，F(xiàn)OA并未求得所有測(cè)試案例的最優(yōu)解，SA與HFOA都求的了所有案例的最優(yōu)解，但SA的求解精度沒(méi)有HFOA高，HFOA求得最優(yōu)解的概率要高于FOA與SA。選擇不同規(guī)模的測(cè)試案例中具有代表性的案例，計(jì)算出各個(gè)算法對(duì)于測(cè)試案例求得結(jié)果的平均偏差率，如圖5所示，可以看出HFOA在不同規(guī)模的測(cè)試案例中都取得了較好的ARPD值。因此，混合果蠅算法HFOA求解第一類(lèi)裝配線平衡問(wèn)題是更有效的。

圖5 不同規(guī)模下的平均偏差率

4 空調(diào)裝配線平衡優(yōu)化

4.1 產(chǎn)品裝配時(shí)間測(cè)定

對(duì)裝配線的工位進(jìn)行10次工時(shí)測(cè)定，取10次測(cè)定的平均值作為每個(gè)工位的加工時(shí)間，得到原63個(gè)工位的加工時(shí)間表，空調(diào)外機(jī)裝配線此時(shí)的生產(chǎn)節(jié)拍為20 s，總的作業(yè)時(shí)間為858 s，根據(jù)式(7)計(jì)算出裝配線的裝配線平衡率為68.1%，此時(shí)的裝配線平衡率較低，說(shuō)明該裝配線處于一種較不平衡的狀態(tài)，需要對(duì)該裝配線進(jìn)行優(yōu)化。

根據(jù)市場(chǎng)需求(產(chǎn)品交貨期和交貨數(shù)量)確定裝配線理論生產(chǎn)節(jié)拍為14 s，此時(shí)原工位中有17個(gè)工位的加工時(shí)間超過(guò)理論生產(chǎn)節(jié)拍，最高者達(dá)到20 s，不能滿足實(shí)際需求。因此，運(yùn)用基礎(chǔ)工業(yè)工程知識(shí)，對(duì)原70個(gè)工位進(jìn)行處理，取消、合并、簡(jiǎn)化掉不必要的作業(yè)，最終得到108個(gè)作業(yè)加工時(shí)間表，如表3所示。對(duì)108個(gè)作業(yè)進(jìn)行工藝分析，判斷作業(yè)之間的緊前緊后關(guān)系，得到作業(yè)優(yōu)先關(guān)系矩陣，用于后續(xù)算法計(jì)算。

表3 108個(gè)作業(yè)加工時(shí)間

4.2 案例求解

本文使用的HFOA采用的是基于權(quán)重的編碼方式，通過(guò)隨機(jī)函數(shù)隨機(jī)初始化作業(yè)單元的優(yōu)先權(quán)重，在MATLAB軟件中運(yùn)行算法求解，相關(guān)參數(shù)設(shè)置如下：種群規(guī)模Sizepop=50，最大迭代次數(shù)Maxgen=100，初始溫度T=800，Markov鏈長(zhǎng)度L=50，溫度衰減參數(shù)K=0.95。運(yùn)行程序10次，可以得到10次的數(shù)據(jù)，運(yùn)行結(jié)果出現(xiàn)了10次46個(gè)工作站。因此，最小工作站數(shù)為46，優(yōu)化后的最優(yōu)工作站劃分情況如圖6所示。

圖6 HFOA優(yōu)化后工站山積圖

由表4可得HFOA求解后的生產(chǎn)節(jié)拍為14 s，工作站數(shù)為46個(gè)，根據(jù)式(7)求得裝配線平衡率為91.46%，裝配線平衡率較高，說(shuō)明該條裝配線處于一種較良好的平衡狀態(tài)，使用HFOA對(duì)空調(diào)外機(jī)裝配線優(yōu)化后，生產(chǎn)節(jié)拍降低了6 s，裝配線平衡率提升了23.36%。分別使用FOA和SA對(duì)該問(wèn)題進(jìn)行求解，求解10次，取平均偏差率，將求解結(jié)果與改進(jìn)FOA求解結(jié)果對(duì)比，如表4所示。HFOA與GA、FOA和SA求解結(jié)果相比，HFOA求解10次的平均偏差率要小于FOA和SA。因此，HFOA求解該問(wèn)題具有一定的有效性和優(yōu)越性。

表4 HFOA與其它智能算法求解結(jié)果對(duì)比

5 結(jié)論

本文對(duì)空調(diào)外機(jī)裝配線平衡問(wèn)題展開(kāi)研究，建立了以最小工作站數(shù)為目標(biāo)函數(shù)的數(shù)學(xué)模型，綜合運(yùn)用基礎(chǔ)工業(yè)工程知識(shí)和改進(jìn)FOA對(duì)空調(diào)外機(jī)裝配線實(shí)際案例進(jìn)行優(yōu)化。在原始FOA的基礎(chǔ)上混合了模擬退火算法，通過(guò)標(biāo)準(zhǔn)案例驗(yàn)證，在同一條件下，HFOA能夠更加高效地找到較優(yōu)解。同時(shí)，將HFOA求解結(jié)果與其他智能算法求解結(jié)果相比，工作站數(shù)均有所減少，裝配線平衡率有所提升，優(yōu)化結(jié)果較為明顯，說(shuō)明HFOA對(duì)空調(diào)外機(jī)裝配線平衡問(wèn)題求解具有一定的有效性與可行性。