面向OEM企業(yè)設(shè)備多行布局問題的遺傳算法

周 娜，徐克林，朱 偉

ZHOU Na, XU Ke-lin, ZHU Wei

（同濟(jì)大學(xué) 機(jī)械工程學(xué)院，上海 201804）

面向OEM企業(yè)設(shè)備多行布局問題的遺傳算法

Genetic algorithm for multi-row layout oriented OEM enterprise

周 娜，徐克林，朱 偉

ZHOU Na, XU Ke-lin, ZHU Wei

（同濟(jì)大學(xué) 機(jī)械工程學(xué)院，上海 201804）

以物流成本為優(yōu)化目標(biāo)建立設(shè)備多行布局?jǐn)?shù)學(xué)模型，設(shè)計了相應(yīng)的遺傳算法優(yōu)化流程并建立了算法模型，研究了適合設(shè)備多行布局的編碼方式、遺傳操作和適應(yīng)度函數(shù)，通過Matlab編程對布局策略進(jìn)行遺傳運(yùn)算，最后，通過具體的實例分析，驗證了算法的收斂性、實用性和有效性。

物流成本；多行布局；遺傳算法；Matlab

0 引言

解決設(shè)備多行布局問題多用連續(xù)優(yōu)化方法，即設(shè)備在行內(nèi)是連續(xù)的，在行間是離散的。連續(xù)優(yōu)化方法研究較多的布局形式有：一是提前確定分行數(shù)，通常設(shè)分行數(shù)為兩行；二是設(shè)備自動換行。由于在布局前無法確定一個車間設(shè)備可分行的數(shù)量，所以事先確定分行數(shù)是不合李的，甚至可能導(dǎo)致最后的布局結(jié)果是非法布局方案，而自動換行技術(shù)成功的避免了非法解的產(chǎn)生。因此，本文采用自動換行布局策略。

1 問題假設(shè)與建模

1.1 問題假設(shè)

為了簡化計算，對多行設(shè)備做出如下簡化與假設(shè)：

1）所有設(shè)備和車間形狀均為矩形，忽略它們的細(xì)節(jié)形狀；

2）設(shè)備按同一方位布置，同一行設(shè)備的中心點位于一條水平線上；

3）零件加工順序同設(shè)備編號順序一致；

4）零件的工序加工時間都是確定的；

5）所有設(shè)備沿X軸方向依次排列。

1.2 問題的建模

目前，關(guān)于車間布局優(yōu)化的目標(biāo)越來越多，在最早最小化物流費用的基礎(chǔ)上，又提出了提高物料流和工藝流效率、空間利用率最大化等目標(biāo)。不難看出，最小物流費用仍然是車間布局問題評價的主要標(biāo)準(zhǔn)。因此，在對車間多行布局進(jìn)行研究時，車間物流費用最小化是研究者首要考慮的最重要原則。

假定某車間共有n臺設(shè)備，m種產(chǎn)品，車間物流成本的數(shù)學(xué)建模為：

其中：Qkij為產(chǎn)品從設(shè)備i到j(luò)的當(dāng)量物流量；dij為設(shè)備i到j(luò)必須保持的最小間距；?lij為設(shè)備i到j(luò)的 X軸方向上間距；?hij為設(shè)備i到j(luò)的 Y軸方向上間距； ?ij為設(shè)備i到j(luò)的 X軸方向上凈間距；xi,yi為設(shè)備i的坐標(biāo)；(xa,ya)，(xb,yb) 為包絡(luò)所有設(shè)備的最小矩形的左下角和右上角的坐標(biāo)；L,H為車間的長和高；li,hi為設(shè)備i的長和高；l0為第一行設(shè)備中心線距離X軸的距離；h為兩個相鄰行的中心距。

圖1 車間布局參量、決策變量和參考線

2 基于遺傳算法的目標(biāo)函數(shù)求解

由于車間多行布局問題屬于非線性規(guī)劃問題，而且約束條件較多，用一般的數(shù)學(xué)方法難以找到較多設(shè)備布局問題的最優(yōu)解，在1976年，Sahni和Gonzalez[1]己經(jīng)證明了設(shè)備布局問題屬于NP完全問題。遺傳算法（Genetic Algorithm,GA）在設(shè)備布局模型尋優(yōu)過程中受到越來越多的關(guān)注，對該類問題的求解則具有較為顯著的優(yōu)勢。遺傳算法的優(yōu)越性主要表現(xiàn)在搜索過程中不易陷入局部最優(yōu)，即使在所定義的適應(yīng)度函數(shù)不連續(xù)的情況下，也能以極大的概率找到最優(yōu)解[2]。因此，本文采用遺傳算法優(yōu)化設(shè)備多行布局。

圖2 遺傳算法優(yōu)化流程

2.1 染色體表達(dá)

自動換行布局策略的染色體只包含設(shè)備符號和凈間距兩個列表，如v=[{m1,m2,…,mn}，{?1,?2,…,?n}]。mi為設(shè)備i的符號；?i為設(shè)備i與相鄰設(shè)備i-1的凈間距。

2.2 罰函數(shù)和適應(yīng)度

本文建立的罰函數(shù)包括兩個方面：一是設(shè)備重疊；二是超出車間尺寸。由于凈間距的存在，設(shè)備在X方向上不會重疊，又有最大間距分行，在Y方向上也不會產(chǎn)生重疊；因為設(shè)備采用自動分行技術(shù)，所以在X方向上設(shè)備不會超出車間，只需要約束設(shè)備在Y方向上不要超出車間尺寸即可：

根據(jù)代價極小化與利益極大化的對偶原則，適應(yīng)度函數(shù)可以采取目標(biāo)函數(shù)值的倒數(shù)的策略來實現(xiàn)：

其中，β為懲罰值，一般取較大的正數(shù)；Fk為第k個染色體代表的布局成本；λ為在Y方向上超過車間尺寸的罰函數(shù)。

2.3 選擇操作

輪盤賭選擇，是一種經(jīng)典的GA選擇方法[3]。依次計算種群中所有個體的適應(yīng)度的總和，再計算每個個體的適應(yīng)度值所占比例，以此作為選擇的概率。適應(yīng)度值越高的個體被選中的概率越大。因此，本文選用輪盤賭的選擇方法。

2.4 交叉操作

通過比較多種交叉方法特點，并結(jié)合車間多行布局編碼形式特點，本文對設(shè)備編碼部分采用單點交叉方式，針對凈間距編碼部分采用算術(shù)交叉方式。

單點交叉是指在相互配對的兩個個體中隨機(jī)設(shè)置一個交叉點，交換個體在所設(shè)定的交叉點的部分基因。

交叉算術(shù)是指由兩個個體的線性組合而產(chǎn)生的兩個新的個體。假設(shè)車間兩個父代個體的凈間距序列：

則子代個體的凈間距為：

α=1-0.9r

式中，r為進(jìn)化代數(shù)。

2.5 變異操作

設(shè)備排序編碼部分采用互換式變異操作方式；設(shè)備凈間距部分，結(jié)合各種變異操作的特點和凈間距序列染色體的特點，本文采用鄰域搜索技術(shù)對機(jī)器位置進(jìn)行細(xì)微的調(diào)整。變異操作過程如下：

假如選定的設(shè)備凈間距為：?1,?2,…,?i,…,?n}，選擇非零基因?i進(jìn)行變異，令φ是一個給定的整數(shù)（局部尋優(yōu)次數(shù)），則可以得到2φ個凈間距。

評估所有鄰域染色體，保留適應(yīng)度值最高的染色體。

3 應(yīng)用研究

B車間主要負(fù)責(zé)面膜的灌裝，采用半自動流水作業(yè)方式。車間長12m，寬12m。車間各工位的主要參數(shù)如表1所示。

因為，只有工位1和2、5和6、9和10在X軸和Y軸方向上均需要保持1m的最小間距，其余各工位物流間距為零。因此，只需計算工位1和2、5和6、9和10間的當(dāng)量物流量和物流頻率即可（如表2所示）。

表1 不同工位尺寸

表2 當(dāng)量物流量/物流頻率

由于當(dāng)量物流量已充分考慮了不同工位間產(chǎn)品搬運(yùn)的難易問題，所以設(shè)所有工位間搬運(yùn)費用均為0.02 元/m。

GA初始參數(shù)的設(shè)置：pop_size=50，Maxgen=500，Pm=0.6，Pc=0.1，β=500。

在Matlab 7.8.0版本上30次運(yùn)行后，其中24次得到問題的最有解，6次得到問題的次優(yōu)解。問題最優(yōu)解在148代開始收斂（如圖3所示），設(shè)凈間距保留兩位有效數(shù)字，多行布局的最優(yōu)解是：{{1 2 3 4 5 8 7 6 9 10}，{0.38 0.40 0.00 0.45 0.25 0.03 0.17 0.25 0.06 0.03}}，設(shè)備共分成3行，第一行：{1 2 3 4 5}，第二行：{8 7 6},第三行：{9 10}。

圖3 基于目標(biāo)函數(shù)的染色體收斂曲線

4 結(jié)論

本文研究了面向OEM企業(yè)車間多行布局的遺傳算法，在染色體表達(dá)上采用自動換行技術(shù)，克服了提前設(shè)定分行數(shù)易產(chǎn)生非法解的缺點。在算法中，根據(jù)車間多行布局的特點，精心設(shè)計了染色體編碼方式、遺傳操作及其適應(yīng)度函數(shù)。最后，通過實例分析，驗證了算法的收斂性、實用性和有效性。本文模型及算法可以為車間進(jìn)行多行布局提供指導(dǎo)。

[1] Sahni S,Gonzalez T.P-complete approximation Problem[J].Journal of Association for Computer Maehiniary.1976,23,(3):555-565.

[2] 陳希,王寧生.基于遺傳算法的車間設(shè)備虛擬布局優(yōu)化技術(shù)研究[J].東南大學(xué)學(xué)報(自然科學(xué)版).2004.9:34(5),627-631.

[3] 馬少平,朱小燕.人工智能.北京:清華大學(xué)出版社,2004.

TH166

A

1009-0134(2010)11(下)-0052-02

10.3969/j.issn.1009-0134.2010.11(下).20

2010-08-20

國家自然科學(xué)基金資助項目 (71071115)

周娜（1979 -），女， 博士研究生，主要從事生產(chǎn)系統(tǒng)優(yōu)化方面的研究工作。