面向低熵的一類多態性作業車間布局智能建模

陳 勇，許雅斌，王 成，王亞良，勵秀宇(浙江工業大學 機械工程學院，浙江 杭州 310014)

面向低熵的一類多態性作業車間布局智能建模

陳 勇，許雅斌，王 成，王亞良，勵秀宇
(浙江工業大學 機械工程學院，浙江 杭州 310014)

針對一類多態性作業車間，提出車間低熵化布局評價指標，利用成組技術和分層思想構建單元外部連續布局和單元內部多行布局的低熵車間布局模型.針對多約束、多變量和非線性的特點，以物料搬運成本、設備成本、非物流附加成本、車間面積利用率、平均在制品數量和柔性為模型多目標函數，借助元胞自動機的拓撲結構和鄰居機制，設計一種基于精英初始解策略和自適應交叉、變異算子的遺傳元胞算法進行求解.通過典型企業作業車間布局改造實例分析，驗證模型和算法的可行性與有效性.

低熵布局；遺傳元胞算法；多目標；多態性

隨著全球市場環境的急劇變化，制造業競爭越來越激烈，客戶需求更加多樣化，使得企業生產產品時變動性特別大，尤其在設備、工藝和定單方面，對車間布局的魯棒性和柔性需求增強，如何降低在制品數量、提高生產系統柔性、實現物流合理化已成為制造型企業必須解決的關鍵問題.針對這一多態性車間，提出一種低熵化車間布局模式能夠使企業車間布局具有低碳節能、高柔性等特性，讓企業在不增加成本或擴建車間前提下能夠應對客戶多樣化需求.

現有面向低熵多態性車間布局建模研究并不多見，多集中于面向低碳物流和多目標車間布局建模研究：肖燕等將系統布置設計法與低碳及低碳物流結合，設計了基于低碳物流的SLP改進方法，使得物流綜合性能大大提高，降低廢物排放[1]；曾強和沈玲以物料搬運量距、非物流關系強度、設施所需總面積為優化目標建立基于NSGAII的多目標優化模型[2]；Ramazan和Orhan利用SA算法求解多目標設施布局問題，并求得帕累托最優解[3]；Ravi將傳統的遺傳算法中的交叉算子進行改造，得到一種新型的改進的遺傳算法，解決車間布局在不確定環境下的大型單行設備布局問題[4]；郭源源等利用粒子群優化算法解決以設備間的搬運成本為目標的連續空間布局優化問題[5]；張屹等在多目標遺傳算法的基礎上引入差分演化策略，有收斂性強、覆蓋范圍廣的特點，有效解決了多目標優化的生產車間設備布局問題[6].筆者以物料搬運成本、設備成本、非物流附加成本、車間面積利用率、平均在制品數量、柔性和設備使用效率等為模型多目標函數設計一種基于精英策略和自適應交叉、變異算子的遺傳元胞算法，借助元胞自動機的拓撲結構和鄰居等機制[7-9]來獲得多目標低熵布局方案.

1 多態性車間低熵布局建模

1.1 車間布局低熵評價指標

車間在生產過程中與外界進行物質和信息交換，可視為一個開放、具有無序性和混亂度的系統，結合統計物理系統理論中關于開放系統的幾率分布和物理熵[10]對車間布局的熵評價指標進行推導.

車間中的設備、物料等可視為開放系統的粒子N，車間各設備、物料不同的組合產能設為各粒子在s狀態下所具有的能量Es，則車間在某一狀態(N，s)的概率PN,s為

(1)

車間熵H為

(2)

式中：K為比例系數；α為粒子運動速率；為能量耗散速率；M′為熵因子.

根據式(1，2)推導車間熵評價指標H為

(3)

式中：K為比例系數；N為系統當中的粒子數即設備和物料數量；PN,s為系統在某一狀態(N，s)的概率，推導可知-lnPN,s為車間系統在某狀態的產能.車間布局低熵評價指標表明車間內設備數量和物料量越多，車間內熵值H越高，混亂度也越高.

1.2 低熵多態性車間布局模型

針對多態性作業車間產品品種多、工藝路線各異、設備多樣性程度高和設備數量多的特點，首先利用成組技術對作業單元進行劃分，確定各作業單元內部的待布置設施和尺寸，進行單元間布局建模.在作業單元間布局模型中，以作業單元為最小建模元素.綜合考慮模型真實性、求解難易程度，做出以下假設：1) 車間為矩形，不考慮車間高度；2) 各作業單元均為矩形，尺寸已提前設定；3) 各作業單元在車間內隨機排列，分別平行于車間四周；4) 作業單元間的物流路徑都平行于X軸和Y軸.根據假設，作業單元間布局問題可以簡化為滿足約束條件的連續型布局優化問題.在完成單元間布局模型的構建和求解之后，可得每個作業單元的具體位置，以設備為最小建模元素，利用機群原則和成組原則相結合的布置原則進行單元內多行布局建模.

1.3 多目標函數

多態性車間低熵布局，除了考慮低熵評價指標中的物料數量，即在制品數量和設備數量因素以外，還要考慮傳統物流搬運費用和車間面積利用率，以及非物流因素、設備利用率和生產柔性.

針對作業單元間布局模型和作業單元內布局模型，構建多目標函數如下：

1) 物料搬運成本C1，即

(4)

式中：N為單元或者設備數量；(Xi,Yi)為設備i的坐標；(Xj,Yj)為設備j的坐標；Cij為作業單元或者設備i，j間移動單位距離的成本；Wij為作業單元或者設備i，j間的物流量.

2) 非物流附加成本C2，即

C2=C2-A+C2-B

(5)

(6)

(7)

3) 車間面積利用率S，即

(8)

式中：Si為各作業單元或者設備的布置面積；Sl為最終布局結果所占用的總面積.

(9)

式中：M為車間產品數量；R0i為車間生產產品i的理論生產能力；Ri為車間生產產品i的瓶頸單元生產能力；Ti為車間生產產品i的生產周期.

(10)

式中：n為作業單元內的設備數量；q為作業單元內的加工的產品數量；pij為設備i在生產產品j的實際產能；p0ij為設備i在生產產品j的理論產能.

6) 設備成本，即

(11)

式中：n為單元內的設備數量；qi為設備i的成本.

7) 柔性V，即

(12)

式中：N為單元數量；M為車間產品數量；Rij為單元i生產產品j的理論生產能力；Tj為車間生產產品j的生產周期；Wij為作業單元i，j間的物流量.

基于模糊滿意度的多目標決策方法，綜合考慮進行歸一化處理，得到目標函數如下：

(13)

1.4 約束條件

結合多態性作業車間部分作業單元布局位置特殊限定因素，約束條件如下：

1) 邊界約束為

(14)

(15)

(16)

(17)

式中：Li為作業單元i的長度；Hi為作業單元i的寬度；L為車間長度；H為車間寬度；L0為作業單元與車間邊界X向最小間距；H0為作業單元與車間邊界Y向最小間距.

2) 間距約束為

Aij×Bij=0

(18)

(19)

(20)

式中：Lmin為作業單元在x方向的最小間距；Hmin為作業單元在y方向的最小間距.

3) 設備布局位置約束為

(21)

(22)

式中：xi為設備i的橫坐標；yi為設備i的縱坐標；li為設備i的長度；hi為設備i的寬度；l為作業單元長度；h為作業單元寬度；lmin和hmin為表示設備在x方向和y方向的最小間距；zik為決策變量，表示設備i是否在k行，如果設備i在k行，zik=1，否則zik=0；k=1,2,…,t，t為單元內布局的總行數.

2 遺傳元胞算法

2.1 初始種群獲取

先利用遺傳算法生成最優解作為精英染色體，重復迭代M次，產生M個精英染色體作為精英染色體種群，取代部分隨機染色體，作為初始種群.

2.2 染色體編碼與解碼

多態性作業車間各單元間物流關系復雜，編碼需表達清楚車間內單元的位置和單元布置方向.單元布置位置部分采用整數和浮點數相結合的混合編碼方式，其中整數部分位表示待布置作業單元的序號，浮點數位部分表示各單元的坐標；單元布置方向部分采用二進制編碼方式(0,1)，0表示單元的長與X方向平行，1表示單元的長與X方向垂直.以5個作業單元編碼為例，其染色體的表達方式如圖1所示.染色體采用這種編碼方式可以直接得到各單元的具體位置，不需要進行解碼.

圖1 染色體編碼方式Fig.1 The schematic diagram of genetic encoding method

2.3 適應度函數

單元間和單元內的目標函數優化方向與適應度函數值增加的方向均不一致，將多態性車間低熵布局多目標函數設為適應度函數如下：

(23)

2.4 選 擇

采用輪盤賭法，從當前個體周圍鄰居中選擇出兩個個體.個體的適應度越高，被選擇的概率越大，個體被選擇的概率為

(24)

式中：i為種群中染色體編號；M為種群個體數量，1≤i≤M；fiti為每個個體的適應度.

2.5 交 叉

采用金晶等[11]提出的交叉算子的非線性處理方法，使交叉概率能夠隨群體中個體適應度值的變化而變化，從而使得種群具有多樣性，避免“早熟”現象和陷入局部最優現象的產生.在進行尋優過程中主要涉及到的是位置選擇染色體部分有單元編號序列選擇、單元坐標序列選擇和單元布置方向序列選擇，分別采取不同的交叉方式.

2.5.1 單元編號序列選擇染色體交叉

采用雙點交叉及修復程序PMX算子相結合的方式如圖2所示.

圖2 單元編號序列選擇染色體PMX交叉Fig.2 The schematic diagram of unit number selection chromosome PMX crossover

2.5.2 坐標選擇序列染色體交叉

(25)

(26)

(27)

(28)

式中：e為0～1之間的小數；i=1,2,…,n，其中n為相鄰間距個數.

2.5.3 布置方向選擇序列染色體交叉

采用兩點交叉方式如圖3所示.

圖3 布置方向序列選擇染色體兩點交叉Fig.3 The schematic diagram of layout direction selection chromosome Two-point crossover

2.6 變 異

采用金晶等[11]提出的非線性處理方法進行變異，為避免個體局部收斂和保證子代為可行解，只對單元編號序列和布置方向序列進行基本位變異.變異概率計算公式如下：

(29)

式中：Pm為變異概率；Pmmax為變異概率可取的最大值；Pmmin為變異概率可取的最小值；fit為進行變異操作的個體的適應度值；fitmax為目前種群中的最大適應度值；fitavg為目前種群中的平均適應度值；λ=9.9.

2.7 遺傳元胞算法求解流程

遺傳元胞算法求解多態性低熵車間布局流程圖如圖4所示.

圖4 遺傳元胞算法求解流程Fig.4 The flowchart of genetic cellular automata algorithm

3 算例驗證分析

為驗證論文提出的遺傳元胞算法的實用性，現以一算例進行證明.算例采用郭源源等在文獻[5]中求解的車間布局案例，分別利用原文獻算法和筆者算法進行求解，并對兩種改進優化算法所得到的結果進行比較.筆者算法參數的設定為種群數量N=200，精英種群M=50，文檔大小K=100，反饋數目C=40，迭代次數T=400，Pcmax=0.8，Pcmin=0.6，Pmmax=0.04，Pmmin=0.005.圖5為筆者算法的仿真過程，表1為車間設備組最終坐標，表2為兩種算法的結果對比表.

圖5 遺傳元胞算法迭代優化過程Fig.5 The optimization process of genetic cellular automata algorithm

表1 車間設備組最終坐標表Table 1 Final coordinates for workshop equipment group

表2 兩種算法結果對比表Table 2 The comparison of result using different algorithm

由表2可知：遺傳元胞算法和文獻[5]算法都能在有限的代數內尋得最優解或近似最優解，但遺傳元胞算法求得目標函數的最優解明顯優于文獻[5]算法，而且所用的代數更短.從而證明遺傳元胞算法在求解車間布局模型的可行性和有效性.

4 案例研究

選取典型制造型企業，其1#車間的長和寬為150 m×80 m，現車間內共有注塑單元、裝配1單元、裝配2單元、手柄預裝單元、地刷預裝單元、塵杯預裝單元、半成品單元、原材料單元、電機單元、包裝1單元、包裝2單元、噴漆單元、絲印單元和檢驗單元等一共14個功能單元，現狀如圖6所示.搬運工具為手推臺車和叉車，單位搬運成本為1(單位1=2×10-1元/m)，通過計算1#車間的物料搬運成本為1.547 8×107元/年，車間面積利用率為65.75%.1#車間所需要生產的產品種類眾多，但各系列產品之間工藝相似度高，可利用成組技術進行作業單元劃分，可劃分為11個單元，如表3所示，其中包括單元編號、單元名稱和單元尺寸，設備尺寸信息如表4所示.

圖6 車間布局現狀Fig.6 Workshop layout status

表3 作業單元劃分信息表Table 3 The result of working unit partition m2

表4 設備尺寸Table 4 The size of equipments m2

使用遺傳元胞算法對車間布局求解，分別對算法部分參數進行設置：取種群規模N=200，精英種群M=50，設定最大迭代代數T為500代，文檔大小K=100，反饋數目C=40，Pcmax=0.8，Pcmin=0.6，Pmmax=0.04，Pmmin=0.005，根據專家規則得到α1=0.53，α2=0.28，α3=0.19，在程序當中運行20次，取其中的最優的一次作為輸出結果.最優的適應度函數值為17.012 3，對應的目標函數值為0.058 781，車間布局最優解如圖7所示，其各項子目標值如表5所示.

圖7 車間布局最優解Fig.7 Optimal solution of workshop layout

表5 目標函數值Table 5 The objective function value

由表5可以看出：最終布局方案相比車間現狀能夠有效降低物料搬運成本、非物流附加成本和在制品水平，有效提高設備綜合效率、布局柔性和車間面積利用率.優化后的布局在生產流程連續性方面得到了的提高，減少了單元內設備在生產時的等待、停機及空轉等現象，應對生產過程當中產品數量、批量等因素變動時，具有較高的自身調節能力和適應能力，提高了抗干擾能力.在滿足車間產能要求的前提下，通過提高設備綜合效率，降低了車間內部設備數量和在制品水平，保證了多態性車間布局的低熵化.

5 結 論

車間布局是企業進行生產的前提，也是制造業實現節能環保、低熵發展的突破口.提出的面向低熵的多態性作業車間布局模型和遺傳元胞算法通過算法運行對比，并應用于車間的實際布局中，結果表明能夠有效降低車間布局熵值和提高布局的柔性，驗證其具有可行性和有效性.但目前建立多態性作業車間布局模型時，假設了所有研究單元和設備都為規則的矩形，沒有實際考慮單元和設備的不規則性，在今后的研究中，可考慮單元設備不規則性對建模求解的影響，使面向低熵的多態性車間布局更加精確.

[1] 肖燕，程云康，周康渠.基于低碳物流的SLP法在工廠布局的應用[J].重慶理工大學學報(自然科學版),2011,25(11)：24-29.

[2] 曾強,沈玲.基于NSGAII的多目標車間設施布局優化方法[J].計算機工程與應用,2012,48(27)：223-228.

[3] RAMAZAN S, ORHAN T. A simulated annealing algorithm to find approximate Pareto optimal solutions for the multi-objective facility layout problem[J]. The international journal of advanced manufacturing technology,2009,41(9)：1003-1018.

[4] RAVI K, DIPTESH G.An efficient genetic algorithm for single row facility layout[J].Optimization letters,2014,8(2)：679-690.

[5] 郭源源,王謙,梁峰.基于粒子群優化算法的車間布局設計[J].計算機集成制造系統,2012,11(18)：2476-2484.

[6] 張屹,盧超,張虎.基于查分元胞多目標遺傳算法的車間布局優化計[J].計算機集成制造系統,2013,19(2)：727-734.

[7] 陳勇,阮興聰,王亞良,等.基于元胞機的大型機械構建生產車間柔性調度求解[J].浙江工業大學學報,2011,39(4)：433-439.

[8] 陳勇,王忠住,王亞良,等.基于遺傳元胞機的多態性作業車間布局建模[J].浙江工業大學學報,2014,42(6)：676-681.

[9] 陳勇,羊笑笑,王成,等.基于細胞自動機的大尺度制造4D調度模型[J].浙江工業大學學報,2015,43(2)：168-173.

[10] 邢修三.物理熵、信息熵及其演化方程[J].中國科學(A輯),2001,1(2)：77-84.

[11] 金晶,蘇勇.一種改進自適應遺傳算法[J].計算機工程與應用,2005,42(18)：64-69.

(責任編輯：陳石平)

Intelligent modeling of a type of polymorphism job shop layout for low entropy

CHEN Yong, XU Yabin, WANG Chen, WANG Yaliang, LI Xiuyu
(College of Mechanical Engineering, Zhejiang University of Technology, Hangzhou 310014, China)

Aiming at the a type of polymorphism job shop layout for low entropy, the mechanism and solutions of low-entropy application be carried out. The layout of modeling for low entropy shop is developed divided into two parts, which includes a model between cells and in cells based on group technology and layered thought. For the characters of multi-constraints, multi-variable and nonlinear of layout models, considering of the material handling cost, equipment cost, additional cost of area utilization ratio, WIP and the flexibility as multi objective function, the paper submitted a kind of cellular automata and genetic algorithm with the help of topological structure of cellular automata and neighbor mechanism. The typical case is used to illustrate the feasibility and effectiveness of the model for the polymorphism job shop.

low-entropy layout; genetic cellular automata algorithm; multi-objective; polymorphism

2016-06-20

國家自然科學基金資助項目(71371170，71301148)；浙江省自然科學基金資助項目(Y16G010038)

陳 勇(1973—)，男，湖南湘潭人，教授，博士，研究方向為生產系統建模與仿真，E-mail：cy@zjut.edu.cn.

TB491

A

1006-4303(2017)02-0119-06