求解帶序列相關準備時間雙邊裝配線平衡問題的改進模擬退火算法

趙瀚明，唐秋華，蒙 凱，李梓響，張子凱

(1.武漢科技大學冶金裝備及其控制教育部重點實驗室，湖北 武漢，430081;2.武漢科技大學機械傳動與制造工程湖北省重點實驗室，湖北 武漢，430081)

在現(xiàn)代化生產(chǎn)中，裝配線已經(jīng)成為制造過程的核心和終端環(huán)節(jié)。根據(jù)布局的不同，裝配線可分為單邊裝配線、雙邊裝配線和U型裝配線等。與傳統(tǒng)的單邊裝配線相比，雙邊裝配線在整線長度、物料搬運成本、設備利用率等方面具有明顯優(yōu)勢[1]，因而在汽車等大型產(chǎn)品的制造過程中得到廣泛應用。

雙邊裝配線平衡是將裝配任務依次分到裝配線兩邊的各工位中，以實現(xiàn)成對工位數(shù)最少、總工位數(shù)最少、生產(chǎn)效率更高、負載更均衡等目標[2]。由于工藝流程的限制，裝配任務之間存在優(yōu)先關系約束，每個任務須等待其前序任務全部完成后才能開始。特別地，一個任務需等待同一成對工位內(nèi)對面工位中的前序任務完成之后才能開始，這種情況下產(chǎn)生的等待時間稱為與序列相關的空閑時間[3]。此外，裝配線上的物料搬運、工件更換、模具準備等因素會導致機床需要額外的準備時間去執(zhí)行某個既定任務，這種準備時間可分為與序列無關和與序列相關兩種，前者時長固定，后者時長取決于同一工位內(nèi)前后兩個加工任務的工藝要求[4]。序列相關空閑時間和序列相關準備時間這兩者都會對雙邊裝配線造成一定影響，在雙邊裝配線平衡時合理規(guī)劃任務分配和任務序列，可以增加任務執(zhí)行的并行度，提高生產(chǎn)效率[5]。

雙邊裝配線平衡屬于NP難問題[6],現(xiàn)有求解方法有精確算法[7]、群智能算法[8-10]和局部優(yōu)化算法[11-12]。精確算法能找到問題的最優(yōu)解，但計算時間很長，不適合在大規(guī)模和超大規(guī)模問題上使用。群智能算法魯棒性強，受問題維數(shù)影響較小，具有較高的運行效率，但算法易陷入局部最優(yōu)，收斂速度慢且優(yōu)化性能受參數(shù)設置影響較大。與群智能算法相比，局部優(yōu)化算法更關注問題特征，運算更快捷，所用參數(shù)更少[13]。模擬退火(Simulated Annealing，SA)算法是一種應用較廣的局部優(yōu)化算法，根據(jù)雙邊裝配線平衡問題的特點對SA算法進行改進，能有效提升算法性能，實現(xiàn)全局搜索和局部搜索的均衡，更快找到性能更穩(wěn)定的解。

?zcan等[14]首次提出帶序列相關準備時間的雙邊裝配線平衡問題(Two-sided Assembly Line Balancing Problem with Sequence-dependent Setup Times，TALBPS)，并設計了混合整數(shù)規(guī)劃模型和啟發(fā)式規(guī)則。Delice[15]采用融合10種啟發(fā)式規(guī)則的遺傳算法求解此問題。上述研究雖然考慮了序列相關準備時間和雙邊裝配線平衡的集成，但在大規(guī)模算例上的搜索性能略顯不足。Li等[16]證明以序列相關空閑時間最小化作為二級目標，能實現(xiàn)對大規(guī)模雙邊裝配線問題的深度搜索。

為此，本文提出一種改進的模擬退火算法，用來求解帶序列相關準備時間的第I類(最小化工位數(shù))雙邊裝配線平衡問題，以序列相關空閑時間為二級目標，并設計了基于分級位置權重的啟發(fā)式初始化策略和改進的收斂準則，最后通過雙邊裝配線標桿案例尤其是大規(guī)模案例,對算法的合理性和有效性進行實驗驗證。

1 問題描述

第I類雙邊裝配線平衡問題最常見的優(yōu)化目標是同時最小化成對工位數(shù)和總工位數(shù)[13]，即：

minf1(X)=wnm·nm+wns·ns

(1)

式中：nm和ns分別是分配完成后的成對工位數(shù)量和總工位數(shù)量；ωnm和ωns為參數(shù)，在雙邊裝配線中，一般2個工位組成一個成對工位，因此參數(shù)ωnm和ωns的值分別設為2和1。

雙邊裝配線平衡需要滿足多種約束：節(jié)拍約束、方向約束和優(yōu)先關系約束，并將加工任務按照一定的序列依次分配到各個成對工位上。圖1所示為一個小規(guī)模案例的任務優(yōu)先關系，圖中包含12個任務，圓圈內(nèi)的數(shù)字表示任務的編號；箭頭指向表示任務之間的優(yōu)先關系，由前序加工指向后序加工；括號內(nèi)的數(shù)字表示任務的加工時間，文字表示任務的方向，其中，左/右表示任務必須分配到成對工位的左/右邊，任意表示可分配到任意一邊。

圖1 12個任務的優(yōu)先關系

在雙邊裝配線上，由于優(yōu)先關系的約束，工位中會產(chǎn)生與序列相關的空閑時間。此外，在同一工位內(nèi)執(zhí)行兩個連續(xù)的裝配任務時，還會產(chǎn)生序列相關的準備時間，在以前的文獻中大多忽略了此準備時間[4]。在實際生產(chǎn)中，當準備時間比空閑時間短時，可以將其包含在空閑時間內(nèi)，此時確實可以忽略準備時間對裝配線的影響;然而當準備時間比空閑時間長時，準備時間包含在空閑時間內(nèi)會導致后續(xù)加工任務延后。針對圖1所示案例，圖2(a)和圖2(b)展示了裝配線節(jié)拍為5時不考慮準備時間與考慮準備時間的兩種任務分配結果。圖2(b)中，任務1、5和任務3、7之間，準備時間比空閑時間短；任務9、11之間，準備時間比空閑時間長。從圖中可以看出，考慮序列相關準備時間時所需要的成對工位數(shù)和總工位數(shù)均多一個。由此可知，序列相關準備時間對生產(chǎn)效率具有顯著影響，在裝配線平衡時不能將其忽略。

圖2 考慮準備時間與不考慮準備時間時的任務分配

2 改進的模擬退火算法

2.1 編碼及解碼

針對雙邊裝配線平衡問題的編碼，目前主要有基于任務序列、基于工位和基于分區(qū)等6種方式。Li等[13]測試了所有的編碼方式，認為基于任務序列的編碼是最優(yōu)方案，故本文采用此方式進行編碼，即根據(jù)任務之間的優(yōu)先關系，按照實數(shù)編碼生成初始解。例如，對于圖1所示的優(yōu)先關系，可生成一個初始解：{3, 2, 1, 5, 4, 8, 6, 7, 9, 10, 11, 12}。

關于解碼，目前存在著任務-工位和工位-任務等10種解碼方式，本文采用文獻[13]所證明的最優(yōu)解碼方式ST5，即優(yōu)先選擇當前工位余量更大的邊進行分配，余量相同則選擇左邊，再根據(jù)任務優(yōu)先策略選擇可優(yōu)先分配的任務進行分配。而針對TALBPS問題，還要對ST5中的任務優(yōu)先策略進行調(diào)整，在選擇可優(yōu)先分配的任務時需要額外限制考慮準備時間后的任務總時長仍然在節(jié)拍內(nèi)。

2.2 基于分級位置權重的初始化

原始的模擬退火算法采用的是隨機初始化，隨機性導致初始解的質(zhì)量較差，需要進行改善。分級位置權重(Ranked Positional Weight，RPW)是裝配線平衡領域中性能較優(yōu)的啟發(fā)式初始化方法，具有提升工位平均負荷、降低裝配平衡延遲率和生產(chǎn)線平滑性指數(shù)等優(yōu)勢[5]。每個任務的位置權重等于其加工時長與所有后序任務的加工時長的總和，具體計算步驟為：

(1)根據(jù)優(yōu)先關系找出每個任務的全部后序任務。

(2)按照下式計算每個任務i的RPW權值。

(2)

式中：n為最大任務數(shù)；ti為任務i的加工時間；當任務j是任務i的后序時，δij=1，否則δij=0。

(3)按照RPW值從大到小排序，生成初始解。

位置權重越大的任務意味著其后序任務總時長越大，優(yōu)先分配可使得其后序任務盡早開始，從而減少在制品堆積，使得各工位工時分配接近滿載。這樣就有可能減少裝配線上序列相關的空閑時間，總的工位數(shù)量也可能減小。

2.3 改進的收斂準則

模擬退火算法是基于迭代求解策略的一種隨機尋優(yōu)算法，其基本原理是由當前解通過鄰域搜索產(chǎn)生一個新解，并采用Metropolis準則決定是否接受這個解。以式(1)中的目標作為適應度值，計算出SA算法的原始Metropolis收斂準則為

(3)

式中：df1=f1(X2)-f1(X1)，其中f1(X1)為當前解的適應度值，f1(X2)為新解的適應度值；T為溫度控制參數(shù)，T=T0q，其中T0為較大的初始值，q為衰減系數(shù)，一般取值為0.8～0.99。

式(3)表示：當新解比當前解更優(yōu)(df1<0)時，采用新解替換當前解；否則，按照一定的概率接受惡化解，且概率exp(-df1/T)的值隨著溫度遞減而逐漸減小。Metropolis準則對新解的收斂方向直接決定了SA算法的搜索性能。

然而對于雙邊裝配線平衡問題，由于方向約束、優(yōu)先關系約束等限制條件的復雜性，當算法迭代到一定次數(shù)后，得出的解的適應度值f1(X)往往相同[13]，難以區(qū)分出性能更優(yōu)的解。此時若采用SA算法原始的Metropolis準則，接受新解的概率很低，算法容易陷入局部最優(yōu)，因此本文提出改進的Metropolis收斂準則，見式(4)。

(4)

式中：df2=f2(X2)-f2(X1)，其中f2(X)為工位空閑時間函數(shù)，計算公式為：

f2(X)=

(5)

式中：J為成對工位集；CT為裝配線節(jié)拍；j和k分別代表成對工位和方向；STjk為分配到工位(j,k)上的任務時間，故CT-STjk為工位(j,k)上的空閑時間。

從式(4)可以看出，改進Metropolis收斂準則對解的性能作了進一步的區(qū)分，并按照不同的概率接受性能不同的解。針對TALBPS-I問題，改進收斂準則中的工位空閑時間函數(shù)f2(X)賦予越靠前的成對工位上序列相關的空閑時間越大的權重，在一級目標f1(X)相同的情況下，二級目標f2(X)越小意味著前面的成對工位負載更飽滿。在算法迭代過程中尤其是迭代后期，當df1=0、df2<0時，按照概率1接受新解。此外，改進的收斂準則又區(qū)分了工位數(shù)量更大(df1>0)和工位數(shù)量相同、工位空閑時間更長(df1=0、df2≥0)兩種不同劣解的情況，分別以概率exp(-df1/T)和略小于前者的概率exp(-df2/T)來接受劣解，增大了跳出局部極值的可能性。

2.4 改進的模擬退火算法流程

融合上述算子設計的改進SA算法流程見圖3。首先，采用基于分級位置權重的啟發(fā)式初始化

圖3 改進模擬退火算法的基本流程

策略，并進行局部搜索使用交換算子產(chǎn)生新解；然后，通過解碼得出新解與舊解的適應度值，并執(zhí)行改進的Metropolis收斂準則，保留性能最優(yōu)的解，通過一定的概率接受性能較差的解；最后通過溫度衰減直至達到終止條件。

3 實驗結果與分析

算法采用MATLAB語言編程，所有實驗都在Intel(R) Core(TM) i5-9300H CPU 2.40 GHz 7.79 GB RMA個人電腦上使用Microsoft Windows10系統(tǒng)進行測試。為了保證算法對比的公平性，采用Ni×Ni×ρms作為終止條件，其中Ni為測試案例的任務數(shù)量，ρ一般取值5、10、15等。這個公式保證了算法運行時間隨著問題規(guī)模的增大而增大，對不同規(guī)模案例的計算有了相對一致的終止準則。每次實驗的性能通過相對百分比偏差(Relative Percentage Deviation，RPD)來衡量[16]。

(6)

式中：Somesol和Best分別為任意一種參數(shù)組合獲得的工位數(shù)量和所有參數(shù)組合獲得的最優(yōu)工位數(shù)量。RPD值越低意味著算法的性能越好。

3.1 算法參數(shù)校驗

參數(shù)設置對算法性能影響很大，故需要進行參數(shù)校驗。對于SA算法，有4個可調(diào)整的控制參數(shù)：初始溫度T0、結束溫度Tend、降溫速率q、每個溫度下的迭代鏈長L。每個參數(shù)設置3個水平：T0∈{500，1000，1500}，Tend∈{0.01，0.1，1}，q∈{0.9，0.95，0.98}，L∈{50，100，150}。設計4因素3水平的正交實驗，共有27種參數(shù)組合?？紤]到大規(guī)模案例的參數(shù)對中小規(guī)模案例同樣有效，故求解最復雜的大規(guī)模標桿案例P205[10]并取最大節(jié)拍2832，以運行時間Ni×Ni×5 ms為終止條件，每個實驗運行5次。以5次實驗中的最小RPD作為最終響應值，對所有實驗組合采用田口分析法，信噪比(SNR)均值越大表示該參數(shù)水平性能越好[17]。實驗結果如圖4所示，最佳參數(shù)組合為{T0=500，Tend=0.1，q=0.9，L=100}。為了保證實驗的公平性，以上方法也用于后文中進行對比的其他智能算法的參數(shù)校驗。

圖4 模擬退火算法參數(shù)的信噪比主效應圖

3.2 改進算子性能測試

與原始SA算法相比，本文算法提出了兩點改進：基于分級位置權重的初始化以及改進的收斂準則。為了驗證兩點改進策略的有效性，將原始SA算法、只加入基于分級位置權重初始化策略的SA算法(SA_RPW)、只加入改進的收斂準則的SA算法(SA_Met)和本文改進SA算法進行對比實驗。

為保證改進策略的普適性，分別對大規(guī)模案例P65[10]、P148[1]和P205[10]進行求解，由于每個案例設置有不同的節(jié)拍，故一共有22個案例。以運行時間Ni×Ni×5 ms為終止條件，每個實驗運行5次，取最小RPD值和平均RPD值進行分析。采用方差分析對4種算法的所有結果進行統(tǒng)計，得到RPD值的95%置信區(qū)間，如圖5所示。由圖5可以看出，SA_RPW和SA_Met兩種算法求得的RPD值都要比原始SA求得的RPD值小，證明所提出的兩點改進策略都是有效的。同時，本文SA算法性能最佳，這是因為兩種改進策略之間存在較強的互補性：分級位置權重減少了整條裝配線上序列相關的空閑時間，使得各工位盡量以滿負荷進行生產(chǎn)作業(yè)，達成工位數(shù)量最小化的目標；改進收斂準則使序列相關空閑時間向后面的成對工位集中，減少了所需的成對工位和總工位數(shù)量，促使解的性能更優(yōu)，此外，改進收斂準則還進一步區(qū)分出解的性能，以不同概率接受劣解，避免算法陷入局部最優(yōu)。

(a)最小RPD值

3.3 算法求解

為了分析準備時間對裝配線上工位數(shù)量的影響，采用本文算法求解TALBPS標桿案例，包括4組小規(guī)模案例(P9[8]、P12[8]、P16[10]、P24[8])和3組大規(guī)模案例(P65[10]、P148[1]、P205[10])，其中P148案例的部分任務的加工時間按照文獻[10]進行調(diào)整。每組案例設置有不同的節(jié)拍，總共有37個案例。為保證計算公平，每次計算以運行時間Ni×Ni×10 ms為終止條件，每個案例求解5次。此外，對兩個水平的準備時間分別計算，低水平準備時間在區(qū)間U[0，0.25·min?i∈ITi]內(nèi)隨機產(chǎn)生，高水平準備時間在區(qū)間U[0，0.75·min?i∈ITi]內(nèi)隨機產(chǎn)生，其中，Ti為每個任務的加工時間，I為所有任務的集合。計算結果如表1所示，其中，NM[NS]表示5次結果中的最小成對工位數(shù)量和總工位數(shù)量，LB表示兩種水平準備時間下理論上的最小工位數(shù)量[14]，BWS表示目前已知文獻中標準雙邊裝配線平衡問題標桿案例的

表1 標桿案例計算結果

最優(yōu)解[18]，Gap1、Gap3和Gap2、Gap4分別表示兩種水平準備時間下所求NS值與BWS和LB之間的相對百分比偏差。

從表1可知，在給定的運行時間內(nèi)，本文改進SA算法均能求解出所有大規(guī)模標桿案例的結果，其中，低水平準備時間下的相對百分比偏差Gap1和Gap2的平均值分別為5.84%和6.02%，高水平準備時間下的相對百分比偏差Gap3和Gap4的平均值分別為7.51%和6.30%。而在文獻[14]中，對應的結果與BWS之間的相對百分比偏差分別為Gap1=8.67%、Gap3=12.69%，在文獻[15]中，對應的結果與LB之間的相對百分比偏差分別為Gap2=13.86%、Gap4=20.73%，這是筆者已知的現(xiàn)有文獻取得的最優(yōu)結果。相比較而言，本文提出的改進SA算法取得的結果明顯更優(yōu)。

3.4 算法對比

為了進一步驗證本文算法的性能，將其與另外5種應用較多的典型算法進行了比較，包括遺傳算法(Genetic Algorithm，GA)[15]、迭代貪婪算法(Iterated Greedy Algorithm，IG)[13]、變鄰域搜索算法(Variable Neighborhood Search，VNS)[18]、禁忌搜索算法(Tabu Search，TS)[13]、粒子群算法(Partical Swarm Optimization，PSO)[13]，前面3種算法基于相應文獻中的改進對它們進行了重新編碼和調(diào)整，后面2種算法采用本文提出的兩點改進策略進行了重新編碼和調(diào)整。通過實驗可知，這5種算法每次均能求得案例P148在表1中全部節(jié)拍下的最優(yōu)解，故本節(jié)實驗只針對大規(guī)模標桿案例P65和P205，其他實驗條件與3.3節(jié)相同，表2所示為6種算法求得的最小RPD和平均RPD值。

表2 改進SA算法與其他5種對比算法的性能比較

從表2可以看出，在相同的終止條件下，本文提出的改進SA算法幾乎在所有案例中都表現(xiàn)出優(yōu)于對比算法的性能。通過方差分析對6種算法的RPD值進行統(tǒng)計，結果如圖6所示。由圖可見，在95%置信區(qū)間上，改進SA算法的最小RPD和平均RPD這兩個指標都要顯著優(yōu)于其他5種算法，并且局部優(yōu)化算法IG、VNS和TS的性能略優(yōu)于群智能算法PSO和GA，展現(xiàn)出改進的局部優(yōu)化算法跳出局部最優(yōu)而收斂于全局最優(yōu)的能力，也印證了算法允許在一定程度上接受劣解的必要性。

(a)最小RPD

4 結語

本文針對帶序列相關準備時間的第I類雙邊裝配線平衡問題，提出了一種改進的模擬退火算法，其中包含兩種不同的改進算子：基于分級位置權重的初始化策略以及改進的收斂準則。對比實驗證明這兩點改進是非常有效的，且兩個改進策略之間存在一定的互補性，其綜合應用性能最佳。應用本文算法求解不同規(guī)模的TALBPS標桿案例，計算結果與理論最小工位數(shù)目更為接近，優(yōu)于已知文獻中的最優(yōu)結果。與其他5種典型算法(變鄰域搜索算法、粒子群算法、遺傳算法、迭代貪婪算法和禁忌搜索算法)相比，本文算法在最小相對百分比偏差和平均相對百分比偏差兩個性能指標上顯著更優(yōu)。未來研究將考慮工位間需要準備時間情形下的雙邊裝配線平衡、并行雙邊裝配線平衡以及雙邊裝配線平衡與預防維護的集成優(yōu)化等問題。