求解隨機型雙邊裝配線平衡問題的混合回溯搜索優(yōu)化算法

吳　意，唐秋華，張利平, 何曉霞

(1. 武漢科技大學(xué)機械自動化學(xué)院，湖北 武漢，430081；2. 武漢科技大學(xué)理學(xué)院，湖北 武漢，430065)

?

求解隨機型雙邊裝配線平衡問題的混合回溯搜索優(yōu)化算法

吳意1，唐秋華1，張利平1, 何曉霞2

(1. 武漢科技大學(xué)機械自動化學(xué)院，湖北 武漢，430081；2. 武漢科技大學(xué)理學(xué)院，湖北 武漢，430065)

摘要：針對現(xiàn)實生產(chǎn)中普遍存在的操作時間為隨機的雙邊裝配線平衡問題，提出一種混合回溯搜索優(yōu)化算法。該算法將變鄰域搜索算法的局部搜索能力融入到回溯搜索優(yōu)化算法的全局搜索中，從而實現(xiàn)廣度搜索和深度搜索的平衡。運用基于隨機鍵的編碼將用于求解連續(xù)問題的回溯搜索優(yōu)化算法應(yīng)用于離散組合優(yōu)化問題，同時提出一種基于均衡雙邊負載的邊選擇策略和減少工位空閑時間的任務(wù)選擇策略的解碼方法，并將該方法同另外4種解碼方法進行對比，以驗證其優(yōu)越性。標桿算例測試表明，所提出的算法具有可行性和有效性。

關(guān)鍵詞：隨機型雙邊裝配線；裝配線平衡問題；回溯搜索優(yōu)化算法；變鄰域搜索算法；混合算法

與傳統(tǒng)的單邊裝配線相比，雙邊裝配線可以縮短裝配線長度、提高工具夾具利用率、減少設(shè)備投資和維護成本、減少物料搬運、提高工人工作效率[1]，故被廣泛應(yīng)用于汽車、裝載機等大型產(chǎn)品的裝配。平衡裝配線的工位負載，可以極大提高生產(chǎn)效率和資源利用率，也導(dǎo)致裝配線平衡成為裝配線規(guī)劃和設(shè)計過程中的首要問題。根據(jù)求解目標的不同，雙邊裝配線平衡問題可以分為TALBP-Ⅰ和TALBP-Ⅱ兩類子問題，其中TALBP-Ⅰ是已知節(jié)拍，最小化工位數(shù)目，而TALBP-Ⅱ是已知工位數(shù)目，最小化生產(chǎn)節(jié)拍。

1993年Bartholdi[1]首次提出了雙邊裝配線平衡問題的概念，并且給出了一種基于優(yōu)先匹配原則的啟發(fā)式平衡算法。此后許多學(xué)者對雙邊裝配線平衡問題進行了研究。Hu等[2]提出了一種面向工位的枚舉算法來求解雙邊裝配線平衡問題。Wu等[3]提出了分支定界算法解決雙邊裝配線平衡問題。Kim等[4]提出了一種基于“工位”編碼方式的遺傳算法，解決了具有位置約束的第一類裝配線平衡問題。Lee等[5]對雙邊裝配時任務(wù)的相關(guān)度和任務(wù)安排的松弛度進行了研究。吳爾飛等[6]提出一種基于任務(wù)排列序列的遺傳算法，求解了第一類雙邊裝配線平衡問題。Yuan等[7]運用延遲接受爬山算法解決含有位置約束、區(qū)域約束和協(xié)同約束的雙邊裝配線平衡問題。李大雙等[8]采用殖民競爭算法，求解了多約束雙邊裝配線平衡問題。

以上研究中均假設(shè)操作時長是確定的、不改變的，而在實際裝配過程中，不論是人工裝配還是機器人裝配，操作時間本身都帶著不確定性。這些不確定因素可能導(dǎo)致確定條件下所求出最優(yōu)平衡方案的性能衰減，甚至不可行，導(dǎo)致生產(chǎn)過程中效率降低，甚至造成生產(chǎn)中斷。對于操作時間的變動符合某種概率分布的隨機雙邊裝配線平衡問題，?zcan[9]提出機會約束分段線性的混合整數(shù)規(guī)劃模型并且采用模擬退火算法求解隨機型雙邊裝配線平衡問題；李大雙等[10]采用多目標混合殖民競爭算求解了隨機型雙邊裝配線平衡問題。

從上述研究現(xiàn)狀可以看出，目前大多數(shù)研究者主要致力于確定型的雙邊裝配線平衡問題，對于現(xiàn)實制造環(huán)境中廣泛存在的隨機裝配線的平衡問題研究較少。針對以上問題，本文提出一種混合回溯搜索優(yōu)化算法，該算法結(jié)合回溯搜索優(yōu)化算法的全局能力和變鄰域搜索算法的局部搜索能力，以期實現(xiàn)搜索深度和廣度間的平衡。同時提出一種均衡各工位任務(wù)負載和減少序列相關(guān)所引起的空閑時間的解碼策略。

1隨機型雙邊裝配線平衡問題

雙邊裝配線是在單邊裝配線的基礎(chǔ)上，將原本的單一生產(chǎn)線分為左右兩條線，任務(wù)在裝配線的左右兩側(cè)并行裝配。在傳送帶左右兩側(cè)，面對面的兩個工位稱為成對工位，兩工位間彼此稱為伴隨工位。

裝配線平衡問題可用如圖1所示的優(yōu)先關(guān)系圖表示。圖1中圓圈內(nèi)的數(shù)字代表任務(wù)，圓圈下邊的標簽(ti，di)代表完成任務(wù)所需的時間和方向，箭頭表示任務(wù)之間的優(yōu)先關(guān)系。對任務(wù)來說，有些僅能在雙邊裝配線的左邊完成，用L表示；有些僅能在雙邊裝配線的右邊完成，用R表示；還有些可以在任一邊完成，稱為E。在雙邊裝配線平衡時必須考慮由于序列相關(guān)所導(dǎo)致的空閑時間。如果一對具有優(yōu)先關(guān)系約束的任務(wù)被分配到同一個成對工位的兩邊，則后續(xù)任務(wù)必須等待其伴隨工位中的前序任務(wù)完成之后才能開始操作，因此有可能產(chǎn)生序列相關(guān)空閑時間。

圖1　雙邊裝配線優(yōu)先關(guān)系圖

2基于混合回溯搜索優(yōu)化算法的隨機型雙邊裝配線平衡

回溯搜索優(yōu)化算法(Backtracking Search Optimization Algorithm，BSA)是Civicioglu于2013年提出的一種新的進化算法[11]。該算法只有一個控制參數(shù)，操作簡單。同時，在優(yōu)化過程中通過產(chǎn)生實驗種群、調(diào)整搜索方向和搜索邊界，使算法具有可快速、有效收斂的優(yōu)勢。鑒于其良好的優(yōu)化性能，BSA已成功用于求解置換流水車間調(diào)度問題[12]，本文是首次將其應(yīng)用于求解隨機型TALBP-Ⅰ問題。

BSA算法共分為種群初始化、選擇Ⅰ、變異、交叉和選擇Ⅱ5個部分。為提高BSA的局部搜索能力以獲得更優(yōu)解，本文提出將變鄰域搜索加入到BSA中，形成混合BSA(HBSA)算法，其總體框架如圖2所示。

圖2　HBSA算法總體框架

2.1編碼和初始化

BSA采用隨機方法進行種群初始化，如下式所示：

Pi,j～U(lowj,upj)

(1)

式中：P為種群；N和D分別表示種群規(guī)模和問題維度；lowj和upj分別為搜索空間中第j維的下界和上界；U表示隨機均勻分布函數(shù)。

隨機型雙邊裝配線平衡問題是典型的離散組合優(yōu)化問題，但BSA算法更適用于求解有邊界值的連續(xù)問題。為了使BSA算法能用于求解離散問題，借鑒Bean[13]的隨機鍵編碼方法產(chǎn)生任務(wù)序列。該方法具體為：將算法的維度對應(yīng)于裝配任務(wù)數(shù)，為每個任務(wù)生成0～1之間的隨機數(shù)，隨機數(shù)的大小表示任務(wù)的優(yōu)先級，隨機數(shù)越小，優(yōu)先級越高，在任務(wù)序列中優(yōu)先分配。以圖1所示的9個任務(wù)為例，對其產(chǎn)生如表1所示的9個[0,1]之間的隨機數(shù)。由表1中可見任務(wù)3對應(yīng)的隨機數(shù)最小，排在任務(wù)排序的第一位，依此類推，獲得9個任務(wù)的排序為：{3,1,4,2,6,5,9,7,8}。

表1　隨機鍵編碼

2.2解碼

基于隨機鍵的編碼可以獲得一組任務(wù)排序，但是該任務(wù)排序僅指明在分配過程中各任務(wù)的優(yōu)先權(quán)，還需要進一步解碼來獲得可行解。

針對雙邊裝配線平衡，常用的啟發(fā)式解碼策略是直接選擇待分配任務(wù)。為促進裝配線同一成對工位兩邊的負載均衡，提出先選邊、再選任務(wù)的解碼策略，其解碼思想是：首先為當(dāng)前成對工位的左右兩邊同時產(chǎn)生兩組候選任務(wù)集，然后優(yōu)先選擇開始時間早的一邊，最后從當(dāng)前所選邊的候選任務(wù)集中優(yōu)先選擇可以減少序列相關(guān)時間的任務(wù)。通過邊選擇策略可以均衡工位之間的負載，通過任務(wù)選擇策略可以減少任務(wù)之間序列相關(guān)閑置時間。詳細解碼流程如圖3所示。另外，在不違反節(jié)拍約束和方向約束的條件下，最后的成對工位可合并為一個工位，以減少工位數(shù)量。

圖3　解碼流程

(2)

式中：Φ-1(α)為分布函數(shù)在概率值為α?xí)r所對應(yīng)的值。

分析式(2)可知，若要任務(wù)完成時間百分百滿足節(jié)拍約束，則會導(dǎo)致節(jié)拍無窮大。實際上，每個操作完成時間接近最大實際完成時間的概率極小，并無必要強制要求節(jié)拍大于最大實際完成時間，故僅強制各工位以概率α滿足節(jié)拍約束。換言之，允許各工位以(1-α)的概率違背節(jié)拍約束，在實際生產(chǎn)中遇到此類情形時，采用停機方式處理。上述思想可用下式表示：

(3)

式中：CT為節(jié)拍；I為任務(wù)集。

2.3適應(yīng)度函數(shù)

由于求解的是第一類裝配線平衡問題，用下式作為目標函數(shù)，以縮短生產(chǎn)線的長度：

(4)

式中：NM表示成對工位數(shù)量；NS表示總工位數(shù)量；wnm和wns為系數(shù)，考慮到一個成對工位包含兩個工位，令其分別取值2和1。

2.4選擇Ⅰ

設(shè)計選擇Ⅰ算子的目的是對種群進行篩選，以構(gòu)造新的歷史種群OldP，具體如下式所示：

ifa

(5)

式中：a,b為(0,1)上服從均勻分布的隨機數(shù)。

利用式(5)，可從前代種群中隨機性地記憶某個歷史種群，直至歷史種群再次發(fā)生改變。并且在歷史種群OldP確定之后，對OldP中各個體的位置進行隨機排列。

通過對歷史種群的這一操作，實現(xiàn)算法對種群位置的記憶功能。同時，利用歷史種群與當(dāng)前種群的差別，還可作為搜索方向，進一步指導(dǎo)搜索過程。

2.5變異

通過下式執(zhí)行變異操作，生成初始實驗種群Mutant：

Mutant=P+F(OldP-P)

(6)

式中：F為控制搜索方向矩陣OldP-P幅度的參數(shù)，F(xiàn)=3rand，其中rand為[0,1]上服從正態(tài)分布的隨機數(shù)。

2.6交叉

交叉過程產(chǎn)生最終的實驗種群T。實驗種群T的初始取值為變異過程產(chǎn)生的Mutant。BSA算法中提出了一種新的種群交叉策略。該交叉策略的第一步是根據(jù)下式計算N×D的二元整數(shù)矩陣map：

(7)

式中：a、b為[0，1]上的隨機數(shù)；mixtrate為混合比例參數(shù)；randi(D)表示在[0, D]中隨機取一個整數(shù)；u為隨機排序后的整數(shù)向量，u∈[1,2,…,D]。

map的初始值為1，采用式(7)的兩種方式來定義map的取值：當(dāng)a

第二步是根據(jù)map的取值采用下式更新實驗種群T：

(8)

2.7選擇Ⅱ

通過貪婪選擇機制在新種群T與初始種群P中選擇目標值較好的種群個體，并記錄當(dāng)前最優(yōu)解和對應(yīng)的解向量，同時更新初始種群，完成一次迭代。

2.8變鄰域搜索

(1)交換(N1)：隨機選擇兩個任務(wù)，交換兩個任務(wù)在操作序列的位置。

(2)多交換(N2)：將交換操作執(zhí)行兩次。

(3)后插(N3)：隨機選擇兩個任務(wù)，將前面的任務(wù)插入到另一個任務(wù)的后面。

(4)前插(N4)：隨機選擇兩個任務(wù)，將后面的任務(wù)插入到另一個任務(wù)的前面。

(a)交換

(b)多交換

(c)后插

(d)前插

設(shè)計圖5所示的算法流程，可交替使用4種鄰域結(jié)構(gòu)，拓寬局部搜索的范圍。

圖5　VNS偽代碼

3算例分析

混合回溯搜索優(yōu)化算法采用 C++語言編程，在電腦CPU為Intel(R) Core5(TM) CPU 3.1 GHz, 8 GB內(nèi)存的Microsoft Visual Studio 2010 平臺下運行。為了驗證所提出的啟發(fā)式解碼和混合回溯搜索優(yōu)化算法的優(yōu)越性能，首先對啟發(fā)式解碼方法進行了對比，然后將計算結(jié)果同現(xiàn)有文獻的計算結(jié)果進行對比。對基準問題P65[5]、P148[1]和 P205[5]進行測試，任務(wù)的方差(包含高方差和低方差)及其他數(shù)據(jù)與文獻[9]一致，概率值α設(shè)定為0.9，相對應(yīng)的正態(tài)分布函數(shù)值為1.28。

3.1解碼對比

本研究中，在啟發(fā)式解碼中采用的任務(wù)選擇策略是優(yōu)先選擇不產(chǎn)生空閑時間的任務(wù)(EBT)。為了說明這種任務(wù)選擇策略的優(yōu)越性，將其與以下幾種不同的任務(wù)選擇策略組成的解碼方式進行對比：①選擇后續(xù)任務(wù)操作時間總和最長的任務(wù)(MAX-TTST)；②選擇具有最多直接后續(xù)作業(yè)數(shù)的任務(wù)(MAX-IFOL)；③選擇有最多后續(xù)作業(yè)數(shù)的任務(wù)(MAX-TFOL);④選擇有最大位置權(quán)重的任務(wù)(MAX-RPW)，位置權(quán)重是指該任務(wù)及該任務(wù)所有后續(xù)任務(wù)的操作時間的和。

將5種解碼方式分別對P148低方差進行求解，每組求解10次。采用相對百分率偏差 (Relative Percentage Deviation, RPD)比較不同解碼方式獲得解的質(zhì)量：

(9)

式中：Somesol表示采用任意一種解碼方式獲得的工位數(shù)；Best表示所有解碼中的最優(yōu)工位數(shù)。

同時，用方差分析(Analysis of Varicance,

ANOVA)來統(tǒng)計分析不同解碼方式獲得解的質(zhì)量，其中解碼作為自變量。在95%最小顯著差數(shù)間隔的置信水平下，5種任務(wù)選擇策略解碼的均值如圖6所示。從圖6中可以看出，本文所提出的解碼方式EBT性能最優(yōu)。

圖6　解碼平均值對比

3.2計算結(jié)果對比

為了驗證混合回溯搜索優(yōu)化算法的有效性，本文將該算法同?zcan[9]提出的模擬退火算法及李大雙[10]提出的多目標混合殖民競爭算法進行對比。每個案例獨立運行10次，取最好的結(jié)果。算法的參數(shù)設(shè)置為：種群規(guī)模為50；混合比例參數(shù)mixtrate設(shè)置為1，算法終止條件為運行時間t=n×n×10 ms,n為任務(wù)數(shù)。運行結(jié)果對比如表2所示。

從表2可以看出，對基準問題P65、P148和 P205，混合回溯搜索優(yōu)化算法取得了當(dāng)前所有的最優(yōu)解。同時，混合回溯搜索優(yōu)化算法還更新了以下7個最優(yōu)值：在低方差的計算結(jié)果中，P148(CT=357)和P205(CT=1888)減少了1個成對工位和1個工位；P205(CT=1510、1699)減少了1個成對工位；P148(CT=510)減少了1個工位；在高方差的計算結(jié)果中，P205(CT=2077)減少了1個成對工位，而P205(CT=2832)則同時減少了1個成對工位和1個工位。由此可見，混合回溯搜索優(yōu)化算法能夠有效求解隨機型雙邊裝配線平衡問題，對實際生產(chǎn)中減少工位數(shù)、降低成本具有重要指導(dǎo)意義。

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

續(xù)表

問題節(jié)拍/s低方差計算結(jié)果NM[NS]模擬退火算法多目標混合殖民競爭算法混合回溯搜索優(yōu)化算法 高方差計算結(jié)果NM[NS]模擬退火算法多目標混合殖民競爭算法混合回溯搜索優(yōu)化算法P205132212[23]11[21]11[21]---151010[20]10[18]9[18]11[22]10[20]10[20]16999[18]9[16]8[16]10[19]9[17]9[17]18888[16]8[15]7[14]9[18]8[16]8[16]20778[15]7[13]7[13]8[16]8[14]7[14]22667[14]6[12]6[12]8[15]7[13]7[13]24547[13]6[11]6[11]7[14]6[12]6[12]26436[12]5[10]5[10]7[13]6[11]6[11]2832---6[12]6[11]5[10]

4結(jié)語

本文首次將回溯搜索優(yōu)化算法應(yīng)用到裝配線平衡問題的求解中，并且針對隨機型雙邊裝配線平衡問題，提出了一種混合回溯搜索優(yōu)化算法。該算法利用隨機鍵進行初始化，并且將變鄰域搜索算法的局部搜索能力同回溯搜索優(yōu)化算法的全局搜索能力相結(jié)合，在算法的搜索深度和廣度之間取得了較好平衡。同時，針對雙邊裝配線的獨有特性，即任務(wù)序列相關(guān)性會導(dǎo)致工位空閑時間，提出了一種均衡工位之間負載和減少序列相關(guān)空閑時間的解碼方法。通過不同方式的解碼對比，并采用方差分析驗證了所提出解碼方法的優(yōu)越性。標桿案例測試表明，該算法獲得了全部的當(dāng)前最優(yōu)解，且更新了7個最優(yōu)值，表明其具有可行性和有效性。

參考文獻

[1]Bartholdi J J. Balancing two-sided assembly lines: a case study[J]. International Journal of Production Research, 1993, 31(10): 2447-2461.

[2]Hu X F, Wu E F, Jin Y. A station-oriented enumerative algorithm for two-sided assembly line balancing[J]. European Journal of Operational Research, 2008, 186(1): 435-440.

[3]Wu E F, Jin Y, Bao J S, et al. A branch-and-bound algorithm for two-sided assembly line balancing[J]. International Journal of Advanced Manufacturing Technology, 2008, 39: 1009-1015.

[4]Kim Y K, Kim Y, Kim Y J. Two-sided assembly line balancing: a genetic algorithm approach[J]. Production Planning and Control, 2000, 11(1): 44-53.

[5]Lee T O, Kim Y, Kim Y K. Two-sided assembly line balancing to maximize work relatedness and slackness[J]. Computers and Industrial Engineering, 2001, 40(3): 273-292.

[6]吳爾飛，金燁，續(xù)愛民，等. 基于改進遺傳算法的雙邊裝配線平衡[J].計算機集成制造系統(tǒng), 2007,13(2):268-274.

[7]Yuan B, Zhang C Y, Shao X Y. A late acceptance hill-climbing algorithm for balancing two-sided assembly lines with multiple constraints[J]. Journal of Intelligent Manufacturing, 2015, 26(1): 159-168.

[8]李大雙, 張超勇, 邵新宇, 等. 基于殖民競爭算法的多約束雙邊裝配線平衡[J]. 機械工程學(xué)報, 2015, 51(2): 183-189.

[9]?zcan U. Balancing stochastic two-sided assembly lines:a chance-constrained, piecewise-linear, mixed integer program and a simulated annealing algorithm [J]. European Journal of Operational Research, 2010, 205 (1): 81-97.

[10]李大雙，張超勇，邵新宇，等. 基于多目標殖民競爭算法的隨機型雙邊裝配線[J]. 計算機集成制造系統(tǒng), 2014, 20(11): 2774-2787.

[11]Civicioglu P. Backtracking search optimization algorithm for numerical optimization problems[J]. Applied Mathematics and Computation, 2013, 219(15): 8121-8144.

[12]Lin Q, Gao L, Li X Y, et al. A hybrid backtracking search algorithm for permutation flow-shop scheduling problem[J]. Computers and Industrial Engineering, 2015, 85: 437-446.

[13]Bean J C. Genetic algorithms and random keys for sequencing and optimization[J].ORSA Journal on Computing, 1994, 6(2): 154-160.

[責(zé)任編輯鄭淑芳]

Solving stochastic two-sided assembly line balancing problem via hybrid backtracking search optimization algorithm

WuYi1,TangQiuhua1,ZhangLiping1,HeXiaoxia2

(1.College of Machinery and Automation, Wuhan University of Science and Technology, Wuhan 430081, China；2. College of Science, Wuhan University of Science and Technology, Wuhan 430065, China)

Abstract:In this paper, a hybrid backtracking search optimization algorithm (HBSA) is proposed to solve the widespread stochastic two-sided assembly line balancing problem. The local search ability of the variable neighborhood search (VNS) is integrated into the global search ability of backtracking search optimization algorithm (BSA) so as to make the balancing between diversification and intensification. The random-key based encoding scheme is employed for successfully applying BSA which is originally proposed for continuous problem to discrete combinatorial optimization problem. A decoding scheme which is based on side and task selection strategies is used to balance the workload between workstations and reduce idle time related to sequence-dependence. And the performance of the proposed decoding scheme is demonstrated by comparison with four other decoding schemes which are based on different heuristic task selection strategies. The corresponding benchmark experiment results demonstrate that the proposed algorithm can solve the problem effectively.

Key words：stochastic two-sided assembly line； assembly line balancing problem; BSA; VNS; hybrid algorithm

收稿日期：2015-12-22

基金項目：國家自然科學(xué)基金資助項目(51275366，51305311，11201356).

作者簡介：吳意(1990-),男，武漢科技大學(xué)碩士生.E-mail:wuyiwust@126.com通訊作者：唐秋華(1970-)，女，武漢科技大學(xué)教授，博士生導(dǎo)師.E-mail：tangqiuhua@wust.edu.cn

中圖分類號：F403.7

文獻標志碼：A

文章編號：1674-3644(2016)02-0121-07