連建新，閆 輝，張小稔

（河北工業(yè)大學(xué) 經(jīng)濟管理學(xué)院，天津 300130）

基于分割樹遺傳算法的空間布局多目標優(yōu)化研究

連建新，閆 輝，張小稔

（河北工業(yè)大學(xué) 經(jīng)濟管理學(xué)院，天津 300130）

在分析單目標平面布局優(yōu)化不足的基礎(chǔ)上，構(gòu)建了多目標的車間空間結(jié)構(gòu)布局的非線性規(guī)劃模型，彌補了傳統(tǒng)車間布局過程中對高度、車間空間約束等因素的忽略；同時利用分割樹、波蘭表達法和遺傳算法相結(jié)合的方法，對染色體編碼和遺傳算子變異進行了有效的改進，大大提高了搜索速度．并以某機械加工企業(yè)的油缸車間為例，對其布局進行優(yōu)化，最后畫出更加切合實際需求的車間布局圖．

空間；多目標優(yōu)化；分割樹；遺傳算法

0 引言

隨著經(jīng)濟全球化的進程日益深入，制造企業(yè)的生產(chǎn)模式逐漸趨于大規(guī)模個性化訂制，相互之間競爭也進入了短兵相接階段．而作為企業(yè)生產(chǎn)得以實施的載體——制造車間，也面臨更加嚴峻的考驗．因為為了能夠迅速的對客戶的要求作出響應(yīng)，能在最短時間、以最低成本制造出使顧客滿意的產(chǎn)品，需要對原有車間進行重構(gòu)與優(yōu)化，以適應(yīng)生產(chǎn)．

據(jù)統(tǒng)計表明：在制造業(yè)中，企業(yè)總運營費用的15%～70%用于物料運輸，而一個高效的布局車間可使此費用節(jié)約10%～30%[1]．此外在整個工廠的生產(chǎn)物流活動當中，生產(chǎn)周期的5%～10%用于加工、檢驗，剩余時間都處于搬運、等待狀態(tài)[2]．因此美國每年要花費超過2 500億美元用于車間的布局優(yōu)化上[3]．由此可見布局研究對于制造企業(yè)來說至關(guān)重要．它可以最大限度地降低車間內(nèi)的物料運輸、廢料處理成本，充分利用現(xiàn)有的生產(chǎn)空間、均衡設(shè)備能力等，有利于提高企業(yè)的整體運作效率．然而車間的重構(gòu)與優(yōu)化絕非易事，不僅要承擔(dān)停產(chǎn)的損失，還要考慮車間空間、物料搬運成本、工藝流程等條件的制約．

為此本文針對多行布局，通過充分考慮空間、成本等因素的條件下[4]，運用分割樹遺傳算法，對車間布局問題進行研究．因為通過分割樹與遺傳算法相結(jié)合的方法，即可以顯著提高布局規(guī)劃人員的效率和最終方案的質(zhì)量；又對傳統(tǒng)遺傳算法進行了改進，使編碼更加容易，易于提高搜索速度；同時在布局過程中，是根據(jù)設(shè)備的實際需求面積進行規(guī)則的塊狀分割，將不規(guī)則設(shè)備和設(shè)備的擺放方位也給于充分的考慮．

1 問題的描述

1.1 問題假設(shè)

車間布局問題就是合理安排車間內(nèi)部各種設(shè)施及其相關(guān)的輔助設(shè)施的相對位置與面積，以確保在生產(chǎn)過程中物料與信息的暢通．為了便于簡化計算，在構(gòu)建模型過程中做了如下簡化與假設(shè)：

1）將1個設(shè)備擺放、操作、輔助設(shè)施等所需的空間看成1個整體，稱為1個作業(yè)單位，且作業(yè)單位尺寸已知，如圖1中所示；

2）所有作業(yè)單位都被看成規(guī)則的立方體或長方體，忽略細節(jié)形狀；且輸出、輸入零部件點位于作業(yè)單位的中心點；

3）所有零部件都是從入口進入車間，從出口出，不存在從入口出或出口入的現(xiàn)象；運輸距離除了水平還包括豎直方向；

4）零部件的加工工藝以及與其相對應(yīng)的設(shè)備已知；

5）所有作業(yè)單位沿著車間主運輸?shù)?邊排列；

6）物料在搬運過程中忽略裝卸費用．

1.2 空間布局模型建立

車間布局示意圖，如圖1所示，其中L、W、H分別為車間的長、寬、高；Ld為出入口與車間主運輸車道的寬度；（XI，W），（XI，0）分別為出、入口坐標；i為作業(yè)單位編號，其中i=1,...,n；Wi、Li、Hi為作業(yè)單位寬、長、高；hi為作業(yè)單位i的操作平臺高度；Zi為作業(yè)單位i離車間頂部距離；xi，yi為作業(yè)單位i相對于坐標原點O的X，Y坐標．

圖1 布局結(jié)構(gòu)參數(shù)示意圖Fig.1 Schematic diagram of layout structure parameters

1.2.1 成本物流模型

實際生產(chǎn)制造過程中，物料在作業(yè)單位間的運輸距離，除了水平方向的移動量，還包括豎直方向的移動量．另外物料由車間入口處至加工第1道工序的作業(yè)單位處，由加工最后1道工序的作業(yè)單位處至出口處的運輸方式都與作業(yè)單位間的物料運輸方式是不一樣，因此運輸成本也不一樣．

假設(shè)車間共有n臺設(shè)備，加工Q種零部件，則物流與重置成本表達式如式 (1)

其中：Pqij為第q種零件在作業(yè)單位i與j之間搬運總費用；PqI為第q種零件從入口至加工第1道工序的作業(yè)單位處的移動成本；PqO為第q種零件加工完成后從作業(yè)單位至出口的移動成本．其中Pqij，PqI，PqO定義如式(2)～(4)所示

其中cqij，fqij分別為第q個零件在作業(yè)單位i與j之間的單位物流成本和物流量；

其中fqI，cqI分別為加工第q個零件時，從入口至第1道工序處的物流量和單位物流成本；xqI，yqI，hqI分別為加工第q個零件時，第1道工序的作業(yè)單位相對于坐標原點O的X，Y，Z坐標．

其中cqo，fqo分別為加工第q個零件時，從最后1道工序加工完成之后至出口的單位物流成本和物流量；xqo，yqo，hqo分別為加工第q種零件時，最后1道工序的作業(yè)單位相對于坐標原點O的X，Y，Z坐標．

1.2.2 車間面積利用率模型

車間面積利用率如式 (5)所示

1.3 約束條件

1）面積約束如式 (6)

其中Ai是作業(yè)單位i所需要的面積．

2）形狀約束如式 (7)～式 (8)

3）非負、邊界約束如式 (9)～式 (13)

其中式 (9)～式 (13)確保所有作業(yè)單位都未超出車間；式 (13)定位車間主運輸通道的．

4）定位、不重疊約束如式 (14)～式 (21)

式 (14)與式 (15)表示作業(yè)單位i位于車間入口處（用來定位）；式 (16)與式 (17)中PHr與PHl分別表示1個水平分割樹的右、左葉子；式 (18)與式 (19)中PVr與PVl分別表示1個垂直分割樹的右、左葉子；式 (20)中TVr與TVl分別是垂直分割樹的右與左子樹；式 (21)中THr與THl分表示的是水平分割樹的右與左子樹；

2 設(shè)備布局的遺傳算法

2.1 染色體編碼與解碼

2.1.1 編碼

編碼是將問題的可行解從解空間轉(zhuǎn)換成遺傳空間的，由基因按一定結(jié)構(gòu)組成的染色體的過程．本文采用分割結(jié)構(gòu)（塊狀布局）來表達，令水平切割和垂直切割用算子（內(nèi)部節(jié)點）+和*表示，分割結(jié)構(gòu)包含n個給定的作業(yè)單位（稱作操作數(shù)或葉子），用字母集=(1,2,...,n,*,+)的分割樹或波蘭表達法進行編碼表示．操作數(shù)與算子之間關(guān)系與表達方式如下圖2所示，編碼過程如圖3所示．

圖2 分割結(jié)構(gòu)及其表示Fig.2 Segmentation structure and its representation

圖3 波蘭編碼過程Fig.3 Poland coding process

在編碼過程中必須遵循以下準則：1）1個染色體必須有n個不同的操作數(shù)（作業(yè)單位數(shù)）和（n 1）算子；2）1條染色體中，任何1個元素i（包括i）之前的操作數(shù)總數(shù)必須大于等于，其中為算子數(shù)，否則不能生成并建立合法的波蘭表達式．

2.1.2 解碼

解碼：編碼的逆向過程，將波蘭表達式轉(zhuǎn)換成分割結(jié)構(gòu)（塊狀布局）．對于1個長度為（2n 1）的分割樹，令i是分割樹上任意分割點（或位置），令分別為從分割點右側(cè)到樹的最右側(cè)包含的操作數(shù)和算子總數(shù)．則解碼過程如下．

如果分割點i是第1個位置，在2n 1～1的范圍內(nèi)從右向左查找使等式成立的位置．則在分割點i分割樹可以分成：1）包括給定分割樹中從1～i的元素的左子樹；2）包括給定分割樹中從i+1～2n 2的元素的右子樹，具體如圖4所示．

圖4 解碼過程Fig.4 Decoding process

2.2 初始種群的產(chǎn)生

運用遺傳算法[5]進行車間布局研究時，必須有1個初始種群作為初始解，其通常是隨機產(chǎn)成的，但隨機產(chǎn)成的初始解無法收斂于最優(yōu)解．同時種群的數(shù)量對求解也有顯著影響[6]，數(shù)量過多，運行時間長，影響搜索效率；種群過少，則會過早收斂．因此本文采用系統(tǒng)布置設(shè)計SLP（Systematic Layout Planning）與隨機法來確定初始種群，種群數(shù)量以20～100為宜[7]．

2.3 適值函數(shù)

適值函數(shù)定義為

2.4 選擇

采用Holland正比選擇法，即根據(jù)每個染色體適值的比列來確定個體的選擇概率[8]．選擇過程就是根據(jù)這些概率先建立1個輪盤賭模型，然后旋轉(zhuǎn)輪盤pop size（種群規(guī)模）次，每次為新種群選出1個個體．設(shè)fi為種群中個體i的適值，N為種群數(shù)．則個體i被選中的概率是

根據(jù)式 (23)，適值概率越高的個體被選中的幾率越大．

2.5 變異操作

針對每個染色體采用2種變異方式．第1種是2個算子相互替代，如圖5所示；第2種是交換2個操作數(shù)或算子的位置，如圖6所示．這種變異可保證產(chǎn)生合法的后代．

3 實例應(yīng)用

以某機械加工企業(yè)的油缸車間為例，該車間總共有11臺設(shè)備（5臺深孔鏜床，5臺普通車床，1臺珩磨機），36種不同規(guī)格油缸．為了便于計算此處將其全部轉(zhuǎn)換成物流量；總面積為17×30m2，實際上用于設(shè)備布局的面積為15×24m2．

圖5 替代操作Fig.5 Alternative operations

圖6 交換操作Fig.6 Switching operations

表1 機加工工序和設(shè)備尺寸Tab.1 Machining processes and equipment dimensions

表2 作業(yè)單位與幾何約束Tab.2 Operating units and geometric constraints

表3 設(shè)備間當量物流量 (kg/d)Tab.3 Equipment room equivalent flow rate (kg/d)

0、12分別為入、出口；1，…，5代表深孔鏜床；6，7，…，10普通車床；11為珩磨機．進出、入口搬運費用為0.002元/（m kg），設(shè)備之間搬運費用0.001元/（m kg）．入、出口坐標分別為（4，0）、（4，24）．遺傳算法的相關(guān)參數(shù)設(shè)：pop size=50，pm=0.001，max gen=200．總目標的權(quán)重定為u1=0.6、u2=0.4．計算結(jié)果如下：[12345****11678910****++]．則該車間布局的原始圖見圖7，優(yōu)化后的布局圖以及相應(yīng)的分割樹見圖8、圖9．

從表4中可得知，車間重構(gòu)后物料搬運的總距離減少了42.5m，搬運費用降至3 320，車間的空間利用提高了．

圖7 原始圖Fig.7 The original graph

圖8 優(yōu)化圖Fig.8 Optimization diagram

圖9 優(yōu)化后的樹表示Fig.9 Optimal tree representation

表4 重構(gòu)前后的相關(guān)參數(shù)對比Tab.4 Comparison of correlation parameters before and after reconstruction

4 結(jié)語

有效、合理的車間設(shè)施布局可以最大限度地縮短物料搬運距離，提高車間的利用率，降低生產(chǎn)成本．本文針對多行布局，構(gòu)建了多目標的車間空間布局非線性規(guī)劃模型，并利用分割樹遺傳算法進行求解．通過以某機械加工企業(yè)的油缸車間重構(gòu)前后物流費用，占用面積比率的對比，驗證了該算法與模型的有效性．

綜上所述，通過對運輸費用、加工工藝、車間的空間限制條件等影響車間布局的相關(guān)因素分析，并通過相關(guān)案例的應(yīng)用，可以得出分割樹遺傳算法可以有效的解決或優(yōu)化這種含有不同種類設(shè)備、多約束條件下的車間布局問題．

[1]Tompkins JA，White JA．Facilities planning[M]．3rd edn，New York：Wiley，2003．

[2]方慶琯，王轉(zhuǎn)．現(xiàn)代物流設(shè)施與規(guī)劃 [M]．北京：機械工業(yè)出版社，2009．

[3]Lee H J．Heuristic graph-theoretic approach in facility layout problem：the development of a decision support system[J]．Annual Reviews in Control，2007，31（1）：255-267．

[4]Kim Jae Gon，Kim Yeong Dae．Layout planning for facilities with fixed shapes and input and output points[J]．Internationanl Journal of Production Research，2000，38（18）：4635-4653．

[5]Farhad Azadivar，Wang John（Jian）．Facility layout optimization using simulation and genetic algorithms[J]．Interntional Journal of Production Reserch，2000，38（17）：4369-4383．

[6]Yosra Ojaghi，Alireza Khademi．Production layout optimization for small and medium scale food industry[J]．Procedia CIRP，2015（26）：27-251．

[7]肖國紅，弓清忠，榮星，等．基于設(shè)備參數(shù)化的鏡片車間優(yōu)化布局 [J]．技術(shù)創(chuàng)新，2015，38（5）：63-65．

[8]Mitsuo Gen，Runwei Cheng．Genetic algorithms and engineering optimization[J]．International Journal of Production Research，2013，24（3）：1095-1109．

[責(zé)任編輯 田 豐 夏紅梅]

Based on the segmentation tree space layout of the multi-objective optimization of genetic algorithm research

LIAN Jianxin，YAN Hui，ZHANG Xiaoren

(School of Economics and Management,Hebei University of Technology,Tianjin 300130,China)

On the basis of the logistics cost and two-dimensional layout optimization analysis of defects on buliding a multi-objective dynamic spatial facility layout optimization model for multi-variety production system.On account of the logistics cost,replacement cost,space utilization,equipment utilization rate,and other factors,the use of partheno genetic algorithm based on objective weighting method and polish expression to evaluate selection,them ore reasonable plan.

space;multi-objective optimization;cut tree;genetic algotithm

F273.1

A

1007-2373(2016)05-0056-08

10.14081/j.cnki.hgdxb.2016.05.009

2016-09-27

連建新（1971-），男（漢族），副研究員．