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

(1.武漢科技大學(xué)冶金裝備及其控制教育部重點(diǎn)實(shí)驗(yàn)室，湖北 武漢，430081;2.武漢科技大學(xué)機(jī)械傳動(dòng)與制造工程湖北省重點(diǎn)實(shí)驗(yàn)室，湖北 武漢，430081)

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

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

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

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

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

1 問(wèn)題描述

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

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

(1)

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

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

圖1 12個(gè)任務(wù)的優(yōu)先關(guān)系

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

圖2 考慮準(zhǔn)備時(shí)間與不考慮準(zhǔn)備時(shí)間時(shí)的任務(wù)分配

2 改進(jìn)的模擬退火算法

2.1 編碼及解碼

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

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

2.2 基于分級(jí)位置權(quán)重的初始化

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

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

(2)按照下式計(jì)算每個(gè)任務(wù)i的RPW權(quán)值。

(2)

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

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

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

2.3 改進(jìn)的收斂準(zhǔn)則

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

(3)

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

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

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

(4)

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

f2(X)=

(5)

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

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

2.4 改進(jìn)的模擬退火算法流程

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

圖3 改進(jìn)模擬退火算法的基本流程

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

3 實(shí)驗(yàn)結(jié)果與分析

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

(6)

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

3.1 算法參數(shù)校驗(yàn)

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

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

3.2 改進(jìn)算子性能測(cè)試

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

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

(a)最小RPD值

3.3 算法求解

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

表1 標(biāo)桿案例計(jì)算結(jié)果

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

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

3.4 算法對(duì)比

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

表2 改進(jìn)SA算法與其他5種對(duì)比算法的性能比較

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

(a)最小RPD

4 結(jié)語(yǔ)

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