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

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

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

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

0 引言

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

1 混流裝配線投產順序的數學模型

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

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

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

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

則混流裝配線投產排序的目標函數：

S：裝配線上工作站數目；

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

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

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

J：裝配所需零部件種類數；

d：MPS中所有產品的需求量；

k：MPS中投入的第k個產品；

xm,j：前k個產品中產品m的累積量；

cm,j：單件產品m所需要部件aj的數量。

2 混流裝配線投產順序的數學模型的求解算法

2.1 粒子群算法

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

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

標準粒子群優化算法的執行過程如下：1）初始化種群，隨機產生每個粒子的位置和速度；2）評價每個粒子的適應度；3）對每個粒子，其適應度值與與自身pBest做比較，如果當前值好于pBest，則將當前值設為粒子的pBest；4）對每個粒子，其適應度值與與gBest做比較，若當前值好于gBest，則將當前值設為粒子的gBest；5）調整變化每個粒子的速度和位置；6)如未達到終止條件（預先設定的最大代數或足夠好適應度值）則返回2），否則結束[3,4]。

2.2 混合粒子群算法

通常，各個目標函數之間沖突的可能性使得多目標優化問題不存在唯一的全局最優解，使各個目標函數同時達到最優。針于這種多目標優化問題，提出一種混合粒子群算法。該算法在變量空間中初始化種群，各個目標函數共同指導粒子在變量空間中的飛行，飛行過程中對粒子的全局極值和個體極值的選取做了改進。混合粒子群算法的基本思想如下：

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

2）對各個目標函數對應粒子個體極值的選取做了改進。各個目標函數個體極值的選取過程中，結合遺傳算法交叉操作思想，先將初始種群的粒子與各個目標函數個體極值交叉，產生兩個新的種群，再將這兩個新的種群與初始種群合并成新的種群，按照各個目標函數的適應度值大小從種群中選取規模同初始種群相同的種群，重新計算各個目標函數的個體極值。

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

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

表1 粒子構架圖

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

3 實例分析

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

表2 各種發動機需要零件數及裝配時間

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

1）設定種群數40，最大循環代數30代，給定參數C1=C2=2，當前代數gen=0，隨機產生每個粒子的位置與速度；

2）用目標函數J1，J2分別計算每個粒子的適應度；

3）針對兩個目標函數J1，J2分別對每個粒子求得個體極值pBest1，pBest2，令pop再與pBest1，pBest1進行交叉，產生粒子群pop1，pop2,將pop和pop1，pop2合并；

4）用目標函數J1，J2分別計算合并后種群每個粒子的適應度值，適應度值分別按升序排列，選擇對應兩個目標函數適應度值都小的粒子，構成新的種群newpop，種群大小不變；

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

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

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

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

9）gen=gen+1，是否達到最大循環代數，如果滿足結束條件，則結束搜索，否則轉入步驟2)；

10）輸出最后一代粒子群中的全局最優解gBest。

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

4 用AutoMod軟件仿真驗證

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

圖1 模型運行時的效果圖

圖2 零件實際使用值與目標值的動態圖

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

圖3 工位閑置和超載時間的動態圖

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

5 結論

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

本文作者創新點：通過改進個體極值和全局極值的選取解決混流裝配線投產順序的多目標優化問題；用AutoMod仿真混流裝配線的投產順序，驗證算法的有效性，證明AutoMod仿真混流裝配線投產順序的可行性，為簡化數學基礎奠定了基礎。

[1] 林獻坤,等.混合粒子群算法在混流裝配線優化調度中的應用[J].工業工程與管理,2006(1)：35-39.

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

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

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

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

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