改進SLP和遺傳算法結(jié)合的車間設(shè)備布局優(yōu)化*

鄧 兵，林光春

(四川大學(xué) 制造科學(xué)與工程學(xué)院，成都 610065)

改進SLP和遺傳算法結(jié)合的車間設(shè)備布局優(yōu)化*

鄧 兵，林光春

(四川大學(xué) 制造科學(xué)與工程學(xué)院，成都 610065)

針對加工多種類產(chǎn)品，且具有固定入口和出口的生產(chǎn)車間，運用改進的SLP和遺傳算法相結(jié)合的方法進行車間設(shè)備布局的優(yōu)化，從而減少人員、物料的移動成本，提高車間利用率和企業(yè)的核心競爭力。首先，在對生產(chǎn)車間的物流進行詳細分析的基礎(chǔ)上，利用改進的SLP理論確定生產(chǎn)車間設(shè)備布局的初步方案。然后，把SLP形成的初步方案作為遺傳算法的初始種群的部分染色體，利用改進的遺傳算法實現(xiàn)對案例車間設(shè)備布局的優(yōu)化。運用改進的SLP和遺傳算法相結(jié)合的方法進行車間設(shè)備布局的優(yōu)化，彌補了SLP過于依賴經(jīng)驗、約束過多的缺點，同時，提高了遺傳算法的選優(yōu)能力，減少了隨機性所引起的誤差，在選出最好個體的同時保證了種群的多樣性，使最終的布局方案更具實用價值。

車間設(shè)備布局；系統(tǒng)布置設(shè)計；遺傳算法；優(yōu)化

0 引言

強化物流管理是提升企業(yè)核心競爭力的有效途徑。隨著對生產(chǎn)加工過程的深入研究，發(fā)現(xiàn)在整個生產(chǎn)加工過程中，物料的搬運、存儲等非加工環(huán)節(jié)花費費用和占用時間的比例都很大。而一個優(yōu)秀的物流運輸系統(tǒng)在工廠的費用方面至少可以減少10%～30%[1-2]。因此，好的車間設(shè)備布局對企業(yè)生產(chǎn)運轉(zhuǎn)、生產(chǎn)成本是至關(guān)重要的。

目前，針對車間設(shè)備布局優(yōu)化問題有兩大主流方法——傳統(tǒng)的系統(tǒng)布置設(shè)計方法(Systematic layout planning,簡稱SLP)[3]和遺傳算法[4-5]。SLP構(gòu)建車間設(shè)備布局，其布局方案易受設(shè)計人員主觀經(jīng)驗的影響。同樣，遺傳算法的初始種群的選擇會直接影響算法的尋優(yōu)能力，且算法的局部搜索能力較差。

本文針對加工多種類產(chǎn)品，且具有固定入口和出口的車間布局問題，提出一種改進的SLP和遺傳算法結(jié)合的方法。首先，對SLP進行改進，簡化SLP的設(shè)計流程，并改進SLP的輸入因素。在對車間物流情況進行詳細分析的基礎(chǔ)上，依據(jù)改進的SLP構(gòu)建車間設(shè)備布局的初步方案。然后，將SLP得到的初始方案作為初始種群的部分染色體，同時對遺傳算子進行改進，以避免發(fā)生早熟。依據(jù)改進的遺傳算法求解車間設(shè)備布局的最終方案。這樣，將改進的SLP得到的初步方案融入到遺傳算法中，實現(xiàn)了二者的優(yōu)勢互補。同時，考慮到了車間加工產(chǎn)品的多樣性以及車間固定入口和出口的限制，使運用此法得到的車間設(shè)備布局結(jié)果更具實用性。

1 車間設(shè)備布局的數(shù)學(xué)模型

1.1 問題描述

布局的實質(zhì)是確定車間內(nèi)設(shè)備的位置，使物流成本最小化。本文將設(shè)備布局問題視為連續(xù)優(yōu)化的多行設(shè)備布局。布局遵循以下原則：已知車間入口和出口的位置；忽略車間和設(shè)備的細節(jié)形狀，將其視為矩形結(jié)構(gòu)，且已知車間的面積；各設(shè)備按行排列，且與車間的長度方向(X軸)平行；設(shè)備間的橫向(X軸)和縱向(Y軸)間距要求已知。這樣，車間設(shè)備布局問題就簡化為滿足約束條件的多行設(shè)備布局問題。其參數(shù)、決策變量、參考線和坐標系的建立如圖1所示。

圖1 參數(shù)、決策變量、參考線示意圖

1.2 數(shù)學(xué)模型

基于上述對問題的分析，車間設(shè)備布局的目標是滿足總的物流成本最小化。傳統(tǒng)的目標函數(shù)表達式為[6]：

(1)

其中，C為物流運輸?shù)目傎M用，n為設(shè)備臺數(shù)，Pij為設(shè)備i和j之間的單位物料每單位距離的搬運費用，Qij為設(shè)備i和j之間的物料搬運頻率，Dij為設(shè)備i和j之間的矩形距離。

上述目標函數(shù)僅考慮設(shè)備間的單位物料每單位距離的搬運費用。對于加工多種類產(chǎn)品的生產(chǎn)車間，不同產(chǎn)品的運輸難易程度不同會導(dǎo)致搬運費用不同。針對加工多種類產(chǎn)品的生產(chǎn)車間，目標函數(shù)采用加權(quán)運輸量與運輸距離的乘積之和。其中，加權(quán)運輸量是運輸量與運輸難易程度權(quán)數(shù)的乘積。將產(chǎn)品運輸費用融入到運輸量中，解決了由于不同產(chǎn)品運輸費用不同的困擾。其目標函數(shù)可表達為：

(2)

其中，fij為設(shè)備i和j之間的月加權(quán)運輸量，dij為設(shè)備i和j之間的矩形距離。

設(shè)備間距表達式：

(3)

其中，xi為設(shè)備i的中心的x坐標，yi為設(shè)備i的中心的y坐標。

加權(quán)月運輸量表達式：

(4)

其中，u為車間加工產(chǎn)品的種類數(shù)量，Q為同類產(chǎn)品的預(yù)計月產(chǎn)量，q為同類產(chǎn)品的單次運輸量，w為運輸難易程度不同導(dǎo)致的運輸成本權(quán)數(shù)。

設(shè)備橫坐標：

xi=xk+(li+lk)/2+hik+Δi

(5)

其中，li為設(shè)備i的長度，hij為設(shè)備i和j之間的最小橫向間距要求，hi0為設(shè)備i和車間邊界的最小橫向間距要求，△i為設(shè)備i和i-1(或邊界)之間的凈間距。

設(shè)備縱坐標：

yi=(k-1)s+s0如果zik=1,i=1,2,…,n;k=1,2,…,m

(6)

同一行設(shè)備不重疊約束條件：

(7)

其中，s為設(shè)備行間距，s0為第一行設(shè)備與車間邊界的間距，m為車間設(shè)備布局的總行數(shù)。

其中：

(8)

同時，一臺設(shè)備只能出現(xiàn)一次：

(9)

2 改進的SLP

本文提出的改進的SLP[7-8]方法是基于物流成本最低這一目標實現(xiàn)的。它適用于加工多種類產(chǎn)品，且具有固定的物流入口和出口的布局問題。該方法是基于SLP的基本思路，利用改進的工具對輸入因素加以分析，從產(chǎn)品的運輸難易程度、物流量和物流強度三個方面對設(shè)備間的接近關(guān)聯(lián)程度加以定義和計算，從而得到設(shè)備相互關(guān)聯(lián)表，根據(jù)關(guān)聯(lián)程度由高到低的順序構(gòu)建車間設(shè)備布局方案。具體操作流程如圖2所示。

圖2 改進的SLP流程圖

(1)多產(chǎn)品的PQ分析。首先對產(chǎn)品進行分析，劃分產(chǎn)品大類；其次收集數(shù)據(jù)，包括預(yù)測產(chǎn)量和各類產(chǎn)品單次運輸量；最后運輸難易程度會影響運輸成本，因此對各產(chǎn)品大類運輸難易程度進行評估，將其賦予不同的權(quán)重。

(2)設(shè)備間的物流量分析。將車間的入口和出口作為兩臺虛擬的設(shè)備，進行物流分析時以入口作為起點，出口作為終點。根據(jù)PQ分析所得數(shù)據(jù)進行設(shè)備間加權(quán)月運輸量的計算，并繪制設(shè)備間月加權(quán)運輸量從至表。

(3)根據(jù)各設(shè)備尺寸、設(shè)備間的間距要求和車間可用面積，將車間進行柵格劃分的處理，并標注入口和出口的位置。

(4)依據(jù)啟發(fā)式規(guī)則對設(shè)備進行排列，得到初步的車間設(shè)備布置方案。

3 結(jié)合SLP的改進遺傳算法

3.1 編碼方式

對于多行設(shè)備的布局采用自動換行策略，即同一行內(nèi)的各設(shè)備長度與實際間距之和超過最大空間長度時，本行最后一臺設(shè)備自動換行[9]。其編碼表達采用設(shè)備符號和凈間距兩個列表的擴展換位表達式：

[{m1,m2,…mn}，{△1,△2…△n}]

(10)

其中，n代表設(shè)備臺數(shù)，mi代表第i個位置的設(shè)備，△i代表設(shè)備i-1和設(shè)備i之間的凈間距。

3.2 初始種群

初始種群的分布狀態(tài)直接關(guān)系到遺傳算法的全局收斂性與搜索效率。為了加快遺傳算法的收斂速度，采用隨機產(chǎn)生與特定代換相結(jié)合的方式產(chǎn)生初始種群，即用SLP得到的設(shè)備排列方式代替隨機產(chǎn)生的初始種群的部分染色體的設(shè)備排列方式。其次，為了簡化目標函數(shù)，在構(gòu)建目標函數(shù)表達式時，沒有考慮車間的入口和出口的位置。因此，需對染色體中設(shè)備排列方式進行調(diào)整，直接固定與車間入口和出口臨近的設(shè)備序列號。即根據(jù)SLP計算的設(shè)備間加權(quán)月運輸量，調(diào)整染色體中設(shè)備的序列號。使與入口鄰近的是設(shè)備與入口之間的月加權(quán)運輸量最大的設(shè)備，與出口鄰近的是設(shè)備與出口之間的月加權(quán)運輸量最大的設(shè)備。

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

采用自動換行策略，則在X方向不會發(fā)生設(shè)備超出車間區(qū)域的情形。因此，只需判斷最后一行設(shè)備在Y方向是否超出車間區(qū)域。

(11)

其中，Pk為不合理懲罰項，H為車間寬度，T為正的大數(shù)懲罰值。

根據(jù)適應(yīng)度函數(shù)的特點，將目標函數(shù)和不合理懲罰項用一個函數(shù)實現(xiàn)，減少重復(fù)計算。對于染色體Vk的適應(yīng)度函數(shù)定義為：

fit(Vk)=1/(C+(T×(m-1)×s+s0)>H)

(12)

3.4 選擇算子

經(jīng)典遺傳算法中采用較多的是輪盤賭選擇算子。為了提高算子的選優(yōu)能力和減少了隨機性所引起的誤差，采用改進的無放回的基于排序的多輪輪盤賭選擇算子[10]，它在選出最好個體的同時能保證種群的多樣性。該選擇算子的具體執(zhí)行過程如下：

(1)設(shè)種群大小為M，將所有個體按其適應(yīng)度值由大到小進行排序。

(2)根據(jù)個體被選取的概率將[0,1]劃分為M個區(qū)間。

(3)進行多輪輪盤賭選擇，產(chǎn)生M個[0,1]之間的均勻隨機數(shù)，統(tǒng)計落入各區(qū)間的數(shù)值個數(shù)，取最大個數(shù)所在區(qū)間對應(yīng)的個體為本輪所選中的個體，若多個區(qū)間落入數(shù)值個數(shù)相等，取適應(yīng)度最大的的個體為本輪所選中的個體。用此方式選出M個個體作為子代種群。

(4)計算子代種群個體的適應(yīng)度值，用父代種群適應(yīng)度值最大的個體代替子代種群適應(yīng)度值最小的個體。存儲所有新選出來的個體作為新的子代種群。

3.5 交叉算子

用部分映射交叉方法處理染色體中設(shè)備排列序列的交叉操作，用算術(shù)交叉方法處理染色體中設(shè)備凈間距的交叉操作。在對染色體中設(shè)備排列序列進行交叉操作后，需再次調(diào)整設(shè)備序列號的排列方式。使與入口鄰近的是設(shè)備與入口之間的月加權(quán)運輸量最大的設(shè)備，與出口鄰近的是設(shè)備與出口之間的月加權(quán)運輸量最大的設(shè)備。

3.6 變異操作

4 計算實例

本文給出的實例車間為19m×18m的矩形固定車間。出口和入口均布置在車間的同一寬度方向，入口中心到車間下邊界的距離為3m，出口中心到入口中心的距離為8m。車間共有16臺設(shè)備。其中，編號1、2、3，7、8，10、11，13、14、15分別為同一型號設(shè)備。第一行設(shè)備到車間下邊界的距離s0為3m，設(shè)備行間距s為4m。車間示意圖如圖3所示，各設(shè)備大小如表1所示，加權(quán)運輸量矩陣[fij]、設(shè)備間水平最小間距要求矩陣[hij]以及各設(shè)備和車間邊界的最小水平間距[hi0]分別如式(13)～式(15)所示。

圖3 車間尺寸示意圖

表1 設(shè)備尺寸

(12)

(13)

(14)

本實例由SLP方法構(gòu)建的三組車間設(shè)備布局方案均為4×4的排列方式，其設(shè)備排列方式如下：

{1 2 13 6 3 15 14 16 9 8 7 4 12 11 15 5}

{1 3 6 4 2 14 13 5 9 15 16 10 12 8 7 11}

{1 2 3 5 15 14 13 4 9 8 16 6 12 7 11 10}

其中，運用啟發(fā)式方法對設(shè)備進行排列時，同一型號的編號為1,2,3的設(shè)備應(yīng)與入口鄰近，選擇編號為1的設(shè)備與入口相鄰，編號為9的設(shè)備與出口相鄰。

本文僅用此實例介紹上述方法進行車間設(shè)備布局優(yōu)化的可行性和實用性，為描述簡潔，△i都取0。其遺傳算法的運行參數(shù)：種群數(shù)量100，終止代數(shù)500，交叉概率0.65，變異概率0.01，正的大數(shù)懲罰值500，Umin為0，Umax為0。

最后，得到的最好染色體為[{1 15 3 2 14 13 10 5 9 2 12 16 11 4 8 7},{0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0}]。

第一行設(shè)備：1(3.2，3)、15(7.2，3)、3(11.2，3)、2(14.7，3)

第二行設(shè)備：14(2.9，7)、13(6.6，7)、10(10.2，7)、5(14.2，7)

第三行設(shè)備：9(3.3，11)、2(7.2，11)、12(11.4，11)、16(15.5，11)

第四行設(shè)備：11(3.8，15)、4(7.8，15)、8(11.3，15) 、7(15.3，15)

其遺傳進化過程如圖4所示，車間設(shè)備布局優(yōu)化結(jié)果如圖5所示。

圖4 遺傳進化過程圖

圖5 車間設(shè)備布局優(yōu)化結(jié)果圖

4 結(jié)論

(1)利用改進的SLP和遺傳算法相結(jié)合的方式，對車間設(shè)備布局進行優(yōu)化。采用改進的SLP方法減少了人的經(jīng)驗判斷對初步的車間設(shè)備布局方案的影響。同時，將得到的初步方案作為遺傳算法的部分初始種群，提高了遺傳算法的搜索效率。

(2)對多行設(shè)備布局模型的改進，該模型是基于使綜合物流成本最低這一目標實現(xiàn)的。適用于加工多種類產(chǎn)品的生產(chǎn)車間。

(3)對選擇算子的改進。改進的選擇算子提高提高了選優(yōu)能力，減少了隨機性所引起的誤差，在選出最好個體的同時能保證種群的多樣性。

[1] 楊國俊,陳健,孫思蒙,等. 基于遺傳算法的車間布局優(yōu)化研究[J]. 機械研究與應(yīng)用,2016(1)：12-14.

[2] 徐立云,楊守銀,李愛平,等. 生產(chǎn)車間布局多目標優(yōu)化及其仿真分析[J]. 機械設(shè)計與研究,2011(6)：55-59.

[3] 葉連發(fā),劉勝,包北方. SLP在H公司柴油機零配件生產(chǎn)車間布局優(yōu)化中的應(yīng)用研究[J]. 現(xiàn)代管理技術(shù),2012(5)：24-28.[4] 張屹,盧超,張虎,等. 基于差分元胞多目標遺傳算法的車間布局優(yōu)化[J]. 計算機集成制造系統(tǒng),2013,19(4)：727-734.

[5] 張志海,張岱峰. 基于遺傳算法的氰酸酯樹脂生產(chǎn)車間布局優(yōu)化研究[J]. 山東交通學(xué)院學(xué)報,3011,19(3):80-83.

[6] 吳鵬.MATLAB高效編程技巧與應(yīng)用：25個案例分析[M].北京:北京航空航天大學(xué)出版社,2010.

[7] 羅軍榮,史烽,肖吉軍,等.SLP技術(shù)在制造車間布局中的應(yīng)用研究[J].企業(yè)科技與發(fā)展，2011(22)：11-14.

[8] 樊雪梅,王龍昭. SLP方法在糧食物流中心內(nèi)部規(guī)劃布局中的應(yīng)用[J]. 物流技術(shù)，2012,31(7)：354-356.

[9] 魏軍凱,吳芳,戚峰. 基于遺傳算法求解車間設(shè)備布局優(yōu)化問題[J]. 蘭州交通大學(xué)學(xué)報,2011,30(3)：75-78.

[10] 李晨,寧紅云.改進的遺傳算法選擇算子[J].天津理工大學(xué)學(xué)報,2008,24(6):1-4.

(編輯 李秀敏)

Workshop Facility Layout Optimization by Using Improved SLP and Genetic Algorithm

DENG Bing, LIN Guang-chun

(School of Manufacturing Science and Engineering, Sichuan University, Chengdu 610065, China)

The workshop manufactures multiple types of products, and has fixed entrance and exit. The paper uses the combination of improved SLP and genetic algorithm to optimize the layout of workshop facility, which reduces the cost of move of employee and product, improves the utilization of workshop and enterprise's core competitiveness. Firstly, according to the logistics analysis of the workshop, we use the improved SLP to determine the preliminary scheme of the layout of workshop facility. Then, we take the preliminary scheme as part of the initial population of chromosomes of genetic algorithm, and use improved genetic algorithm to calculate optimal facility layout scheme of case workshop. Using the improved SLP and the genetic algorithm to optimize the layout of workshop facility, we make up for the shortcomings of rely on experience and have a lot of constraints, improve the ability of the selection of genetic algorithm, reduce the error caused by random, ensure the diversity of population, and make the final layout plan more practical value.

workshop facility layout; systematic layout planning; genetic algorithm; optimization

1001-2265(2017)08-0148-04

10.13462/j.cnki.mmtamt.2017.08.039

2016-10-14；

2016-11-13

四川省科技計劃項目(2015FZ0005)

鄧兵(1991—)，男，四川綿陽人，四川大學(xué)碩士研究生，研究方向為機構(gòu)學(xué)及工業(yè)機器人， (E-mail)1501848963@qq.com。

TH181；TG506

A