SLP和遺傳算法相結(jié)合的車(chē)間布局研究

冷護(hù)基

摘要：針對(duì)多個(gè)加工區(qū)域的車(chē)間布局問(wèn)題，文章利用SLP得到的4個(gè)初步優(yōu)化布局方案作為遺傳算法初始種群的一部分，將兩種方法結(jié)合起來(lái)，既避免了SLP設(shè)計(jì)時(shí)的主觀性影響，又提高了遺傳算法的搜索效率與準(zhǔn)確性。通過(guò)實(shí)例驗(yàn)證了該方法的有效性，為車(chē)間布局規(guī)劃人員提供參考價(jià)值。

Abstract： For the layout problem of multiple processing areas， the article uses the four preliminary optimization layout schemes obtained by SLP as part of the initial population of the genetic algorithm. The two methods are combined to avoid the subjective influence of SLP design and improve the subjectivity. Search efficiency and accuracy of genetic algorithms. The effectiveness of the method is verified by an example， which provides reference value for workshop layout planners.

關(guān)鍵詞：車(chē)間布局;SLP;遺傳算法

Key words： shop layout;SLP;genetic algorithm

中圖分類(lèi)號(hào)：TB491? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文章編號(hào)：1006-4311（2019）16-0063-04

0? 引言

據(jù)相關(guān)研究表明，車(chē)間內(nèi)僅有不到20%的時(shí)間用于產(chǎn)品的加工制造，在生產(chǎn)過(guò)程中物料搬運(yùn)的時(shí)間超過(guò)整個(gè)生產(chǎn)時(shí)間的35%，其帶來(lái)的物料搬運(yùn)成本在總的經(jīng)營(yíng)費(fèi)用中占比高達(dá)30%-55%[1]。通過(guò)設(shè)計(jì)出高效優(yōu)秀的車(chē)間布局能大幅度縮短物料搬運(yùn)距離，有效降低綜合生產(chǎn)費(fèi)用。由于車(chē)間布局問(wèn)題一般為非線性并且有NP難的特點(diǎn)，一般采用遺傳算法等啟發(fā)式算法對(duì)所建立的符合車(chē)間實(shí)際需求的數(shù)學(xué)模型進(jìn)行求解[2]。

1? 車(chē)間布局問(wèn)題的數(shù)學(xué)模型

1.1 模型假設(shè)

本文研究的是面積不等的車(chē)間多行布局連續(xù)優(yōu)化問(wèn)題，確定各作業(yè)區(qū)域的位置是側(cè)重點(diǎn)，現(xiàn)對(duì)布局的數(shù)學(xué)模型做出如下假設(shè)：

①所有作業(yè)區(qū)域均是邊長(zhǎng)已知的矩形，忽略形狀細(xì)節(jié);②區(qū)域之間按照與X軸保持水平方向排列，且同一行區(qū)域中心Y坐標(biāo)相同;③區(qū)域之間的搬運(yùn)方式按X軸水平方向或者Y軸垂直方向的路線移動(dòng)。

根據(jù)以上假設(shè)，數(shù)學(xué)模型可以描述為：在有限車(chē)間面積內(nèi)，滿足約束條件的情況下，求物料搬運(yùn)總量最小的車(chē)間布局。

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

根據(jù)以上描述，建立車(chē)間布局?jǐn)?shù)學(xué)模型如圖1所示。其中（0，0）為車(chē)間墻角坐標(biāo);L、W分別表示車(chē)間的長(zhǎng)度和寬度;mi、mj、mk分別表示作業(yè)區(qū)域i、j、k;（xi，yi）代表作業(yè)區(qū)域i的中心坐標(biāo);lk表示作業(yè)區(qū)域k的長(zhǎng)度;hj表示作業(yè)區(qū)域j的寬度;Δk表示作業(yè)區(qū)域j與k間的凈距離;ui0表示作業(yè)區(qū)域i和邊界水平最小要求距離;如ujk表示作業(yè)區(qū)域j與k間最小要求距離;v 表示相鄰兩行作業(yè)區(qū)域中心的行間距;v0表示首行作業(yè)區(qū)域中心到車(chē)間下邊界的距離。

2? SLP與遺傳算法相結(jié)合

2.1 方法概述

Muther設(shè)計(jì)的SLP方法，分析布局問(wèn)題從五個(gè)基本要素：產(chǎn)品（P）、產(chǎn)量（Q）、工藝路線（R）、輔助設(shè)施（S）、時(shí)間（T）入手，進(jìn)行物流與非物流關(guān)系的綜合分析，繪制位置相關(guān)圖并在修正因素下得出若干個(gè)可行方案[3]。SLP不足之處在于受設(shè)計(jì)人員主觀看法與經(jīng)驗(yàn)因素影響較大，難以得到最優(yōu)解[4]。遺傳算法（GA）是一種模仿自然生物遺傳進(jìn)化的智能搜索計(jì)算機(jī)輔助技術(shù)方法，它可以通過(guò)對(duì)染色體即問(wèn)題的解進(jìn)行不斷地選擇、交叉和變異，最終獲得最優(yōu)解[5]。GA計(jì)算過(guò)程中容易發(fā)生早熟、搜索效率差的問(wèn)題，這些跟初始種群的選擇有關(guān)[6]。本文針對(duì)上述兩種方法的不足，通過(guò)SLP得出的布局方案作為較優(yōu)染色體成為GA初始種群的一部分，可以提高GA的搜索效率和準(zhǔn)確性，通過(guò)將兩種方法結(jié)合起來(lái)彌補(bǔ)了雙方的缺點(diǎn)，能更有效地得出最佳車(chē)間布局方案。

2.2 具體步驟

2.2.1 選擇編碼方式

車(chē)間的布局問(wèn)題重點(diǎn)是布置作業(yè)區(qū)域之間的相對(duì)位置[7]。編碼方式表示為將區(qū)域符號(hào)和凈間距這兩個(gè)變量作為兩個(gè)擴(kuò)展換位：[{m1，m2，…，mn}，{Δ1，Δ2，…，Δn}]，其中mi代表作業(yè)區(qū)域i;Δk表示相鄰兩個(gè)作業(yè)區(qū)域k與k-1之間的凈間距。采用自動(dòng)換行策略即：同行中各作業(yè)區(qū)域的長(zhǎng)度之和大于車(chē)間的長(zhǎng)度，本行最后一個(gè)作業(yè)區(qū)域自動(dòng)切換到下一行的首個(gè)位置進(jìn)行排列[8]。

2.2.2 初始種群的設(shè)定

初始種群數(shù)目太小可能會(huì)收斂過(guò)早，太大則會(huì)影響運(yùn)算時(shí)間降低效率[9]。為了加快遺傳算法的收斂速度并且提高搜索的準(zhǔn)確性，采用隨機(jī)產(chǎn)生和SLP方法得到的4個(gè)改進(jìn)方案相結(jié)合的方式得到初始種群。

2.2.3 適應(yīng)度和懲罰項(xiàng)的設(shè)定

2.2.4 選擇方式

2.2.5 交叉、變異操作

3? 實(shí)例研究

H公司是一家專(zhuān)業(yè)從事各類(lèi)冶金機(jī)械刃模具生產(chǎn)與加工的企業(yè)，本文針對(duì)該公司刀具生產(chǎn)車(chē)間進(jìn)行布局優(yōu)化。該車(chē)間是一個(gè)尺寸為80m×60m的矩形，共有16個(gè)不同的功能區(qū)域，各自占地尺寸如表1所示;第一行區(qū)域到下邊界距離v0為8m，區(qū)域行間距v為15m，區(qū)域間最小間距u0均為為3m，區(qū)域間凈距離取值范圍Δ定為[0，3]，區(qū)域與車(chē)間邊界最小間距u均為2m。區(qū)域間的物流量F如式（11）所示。

4? 結(jié)語(yǔ)

將SLP和遺傳算法相結(jié)合，減少了SLP方法的人為主觀因素在設(shè)計(jì)車(chē)間布局時(shí)帶來(lái)的影響，將SLP初步優(yōu)化方案作為遺傳算法初始種群一部分有效地提高了算法的搜索效率與準(zhǔn)確性。自動(dòng)換行策略和懲罰項(xiàng)的引入解決了車(chē)間布局設(shè)計(jì)中超出車(chē)間范圍的問(wèn)題，針對(duì)交叉算子和變異算子的設(shè)計(jì)增強(qiáng)了算法的種群多樣性和局部搜索能力，使之快速向最優(yōu)解靠攏，避免大量的計(jì)算。

參考文獻(xiàn)：

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

[2]羅東東.基于SLP和遺傳算法的廠區(qū)平面布置設(shè)計(jì)及優(yōu)化[D].長(zhǎng)春：長(zhǎng)春工業(yè)大學(xué)，2015.

[3]趙濤，趙雙記，林濤.淺析SLP法在企業(yè)設(shè)施布局的應(yīng)用[J].價(jià)值工程，2012，31（6）：30.

[4]甘衛(wèi)華，徐綦鶴，黃雯，謝冬蓮.基于SLP和生產(chǎn)物流的F公司車(chē)間設(shè)施布局改善[J].華東交通大學(xué)學(xué)報(bào)，2015，32（3）：55-62，102.

[5]Dhamodharan Raman，Sev V. Nagalingam，Bruce W. Gurd. A genetic algorithm and queuing theory based methodology for facilities layout problem[J].International Journal of Production Research，2009，47（20）：455-460.

[6]Karina Hauser，Chen H. Chung. Genetic algorithms for layout optimization in crossdocking operations of a manufacturing plant[J].International Journal of Production Research，2006，44（21）：145-147.

[7]邱勝海，陳曙鼎，王云霞，賈曉林.遺傳算法在車(chē)間設(shè)施布局優(yōu)化中的應(yīng)用[J].機(jī)械設(shè)計(jì)與制造工程，2017，46（2）：80-83.

[8]于瑞峰，王永縣，彭海.工作地中設(shè)施布局問(wèn)題的改進(jìn)遺傳算法[J].清華大學(xué)學(xué)報(bào)（自然科學(xué)版），2003（10）：1351-1354.

[9]Serkan Altuntas. A fuzzy DEMATEL-based solution approach for facility layout problem： a case study[J]. The International Journal of Advanced Manufacturing Technology，2014，73（8）：67-68.

[10]包子陽(yáng)，余繼周.智能優(yōu)化算法及其MATLAB實(shí)例[M].北京：電子工業(yè)出版社，2016.