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

面向低熵的一類多態(tài)性作業(yè)車間布局智能建模

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

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

低熵布局；遺傳元胞算法；多目標；多態(tài)性

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

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

1 多態(tài)性車間低熵布局建模

1.1 車間布局低熵評價指標

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

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

(1)

車間熵H為

(2)

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

根據(jù)式(1，2)推導(dǎo)車間熵評價指標H為

(3)

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

1.2 低熵多態(tài)性車間布局模型

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

1.3 多目標函數(shù)

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

針對作業(yè)單元間布局模型和作業(yè)單元內(nèi)布局模型，構(gòu)建多目標函數(shù)如下：

1) 物料搬運成本C1，即

(4)

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

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

C2=C2-A+C2-B

(5)

(6)

(7)

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

(8)

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

(9)

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

(10)

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

6) 設(shè)備成本，即

(11)

式中：n為單元內(nèi)的設(shè)備數(shù)量；qi為設(shè)備i的成本.

7) 柔性V，即

(12)

式中：N為單元數(shù)量；M為車間產(chǎn)品數(shù)量；Rij為單元i生產(chǎn)產(chǎn)品j的理論生產(chǎn)能力；Tj為車間生產(chǎn)產(chǎn)品j的生產(chǎn)周期；Wij為作業(yè)單元i，j間的物流量.

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

(13)

1.4 約束條件

結(jié)合多態(tài)性作業(yè)車間部分作業(yè)單元布局位置特殊限定因素，約束條件如下：

1) 邊界約束為

(14)

(15)

(16)

(17)

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

2) 間距約束為

Aij×Bij=0

(18)

(19)

(20)

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

3) 設(shè)備布局位置約束為

(21)

(22)

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

2 遺傳元胞算法

2.1 初始種群獲取

先利用遺傳算法生成最優(yōu)解作為精英染色體，重復(fù)迭代M次，產(chǎn)生M個精英染色體作為精英染色體種群，取代部分隨機染色體，作為初始種群.

2.2 染色體編碼與解碼

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

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

2.3 適應(yīng)度函數(shù)

單元間和單元內(nèi)的目標函數(shù)優(yōu)化方向與適應(yīng)度函數(shù)值增加的方向均不一致，將多態(tài)性車間低熵布局多目標函數(shù)設(shè)為適應(yīng)度函數(shù)如下：

(23)

2.4 選 擇

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

(24)

式中：i為種群中染色體編號；M為種群個體數(shù)量，1≤i≤M；fiti為每個個體的適應(yīng)度.

2.5 交 叉

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

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

采用雙點交叉及修復(fù)程序PMX算子相結(jié)合的方式如圖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之間的小數(shù)；i=1,2,…,n，其中n為相鄰間距個數(shù).

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為進行變異操作的個體的適應(yīng)度值；fitmax為目前種群中的最大適應(yīng)度值；fitavg為目前種群中的平均適應(yīng)度值；λ=9.9.

2.7 遺傳元胞算法求解流程

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

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

3 算例驗證分析

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

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

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

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

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

4 案例研究

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

圖6 車間布局現(xiàn)狀Fig.6 Workshop layout status

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

表4 設(shè)備尺寸Table 4 The size of equipments m2

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

圖7 車間布局最優(yōu)解Fig.7 Optimal solution of workshop layout

表5 目標函數(shù)值Table 5 The objective function value

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

5 結(jié) 論

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

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

[2] 曾強,沈玲.基于NSGAII的多目標車間設(shè)施布局優(yōu)化方法[J].計算機工程與應(yīng)用,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] 郭源源,王謙,梁峰.基于粒子群優(yōu)化算法的車間布局設(shè)計[J].計算機集成制造系統(tǒng),2012,11(18)：2476-2484.

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

[7] 陳勇,阮興聰,王亞良,等.基于元胞機的大型機械構(gòu)建生產(chǎn)車間柔性調(diào)度求解[J].浙江工業(yè)大學(xué)學(xué)報,2011,39(4)：433-439.

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

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

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

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

(責(zé)任編輯：陳石平)

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

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

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

TB491

A

1006-4303(2017)02-0119-06