基于改進粒子群算法的制造單元構建方法研究*

徐立云 榮 巨 郭昆吾 李愛平

(同濟大學現代制造技術研究所，上海 201804)

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

1 問題描述

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

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

2 數學建模

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

2.1 設備間物流量的計算

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

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

2.2 單元內單位物流量的搬運費用計算

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

故在計算中需要考慮物流方向對物流搬運費用的影響，單向線性布局中物流方向分為順向與逆向兩個方向，從上游設備向下游設備的流動稱為順向，反之則稱為逆向或物流回溯。物流回溯會降低單元內的搬運效率，且其產生的單位物流費用也比順向物流費用要高(CAp＜CBp)。

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

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

2.3 單元間單位物流量的搬運費用計算

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

2.4 數學模型

制造單元構建的目標就是單元內部設備間與單元間的物流搬運費用最小化，數學模型如下:

決策變量:

約束條件:

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

3 算法設計與求解

3.1 基本粒子群算法

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

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

3.2 改進粒子群算法

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

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

式中:l 為粒子長度。

3.3 粒子的編碼與解碼

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

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

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

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

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

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

3.4 IPSO 算法的流程設計

采用IPSO 算法求解制造單元構建問題，算法流程

圖1 粒子位置編碼格式

設計如下:

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

步驟2 計算當前所有粒子的適應度值;

步驟3 判斷是否達到最大迭代次數，若是，停止迭代，輸出結果;否則，轉向步驟4;

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

步驟5 比較當前粒子適應度值與個體最優值pbest，如果當前粒子適應度值比pbest更優，則更新pbest;

步驟6 比較當前粒子適應度值與群體最優值gbest，如果當前粒子適應度值比gbest更優，則更新gbest;

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

4 應用實例

4.1 實例描述

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

表1 生產任務信息表

4.2 案例求解

(1)粒子的編碼

本文采用實數編碼的方式，將粒子編碼分為兩部分，即設備位置的編碼和單元分割點的編碼。每個粒子的結構由設備位置信息和單元分割點信息組成，其表現形式如3.3 節圖1 所示。

(2)初始種群的生成

采用隨機產生初始種群的方法構造初始群體。案例中，機床數為M=20 臺，根據本文所采用的編碼策略，隨機產生的一組初始種群為:

(3)粒子的解碼

本文所采用的解碼策略，是對單元分割點所對應的粒子編碼進行解碼，用函數round 對各編碼位上的數值進行四舍五入操作。因此初始種群里粒子編碼結構的單元分割點解碼為C'div(0，0，0，1，0，1，0，0，0，1，1，0，0，1，0，0，1，0，0)。

(4)適應度計算

本文的目標函數是求搬運費用的最小值，所以根據適應度函數特點，設置其為目標函數的倒數，即:

其中LC 為粒子i 的目標函數。由函數關系知，適應度值fitness(i)與目標函數LC 成反比，目標函數值越小，粒子的適應度越高，粒子更容易接近個體極值點和群體極值點。

(5)速度和位置的更新

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

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

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

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

圖2 父代粒子串

圖3 原始子代粒子串

圖4 修正后的子代粒子串

②單元分割點段交叉操作采用算術交叉，假如選擇的兩個個體是，則交叉運算后產生的新個體是:

其中σ=l1/l。

(7)終止選擇

本文算法中的終止準則采用了預先規定一個最大的迭代次數來終止算法。

4.3 案例分析

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

根據優化算法結果，將車間內設備分成的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}。按照單元內設備線性布置要求，構建車間的制造單元，并對6 種產品加工過程物流量進行仿真分析，如圖6 所示，6 種不同顏色的箭頭分別表示6種產品的物流量Wp。

圖5 目標函數迭代過程

5 結語

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

［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］王愛民，丁國智，寧汝新.制造單元快速構建技術研究［J］.北京理工大學學報，2006，26(10):850 -854.

［3］白書清，王愛民，李伯虎.面向應急動員批產的流水式制造單元構建技術［J］.計算機集成制造系統，2008，14(1):64 -73.

［4］王建維.制造單元構建的關鍵技術研究［D］.大連:大連理工大學，2009.

［5］金哲，宋執環，楊將新.可重構制造系統工藝路線與系統布局設計研究［J］.計算機集成制造系統，2007(1):7 -12.

［6］李淑霞，單鴻波.基于敏捷制造單元的車間動態重構［J］.計算機集成制造系統，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.