唐 贇

（1.上海交通大學(xué)，上海200240；2.上海電氣電站設(shè)備有限公司上海電站輔機(jī)廠，上海200090）

基于單親遺傳算法的車間布局研究

唐 贇1，2

（1.上海交通大學(xué)，上海200240；2.上海電氣電站設(shè)備有限公司上海電站輔機(jī)廠，上海200090）

生產(chǎn)車間的布局問(wèn)題主要是針對(duì)各個(gè)產(chǎn)品總裝區(qū)域的布置，關(guān)系到生產(chǎn)的物流成本及產(chǎn)出效益。將某大型車間的布局方案，抽象成二次分配問(wèn)題，即給定若干個(gè)位置，為每個(gè)產(chǎn)品總裝區(qū)分配一個(gè)位置，使得區(qū)域間的物流費(fèi)用之和最小。采用單親遺傳算法進(jìn)行求解，應(yīng)用正交試驗(yàn)找出最合適的種群規(guī)模、基因重組概率和遺傳代數(shù)，通過(guò)計(jì)算機(jī)編程實(shí)現(xiàn)算法，成功找到了滿意的車間布局方案。

車間布局；單親遺傳算法；物流；成本；二次分配模型；編程；正交試驗(yàn)；計(jì)算

0 概 述

根據(jù)價(jià)值流分析的統(tǒng)計(jì)結(jié)果，在加工和裝配類的制造型企業(yè)中，產(chǎn)品處于加工或裝配時(shí)間僅占整個(gè)制造周期的10%～20%，其他時(shí)間主要花費(fèi)于物流或加工等待，導(dǎo)致產(chǎn)品物流的相關(guān)成本占產(chǎn)品總成本的20%～50%。良好的車間布局方案，可有效地減少車間內(nèi)部的物流距離和物流時(shí)間，并使得物流的相關(guān)成本下降10%～30%，同時(shí)，還能提高車間的生產(chǎn)效率，降低生產(chǎn)成本，提高生產(chǎn)安全系數(shù)等，不僅能節(jié)約物流費(fèi)用、減少制造成本、縮短制造周期，還能加快生產(chǎn)資金的流轉(zhuǎn)，提高企業(yè)的競(jìng)爭(zhēng)力。

1 課題來(lái)源

研究課題來(lái)源于某企業(yè)重型車間布置的實(shí)際需求。隨著發(fā)電技術(shù)的進(jìn)步，大容量高參數(shù)機(jī)組有了很大的發(fā)展，因而設(shè)備的尺寸越來(lái)越大、重量也越來(lái)越重。因此，某企業(yè)將籌建專門(mén)用于制造大型新產(chǎn)品的重型車間，希望通過(guò)單親遺傳算法，為車間內(nèi)的新產(chǎn)品總裝場(chǎng)地和零部件堆放場(chǎng)地找到一個(gè)合適的布局方案，使得車間內(nèi)部物流的總成本最低，從而降低新產(chǎn)品的總體成本，提升新產(chǎn)品的競(jìng)爭(zhēng)力。

2 單親遺傳算法

美國(guó)密歇根大學(xué)的Holland教授于20世紀(jì)70年代提出了遺傳算法，通過(guò)模擬自然界生物的遺傳和進(jìn)化過(guò)程進(jìn)行搜索計(jì)算，其核心機(jī)制就是優(yōu)勝劣汰，在選擇、交叉和變異等遺傳操作的影響下，通過(guò)進(jìn)化得到最適應(yīng)環(huán)境的個(gè)體，即求得問(wèn)題的滿意解。針對(duì)遺傳算法在組合優(yōu)化問(wèn)題上的不足，李茂軍和童調(diào)生等在1998年對(duì)遺傳算法進(jìn)行改進(jìn)并提出了一個(gè)新的算法，這個(gè)算法不使用交叉操作，所有的遺傳操作都只需要一個(gè)染色體，即通過(guò)一個(gè)父代就可以產(chǎn)生子代，類似自然界中泥鰍和蚯蚓等可以單親繁殖的動(dòng)物，因此被稱之為單親遺傳算法。單親遺傳算法通過(guò)循環(huán)迭代，求得最優(yōu)解，求解的基本的流程，如圖1所示。

圖1 單親遺傳算法流程圖

3 建立車間布局的數(shù)學(xué)模型

某重型車間位于上海臨港地區(qū)，廠房由鋼結(jié)構(gòu)件和彩鋼板組成的標(biāo)準(zhǔn)長(zhǎng)方形，東西長(zhǎng)360 m，南北寬36 m，高度24 m。超大超重的設(shè)備總裝均在該重型車間內(nèi)完成，計(jì)劃年產(chǎn)量是6臺(tái)1 000 MW核電除氧器、2臺(tái)1 000 MW核電冷凝器、4臺(tái)1 000 MW核電汽水分離再熱器、9臺(tái)1000 MW高壓給水加熱器和6臺(tái)1 000 MW低壓給水加熱器。

根據(jù)各個(gè)產(chǎn)品的制造周期和年產(chǎn)量，可計(jì)算所需的總裝區(qū)域，即需要2個(gè)核電除氧器總裝區(qū)域、2個(gè)核電冷凝器總裝區(qū)域、1個(gè)汽水分離再熱器總裝區(qū)域、1個(gè)高壓給水加熱器總裝區(qū)域和1個(gè)低壓給水加熱器總裝區(qū)域，再加上1個(gè)零部件堆放區(qū)域，因而需要完成8個(gè)區(qū)域的布局設(shè)計(jì)。重型車間內(nèi)已布置有退火爐、水壓試驗(yàn)臺(tái)、卷板機(jī)、十字架自動(dòng)焊機(jī)、數(shù)控鏜銑床、噴砂房和探傷室等設(shè)備和設(shè)施，剩余的場(chǎng)地有2塊，場(chǎng)地尺寸分別為96 m×18 m；288 m× 18 m，如將其分為相同的8塊，可得到每塊區(qū)域的長(zhǎng)度為48m，寬度為18m。車間內(nèi)的區(qū)域劃分及編號(hào)，如表1所示。車間的區(qū)域分布圖，如圖2所示。

表1 車間區(qū)域表

為了簡(jiǎn)化車間布局問(wèn)題，提出下列假設(shè)條件：

（1）車間內(nèi)的各個(gè)區(qū)域各不相同，即使2個(gè)總裝區(qū)內(nèi)的產(chǎn)品相同。

（2）不考慮車間內(nèi)綠色通道的寬度，將其視為直線。

圖2 車間區(qū)域圖

（3）各個(gè)產(chǎn)品的總裝區(qū)域和零部件堆放區(qū)域均為面積相同的矩形。

（4）不考慮各個(gè)區(qū)域布置的固定成本。

（5）區(qū)域之間的距離dij為其中心間的直角距離，如果區(qū)域i的中心中標(biāo)為（xi，yi），區(qū)域j的中心坐標(biāo)為（xj，yj），則dij=｜xi-xj｜+｜yi-yj｜。

（6）區(qū)域之間的單位物流費(fèi)用cij與距離dij成正比，可令cij=dij。

根據(jù)假設(shè)條件和二次分配模型，得到該重型車間數(shù)學(xué)模型的目標(biāo)函數(shù)式，如式（1）所示。

式（1）～式（4）中：

vp-代表一種車間布局方案；

n-區(qū)域數(shù)量；

xik=1-區(qū)域i被分配到位置k，否則xik=0；

fij-區(qū)域i到區(qū)域j的物流量；

dij-區(qū)域i到區(qū)域j的距離。

于是，該重型車間的布局問(wèn)題轉(zhuǎn)化為求解vp，即使表達(dá)式（1）的值最小。

以該重型車間的西南角為原點(diǎn)，東西方向?yàn)閤軸，南北方向?yàn)閥軸，可得各位置中心坐標(biāo)的矩陣：

一旦確定所有區(qū)域的位置，就可計(jì)算出各個(gè)區(qū)域之間的距離dij。通過(guò)分析各個(gè)產(chǎn)品的工藝流程和年產(chǎn)量，可得到臨港車間年度的區(qū)域物流量fij：

4 基于單親遺傳算法的布局求解

問(wèn)題解的編碼方式采用序號(hào)編碼，由于尚未確定的區(qū)域有8個(gè)，因此將染色體的長(zhǎng)度定為8，并在Matlab程序中，將此變量定義為chromosome_size。8個(gè)基因位分別代表了位置1至位置8，而8個(gè)序號(hào)基因值分別代表了8個(gè)待定區(qū)域。

單親遺傳算法對(duì)于種群的個(gè)體多樣性沒(méi)有要求，因此，通過(guò)隨機(jī)方式產(chǎn)生初始種群，綜合考慮計(jì)算效率和計(jì)算精度之后，根據(jù)經(jīng)驗(yàn)設(shè)定種群規(guī)模的5個(gè)可選值：1、2、4、8、16。在Matlab程序中，將此變量定義為population_size，并通過(guò)first_ generation函數(shù)產(chǎn)生初始種群。

%x為染色體長(zhǎng)度，y為種群規(guī)模，z為初始種群。

評(píng)價(jià)種群就是使用適應(yīng)度函數(shù)來(lái)計(jì)算各個(gè)染色體的適應(yīng)度，由于臨港車間布局問(wèn)題的目標(biāo)函數(shù)需要求出最小值，因此將適應(yīng)度函數(shù)定為目標(biāo)函數(shù)的倒數(shù)。

在Matlab程序中使用fit函數(shù)來(lái)計(jì)算染色體的適應(yīng)度。

%x為染色體，D為位置坐標(biāo)矩陣，f為區(qū)域物流量矩陣。

車間布局問(wèn)題算法的停止條件為達(dá)到設(shè)定的遺傳代數(shù)，綜合考慮計(jì)算效率和計(jì)算精度之后，根據(jù)經(jīng)驗(yàn)，設(shè)定遺傳代數(shù)的5個(gè)可選值：5、10、20、50、100。在Matlab程序中，將此變量定義為end_generation _number。

單親遺傳算法的基因重組操作主要有三種：基因換位、基因移位和基因倒位，已有文獻(xiàn)證明這三種基因重組操作之間是等價(jià)的，因此在車間布局問(wèn)題中，僅使用單點(diǎn)基因換位。染色體的基因換位是按一定的概率進(jìn)行的，綜合考慮計(jì)算效率和計(jì)算精度之后，根據(jù)經(jīng)驗(yàn)，設(shè)定基因換位概率的5個(gè)可選值為：0.1、0.3、0.5、0.7、0.9。在Matlab程序中，將此變量定義為transposition_rate，并使用transposition函數(shù)來(lái)實(shí)現(xiàn)染色體的單點(diǎn)基因換位操作。

%x是父代染色體，y是基因換位后的子代染色體。

由于車間布局問(wèn)題中不存在同序基因，即同序基因數(shù)gc=1，因此不存在基因突變現(xiàn)象。

車間布局問(wèn)題的選擇操作，采用的是父子競(jìng)爭(zhēng)選擇方式，即將父代的所有染色體和基因重組后的新染色體放在一起，根據(jù)種群規(guī)模，選取其中適應(yīng)度最高的那些染色體作為子代染色體。在Matlab程序中，對(duì)染色體按適應(yīng)度進(jìn)行排序后，再進(jìn)行選擇計(jì)算。

車間布局問(wèn)題的單親遺傳算法Matlab主函數(shù)被命名為lingang_pga，它是Matlab程序的主要部分，通過(guò)對(duì)各個(gè)子函數(shù)的調(diào)用以及對(duì)各個(gè)變量的運(yùn)算來(lái)實(shí)現(xiàn)單親遺傳算法并得到結(jié)果。子函數(shù)一共有3個(gè)，分別是產(chǎn)生初始種群的first_generation函數(shù)、實(shí)現(xiàn)單點(diǎn)換位操作的transposition函數(shù)和計(jì)算染色體適應(yīng)度的fit函數(shù)。變量一共有7個(gè)，分別是染色體長(zhǎng)度chromosome_size、種群規(guī)模population_ size、基因換位概率transposition_rate、遺傳終止代數(shù)end_generation_number、位置坐標(biāo)矩陣D、區(qū)域物流量矩陣f和確定區(qū)域矩陣g，其中確定區(qū)域矩陣g=［9，10，11，12，13，14，15］，它表示已經(jīng)確定位置的7個(gè)區(qū)域和位置9至位置15的對(duì)應(yīng)關(guān)系。子函數(shù)的具體內(nèi)容前文已經(jīng)給出，主函數(shù)的具體內(nèi)容如下：

%y是每代最優(yōu)結(jié)果的集合。

在車間布局問(wèn)題的單親遺傳算法中，有3個(gè)參數(shù)還未確定，分別是：種群規(guī)模，用M表示；基因換位概率，用P表示；遺傳代數(shù)，用N表示?？梢詫?個(gè)參數(shù)看作是3個(gè)因素，每個(gè)參數(shù)的5個(gè)可選值可以看作是5個(gè)水平，因此這個(gè)問(wèn)題可以轉(zhuǎn)化為一個(gè)多因素多水平的試驗(yàn)設(shè)計(jì)問(wèn)題。對(duì)于3因素5水平的試驗(yàn)，如果進(jìn)行全面試驗(yàn)需要進(jìn)行53=125次試驗(yàn)，而如果進(jìn)行正交試驗(yàn)，可以取6因素5水平正交表L25（56）的前3列，從而得到需要進(jìn)行25次試驗(yàn)，工作量減少80%。為了減小隨機(jī)誤差，每種參數(shù)組合計(jì)算5次并取平均值，試驗(yàn)結(jié)果如表2所示。

極差Rj表示各個(gè)因素對(duì)于試驗(yàn)結(jié)果的影響程度，Rj值越大說(shuō)明影響越大，由于R3＞R2＞R1，所以對(duì)于車間布局問(wèn)題的單親遺傳算法結(jié)果，影響最大的參數(shù)是遺傳代數(shù)N，其次是基因換位概率P，影響最小的是種群規(guī)模M。

對(duì)于車間布局問(wèn)題的單親遺傳算法而言，使得試驗(yàn)結(jié)果平均值越小的因素水平越好。由于K 11＞K 21＞K 31＞K 41＞K 51，所以種群規(guī)模M選擇水平5比較好，即最好的取值是M=16。由于K 12＞K 22＞K 32＞K42＞K52，所以基因換位概率P選擇水平5比較好，即最好的取值是P=0.9。由于K 13＞K23＞K 33＞K 43＞K53，所以遺傳代數(shù)N選擇水平5比較好，即最好的取值是N=100。

表2 正交試驗(yàn)結(jié)果統(tǒng)計(jì)表

計(jì)算后，得到的試驗(yàn)結(jié)果，如表3所示。

表3 正交試驗(yàn)結(jié)果分析表

分析正交試驗(yàn)結(jié)果后，最佳的參數(shù)組合是M= 16，P=0.9，N=100。將最佳參數(shù)組合代入Matlab程序運(yùn)行后得到結(jié)果：適應(yīng)度最高的染色體是32 576 841，總物流成本為3 764 400，收斂代數(shù)為13，計(jì)算時(shí)間為391.404 s，相對(duì)應(yīng)的臨港車間布局方案圖，如圖3所示。

圖3 計(jì)算所得的車間區(qū)域布置圖

5 結(jié) 語(yǔ)

車間布局問(wèn)題是企業(yè)在規(guī)劃和籌建時(shí)必須考慮的重要問(wèn)題，傳統(tǒng)的車間布局方法往往依賴經(jīng)驗(yàn)和各區(qū)域的相互關(guān)系，缺少定量的分析判斷。利用單親遺傳算法，不僅能夠自動(dòng)尋找最佳布置方案，而且操作簡(jiǎn)單、計(jì)算高效、通用性強(qiáng)。在解決車間布局問(wèn)題尤其是動(dòng)態(tài)布局中，單親遺傳算法將會(huì)有更廣闊的應(yīng)用前景。

［1］李茂軍，童調(diào)生，用單親遺傳算法求解有序組合優(yōu)化問(wèn)題［J］.系統(tǒng)工程與電子技術(shù)，1998，22（10）：58-61.

［2］Koopmans T C and Beckman M.Assignment problems and the location of economic activities［J］.Econometrica，1957，25：53-76.

簡(jiǎn)訊

中廣核電力被納入恒生指數(shù)

近日，據(jù)香港恒生指數(shù)有限公司2014年四季度報(bào)告顯示，中廣核電力（01816HK）已被納入恒生綜合中型股指數(shù)，并將于2015年3月9日起生效，納入該指數(shù)的原因，主要是得益于公司股票的發(fā)行規(guī)模和活躍的成交量。該指數(shù)是中廣核電力繼MSCI、富時(shí)指數(shù)后納入的第三個(gè)重要指數(shù)。

中廣核電力成為恒生綜合中型指數(shù)成份股后，將進(jìn)入港股通股票的交易范圍。加入港股通后，將進(jìn)一步提高中廣核在資本市場(chǎng)的聲譽(yù)，加深投資者對(duì)公司的了解和認(rèn)識(shí)，可以使境內(nèi)投資者直接投資中廣核電力股票，拓寬了中廣核的潛在投資者范圍。

摘自上海電氣電站設(shè)備有限公司電站輔機(jī)廠技術(shù)部《信息簡(jiǎn)訊》第196期

Study on the Workshop Layout Based on Partheno-genetic Alogorithm

TANG Yun1，2
（1.Shanghai Jiao Tong University，Shanghai 200240；2.Shanghai Electric Power Generation Equipment Co.，Ltd. Shanghai Auxiliary Plant，Shanghai 200090，China）

The workshop layout problem is mainly to decorating each product assembly area，which is related to the logistics cost and the output efficiency of production.The workshop layout problem can be abstracted into Quadratic Assignment Problem It belongs to the workshop class layout problem.It minimizes the sum of the logistics cost between these areas by assigning a given location for each product assembly area.Partheno-genetic algorithm and quadratic assignment are used to seek the suitable Population size，gene recombination probability and genetic algebra.The paper finds a satisfactory workshop layout by computer program and calculation.

workshop lagout；partheno-genetic alogorithm；logistics；cost；quadratic assignment model；program；orthogonal experiment；calculation

TH181

：A

1672-0210（2015）01-0035-05

2014-11-06

唐贇（1982-），男，本科，助理工程師，主要從事電站輔機(jī)的技術(shù)管理工作。