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

(武漢紡織大學a.機械工程與自動化學院；b.紡織科學與工程學院，武漢 430073)

0 引言

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

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

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

1 問題描述

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

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

ALBP-Ⅰ可以用如下數(shù)學模型來表示[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)表示目標函數(shù)，表示工作站數(shù)的最小值；式(2)表示作業(yè)分配時的限制條件，每個作業(yè)都要被分配到一個工作站中，并且同一個作業(yè)不能同時分配到兩個及以上個工作站中；式(3)表示所有工作站中的作業(yè)的集合與裝配線上的任務集合相等；式(4)表示作業(yè)優(yōu)先關系，保證作業(yè)分配時滿足作業(yè)優(yōu)先關系，確保緊后工序不會被分配在緊前工序前面的工作站中；式(5)確保每一個工作站的時間小于等于生產(chǎn)節(jié)拍。裝配線平衡問題的衡量指標如表1所示。

表1 計算公式

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

2 改進果蠅算法設計

2.1 果蠅算法原理介紹

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

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

步驟2：給出每個果蠅嗅覺搜索時隨機方向和距離；

步驟3：因為一開始食物的位置是未知的，因此在計算味道濃度判定值時，需要先計算每個果蠅與原點之間的距離Dist，再來計算味道濃度判定值Di；

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

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

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

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

2.2 改進的混合果蠅算法

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

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

圖1 混合果蠅算法流程圖

2.3 工序編碼規(guī)則

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

以圖2為例，每個工序的編號分別是[1,2,3,4,5,6,7,8,9,10,11]，工序對應的隨機權重為[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問題作業(yè)優(yōu)先關系圖 圖3 Jackson問題工站山積圖

2.4 自適應增長的權重更新策略

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

圖4 果蠅個體權重變化圖

(8)

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

3 算法性能驗證

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

3.1 案例測試

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

表2 測試案例運行結果

3.2 算法性能分析

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

(9)

(10)

3.3 測試結果分析

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

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

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

4.1 產(chǎn)品裝配時間測定

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

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

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

4.2 案例求解

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

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

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

表4 HFOA與其它智能算法求解結果對比

5 結論

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