鄧 兵，林光春

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

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

鄧 兵，林光春

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

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

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

0 引言

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

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

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

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

1.1 問題描述

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

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

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

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

(1)

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

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

(2)

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

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

(3)

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

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

(4)

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

設(shè)備橫坐標(biāo)：

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

(5)

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

設(shè)備縱坐標(biāo)：

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í)，一臺(tái)設(shè)備只能出現(xiàn)一次：

(9)

2 改進(jìn)的SLP

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

圖2 改進(jìn)的SLP流程圖

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

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

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

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

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

3.1 編碼方式

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

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

(10)

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

3.2 初始種群

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

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

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

(11)

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

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

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

(12)

3.4 選擇算子

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

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

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

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

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

3.5 交叉算子

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

3.6 變異操作

4 計(jì)算實(shí)例

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

圖3 車間尺寸示意圖

表1 設(shè)備尺寸

(12)

(13)

(14)

本實(shí)例由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}

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

本文僅用此實(shí)例介紹上述方法進(jìn)行車間設(shè)備布局優(yōu)化的可行性和實(shí)用性，為描述簡(jiǎn)潔，△i都取0。其遺傳算法的運(yùn)行參數(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)

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

圖4 遺傳進(jìn)化過程圖

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

4 結(jié)論

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

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

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

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

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

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

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

[6] 吳鵬.MATLAB高效編程技巧與應(yīng)用：25個(gè)案例分析[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é)報(bào),2011,30(3)：75-78.

[10] 李晨,寧紅云.改進(jìn)的遺傳算法選擇算子[J].天津理工大學(xué)學(xué)報(bào),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

四川省科技計(jì)劃項(xiàng)目(2015FZ0005)

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

TH181；TG506

A