求解雙邊裝配線第I類平衡問題的改進離散蝙蝠算法*

詹慧文，羅亞波

(武漢理工大學(xué) 機電工程學(xué)院，武漢 430070)

0 引言

雙邊裝配線常用于汽車、裝載機等大型產(chǎn)品的裝配，與單邊裝配線相比，具有縮短裝配線長度，提高工裝、夾具的利用率，降低物流成本等優(yōu)點。裝配線平衡問題按照研究目的可分為兩類：①最小化工位數(shù)[1]；②最小化生產(chǎn)節(jié)拍[2]。1993年，Bartholdi[3]首次提出雙邊裝配線平衡問題，并提出一種基于先分配原則的啟發(fā)式平衡算法。由于TALBP-I復(fù)雜的NP屬性，啟發(fā)式方法可以快速找到問題的近似解，然而任何一種啟發(fā)式規(guī)則都有一定的偏好，可能對某類問題求解效果比較好[4]，具有一定的適用性。2000年，Kim等[5]提出一種基于工位編碼的遺傳算法，但提出的關(guān)鍵位階權(quán)重啟發(fā)式解碼方法使算法無法搜索到部分可行解空間。2007年，針對Kim提出的遺傳算法的缺陷，吳爾飛[6]提出基于序列組合的編碼方法，設(shè)計了相應(yīng)的交叉與變異算子，使搜索過程僅在可行解空間內(nèi)進行，提高了搜索效率。2008年，Baykasoglu等[7]首次應(yīng)用蟻群算法求解TALBP-I，并首次引入?yún)^(qū)域約束，使研究更貼近生產(chǎn)實踐情況。2014年李大雙等[8]研究了基于Pareto機制的多目標(biāo)隨機型TALBP-I，為TALBP-I的研究提供了新思路。2016年，李梓響等[9]研究了TALBP-I的解碼策略，提出了工位-操作融合的解碼策略，改進了以往的操作-工位解碼策略。

目前遺傳算法、蟻群算法、模擬退火算法等被廣泛用于雙邊裝配線平衡問題中，但是Yang[10]于2010年提出的蝙蝠算法，相比遺傳算法等具有易實現(xiàn)、尋優(yōu)精度高、魯棒性好等優(yōu)點，但目前還未見其在雙邊裝配線平衡問題方面應(yīng)用的報道?；掘鹚惴ㄇ蠼怆x散問題具有局限性[11]，需要對其改進，才能夠應(yīng)用于TALBP-I。針對TALBP-I，本文設(shè)計了一種改進離散蝙蝠算法，并與其它文獻結(jié)果對比，驗證算法的有效性。

1 雙邊裝配線平衡問題

1.1 問題描述

雙邊裝配線將生產(chǎn)線分為左右兩邊，兩邊都可以作業(yè)，一對左右對稱分布的工位被稱為成對工位，成對工位中的任一工位被稱為另一工位的伴隨工位。雙邊裝配線工位布置如圖1所示。

由于雙邊裝配線的布局特點，有些任務(wù)適合左邊(L)操作，有些任務(wù)適合右邊(R)操作，有些可以在任意一邊(E)操作，此為操作方位約束。任務(wù)彼此間存在優(yōu)先關(guān)系，此為優(yōu)先約束。圖2是算例P9[5]的任務(wù)優(yōu)先關(guān)系圖，圓圈內(nèi)數(shù)字表示任務(wù)編號，(*，*)分別表示任務(wù)的加工時間和方位。

單邊裝配線上各工位工人之間作業(yè)相互獨立，工位負載等于所有分配在該工位上的任務(wù)操作時間總和。但是，雙邊裝配線由于存在成對工位，左右工位任務(wù)之間存在優(yōu)先關(guān)系，可能會產(chǎn)生因序列相關(guān)而造成的等待時間，具體情況以圖3為例說明。圖3是P9問題第一個成對工位的一個可能布置方案。

圖2 P9任務(wù)優(yōu)先關(guān)系圖

圖3 P9問題第一個成對工位任務(wù)分配圖

右邊工位的任務(wù)6因左邊工位內(nèi)的任務(wù)3和它存在優(yōu)先關(guān)系，所以任務(wù)6必須等待任務(wù)3完成才可以開始裝配，圖3中的剖面線部分就是因序列相關(guān)而產(chǎn)生的1個單位的等待時間。工位節(jié)拍為5，左邊工位已分配不下任何其它任務(wù)，所以末端產(chǎn)生了1個單位的空閑時間，如圖中網(wǎng)格線部分所示。

1.2 啟發(fā)式目標(biāo)函數(shù)

TALBP-I常見的優(yōu)化目標(biāo)為同時最小化成對工位數(shù)和最小化總工位數(shù)[6-7]，即：

minf1=wnm·nm+wns·ns

(1)

式中，nm和ns分別為裝配線使用的成對工位數(shù)和啟用的總工位數(shù)，wnm和wns為相應(yīng)的權(quán)值，一般根據(jù)成對工位數(shù)和總工位數(shù)的比值，設(shè)為2和1。為了在工位相同時篩選出較優(yōu)解，提出如下啟發(fā)式二級目標(biāo)：

(2)

式中，j、J分別為成對工位編號和成對工位集，k為操作方位，CT為節(jié)拍，STjk為分配到工位(j,k)上的操作時間，(CT-STjk)為該工位的空閑時間。該目標(biāo)傾向于保留前面工位空閑時間更少的方案。如果前面工位的空閑時間少，留下的操作會隨之減少，需要的工位數(shù)量也可能會更少。TALBP-I的其他基本約束的數(shù)學(xué)模型描述可參考文獻[3]。

2 改進蝙蝠算法

2.1 基本蝙蝠算法

fi=fmin+(fmax-fmin)·β

(3)

(4)

(5)

上述公式是針對全局搜索方式的，為提高算法性能，蝙蝠算法設(shè)計了如下局部搜索方式：

(6)

隨著迭代過程的進行，響度會逐漸降低，脈沖頻度會提高，迭代過程可用公式(7)、式(8)模擬。

(7)

(8)

2.2 編碼策略：雙重編碼

TALBP-I的優(yōu)先關(guān)系圖是一個有向無環(huán)圖，任務(wù)分配活動可以用AOV網(wǎng)[12](Activity On Vertex)描述，求TALBP-I最優(yōu)解就是求AOV網(wǎng)的最優(yōu)拓撲排序。蝙蝠算法中蝙蝠位置對應(yīng)問題的解，對于TALBP-I，將蝙蝠位置對應(yīng)的解定義成一個n×n的拓撲排序矩陣[13]：

(9)

(10)

式(10)是P9問題的一種可能拓撲排序矩陣，式(10)可以推出它的拓撲排序為3 2 1 6 4 5 9 8 7。

(11)

(12)

(13)

第1列開始，依次重新構(gòu)造拓撲排序矩陣，任務(wù)j被分配到c列的概率為：

(14)

2.3 工位-操作解碼方法

TALBP-I目前廣泛應(yīng)用的解碼方法是“操作-工位”，即首先選擇一個操作，然后選擇工位分配操作[7]。但是這種解碼容易導(dǎo)致成對工位的兩邊負載不均衡，李梓響[9]于2016年提出一種基于“工位-操作”的新解碼方法。其主要思想就是首先選擇余量更大的邊作為當(dāng)前工位，然后優(yōu)先選擇不產(chǎn)生等待時間的操作進行分配。實驗表明該種策略能提高解碼效果，較為顯著地降低工位數(shù)。

2.4 改進的局部搜索機制：變鄰域搜索

基本蝙蝠算法和其他智能算法一樣，同樣存在后期搜索速度慢，易陷入局部最優(yōu)等問題[11]，主要原因還是鄰域結(jié)構(gòu)太過單一，對于TALBP-I這樣的組合優(yōu)化問題，搜索易陷入停滯。為了擴大BA的鄰域搜索空間，本文設(shè)計了4種插入算子，產(chǎn)生鄰域解集，4種插入算子如圖4所示。4種算子按照變鄰域方式搜索，即先用單次插入算子對最優(yōu)任務(wù)序列做輕微擾動，當(dāng)單次插入算子不能獲得更好解時采用多次插入算子，再對任務(wù)序列做較大范圍擾動。

圖4 4種插入算子

2.5 算法步驟

所提IDBA算法采用隨機初始化方法產(chǎn)生初始種群，利用雙重編碼映射機制實現(xiàn)蝙蝠實際位置到拓撲序列映射，采用“工位-操作”方法生產(chǎn)解碼方案，局部搜索采用變鄰域搜索方式，算法基本流程如圖5所示。

3 基于標(biāo)桿算例的比對實驗

圖5 DBA算法流程圖

表1 算法完整名稱及簡寫

從表2可以看出，對于標(biāo)桿算例，只有IDBA和DABC能找到所有問題的最優(yōu)解。各算法求解結(jié)果顯示，GA、ACO求解性能較差，SA較好些，DABC、IDBA均比GA多找到4個更優(yōu)解，比ACO多找到3個更優(yōu)解，比SA多找到一個更優(yōu)解。DABC是對比算法中求解TALBP-I性能最好的算法，但是DABC算法過程過于復(fù)雜。算法首先要利用分級位置權(quán)的啟發(fā)式方法生成初始種群，算法對初始解的質(zhì)量有較強依賴。算法尋優(yōu)過程包含雇傭蜂階段，觀察蜂階段，探測蜂階段，每一個階段都要設(shè)計相應(yīng)的算子。IDBA算法雖然和DABC算法獲得的最優(yōu)解相同，但IDBA算法尋優(yōu)過程簡單，整個過程不產(chǎn)生非法解，不需要二叉樹調(diào)整算法[8]重新調(diào)整任務(wù)序列。與未采用變鄰域搜索方式的DBA相比，改進后IDBA算法性能更好。如對于P205(CT=1133)這種裝配線平衡問題中的“難解”問題[6]，采用變鄰域搜索的IDBA找到了21個工位數(shù)的最優(yōu)解，比DBA少了一個工位數(shù)，事實上對于P205(CT=1133)問題，所有算法中只有IDBA和DABC算法能找到該問題的最優(yōu)解。另外從DBA、IDBA的10次運行結(jié)果可以看出，IDBA比DBA運行結(jié)果更穩(wěn)定，證明IDBA搜索域更廣，在搜索過程中可以很好的保持種群的多樣性。

表2 算法對比結(jié)果

4 結(jié)論

本文針對TALBP-I所具有的離散性、序列相關(guān)性等特征，采用雙重編碼機制，使基本蝙蝠算法可以解決離散問題，擴展了蝙蝠算法的應(yīng)用范圍。所提改進蝙蝠算法為了避免搜索過程陷入局部最優(yōu)，設(shè)計了四種插入算子，進行變鄰域搜索，改進了蝙蝠算法單一的局部搜索方式?；跇?biāo)桿問題的對比實驗驗證了所提算法求解TALBP-I的有效性和優(yōu)越性，為解決TALBP-I提供了新方法。然而本文只研究了基礎(chǔ)的TALBP-I，未來復(fù)雜約束耦合的TALBP-I和第II類平衡問題將是下一步的研究內(nèi)容。