基于混合粒子群算法的混流裝配線投產(chǎn)順序研究及仿真

南 翔，黨保華，頡潭成，張朋俊

NAN Xiang1，DANG Bao-hua2，XIE Tan-cheng1，ZHANG Peng-jun1

（1. 河南科技大學(xué) 機(jī)電工程學(xué)院，洛陽 471003；2. 洛陽理工學(xué)院 機(jī)電工程系，洛陽 471023）

0 引言

隨著市場競爭越來越激烈和用戶對產(chǎn)品的個性化要求，混流裝配線被越來越多的企業(yè)采用。在混流裝配線上，不同裝配工位對不同產(chǎn)品裝配的作業(yè)時間相差很大，產(chǎn)生閑置和超載現(xiàn)象，裝配時所需零部件也不完全相同使裝配過程中各種零部件的消耗速率變化很大，導(dǎo)致零部件的需求量產(chǎn)生很大波動。每個工位的閑置和超載時間及零部件的消耗速率與流過這個工位的產(chǎn)品投產(chǎn)順序有關(guān)。因此不同產(chǎn)品的投產(chǎn)順序直接影響企業(yè)的生產(chǎn)效率，解決產(chǎn)品投產(chǎn)順序成為關(guān)鍵問題。

1 混流裝配線投產(chǎn)順序的數(shù)學(xué)模型

設(shè)裝配線上產(chǎn)品類型為M，在計劃期內(nèi)總產(chǎn)量為D，第m種產(chǎn)品的產(chǎn)量為Dm。通常研究產(chǎn)品投產(chǎn)順序問題時以最小生產(chǎn)循環(huán)(MPS)為對象，若Dm的最大公約數(shù)為g，則當(dāng)M種產(chǎn)品以MPS投入裝配線時,循環(huán)次數(shù)為g。以MPS為對象，建立混流裝配線投產(chǎn)順序的數(shù)學(xué)模型。

1.1 最小化工位的閑置和超載時間

對某一投產(chǎn)序列，在第s個工位上，每一個循環(huán)開始時，第一個產(chǎn)品的開始時間Bs,1=0(s=1,2,...,S)。若第k(k=1,2,...,d)個產(chǎn)品的開始時間為Bs,k，則該產(chǎn)品的結(jié)束時間Es,k=Bs,k+Ts,k。第k個產(chǎn)品裝配結(jié)束后，該裝配工位裝配第k+1個產(chǎn)品。第k+1個產(chǎn)品的加工起點有操作工提前完成裝配和未提前完成裝配兩種情況：

則投產(chǎn)序列的第k個產(chǎn)品在第s個工位上的閑置和超載時間分別為：

則混流裝配線投產(chǎn)排序的目標(biāo)函數(shù)：

S：裝配線上工作站數(shù)目；

Ts,k：MPS中，在第s個工位，第k個產(chǎn)品的裝配時間。

1.2 保持均勻的零部件消耗速率

MPS中需要的零件aj(j=1,2,...,J)的數(shù)量為pj，那么單位產(chǎn)品中零件aj的平均需求量mj=pj/d。MPS中生產(chǎn)第k個產(chǎn)品需要零件aj的平均數(shù)為k.mj。在投產(chǎn)順序計劃中，將k.mj是消耗零件aj的目標(biāo)值，實際上生產(chǎn)前面k個產(chǎn)品所需零件aj的數(shù)量為實際值。要使aj的出現(xiàn)率為恒值，就應(yīng)該使aj的實際值和目標(biāo)值盡可能接近。目標(biāo)函數(shù)：

J：裝配所需零部件種類數(shù)；

d：MPS中所有產(chǎn)品的需求量；

k：MPS中投入的第k個產(chǎn)品；

xm,j：前k個產(chǎn)品中產(chǎn)品m的累積量；

cm,j：單件產(chǎn)品m所需要部件aj的數(shù)量。

2 混流裝配線投產(chǎn)順序的數(shù)學(xué)模型的求解算法

2.1 粒子群算法

粒子群優(yōu)化算法(PSO)是一種源于對鳥群捕食行為的研究而發(fā)明的進(jìn)化計算技術(shù)。最初在二維空間圖形化模擬鳥群捕食過程，后來將其推廣到維空間。每個優(yōu)化問題的解是搜索空間中的一只鳥，也看成是一個粒子，每個粒子在搜索空間中以一定的速度飛行，此速度根據(jù)自已和其他粒子的飛行經(jīng)驗動態(tài)調(diào)整。然后定義一個適應(yīng)度函數(shù)來衡量每個粒子解的優(yōu)劣程度，這樣每個粒子就可以根據(jù)自己和其他粒子的飛行經(jīng)驗群游，來達(dá)到從全空間搜索最優(yōu)解的目的[1,2]。全局優(yōu)化模型如下：

其中，Vid是粒子i的速度；Xid是粒子i的位置；pid是粒子i所經(jīng)歷的最好位置（pBest）；pgd是所有粒子所經(jīng)歷過的最好位置（gBest）；W是慣性權(quán)重；C1，C2是加速度常數(shù)，表示把粒子拉向pBest和gBest的權(quán)值；Rand， rand是兩個在[0，1]范圍變化的隨機(jī)數(shù)。

標(biāo)準(zhǔn)粒子群優(yōu)化算法的執(zhí)行過程如下：1）初始化種群，隨機(jī)產(chǎn)生每個粒子的位置和速度；2）評價每個粒子的適應(yīng)度；3）對每個粒子，其適應(yīng)度值與與自身pBest做比較，如果當(dāng)前值好于pBest，則將當(dāng)前值設(shè)為粒子的pBest；4）對每個粒子，其適應(yīng)度值與與gBest做比較，若當(dāng)前值好于gBest，則將當(dāng)前值設(shè)為粒子的gBest；5）調(diào)整變化每個粒子的速度和位置；6)如未達(dá)到終止條件（預(yù)先設(shè)定的最大代數(shù)或足夠好適應(yīng)度值）則返回2），否則結(jié)束[3,4]。

2.2 混合粒子群算法

通常，各個目標(biāo)函數(shù)之間沖突的可能性使得多目標(biāo)優(yōu)化問題不存在唯一的全局最優(yōu)解，使各個目標(biāo)函數(shù)同時達(dá)到最優(yōu)。針于這種多目標(biāo)優(yōu)化問題，提出一種混合粒子群算法。該算法在變量空間中初始化種群，各個目標(biāo)函數(shù)共同指導(dǎo)粒子在變量空間中的飛行，飛行過程中對粒子的全局極值和個體極值的選取做了改進(jìn)?；旌狭Ｗ尤核惴ǖ幕舅枷肴缦拢?/p>

1）參照遺傳算法編碼的思想，給出粒子的構(gòu)造方法。

2）對各個目標(biāo)函數(shù)對應(yīng)粒子個體極值的選取做了改進(jìn)。各個目標(biāo)函數(shù)個體極值的選取過程中，結(jié)合遺傳算法交叉操作思想，先將初始種群的粒子與各個目標(biāo)函數(shù)個體極值交叉，產(chǎn)生兩個新的種群，再將這兩個新的種群與初始種群合并成新的種群，按照各個目標(biāo)函數(shù)的適應(yīng)度值大小從種群中選取規(guī)模同初始種群相同的種群，重新計算各個目標(biāo)函數(shù)的個體極值。

3）對粒子的全局極值和個體極值的選取做了改進(jìn)。首先找到每個粒子對應(yīng)于各個目標(biāo)函數(shù)的全局極值和個體極值；其次，在更新每個粒子的速度時，用各個粒子全局極值的均值作為全局極值，若個體極值的離散程度小于全局極值的離散程度，個體極值隨機(jī)取各目標(biāo)函數(shù)個體極值，反之，個體極值取各目標(biāo)函數(shù)個體極值的均值。

若MPS對應(yīng)9個產(chǎn)品，借鑒遺傳算法中實數(shù)染色體的編碼方法，粒子構(gòu)成有九維[5,6]。把A型綁定1，2，3位置，B型綁定4，5，6，7位置，C型占據(jù)綁定8，9位置，對每個粒子中的每維值進(jìn)行排序，根據(jù)排序的序號和對應(yīng)的位置，可以映射出一個對應(yīng)產(chǎn)品型號的排序方式。粒子構(gòu)架圖如表1所示。

表1 粒子構(gòu)架圖

為了增加各個目標(biāo)函數(shù)對應(yīng)粒子個體極值的收斂速度及防止其陷入局部最優(yōu)，通過遺傳算法的兩點式隨機(jī)交叉增加種群規(guī)模來克服，同時更新種群。在更新粒子速度時，本文的選取方式使得每個粒子向解移動時的行為各不相同，每個粒子都移向解區(qū)域中不同的解。選取避免了所有個體落于某一目標(biāo)函數(shù)的最優(yōu)點，體現(xiàn)了各個目標(biāo)函數(shù)間的制約關(guān)系[5,6]。

3 實例分析

對某一發(fā)動機(jī)混流裝配線，在計劃期內(nèi)，要生產(chǎn)300件A，400件B，200件C，生產(chǎn)節(jié)拍為105s，零件p11，p12，p21，p22的供應(yīng)節(jié)拍分別是24s，30s，22s，20s。以裝配線的兩個關(guān)鍵工位為研究對象，則在MPS中，不同產(chǎn)品的數(shù)量，零件使用情況和工位裝配時間如表2所示。表2中m表示產(chǎn)品類型，dm表示不同產(chǎn)品的數(shù)量，psj表示在工位s每種產(chǎn)品需要零部件j的數(shù)量，其中tsj表示在工位s每種產(chǎn)品裝配一個零部件j所需要的時間。

表2 各種發(fā)動機(jī)需要零件數(shù)及裝配時間

為了將混合粒子群算法運用到產(chǎn)品投產(chǎn)順序的優(yōu)化問題上，需要對微粒的位置和速度做出重新定義。設(shè)一個MPS中有d個產(chǎn)品，不妨設(shè)某個位置X=(x1,x2,...,xd)，該位置的速度為V=(v1,v2,...,vd)。運用上文提出的粒子構(gòu)架方式構(gòu)造粒子。針對本文提出的兩個目標(biāo)函數(shù)J1，J2，運用混合粒子群算法，算法流程如下：

1）設(shè)定種群數(shù)40，最大循環(huán)代數(shù)30代，給定參數(shù)C1=C2=2，當(dāng)前代數(shù)gen=0，隨機(jī)產(chǎn)生每個粒子的位置與速度；

2）用目標(biāo)函數(shù)J1，J2分別計算每個粒子的適應(yīng)度；

3）針對兩個目標(biāo)函數(shù)J1，J2分別對每個粒子求得個體極值pBest1，pBest2，令pop再與pBest1，pBest1進(jìn)行交叉，產(chǎn)生粒子群pop1，pop2,將pop和pop1，pop2合并；

4）用目標(biāo)函數(shù)J1，J2分別計算合并后種群每個粒子的適應(yīng)度值，適應(yīng)度值分別按升序排列，選擇對應(yīng)兩個目標(biāo)函數(shù)適應(yīng)度值都小的粒子，構(gòu)成新的種群newpop，種群大小不變；

5）針對目標(biāo)函數(shù)J1，J2對每個粒子重新求得個體極值pBest11， pBest22，計算每個粒子在兩目標(biāo)函數(shù)下個體極值的差值；

6）針對兩個目標(biāo)函數(shù)J1，J2分別求兩個全局極值，計算兩全局矢量的均值和距離，全局極值取兩全局極值的平均值；

7）若個體極值的差值小于全局極值的差值，個體極值取兩個目標(biāo)函數(shù)任一個體極值。若個體極值的差值大于等于全局極值的差值，個體極值取兩個目標(biāo)函數(shù)個體極值的平均值；

8）由6）和7）求得全局極值和個體極值和公式調(diào)整粒子的速度和位置；

9）gen=gen+1，是否達(dá)到最大循環(huán)代數(shù)，如果滿足結(jié)束條件，則結(jié)束搜索，否則轉(zhuǎn)入步驟2)；

10）輸出最后一代粒子群中的全局最優(yōu)解gBest。

在VC++平臺上運行程序，求得最佳排序BACBABCAB。

4 用AutoMod軟件仿真驗證

建立發(fā)動機(jī)裝配線在投產(chǎn)順序BACBABCAB下的仿真模型，運行8個小時。圖1是發(fā)動機(jī)模型運行時的效果圖，產(chǎn)品按照BACBABCAB投產(chǎn)順序循環(huán)裝配。sta1，sta2分別代表工位1，工位2。每個工位旁邊有兩個隊列，零件以一定節(jié)拍進(jìn)入隊列，等待操作工把零件裝配到不同產(chǎn)品上。

圖1 模型運行時的效果圖

圖2 零件實際使用值與目標(biāo)值的動態(tài)圖

由圖2可以看出，圖形右側(cè)有8個參數(shù)，參數(shù)C_11.Cur、C_12.Cur、C_21.Cur、C_22.Cur分別表示零件p11、p12、p21、p22的實際使用量；參數(shù)V1、V2、V3、V4分別表示零件p11、p12、p21、p22的目標(biāo)使用量。由圖3可知，每個零件目標(biāo)值與實際值的曲線比較接近，隨時間變化目標(biāo)值與實際值之間的差值增加。目標(biāo)值與實際值之間的差值的變化從另一個角度反映隊列中庫存量的變化。庫存量達(dá)到一定量時，可以采取措施，減慢或者加速零件的供應(yīng)速度。

圖3 工位閑置和超載時間的動態(tài)圖

從圖3看出裝配線運行一天，裝配線的工位閑置和超載時間大約是1000s。另外從該仿真模型中還可以得到操作工R1的利用率為90%，操作工R2的利用率為98.3%。選3種投產(chǎn)順序方案：A B A C B C B A B，C A B A C B A B B，BCBABCABA。分別對這幾種投產(chǎn)方案仿真運行并與求得的方案對比。三種方案工位閑置和超載時間分別是1273s，1530s，1420s均大于1000s，并且操作工的利用率都不及求得的方案。所以方案BACBABCAB是最佳排序方案。

5 結(jié)論

本文通過把粒子群算法與遺傳算法編碼交叉的思想相結(jié)合，利用最優(yōu)解評估選取方法，改進(jìn)個體極值和全局極值的選取辦法，提出了混合粒子群算法。用該算法解決了混流裝配線投產(chǎn)順序的多目標(biāo)優(yōu)化問題，得到了較優(yōu)的可行解。并用AutoMod仿真驗證，證明了該算法求解混流裝配線投產(chǎn)順序的有效性以及AutoMod仿真混流裝配線投產(chǎn)順序的可行性。

本文作者創(chuàng)新點：通過改進(jìn)個體極值和全局極值的選取解決混流裝配線投產(chǎn)順序的多目標(biāo)優(yōu)化問題；用AutoMod仿真混流裝配線的投產(chǎn)順序，驗證算法的有效性，證明AutoMod仿真混流裝配線投產(chǎn)順序的可行性，為簡化數(shù)學(xué)基礎(chǔ)奠定了基礎(chǔ)。

[1] 林獻(xiàn)坤,等.混合粒子群算法在混流裝配線優(yōu)化調(diào)度中的應(yīng)用[J].工業(yè)工程與管理,2006(1)：35-39.

[2] 劉亞欣,等.基于粒子群算法的數(shù)據(jù)庫查詢優(yōu)化[J].微計算機(jī)信息,2007(3)：7-11.

[3] 蘇平,等.基于混合遺傳算法的混合裝配線排序問題研究[J].計算機(jī)集成制造統(tǒng),2008(5)：14-19.

[4] 曹振新,等.混流裝配線負(fù)荷平衡與投產(chǎn)排序的優(yōu)化研究[J].信息與控制,2004(6)：33-38.

[5] 張利彪,等.基于粒子群算法求解多目標(biāo)優(yōu)化問題[J].計算機(jī)研究與發(fā)展,2004 (7)：41-45.

[6] 趙建軍,等.基于Flexsim混流裝配線投產(chǎn)排序的仿真[J].控制與管理,2007(3)：8-11.