徐立云 榮 巨 郭昆吾 李愛平

(同濟(jì)大學(xué)現(xiàn)代制造技術(shù)研究所，上海 201804)

為適應(yīng)目前多品種、少批量的市場需求，單元化制造模式應(yīng)運(yùn)而生，它融合了job-shop 高柔性與flowshop 高生產(chǎn)率的特點(diǎn)，使傳統(tǒng)生產(chǎn)方式下生產(chǎn)率與生產(chǎn)柔性之間的矛盾得到較好解決［1］。實(shí)施單元化生產(chǎn)的關(guān)鍵是制造單元的構(gòu)建，即如何將一個給定的制造系統(tǒng)劃分成若干個制造單元。國內(nèi)外學(xué)者對制造單元的構(gòu)建問題進(jìn)行了較多研究，制造單元的構(gòu)建技術(shù)主要有圖論方法、數(shù)學(xué)規(guī)劃方法和啟發(fā)式算法等［2-3］。王建維［4］提出了一種基于模糊C 均值算法劃分制造單元的方法;金哲等［5］提出了一種用排隊(duì)論構(gòu)建制造單元的方法;李淑霞等［6］提出了一種基于敏捷制造單元的車間動態(tài)重構(gòu)方法，通過聚類算法對車間制造資源進(jìn)行選擇組織。但這些方法大多側(cè)重對已有的制造資源進(jìn)行聚類劃分，而車間物流因素對單元構(gòu)建問題的影響是不容忽視的。本文利用并行工程的思想，綜合考慮了單元內(nèi)與單元間的物流情況以及設(shè)備單元分組和單元內(nèi)設(shè)備的具體排序，建立了相應(yīng)的優(yōu)化模型。針對求解模型，設(shè)計(jì)了具有交叉算子的改進(jìn)粒子群優(yōu)化(improved particle swarm optimization，IPSO)算法，構(gòu)建制造單元。

1 問題描述

制造單元構(gòu)建問題是通過對所加工的工件進(jìn)行工藝分析，將所有工件和所需的加工設(shè)備進(jìn)行分組，形成特定的工件族和與之對應(yīng)的設(shè)備組，每一工件族和相對應(yīng)的設(shè)備組即構(gòu)成一個特定的制造單元［7］。良好的單元構(gòu)建工作一般要考慮到兩方面的內(nèi)容，一是單元的獨(dú)立性，即要使單元工件的全部加工工序所包含的設(shè)備都在一個單元內(nèi)，這樣可有效減少工件在單元間的移動;二是單元的緊湊性，即同一單元內(nèi)的設(shè)備在布置時，使設(shè)備間的間距盡可能小，以減小單元內(nèi)的物流平均距離。但單元構(gòu)建時考慮的這兩方面內(nèi)容在某種程度上又是矛盾的，所以在單元構(gòu)建過程中，一般單元緊湊性通常是通過限定單元尺寸這一約束條件來實(shí)現(xiàn)［8］，文獻(xiàn)［9 -10］認(rèn)為，單元內(nèi)部及單元之間的物流搬運(yùn)費(fèi)用可以作為單元構(gòu)建的有效評價指標(biāo)。

本文要解決的制造單元構(gòu)建問題可以描述為:已知加工設(shè)備的數(shù)量，工件的種類，加工批量，工件的加工工藝路線以及每道工序所需要的設(shè)備，通過確定車間內(nèi)所有設(shè)備的分組與單元內(nèi)設(shè)備的具體排列順序，以單元內(nèi)部與單元間的物流搬運(yùn)費(fèi)用最小化為目標(biāo)，完成制造單元構(gòu)建。

2 數(shù)學(xué)建模

現(xiàn)有加工設(shè)備M 臺，待加工工件種類及其加工批量等工藝參數(shù)均已知。為了描述方便，引入以下相關(guān)參數(shù)變量:p 為工件編號，p=1，2，…，P;m 為設(shè)備編號，m=1，2，…，M;c 為單元編號，c=1，2，…，C;k 為設(shè)備位置編號，k=1，2，…K;Vp為工件p 的生產(chǎn)批量;Hp為車間使用的搬運(yùn)設(shè)備一次可以容納工件p 的數(shù)量;Vp為工件p 的生產(chǎn)批量;CAp為單位物流量工件在單元內(nèi)單位距離的順流搬運(yùn)成本;CBp為單位物流量工件在單元內(nèi)單位距離的逆向搬運(yùn)成本;CXp為單位物流量工件在單元間的物流成本。

2.1 設(shè)備間物流量的計(jì)算

設(shè)備間物流量和幾個參數(shù)有關(guān):工件的生產(chǎn)批量、搬運(yùn)設(shè)備單次搬運(yùn)的工件數(shù)量、工件加工過程需在設(shè)備間移動的次數(shù)。因此，對于工件p 而言，先后訪問相鄰兩道工序的設(shè)備m 和m'，在設(shè)備m 和m'間引起的物流量的計(jì)算公式為:

其中:Lpmm'為0 -1 輔助變量，表示m 和m'是否為工件p 工藝路線上需要連續(xù)訪問的兩臺設(shè)備，若是，則Lpmm'=1，Lpmm'=0 表示其他情況;npmm'為工件p 的加工過程中需要在m 與m'間移動的次數(shù)，若工件p 的工藝路徑為1 -4 -3 -2 -1 -4，此時n1，4=2，n4，3=n3，2=n2，1=1;符號表示向上取整。

2.2 單元內(nèi)單位物流量的搬運(yùn)費(fèi)用計(jì)算

為了簡化，本文假定:(1)制造單元內(nèi)均采用線型布局;(2)在制造單元內(nèi)部，相鄰兩設(shè)備的中心間距D是相等的;(3)單元內(nèi)部均是單一方向的物流。

故在計(jì)算中需要考慮物流方向?qū)ξ锪靼徇\(yùn)費(fèi)用的影響，單向線性布局中物流方向分為順向與逆向兩個方向，從上游設(shè)備向下游設(shè)備的流動稱為順向，反之則稱為逆向或物流回溯。物流回溯會降低單元內(nèi)的搬運(yùn)效率，且其產(chǎn)生的單位物流費(fèi)用也比順向物流費(fèi)用要高(CAp＜CBp)。

綜上所述，考慮物流回溯對物流費(fèi)用的影響，則單元內(nèi)單位流量工件p 的工藝路徑上，設(shè)備m 和m'間的物流搬運(yùn)費(fèi)用為:

xmc=1 表示設(shè)備m 屬于單元c，xmc=0 表示其他;ycmk=1 表示設(shè)備m 被布置在單元c 的位置k 上，ycmk=0 表示其他。

2.3 單元間單位物流量的搬運(yùn)費(fèi)用計(jì)算

單元構(gòu)建階段還沒有涉及到單元間的布局情況，故單元間物流距離無法獲知，因此單元間的物流費(fèi)用也就無法求出。文獻(xiàn)［11］認(rèn)為當(dāng)單元尺寸變化在一定范圍內(nèi)時，單元間單位物流費(fèi)用近似為一個常量。對于單元內(nèi)部的物流距離以及費(fèi)用情況，由公式(2)可以求出，而對單元間的物流費(fèi)用需要進(jìn)行估算。為簡化起見，本文采用與文獻(xiàn)［12］類似的策略，設(shè)單元之間單位物流量費(fèi)用為常數(shù)CXp，即Cpmm'=CXp。

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

制造單元構(gòu)建的目標(biāo)就是單元內(nèi)部設(shè)備間與單元間的物流搬運(yùn)費(fèi)用最小化，數(shù)學(xué)模型如下:

決策變量:

約束條件:

約束(4)和(5)表示每一臺設(shè)備只屬于一個制造單元，而每一個單元最少包括兩臺設(shè)備，約束(6)與(7)則限制一個位置空間上只能放置一臺設(shè)備，一臺設(shè)備只能被放置于一個位置空間，約束(8)表示對單元數(shù)的限制。

3 算法設(shè)計(jì)與求解

3.1 基本粒子群算法

PSO 算法最早是由Kennedy 和Eberhart 在1995年提出，該算法源于對鳥類捕食行為的研究，通過模擬鳥集群飛行覓食的集體協(xié)作行為，使群體達(dá)到最優(yōu)的目的。

PSO 算法中，每個優(yōu)化問題的解都被看作是搜索空間中的一只鳥，稱為粒子，每個粒子都有自己的位置和速度(決定飛行的方向和距離)，以及一個由優(yōu)化函數(shù)決定的適應(yīng)度值，其值的好壞表示粒子的優(yōu)劣。粒子在解空間中運(yùn)動，通過跟蹤個體極值點(diǎn)(用pbest表示其位置)和群體極值點(diǎn)(用gbest表示其位置)更新個體位置。個體極值點(diǎn)(pbest)是指個體經(jīng)歷位置中計(jì)算得到的適應(yīng)度值最優(yōu)解;群體極值點(diǎn)(gbest)是指種群中所有粒子搜索到的適應(yīng)度最優(yōu)解。在找到這兩個最優(yōu)解后，每個粒子根據(jù)式(9)～(11)來更新自己的速度和位置。

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

基本PSO 算法的搜索過程很大程度上置于一個位置空間，每個位置空間上有且僅依賴個體最優(yōu)解和全局最優(yōu)解，其搜索區(qū)域受到個體最優(yōu)解和全局最優(yōu)解的限制，比較容易陷入局部最優(yōu)解。針對基本PSO 算法的不足，借鑒進(jìn)化算法的思想，將進(jìn)化算法中的交叉操作與基本PSO 算法進(jìn)行混合，對交叉算子進(jìn)行非線性設(shè)計(jì)，使得交叉率隨種群中個體的適應(yīng)度值的變化而變化，兩個不同的粒子可以進(jìn)行信息交換，增加了粒子“飛行”到搜索空間其他新位置的能力，避免粒子群過早地陷入局部最優(yōu)。因此，其交叉率為:

式中:Pc為交叉率;favg為每代群體的平均適應(yīng)度值;fmax為當(dāng)前群體中最大的適應(yīng)度值;f'為要交叉的兩個粒子中較大的適應(yīng)度值;pcmax與pcmin分別表示交叉率值的上限和下限，φ 為設(shè)定的常數(shù)。為改變交叉點(diǎn)的隨機(jī)性和盲目性，根據(jù)父代粒子的適應(yīng)度值來控制交叉點(diǎn)的位置。具體實(shí)現(xiàn)過程為:隨機(jī)從種群中抽取要交叉的兩個個體，假定其適應(yīng)度值分別為f1、f2，則交叉點(diǎn)的串長為:

式中:l 為粒子長度。

3.3 粒子的編碼與解碼

PSO 算法的模型是在實(shí)數(shù)連續(xù)空間搜索，而制造單元構(gòu)建問題的模型是屬于離散空間的解。因此，需要設(shè)計(jì)合適的PSO 編碼來完成連續(xù)空間的粒子與離散空間的單元組合進(jìn)行映射。

PSO 算法中可以用二進(jìn)制、實(shí)數(shù)和實(shí)值等對粒子進(jìn)行編碼。對于本文研究的問題，設(shè)計(jì)的粒子編碼方式需要劃分出單元個數(shù)的同時要確定設(shè)備在單元中具體的排列順序。因此，本文將粒子編碼分為兩部分。

(1)設(shè)備位置的編碼(Mpos) 采用實(shí)數(shù)編碼方式，長度為設(shè)備的數(shù)量M，每個編碼位對應(yīng)一臺設(shè)備，編碼直接采用設(shè)備編號，這樣粒子可以更直觀地表達(dá)單元內(nèi)設(shè)備的排列順序。

(2)單元分割點(diǎn)的編碼(Cdiv) 這一部分是長度為(M-1)，數(shù)值范圍為［0，1］的實(shí)數(shù)編碼串。

解碼時，對各編碼位上的數(shù)值進(jìn)行四舍五入操作，用函數(shù)round 表示。規(guī)定round(xid)=1 的編碼位為一個單元的分割點(diǎn)。這兩部分的編碼結(jié)合起來可以確定出單元的劃分以及單元內(nèi)設(shè)備的具體排列順序。

如圖1，現(xiàn)有8 臺設(shè)備其位置編碼為(8，1，4，5，3，2，7，6)，單元分割點(diǎn)編碼為(0.22，0.35，0.76，0.15，0.17，0.96，0.41)，解碼后為(0，0，1，0，0，1，0)。單元分割點(diǎn)解碼后有兩個“1”，將所有設(shè)備分為3 個單元，其中單元1 由設(shè)備“8，1，4”組成，單元2 由設(shè)備“5，3，2”組成，單元3 由設(shè)備“7，6”組成。設(shè)備編碼段的編碼順序也決定了設(shè)備在單元內(nèi)的布置順序。

3.4 IPSO 算法的流程設(shè)計(jì)

采用IPSO 算法求解制造單元構(gòu)建問題，算法流程

圖1 粒子位置編碼格式

設(shè)計(jì)如下:

步驟1 初始化，設(shè)定加速度因子c1和c2，最大迭代次數(shù)Tmax，將當(dāng)前迭代次數(shù)設(shè)置為t=1，初始化粒子位置和速度;

步驟2 計(jì)算當(dāng)前所有粒子的適應(yīng)度值;

步驟3 判斷是否達(dá)到最大迭代次數(shù)，若是，停止迭代，輸出結(jié)果;否則，轉(zhuǎn)向步驟4;

步驟4 按式(9)～(11)對粒子的速度和位置進(jìn)行更新;

步驟5 比較當(dāng)前粒子適應(yīng)度值與個體最優(yōu)值pbest，如果當(dāng)前粒子適應(yīng)度值比pbest更優(yōu)，則更新pbest;

步驟6 比較當(dāng)前粒子適應(yīng)度值與群體最優(yōu)值gbest，如果當(dāng)前粒子適應(yīng)度值比gbest更優(yōu)，則更新gbest;

步驟7 隨機(jī)找出兩個需要交叉的粒子按照IPSO算法進(jìn)行交叉操作，交叉率和交叉串長分別按式(12)、式(13)來確定，交叉操作后轉(zhuǎn)向步驟2。

4 應(yīng)用實(shí)例

4.1 實(shí)例描述

為響應(yīng)市場需求的快速變化，某企業(yè)擬新建一加工車間，決定采用單元化生產(chǎn)模式。現(xiàn)有各種型號的車床、銑床、刨床、鉆床、磨床等加工設(shè)備共20 臺，待加工工件為6 種柴油發(fā)動機(jī)相關(guān)零配件，其生產(chǎn)批量以及工藝路徑等工藝信息如表1 所示。制造單元構(gòu)建時需要對這些設(shè)備進(jìn)行分組，并以單元內(nèi)部與單元間的物流搬運(yùn)費(fèi)用最小化為目標(biāo)，構(gòu)建制造單元。

表1 生產(chǎn)任務(wù)信息表

4.2 案例求解

(1)粒子的編碼

本文采用實(shí)數(shù)編碼的方式，將粒子編碼分為兩部分，即設(shè)備位置的編碼和單元分割點(diǎn)的編碼。每個粒子的結(jié)構(gòu)由設(shè)備位置信息和單元分割點(diǎn)信息組成，其表現(xiàn)形式如3.3 節(jié)圖1 所示。

(2)初始種群的生成

采用隨機(jī)產(chǎn)生初始種群的方法構(gòu)造初始群體。案例中，機(jī)床數(shù)為M=20 臺，根據(jù)本文所采用的編碼策略，隨機(jī)產(chǎn)生的一組初始種群為:

(3)粒子的解碼

本文所采用的解碼策略，是對單元分割點(diǎn)所對應(yīng)的粒子編碼進(jìn)行解碼，用函數(shù)round 對各編碼位上的數(shù)值進(jìn)行四舍五入操作。因此初始種群里粒子編碼結(jié)構(gòu)的單元分割點(diǎn)解碼為C'div(0，0，0，1，0，1，0，0，0，1，1，0，0，1，0，0，1，0，0)。

(4)適應(yīng)度計(jì)算

本文的目標(biāo)函數(shù)是求搬運(yùn)費(fèi)用的最小值，所以根據(jù)適應(yīng)度函數(shù)特點(diǎn)，設(shè)置其為目標(biāo)函數(shù)的倒數(shù)，即:

其中LC 為粒子i 的目標(biāo)函數(shù)。由函數(shù)關(guān)系知，適應(yīng)度值fitness(i)與目標(biāo)函數(shù)LC 成反比，目標(biāo)函數(shù)值越小，粒子的適應(yīng)度越高，粒子更容易接近個體極值點(diǎn)和群體極值點(diǎn)。

(5)速度和位置的更新

粒子在解空間中運(yùn)動，通過跟蹤個體極值點(diǎn)和群體極值點(diǎn)更新個體位置。每個粒子根據(jù)式(11)～(13)來更新自己的速度和位置。

(6)粒子速度和位置的交叉操作

利用交叉操作，使兩個不同的粒子進(jìn)行信息交換，以增加粒子“飛行”到搜索空間其他新位置的能力，避免粒子群過早地陷入局部最優(yōu)。根據(jù)本文編碼的特點(diǎn)和意義，將粒子的交叉操作分段進(jìn)行。對設(shè)備位置段采用部分映射交叉法(PMX)處理，對單元分割點(diǎn)段采用算術(shù)交叉方法處理。

①設(shè)備位置段的交叉操作假設(shè)選出的粒子對如圖2 所示，計(jì)算得到交叉點(diǎn)串長為6，進(jìn)行交叉操作后得到的原始子代如圖3 所示。交叉操作得到的原始子代，產(chǎn)生了非可行解，使得粒子編碼串不能完整表達(dá)設(shè)備編號，故需確定兩個子串的映射關(guān)系:5 ＜-＞13，3＜-＞19，4 ＜-＞1，20 ＜-＞7，8 ＜-＞11。根據(jù)映射關(guān)系去除非可行解，得到的子代如圖4 所示。

圖2 父代粒子串

圖3 原始子代粒子串

圖4 修正后的子代粒子串

②單元分割點(diǎn)段交叉操作采用算術(shù)交叉，假如選擇的兩個個體是，則交叉運(yùn)算后產(chǎn)生的新個體是:

其中σ=l1/l。

(7)終止選擇

本文算法中的終止準(zhǔn)則采用了預(yù)先規(guī)定一個最大的迭代次數(shù)來終止算法。

4.3 案例分析

經(jīng)對實(shí)際物流情況，工件1～6 的單元內(nèi)單位物流量的單位距離順流搬運(yùn)費(fèi)用CAp依次為(0.75，0.60，1.00，0.80，0.72，0.50)，逆向搬運(yùn)費(fèi)用CBp依次為(1.30，1.25，2.20，1.45，1.50，1.20)，單元間單位物流量的物流搬運(yùn)費(fèi)用CXp=20，設(shè)備間距D=3.5 m。設(shè)定算法最大迭代次數(shù)Tmax=400，種群大小sizepop=40，取加速因子c1=c2=2，最大慣性權(quán)重ωmax=0.9，最小慣性權(quán)重ωmin=0.4，pcmax=0.8，pcmin=0.3，φ=9.9，l=20。采用本文的模型和算法，運(yùn)用MATLAB 軟件編寫相應(yīng)的算法程序并運(yùn)行，得到其目標(biāo)函數(shù)最優(yōu)值的收斂情況如圖5 所示。從圖5 中可以看出，混合粒子群算法大約在第190 代收斂于最優(yōu)解或近似最優(yōu)解，目標(biāo)函數(shù)最優(yōu)值為3 687.8。

根據(jù)優(yōu)化算法結(jié)果，將車間內(nèi)設(shè)備分成的5 個制造單元為:制造單元C1{m8，m9，m1，m3，m20};制造單元C2{m15，m7，m11，m18};制造單元C3{m6，m14，m4};制造單元C4{m19，m12，m13，m10};制造單元C5{m5，m17，m16，m2}。按照單元內(nèi)設(shè)備線性布置要求，構(gòu)建車間的制造單元，并對6 種產(chǎn)品加工過程物流量進(jìn)行仿真分析，如圖6 所示，6 種不同顏色的箭頭分別表示6種產(chǎn)品的物流量Wp。

圖5 目標(biāo)函數(shù)迭代過程

5 結(jié)語

本文研究了制造單元的構(gòu)建問題，在滿足約束條件的情況下，建立了以最小化單元內(nèi)部及單元之間物流費(fèi)用為優(yōu)化目標(biāo)的數(shù)學(xué)模型。針對單元構(gòu)建問題的特殊性，設(shè)計(jì)了改進(jìn)粒子群算法，采樣兩種編碼方式實(shí)現(xiàn)單元分割點(diǎn)和位置確認(rèn)，引入交叉操作，并對交叉算子進(jìn)行非線性設(shè)計(jì)，使交叉概率隨種群中個體適應(yīng)度值的變化而自適應(yīng)修正，防止了算法收斂到局部最優(yōu)解。論文以某企業(yè)實(shí)際案例為對象進(jìn)行了單元構(gòu)建與物流仿真，較好地解決了實(shí)際單元構(gòu)建問題。

［1］Steve Ah kioon，Akif Asil Bulgak，Tolga Bektas.Integrated cellular manufacturing systems design with production planning and dynamic system reconfiguration［J］.European Journal of Operational Research，2007，192 (2):414 -428.

［2］王愛民，丁國智，寧汝新.制造單元快速構(gòu)建技術(shù)研究［J］.北京理工大學(xué)學(xué)報(bào)，2006，26(10):850 -854.

［3］白書清，王愛民，李伯虎.面向應(yīng)急動員批產(chǎn)的流水式制造單元構(gòu)建技術(shù)［J］.計(jì)算機(jī)集成制造系統(tǒng)，2008，14(1):64 -73.

［4］王建維.制造單元構(gòu)建的關(guān)鍵技術(shù)研究［D］.大連:大連理工大學(xué)，2009.

［5］金哲，宋執(zhí)環(huán)，楊將新.可重構(gòu)制造系統(tǒng)工藝路線與系統(tǒng)布局設(shè)計(jì)研究［J］.計(jì)算機(jī)集成制造系統(tǒng)，2007(1):7 -12.

［6］李淑霞，單鴻波.基于敏捷制造單元的車間動態(tài)重構(gòu)［J］.計(jì)算機(jī)集成制造系統(tǒng)，2007(3):520 -52.

［7］Jaydeep Balakrishnan，Chun Hung Cheng.Multi -Period planning and uncertainty issues in cellular manufacturing:A review and future directions［J］.European Journal of Operational Research，2007，177:281 -309.

［8］Asokan P，Prabhakaran G，Satheesh G Kumar.Machine-Cell Grouping in Cellular Manufacturing Systems Using Non-traditional Optimization Techniques-A Comparative Study［J］.International Journal of Advanced Manufacturing Technology，2001，18(2):140 -147.

［9］Adil G K，Rajamani D.The tradeoff between intra-cell and inter-cell moves in group technology cell formation［J］.Journal of Manufacturing Systems，2000，19 (5):305 -317.

［10］Sh.Ariafar，N.Ismail.Inter-cell and intra-cell layout design in a cellular manufacturing system［J］.Symposium on Business，Engineeringand Industrial Applications，2011(9)，28 -32.

［11］Nsakanda A L，Diaby M and Price W L.Hybrid genetic approach for solving large-scale capacitated cell formation problems with multiple routings［J］.European Journal of Operational Research，2006，171:1051 -1070.

［12］HU L，YASUDA K.Minimizing material handling cost in cell formation with alternative processing routes by grouping genetic algorithm［J］.International Journal of Production Research，2006，44(11):2133 -2167.