翁耀煒，魯建廈，鄧 偉

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

0 引 言

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

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

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

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

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

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

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

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

有M 種產(chǎn)品需要在裝配線上裝配，每個(gè)品種的需求量為D1,D2,D3,…,DM，則總需求量為排序采用最小生產(chǎn)循環(huán)（MPS，Minimum Part Set）模式，即整個(gè)生產(chǎn)順序由若干個(gè)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，那么這個(gè)MPS可以表示為d1/h,d2/h,…dM/h。因此，只要對(duì)這個(gè)MPS進(jìn)行排序，將最后排序的結(jié)果循環(huán)進(jìn)行h 次，就可以得到整個(gè)裝配產(chǎn)品的投產(chǎn)順序。

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

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

1.2.1 最小化超載時(shí)間

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

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

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

1.2.2 平順化零部件消耗

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2.1 編碼與解碼方式

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

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

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

w 的隨機(jī)更新計(jì)算公式為：

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)例研究

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

（References）：

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

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

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

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

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

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

[7]薛琴微，蘭秀菊，陳呈頻.基于蟻群算法的混流裝配線排序研究[J].輕工機(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]鞠全勇，朱劍英.基于混合遺傳算法的動(dòng)態(tài)車間調(diào)度系統(tǒng)的研究[J].中國機(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].中國機(jī)械工程，2008，19（16）：1898-1903.

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