徐 兵，楊新愉

(長春工業(yè)大學(xué)機(jī)電工程學(xué)院，長春 130012)

0 引言

隨著生產(chǎn)需求多樣且復(fù)雜化，混流裝配的生產(chǎn)方式越來越多的被企業(yè)應(yīng)用，混流裝配線的投產(chǎn)排序問題也越來越被企業(yè)和學(xué)者關(guān)注。文獻(xiàn)[1]首次提出混流裝配線的平衡和排序問題，后期利用單一產(chǎn)品裝配線的相關(guān)技術(shù)和方法最早解決了混流裝配線的平衡問題。文獻(xiàn)[2]設(shè)計(jì)了基于禁忌搜索的遺傳算法對混流裝配線平衡和排序的優(yōu)化問題進(jìn)行求解。

由于空間資源的限制，研究緩沖區(qū)有限的混流裝配線排產(chǎn)優(yōu)化問題雖更復(fù)雜卻也更具備實(shí)際意義。文獻(xiàn)[3-4]提出了改進(jìn)ICA算法，求解具有有限緩沖區(qū)的柔性流水車間排產(chǎn)優(yōu)化問題研究。文獻(xiàn)[5]提出一種混合探路者算法對帶能耗閾值約束和有限緩沖區(qū)的綠色流水車間調(diào)度問題進(jìn)行了求解。粒子群算法因其概念簡明、實(shí)現(xiàn)方便、收斂速度快等優(yōu)點(diǎn)，近年來越來越多的被運(yùn)用于解決此類NP-hard[6]等組合優(yōu)化問題中。文獻(xiàn)[7]為了解決柔性流水車間有限緩沖區(qū)間歇調(diào)度問題，提出了一種自適應(yīng)細(xì)胞自動變異粒子群優(yōu)化算法，表明了該算法具有很強(qiáng)的魯棒性，尋優(yōu)結(jié)果較優(yōu)。文獻(xiàn)[8]為了解決多車間混流裝配線的作業(yè)排序問題，提出了種群庫概念改進(jìn)離散粒子群算法。

對排產(chǎn)優(yōu)化問題，許多學(xué)者做了很多努力但是大多數(shù)研究往往針對一條生產(chǎn)線解決單一LBFFSP問題，無法針對企業(yè)緩沖區(qū)有限和多生產(chǎn)線等多因素的實(shí)際情況解決排產(chǎn)優(yōu)化問題。因此，基于前人對粒子群算法在組合優(yōu)化問題上的研究，本文結(jié)合部分企業(yè)生產(chǎn)線的實(shí)際情況，引用了基于慣性權(quán)重的粒子群算法，研究混流裝配線的排產(chǎn)優(yōu)化和緩沖區(qū)容量限制問題。

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

1.1 問題描述

氮氧化物傳感器的生產(chǎn)具有多品種小批量的特點(diǎn)，其生產(chǎn)工藝流程主要分為三大工序：底座與外殼的生產(chǎn)、半成品裝配、成品檢驗(yàn)。本文研究的主要是前兩道工藝的排產(chǎn)優(yōu)化問題，其數(shù)學(xué)規(guī)劃模型如圖1所示。

圖1 具有有限緩沖區(qū)的混流裝配線排產(chǎn)數(shù)學(xué)規(guī)劃模型

此類傳感器的生產(chǎn)由兩條子生產(chǎn)線和總裝配線復(fù)合而成，即子生產(chǎn)線是由一條專門生產(chǎn)不同種類的底座和一條生產(chǎn)不同類型外殼的混流生產(chǎn)線所組成。緩沖區(qū)的大小影響著整條線的生產(chǎn)效率，為了提高氮氧化物傳感器的生產(chǎn)效率及實(shí)現(xiàn)子生產(chǎn)線與總裝配線的生產(chǎn)負(fù)荷均衡。特此，在總裝配線的前一道工序設(shè)立一個有限緩沖區(qū)。該生產(chǎn)線根據(jù)當(dāng)天生產(chǎn)計(jì)劃進(jìn)行排產(chǎn)需考慮以下要素：

①第一條子生產(chǎn)線加工的第一個工件如果與第二條子生產(chǎn)線第一個加工的工件同時完成，則該兩條子線加工出來的半成品不需要相互等待可直接進(jìn)入下一道裝配線進(jìn)行組裝；

②若兩條子線的第一個工件不是同時加工完畢，則先出來的工件需要等待后出來的工件然后再進(jìn)入裝配線進(jìn)行組裝；

③投產(chǎn)順序在第二及以后的工件在完成各自子生產(chǎn)線最后一道工序的加工后，需考慮工件出來的先后順序、緩沖區(qū)的容量、緩沖區(qū)內(nèi)工件的數(shù)量以及裝配線上第一道工序是否空閑等因素；才能決定當(dāng)前工件是否堵塞在現(xiàn)在的工位上、是否進(jìn)入緩沖區(qū)等待、是否進(jìn)入裝配線上進(jìn)行下一步的加工。

在排產(chǎn)過程中經(jīng)常會存在兩條子線生產(chǎn)加工出來的產(chǎn)品因速度不一樣導(dǎo)致需要組裝的產(chǎn)品相互等待、裝配線裝配的時間過長而緩沖區(qū)的容量不夠?qū)е虑懊孀泳€出現(xiàn)堵塞現(xiàn)象甚至停機(jī)停產(chǎn)，因此研究子生產(chǎn)線和裝配線的投產(chǎn)順序以及緩沖區(qū)容量的大小對縮短產(chǎn)品的生產(chǎn)周期和提高設(shè)備的利用率有著至關(guān)重要的作用。針對這種生產(chǎn)模式，本文優(yōu)化了子生產(chǎn)線和裝配線的投產(chǎn)順序以及有限緩沖區(qū)的容量。為方便討論，文中對于子生產(chǎn)線和裝配線及緩沖區(qū)所組成的生產(chǎn)系統(tǒng)統(tǒng)稱為混流裝配線。

1.2 數(shù)學(xué)模型

1.3 符號定義

該生產(chǎn)線基本符合Fm|blocking|Cmax阻塞流水車間調(diào)度問題[9]的描述，每一條子生產(chǎn)線及裝配線上的工件i及機(jī)器j都是獨(dú)立的，π={π(1),π(2),...,π(n)}表示一個工件序列，其中n=ds；為方便討論，引入以下符號：

①第一條子生產(chǎn)線：pπ(i),j表示工件i在機(jī)器j上的加工時間；b表示這條線最后一臺機(jī)器后面的緩沖區(qū)的工位數(shù)；dπ(i),j表示工件i在機(jī)器j上完成加工后的釋放時間；第一條子生產(chǎn)線dπ(i),j的計(jì)算過程如下：

dπ(1),1=pπ(1),1,i=1,j=1;

(1)

dπ(1),j=dπ(1),j-1+pπ(1),j,i=1;j=2,3,…,m;

(2)

dπ(i),1=max{dπ(i-1),1+pπ(i),1,dπ(i-1),j+1},i=2,3,…,n;j=1;

(3)

dπ(i),j=max{dπ(i),j-1+pπ(i),j,dπ(i-1),j+1},i=2,3,…,n;j=2,3,…m-1;

(4)

dπ(i),j=max{dπ(i-1),j,dπ(i),j-1}+pπ(i),j,i≤b+1;j=m;

(5)

dπ(i),j=max{max{dπ(i-1),j,dπ(i),j-1}+pπ(i),j,ZDπ(i-1),1},i>b+1;j=m;

(6)

②第二條子生產(chǎn)線：Pπ(i),j表示工件i在機(jī)器j上的加工時間；π={π(1),π(2),...,π(n)}表示一個工件序列；B表示這條線最后一臺機(jī)器后所設(shè)立的緩沖區(qū)的工位數(shù)；Dπ(i),j表示工件i在機(jī)器j上完成加工后的釋放時間；第二條子生產(chǎn)線的Dπ(i),j計(jì)算與上述計(jì)算完全一致，下列列舉總裝配線需要用到的部分公式，計(jì)算過程如下：

Dπ(1),1=Pπ(1),1,i=1;j=1;

(7)

Dπ(i),j=max{Dπ(i-1),j,Dπ(i),j-1}+Pπ(i),j,i≤B+1;j=m;

(8)

Dπ(i),j=max{max{Dπ(j-1),j,Dπ(i),j-1}+Pπ(i),j,ZDπ(i-1),1},i>B+1;j=m;

(9)

③總裝配線：ZPi,j表示工件i在機(jī)器j上的裝配時間；π={π(1),π(2),...,π(n)}表示一個工件序列；ZDπ(i),j表示工件i在機(jī)器j上完成加工后的釋放時間；Cmax(π)表示一個工件序列π的總加工時間，所有可能的加工序列集合用Π表示。ZDπ(i),j與Cmax(π)的計(jì)算過程如下：

ZDπ(1),1=max{dπ(1),m,Dπ(1),m}+ZPπ(1),1,i=1;j=1;

(10)

ZDπ(i),1=max{max{dπ(i),m,Dπ(i),m,ZDπ(i-1),1}+ZPπ(i),1,ZDπ(i-1),j+1},i=2,3…n;

(11)

ZDπ(1),j=ZDπ(1),j-1+ZPπ(1),j,i=1;j=2,3,…m;

(12)

ZDπ(i),j=max{max{ZDπ(i-1),j,ZDπ(i),j-1}+ZPπ(i),ZDπ(i-1),j+1},i=2,3,…,n;j=2,3,…,m-1;

(13)

ZDπ(i),j=max{ZDπ(i-1),j,ZDπ(i),j-1}+ZPπ(i),j,i=2,3,…,n;j=m;

(14)

Cmax(π)=ZDπ(n),m

(15)

1.4 目標(biāo)函數(shù)

求解有限緩沖區(qū)的混流裝配線排產(chǎn)優(yōu)化問題，就是尋找一個加工序列π*，使得該序列所有工件經(jīng)過子生產(chǎn)線及總裝配線的加工，完成的總加工時間最小，即滿足Π。

Cmax(π*)≤Cmax(π),?π∈∏

(16)

尋找最佳的緩沖區(qū)容量，就是找到最小的緩沖區(qū)B*、b*，使得該容量下緩沖區(qū)所起的作用接近無限緩沖區(qū)，以盡量減少緩沖區(qū)工位數(shù)占用生產(chǎn)線的空間資源。根據(jù)式(1)～式(15)，當(dāng)緩沖區(qū)B,b趨于無窮的時候，存在一個工件序列使得總加工時間最少，即滿足N。

(17)

2 問題的求解方法

子生產(chǎn)線與裝配線是兩個不同的工藝階段，為了保證滿足產(chǎn)品型號及數(shù)量符合訂單需求，根據(jù)后面瓶頸工序裝配線的投產(chǎn)順序決定前兩條子生產(chǎn)線的零部件的投產(chǎn)次序。在有限緩沖區(qū)按照先進(jìn)先出不改變投產(chǎn)順序的規(guī)則下，它們既相關(guān)又獨(dú)立，因此，按照兩個不同的工藝階段，先研究裝配線的裝配排序，再研究子生產(chǎn)線的投產(chǎn)順序。

對于混流裝配線的排序問題，許多學(xué)者運(yùn)用粒子群算法(PSO)求解這類問題均取得了較好的效果[10]。然而因?yàn)榱Ｗ尤核惴ㄓ幸子谙萑刖植孔顑?yōu)的缺點(diǎn)，文章采用線性遞減慣性權(quán)重[11-12]的粒子群算法求解本文研究的具有有限緩沖區(qū)的混流裝配線排產(chǎn)優(yōu)化問題，通過將慣性權(quán)重w設(shè)置為動態(tài)變化引入PSO算法中，提高算法后期的局部搜索能力，使得算法跳出局部最優(yōu)從而找到最好的解。根據(jù)本文研究混流裝配線的特點(diǎn)，最大生產(chǎn)周期隨著有限緩沖區(qū)的容量變化而變化，具有有限緩沖區(qū)的混流裝配線排產(chǎn)優(yōu)化問題的粒子群算法流程設(shè)置如圖2所示。

圖2 粒子群算法求解混流裝配線流程圖

2.1 粒子群算法設(shè)計(jì)

(1)編碼解碼。粒子群算法中的每個粒子都代表一種生產(chǎn)排序方式，粒子的維度表示加工序列總的工件數(shù)，該算法的編碼方式運(yùn)用粒子的每個維度代表一個工件。采用rands函數(shù)，其在[-1,1]隨機(jī)產(chǎn)生的任意實(shí)數(shù)表示粒子每一維的位置，把隨機(jī)生成的實(shí)數(shù)按照從小到大的規(guī)則排序，以排序后的位置順序?yàn)榛鶞?zhǔn)與維數(shù)進(jìn)行映射，從而獲得工件的加工順序。設(shè)某一加工序列工件數(shù)為6，即粒子的維度為6，表1詳細(xì)介紹了粒子的編碼解碼方法。

表1 粒子編碼解碼方法

(2)初始種群。隨機(jī)產(chǎn)生的實(shí)數(shù)經(jīng)一定規(guī)則重新排序后得到新的工件序列為初始種群。

(3)適應(yīng)度值計(jì)算。根據(jù)式(1)～式(15)編寫適應(yīng)度函數(shù)并運(yùn)用MATLAB軟件進(jìn)行計(jì)算。

(4)引入慣性權(quán)重w。為了避免算法陷入局部最優(yōu)，在粒子群更新速度和位置的初期，引入線性遞減的慣性權(quán)重w，隨著迭代的進(jìn)行，慣性權(quán)重動態(tài)變化，迭代初期較大的慣性權(quán)重使得算法保持了較強(qiáng)的全局搜索能力，而迭代后期較小的慣性權(quán)重利于算法進(jìn)行更精確的局部搜索。通過五種慣性權(quán)重的算法性能比較，采用公式(18)引用慣性系數(shù)。

w(k)=wstart-(wstart-wend)(k/Tmax)2

(18)

其中，Wstart為初始慣性權(quán)重；Wend為迭代到最后一代時的慣性權(quán)重；k為當(dāng)前迭代代數(shù)；Tmax為最大迭代代數(shù)。

(5)粒子速度與位置更新。在每次迭代過程中，粒子通過個體極值和群體極值更新自身的速度和位置，其公式參考文獻(xiàn)[13]即：

(19)

(20)

(6)局部優(yōu)化。為了提高粒子群算法的局部搜索能力，對每代速度位置更新后生成的粒子進(jìn)行局部變異，隨機(jī)生成兩個[-1,1]的隨機(jī)數(shù)更新粒子位置，形成領(lǐng)域解,通過sort函數(shù)將領(lǐng)域解轉(zhuǎn)換成工件排序，通過設(shè)置循環(huán)次數(shù)不斷搜索更新領(lǐng)域最優(yōu)解。通過局部搜索，可以提高粒子個體新解的質(zhì)量。

2.2 最大生產(chǎn)周期算法設(shè)計(jì)

清楚了解每條生產(chǎn)線零部件出來的時間先后順序及裝配線第一道工序的運(yùn)行情況和緩沖區(qū)是否滿負(fù)荷，就會方便計(jì)算工件序列在整個生產(chǎn)系統(tǒng)的最大生產(chǎn)周期。本文針對混流生產(chǎn)系統(tǒng)，設(shè)計(jì)了有限緩沖區(qū)容量由B=0,b=0時最大生產(chǎn)周期不斷向無限緩沖區(qū)時最大生產(chǎn)周期靠近而逐步增加的計(jì)算算法，流程如圖2所示。以下介紹了工件在各個階段是否釋放的計(jì)算算法，用于判斷每個工件在任意時間點(diǎn)所在機(jī)器的閑忙狀態(tài)。設(shè)計(jì)了工件在各個生產(chǎn)階段是否釋放的計(jì)算算法，方法如下：

步驟1：參數(shù)初始化。0時刻的工件開始加工時間為0，緩沖區(qū)工件數(shù)量為0。

步驟2：對兩條子生產(chǎn)線SL(1,2)每一次加工完成進(jìn)入緩沖區(qū)的時間以及后一條裝配線第一道工序機(jī)器閑忙狀態(tài)進(jìn)行判斷。

(1)對第一個工件在第一條生產(chǎn)線完成最后一道工序的釋放時間dπ(1),m和第二條生產(chǎn)線的第一個工件完成最后一道工序的釋放時間Dπ(1),m進(jìn)行比較；此時，裝配線上的第一道工序機(jī)器空閑，工件在兩條子生產(chǎn)線最后一道工序SL(1,2),m上正常釋放，取釋放時間長的作為后一道工序的開始加工時間ZSπ(1),1=max{dπ(1),m,Dπ(1),m}。

(2)令i=i+1，i∈(1,2,…,n-1)。在x時刻作出判斷，第一步先判斷第一條生產(chǎn)線第i個工件完成最后一道工序SL1,j=m的釋放時間dπ(i),m與第二條生產(chǎn)線第i個工件完成最后一道工序SL2,j=m的釋放時間Dπ(i),m，再判斷緩沖區(qū)內(nèi)是否有工件、緩沖區(qū)工件數(shù)是否已達(dá)到最大容量、第i-{B,b}-1個工件在裝配線上的第一道工序ZL3,j=1是否釋放；若緩沖區(qū)內(nèi)無剩余容量且第i-{B,b}-1個工件在ZL3,j=1上正在加工，此時該機(jī)器在忙，第i個工件被堵塞在當(dāng)前工位上；若緩沖區(qū)內(nèi)有剩余容量，則無論ZL3,j=1是否空閑，工件i在加工完成后正常釋放。

(3)返回步驟(2)，并開始循環(huán)判斷，直到i=n-1，即判斷完一個序列π的最后一個工件的生產(chǎn)狀態(tài)后跳出循環(huán)。

步驟3：計(jì)算得出最后結(jié)果。

3 案例分析

設(shè)某日公司內(nèi)的一條混流裝配線生產(chǎn)7種氮氧化合物傳感器，傳統(tǒng)排產(chǎn)方式規(guī)定一班次為一個最小循環(huán)，假設(shè)在一個班次對7種產(chǎn)品的需求量分別為D(1),D(2),...,D(7),7種產(chǎn)品經(jīng)過組裝線的3道工序進(jìn)行組裝，組裝時間如表2所示。

表2 各種產(chǎn)品在裝配線上各工序的加工時間

某日該線氮氧化物傳感器的日生產(chǎn)任務(wù)為生產(chǎn)A1、B1、C1、D1、E1、F1、G1等7種不同品種傳感器共150件，7種產(chǎn)品在一個最小循環(huán)數(shù)量分別為5:7:7:5:8:8:10，一個班次為50件產(chǎn)品，分三次完成。表3為一個最小循環(huán)生產(chǎn)這7種氮氧化物傳感器所需要的零部件類型及數(shù)量，表4是各零部件在各自生產(chǎn)線上各工序的加工時間。

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

表4 各工序加工時間

運(yùn)用粒子群算法尋找個體最優(yōu)值，整個生產(chǎn)系統(tǒng)參數(shù)設(shè)置如下：迭代次數(shù)為200，粒子種群規(guī)模為20，粒子的維數(shù)為50，學(xué)習(xí)因子c1=c2=1.49，最終得到兩條子生產(chǎn)線及裝配線的最佳投產(chǎn)排序?yàn)椋? 21 6 32 36 17 11 18 19 10 28 37 2 46 38 44 30 22 14 5 35 49 31 20 12 48 25 34 4 33 1 43 50 29 40 41 26 24 9 15 16 7 42 23 8 13 47 45 27 39，通過粒子編碼解碼得到該傳感器最佳排序?yàn)椋篈DBEFCBCCBEFAGFGEDCAFGEDBGEFAFAGGEFGEDBCCBGDBCGGEF；最短生產(chǎn)周期為448 min，與傳統(tǒng)排產(chǎn)方式所得的生產(chǎn)周期480 min，縮短了生產(chǎn)周期6.7%；第一、二條子生產(chǎn)線最佳的緩沖區(qū)容量分別是B為17、b為14，因此總的緩沖區(qū)最小可設(shè)為31便能達(dá)到無限緩沖區(qū)的效果。最小生產(chǎn)周期迭代如圖3所示。

圖3 粒子群算法改進(jìn)圖

由圖3可知，基本粒子群算法及改進(jìn)后的粒子群算法能快速找到比傳統(tǒng)排序更優(yōu)的生產(chǎn)排序，通過引用慣性權(quán)重及遺傳變異不斷改進(jìn)后的粒子群算法，其尋優(yōu)能力及收斂速度比改進(jìn)前有了顯著提高，驗(yàn)證了改進(jìn)后算法的有效性。

4 總結(jié)

混流裝配線的投產(chǎn)排序問題在企業(yè)多品種少批量的生產(chǎn)模式下起著重要的作用。本文以某公司一氮氧化物傳感器生產(chǎn)線為例，研究了具有有限緩沖區(qū)的兩條子生產(chǎn)線及裝配線復(fù)合而成的生產(chǎn)系統(tǒng)排序問題。針對不同零件在機(jī)器設(shè)備加工時間不均衡的約束，分別對子線及總裝線的運(yùn)行匹配度進(jìn)行優(yōu)化，以減少零件在機(jī)器上的堵塞時間。采用基本粒子群算法對每一排序進(jìn)行生產(chǎn)周期的計(jì)算，引用慣性權(quán)重提高算法的全局搜索能力，并采用隨機(jī)變異方式改進(jìn)算法，提高粒子的多樣性，最終得到該生產(chǎn)任務(wù)的最優(yōu)排序方案以及緩沖區(qū)的最佳容量，顯著提高了企業(yè)該生產(chǎn)線的生產(chǎn)效率及資源利用率。