基于禁忌粒子群算法的混流裝配線排序研究*

翁耀煒，魯建廈，鄧 偉

（浙江工業(yè)大學(xué) 工業(yè)工程研究所，浙江 杭州 310014）

0 引 言

混流裝配線可以在基本不改變生產(chǎn)組織方式的前提下，同時生產(chǎn)出多種不同型號、不同數(shù)量的產(chǎn)品，它是應(yīng)對大規(guī)模定制生產(chǎn)的一種有效組織方式[1]。目前，我國家電、汽車生產(chǎn)行業(yè)大量采用了混流裝配方式，裝配線上合理的投產(chǎn)順序能有效提高裝配線的生產(chǎn)效率、降低生產(chǎn)周期和充分利用生產(chǎn)資源，因此解決混流裝配線的排序問題是混流裝配線能否高效運作的關(guān)鍵。

在求解混流裝配線的排序問題上，通過智能算法求解是目前的研究重點。目前，常用的智能算法有遺傳算法、粒子群算法（PSO）、蟻群算法等。鄭永前、王永生等[2]通過免疫粒子群算法求解最小化超載時間與空閑時間的費用的混流裝配線排序模型，但算法結(jié)果一般，且沒有考慮其他影響裝配線效率的因素；劉煒琪、劉瓊等[3]通過混合粒子群算法求解以最小化超載時間、最小化調(diào)整時間、最小化產(chǎn)品變化率為優(yōu)化目標(biāo)的混流裝配線排序模型，取得一定的效果，但忽略了所優(yōu)化的多目標(biāo)間的沖突和競爭；王炳剛、饒運清等[4]和蘇平、于兆勤[5]通過混合遺傳算法對零部件消耗均勻和最短生產(chǎn)循環(huán)周期對混流裝配線排序問題進行優(yōu)化；董巧英、闞樹林等[6]通過改進離散微粒群算法對最小超載、空閑和調(diào)整時間的費用最低的混流裝配線排序問題進行優(yōu)化；薛琴微、蘭秀菊等[7]通過小生境蟻群算法求解以傳送帶中斷時間最短為目標(biāo)的混流裝配線優(yōu)化模型。

與其他算法相比，粒子群算法在求解過程中，微粒只需要在解空間內(nèi)追隨最優(yōu)的微粒進行搜索，并用公式來更新自己的速度及位置，不需要進行交叉和變異等操作，具有原理簡單、計算方便、全局搜索能力強等優(yōu)點。在連續(xù)空間的實值型處理上已經(jīng)表現(xiàn)出優(yōu)良的性能，但其不能直接進行離散空間問題的求解，且容易陷入局部最優(yōu)點，禁忌搜索算法（TS，Tabu Search 或Taboo Search）[8]具有很強的局部搜索能力，可以有效避免陷入局部最優(yōu)。

因此，本研究通過建立基于PSO 算法和禁忌搜索算法的模型求解混流裝配線排序問題。

1 混流裝配線排序數(shù)學(xué)模型建立

1.1 混流裝配線排序問題描述

由于混流裝配線的類型各不相同，目前學(xué)術(shù)界主要研究的是由傳送帶（鏈）連接的封閉作業(yè)域混流裝配線。在這類裝配線中，當(dāng)某工作站未能完成產(chǎn)品的加工時，往往假設(shè)由線外的員工及時完成，但在實際生產(chǎn)中往往不能達到這個要求，而且一般家電、汽車的總裝配線通常采用開放式的作業(yè)域。因此，為更加貼近實際生產(chǎn)要求，本研究對開發(fā)式作業(yè)域的混流裝配線排序問題進行了研究。

開放式作業(yè)域的混流裝配線排序模型可以描述為：混流裝配線由傳送帶（鏈）連接N 個工位，傳送帶（鏈）以恒定速率VC移動，每個裝配工位長度為Li，工位是開放的，裝配線上的工人在裝配時需要隨著裝配輸送鏈的移動而移動，當(dāng)工人不能在自身的工位內(nèi)完成加工時，可以在不影響其他工位加工的情況下進入下游加工，同時也可以進入上游工位進行加工。假設(shè)：①工件的投產(chǎn)間隔時間固定，以間隔時間λ進行投產(chǎn)；②忽略工人的行走時間；③兩個工位之間沒有緩沖區(qū)。

有M 種產(chǎn)品需要在裝配線上裝配，每個品種的需求量為D1,D2,D3,…,DM，則總需求量為排序采用最小生產(chǎn)循環(huán)（MPS，Minimum Part Set）模式，即整個生產(chǎn)順序由若干個MPS 構(gòu)成，MPS 由各產(chǎn)品需求量比例形成最小生產(chǎn)序列，如每種產(chǎn)品的需求量為dm（m=1,2,3,…,M），h 為dm 的最大公約數(shù)，則每種產(chǎn)品在最小生產(chǎn)循環(huán)中的數(shù)量為dm/h，那么這個MPS可以表示為d1/h,d2/h,…dM/h。因此，只要對這個MPS進行排序，將最后排序的結(jié)果循環(huán)進行h 次，就可以得到整個裝配產(chǎn)品的投產(chǎn)順序。

1.2 混流裝配線優(yōu)化目標(biāo)描述

針對排序問題采用不同的優(yōu)化目標(biāo)，排序結(jié)果會有很大差異。為提高裝配線上工人和設(shè)備的利用率并縮短總裝配時間，本研究選擇以最小化超載時間和平順化零部件消耗為優(yōu)化目標(biāo)。

1.2.1 最小化超載時間

在混流裝配過程中，當(dāng)工人在規(guī)定工位區(qū)域內(nèi)沒能完成裝配任務(wù)，則剩余裝配任務(wù)的標(biāo)準(zhǔn)工時為超載時間。Sarker 等[9]考慮了不完全開放式作業(yè)域的混流裝配線模型，在此基礎(chǔ)上擴展了其模型，建立了開放式作業(yè)域的混流裝配線，該目標(biāo)模型表示為：

式中：J—一個MPS 的投產(chǎn)序列，j—序列中的某一順序的產(chǎn)品，Uij—投產(chǎn)序列中第 j 個產(chǎn)品在工位i 上的超載時間，Zi,j—投產(chǎn)序列中第 j 個產(chǎn)品在工位i 上的起始裝配位置，Zi0—工位i 的起始裝配位置，L—工位的長度，Vc—傳送帶（鏈）的傳送速度，λ—裝配線上產(chǎn)品的投產(chǎn)間隔時間—序列中第 j 個產(chǎn)品在第i 個工位上的加工時間序列中第 j個產(chǎn)品所屬的產(chǎn)品類型。

由于第一個工位屬于封閉式的作業(yè)域，研究者需要另外計算，計算公式為式（5，7）。

1.2.2 平順化零部件消耗

混流裝配線上不同的產(chǎn)品需要的零部件不盡相同，因此平順化零部件消耗是指將裝配線上的不同產(chǎn)品所需零部件的消耗處于一個平穩(wěn)的狀態(tài)。

式中：f2—平順化零部件消耗；x*ij—在一個MPS 中，裝配前 j 個產(chǎn)品消耗第k 種零部件數(shù)量的期望值，J；Rk—在一個MPS 中裝配所有產(chǎn)品消耗的第k 種零部件的數(shù)量；xij—在一個MPS 中，裝配前 j個產(chǎn)品實際消耗的第k 種零部件數(shù)量—實際裝配第m 種產(chǎn)品時所消耗的第k 種零部件的數(shù)量。

優(yōu)化模型中采用了最小化超載時間與平順化零部件消耗兩個目標(biāo)，是多目標(biāo)優(yōu)化問題。為求解多目標(biāo)優(yōu)化問題，本研究采用加權(quán)系數(shù)法。盡管該方法有其固有缺點，但考慮到它具有簡單易行和求解速度快等特點，并且生產(chǎn)中需要的是可以接受的近優(yōu)解，仍在實際運用中得到了大量的應(yīng)用。因此，優(yōu)化目標(biāo)表示為：

式中：ω1,ω2—超載時間 f1和平順化零部件消耗 f2在多目標(biāo)優(yōu)化問題中的重要程度的權(quán)重系數(shù)。

2 模型求解算法設(shè)計

2.1 標(biāo)準(zhǔn)PSO 模型

粒子群優(yōu)化算法是一種進化計算技術(shù)算法，由Eberhart 和Kennedy 提出。在該算法中，種群中的每一個體被稱為微粒，微粒在搜索空間中以一定的速度飛行，并根據(jù)它本身的飛行經(jīng)歷以及同伴的飛行經(jīng)歷進行動態(tài)調(diào)整。在每一次的迭代中，微粒通過跟蹤兩個最優(yōu)解來更新自己，第一個是自身所找到的最優(yōu)解，即個體極值 pbest，記為 Pi(t)=(pi,1(t),pi,2(t),…,pi,d(t))，式中：i—粒子數(shù)，d—問題維數(shù)；另一個是整個種群所找到的最優(yōu)解gbest，記為Pg，微粒的更新速度和位置為：

式中：c1,c2—學(xué)習(xí)因子；r1,r2—（0，1）之間的隨機數(shù)；i—粒子數(shù)；j—問題某一維數(shù)；w—慣性權(quán)因子。

標(biāo)準(zhǔn)PSO 算法的流程如圖1 所示。

圖1 標(biāo)準(zhǔn)粒子群算法流程

在算法的初期，由于個體最優(yōu)值pbest和全局最優(yōu)值gbest在不斷變化，算法全局搜索能力強。但是在算法的中后期，由于pbest和g best 變化不大，同時由于微粒具有“趨同性”，微粒速度將越來越小，最終使得大部分微粒速度接近或等于0，微粒位置得不到更新，有可能使算法陷入局部最優(yōu)。禁忌搜索算法是一種全局性的鄰域搜索算法。TS 在進行搜索時，它模擬人類大腦具有記憶功能的特點，對某些狀態(tài)進行記憶，同時采用相對應(yīng)的禁忌規(guī)則，使算法能夠有效地避免循環(huán)搜索，提高算法的效率，并且算法采用“藐視準(zhǔn)則”來特赦某些具有優(yōu)良狀態(tài)的解，避免丟棄導(dǎo)致由于禁忌規(guī)則的約束使一些狀態(tài)良好的解被遺留，進而既提高了有效性又保證了算法執(zhí)行中種群的多樣化，最終實現(xiàn)了全局優(yōu)化。

2.2 禁忌粒子群算法設(shè)計

由于PSO 算法的缺陷，本研究在標(biāo)準(zhǔn)PSO 中引入兩種策略進行改進：引入禁忌搜索算法，通過TS 算法搜索每次迭代群體中的最優(yōu)解，由于TS 算法的特點，使劣解也可以更新pbest，有利于改善算法的全局搜索性能；隨機權(quán)重法，將權(quán)重w 設(shè)置為隨機時，有可能加速算法的收斂速度，當(dāng)算法初期找不到最好點時，由于w 的線性遞減可能導(dǎo)致算法最終不能收斂到全局最優(yōu)點，而隨機權(quán)重可以克服這種局限。算法的關(guān)鍵及細節(jié)設(shè)計如下：

2.2.1 編碼與解碼方式

由于傳統(tǒng)的基于產(chǎn)品表示的編碼方式并不適用于PSO 算法的微粒進化方式，本研究需要新的解碼和編碼方式。假設(shè)一個MPS 中有1 個A 產(chǎn)品，2 個B 產(chǎn)品，3 個C 產(chǎn)品，則用數(shù)字1 代表A 產(chǎn)品，2 和3 代表B 產(chǎn)品，4、5 和6 代表C 產(chǎn)品，然后引入Bean[8]提出的隨機數(shù)表示法進行編碼，解碼則采用映射規(guī)則依次升序解碼。

2.2.2 慣性權(quán)重更新方式

將標(biāo)準(zhǔn)PSO 算法中設(shè)定w 為服從某種分布的隨機數(shù)，可以從兩方面克服由于w 的線性遞減的不足。首先，在算法初期，隨機w 可以產(chǎn)品相對較小的w 值，加快算法的收斂速度；其次，如果算法初期找不到最優(yōu)解，隨著w 的遞減可能使算法最終收斂到局部最優(yōu)點，隨機w 可以克服這種局限性。

w 的隨機更新計算公式為：

式中：N(0,1)—標(biāo)準(zhǔn)正態(tài)分布；rand(0,1)—0～1 之間的隨機數(shù)；μmax，μmin—隨機權(quán)重平均值的最大值和最小值；σ—隨機權(quán)重的方差，由算法給定。

2.2.3 最優(yōu)微粒的更新方式

在算法的每次迭代過程中都會得到一個gbest值，若經(jīng)過g 次迭代后，g best 的值保持不變，則使用禁忌搜索算法進行鄰域解的搜索，由于禁忌搜索可以接受劣解，提高了跳出局部最優(yōu)解的能力。由于禁忌搜索采用鄰域搜索方式，需要重新解碼、編碼。在禁忌搜索算法中候選解、禁忌表長度、禁忌對象、藐視準(zhǔn)則是影響算法性能的主要因素。根據(jù)優(yōu)化模型的優(yōu)化問題和編碼方式，禁忌表長度則根據(jù)經(jīng)驗設(shè)置為0.6 l（l 為候選解個數(shù)），候選解從鄰域中選擇若干目標(biāo)值最佳的粒子入選，禁忌對象采用目標(biāo)值的變化，藐視準(zhǔn)則設(shè)置為根據(jù)適應(yīng)度值的大小。最優(yōu)微粒的TS 算法更新方式如圖2 所示。

基于上述思想，禁忌粒子群算法的算法流程如下：

（1）隨機初始化種群中各微粒的位置和速度；

（2）評價每個微粒的適應(yīng)度，將當(dāng)前各微粒的位置和適應(yīng)度存儲在各微粒的pbest中；將所有 p best 中最優(yōu)個體的位置和適應(yīng)度值存儲在gbest中；

圖2 微粒的TS 算法更新方式

（3）通過公式（11，12）更新微粒的速度和位移；

（4）對每個微粒，將其適應(yīng)度值與其經(jīng)歷的最好位置作比較，如果較好，則將其作為當(dāng)前的最好位置，并同時更新gbest；

（5）解碼并重新編碼對群體中的最佳微粒執(zhí)行禁忌搜索，并更新其 pbest及群體的gbest；

（6）通過公式（13，14）更新權(quán)重值；

（7）若滿足迭代次數(shù)，停止搜索，輸出結(jié)果，否則返回步驟（2）。

3 實例研究

某冰箱裝配企業(yè)某條總裝線采用混流方式進行生產(chǎn)，該裝配線共6 個工作站，混合裝配4 種產(chǎn)品，計劃日產(chǎn)量分別為120 臺A 產(chǎn)品、40 臺B 產(chǎn)品、60 臺C 產(chǎn)品和40 臺D 產(chǎn)品。那么日產(chǎn)的MPS 為6A，2B，3C，2D，共13 個產(chǎn)品。

各產(chǎn)品在各工作站上的裝配時間以及工位長度如表1 所示；各個不同產(chǎn)品裝配所需零部件如表2 所示。

GA 是目前求解混流裝配線排序問題的常見方法[11-14]。因此，為了驗證算法的優(yōu)越性，本研究通過禁忌粒子群算法和GA 算法對案例進行優(yōu)化。GA 算法參數(shù)：編碼方式采用基于產(chǎn)品的編碼方式，染色體選擇策略為輪盤賭，迭代次數(shù)為100，種群數(shù)量20，交叉算子為單點交叉再進行編碼修正，交叉概率為0.9，變異概率為0.09。禁忌粒子群算法參數(shù)：學(xué)習(xí)因子 c1=c2=2，μmax=0.8，μmin=0.8，σ=0.2，初始粒子種群數(shù)量為50個，迭代次數(shù)為500。裝配線的運行參數(shù)為：Vc取10 mm/s，λ 取50 s，兩個目標(biāo)函數(shù)的權(quán)重w1，w2分別取0.5 和0.5。各個算法都運行10 次，取最優(yōu)值。

表1 工位裝配產(chǎn)品時間及工位長度

表2 各種產(chǎn)品所需零部件數(shù)量

兩種算法的優(yōu)化結(jié)果如表3 所示。禁忌粒子群算法的收斂圖如圖3 所示。

表3 案例優(yōu)化結(jié)果及對比

圖3 禁忌粒子群算法收斂圖

由表3 和圖3 可知，禁忌粒子群算法在計算結(jié)果上優(yōu)于GA 算法，同時擁有很好的收斂速度。這是因為禁忌粒子群算法結(jié)合了粒子群算法全局搜索的能力以及和TS 算法在鄰域搜索能力較強的特點以及隨機權(quán)重更新方式，加強了算法的全局和鄰域搜索的平衡能力，并且粒子群的快速收斂能力為禁忌搜索算法對提供了較好的初始解。

4 結(jié)束語

為了更好地解決開放式作業(yè)域的混流裝配線排序問題，本研究探索了一種新的粒子群算法。針對開放式混流裝配線，筆者建立了以最小化超載時間與平順化零部件為優(yōu)化目標(biāo)的混流裝配線排序數(shù)學(xué)模型；為求解該排序模型，給出了提高鄰域搜索能力和跳出局部最優(yōu)的解決方法，給出了平衡全局搜索和局部搜索的平衡方法，給出了禁忌粒子群算法流程；通過比較算例結(jié)果，本研究設(shè)計的禁忌粒子群算法在求解混流裝配線排序問題優(yōu)于遺傳算法，驗證了該算法的有效性。但由于禁忌粒子群算法還是對單目標(biāo)優(yōu)化問題的求解，且沒有對算法中的相關(guān)參數(shù)的設(shè)定進行靈敏度的分析，還存在禁忌粒子群算法在多目標(biāo)優(yōu)化問題上的適用性問題和對算法參數(shù)研究不足的問題，有待于進一步研究。

（References）：

[1]邵新宇，饒運清.制造系統(tǒng)運行優(yōu)化理論與方法[M].北京：科學(xué)出版社，2010：91-93.

[2]鄭永前，王永生.免疫粒子群算法在混流裝配線排序中的應(yīng)用[J].工業(yè)工程與管理，2011，16（4）：16-20.

[3]劉煒琪，劉 瓊，張超勇，等.基于混合粒子群算法求解多目標(biāo)混流裝配線排序[J].計算機集成制造系統(tǒng)，2011，17（12）：2590-2598.

[4]王炳剛，饒運清，邵新宇，等.基于多目標(biāo)遺傳算法的混流加工/裝配系統(tǒng)排序問題研究[J].中國機械工程，2009，20（12）：1434-1438.

[5]蘇 平，于兆勤.基于混合遺傳算法的混合裝配線排序問題 研 究[J].計 算 機 集 成 制 造 系 統(tǒng) ，2008，14（5）：1001-1007.

[6]董巧英，闞樹林，桂元坤，等.基于改進離散微粒群優(yōu)化算法的混流裝配線多目標(biāo)排序[J].系統(tǒng)仿真學(xué)報，2009，21（22）：7103-7108.

[7]薛琴微，蘭秀菊，陳呈頻.基于蟻群算法的混流裝配線排序研究[J].輕工機械，2010，28（5）：107-112.

[8]GLOVER FW.tabu search[Z].Springer，1997.

[9]SARKER B R P H.Designing a mixed-model，open-sta?tion assembly line using mixed-integer programming[J].The Journal of the Operational Research Society，2001，52（5）：545-558.

[10]BEAN J C.Genctic Algorithms and Random Keys for Se?qucncing and Optimization[J].ORSA Journal on Com?puting（S0899-1499），1994，6（2）：154-160.

[11]鞠全勇，朱劍英.基于混合遺傳算法的動態(tài)車間調(diào)度系統(tǒng)的研究[J].中國機械工程，2007，18（1）：40-43.

[12]LEU Y，MATHESON L A，REES L P.Sequencing mixed-model assembly lines with genetic algorithms[J].Computers&；Industrial Engineering，1996，30（4）：1027-1036.

[13]苑明海，白 穎，李東波.可重構(gòu)裝配線多目標(biāo)優(yōu)化調(diào)度研究[J].中國機械工程，2008，19（16）：1898-1903.

[14]王慶明，李 微.訂單型企業(yè)多目標(biāo)生產(chǎn)計劃的制定及其調(diào)度[J].機電工程，2012，29（6）：621-626.