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

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

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

0 引言

隨著市場競爭越來越激烈和用戶對(duì)產(chǎn)品的個(gè)性化要求，混流裝配線被越來越多的企業(yè)采用。在混流裝配線上，不同裝配工位對(duì)不同產(chǎn)品裝配的作業(yè)時(shí)間相差很大，產(chǎn)生閑置和超載現(xiàn)象，裝配時(shí)所需零部件也不完全相同使裝配過程中各種零部件的消耗速率變化很大，導(dǎo)致零部件的需求量產(chǎn)生很大波動(dòng)。每個(gè)工位的閑置和超載時(shí)間及零部件的消耗速率與流過這個(gè)工位的產(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，在計(jì)劃期內(nèi)總產(chǎn)量為D，第m種產(chǎn)品的產(chǎn)量為Dm。通常研究產(chǎn)品投產(chǎn)順序問題時(shí)以最小生產(chǎn)循環(huán)(MPS)為對(duì)象，若Dm的最大公約數(shù)為g，則當(dāng)M種產(chǎn)品以MPS投入裝配線時(shí),循環(huán)次數(shù)為g。以MPS為對(duì)象，建立混流裝配線投產(chǎn)順序的數(shù)學(xué)模型。

1.1 最小化工位的閑置和超載時(shí)間

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 粒子群算法

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

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

2.2 混合粒子群算法

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

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

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

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

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

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

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

3 實(shí)例分析

對(duì)某一發(fā)動(dòng)機(jī)混流裝配線，在計(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。以裝配線的兩個(gè)關(guān)鍵工位為研究對(duì)象，則在MPS中，不同產(chǎn)品的數(shù)量，零件使用情況和工位裝配時(shí)間如表2所示。表2中m表示產(chǎn)品類型，dm表示不同產(chǎn)品的數(shù)量，psj表示在工位s每種產(chǎn)品需要零部件j的數(shù)量，其中tsj表示在工位s每種產(chǎn)品裝配一個(gè)零部件j所需要的時(shí)間。

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

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

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

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

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

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

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

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

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

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

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

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

在VC++平臺(tái)上運(yùn)行程序，求得最佳排序BACBABCAB。

4 用AutoMod軟件仿真驗(yàn)證

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

圖1 模型運(yùn)行時(shí)的效果圖

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

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

圖3 工位閑置和超載時(shí)間的動(dòng)態(tài)圖

從圖3看出裝配線運(yùn)行一天，裝配線的工位閑置和超載時(shí)間大約是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。分別對(duì)這幾種投產(chǎn)方案仿真運(yùn)行并與求得的方案對(duì)比。三種方案工位閑置和超載時(shí)間分別是1273s，1530s，1420s均大于1000s，并且操作工的利用率都不及求得的方案。所以方案BACBABCAB是最佳排序方案。

5 結(jié)論

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

本文作者創(chuàng)新點(diǎn)：通過改進(jìn)個(gè)體極值和全局極值的選取解決混流裝配線投產(chǎn)順序的多目標(biāo)優(yōu)化問題；用AutoMod仿真混流裝配線的投產(chǎn)順序，驗(yà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ì)算機(jī)信息,2007(3)：7-11.

[3] 蘇平,等.基于混合遺傳算法的混合裝配線排序問題研究[J].計(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ì)算機(jī)研究與發(fā)展,2004 (7)：41-45.

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