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

唐 贇

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

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

唐 贇1，2

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

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

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

0 概 述

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

1 課題來源

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

2 單親遺傳算法

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

圖1 單親遺傳算法流程圖

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

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

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

表1 車間區(qū)域表

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

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

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

圖2 車間區(qū)域圖

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

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

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

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

根據(jù)假設(shè)條件和二次分配模型，得到該重型車間數(shù)學(xué)模型的目標函數(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的距離。

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

以該重型車間的西南角為原點，東西方向為x軸，南北方向為y軸，可得各位置中心坐標的矩陣：

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

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

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

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

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

評價種群就是使用適應(yīng)度函數(shù)來計算各個染色體的適應(yīng)度，由于臨港車間布局問題的目標函數(shù)需要求出最小值，因此將適應(yīng)度函數(shù)定為目標函數(shù)的倒數(shù)。

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

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

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

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

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

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

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

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

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

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

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

對于車間布局問題的單親遺傳算法而言，使得試驗結(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 正交試驗結(jié)果統(tǒng)計表

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

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

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

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

5 結(jié) 語

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

［1］李茂軍，童調(diào)生，用單親遺傳算法求解有序組合優(yōu)化問題［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.

簡訊

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

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

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

摘自上海電氣電站設(shè)備有限公司電站輔機廠技術(shù)部《信息簡訊》第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-），男，本科，助理工程師，主要從事電站輔機的技術(shù)管理工作。