管賢平

（江蘇大學(xué) 現(xiàn)代農(nóng)業(yè)裝備與技術(shù)省部共建教育部重點(diǎn)實(shí)驗(yàn)室，鎮(zhèn)江 212013）

0 引言

隨著市場(chǎng)需求的多樣化和個(gè)性化，能以較低成本快速響應(yīng)市場(chǎng)需求的可重構(gòu)制造系統(tǒng)（RMS）得到廣泛關(guān)注[1]。布局設(shè)計(jì)問題是已知負(fù)載流量，根據(jù)給定系統(tǒng)可能的分布位置，確定各個(gè)工作站在車間的位置分布，以使得總物流成本最小化[2]。在可重構(gòu)制造環(huán)境下，需要快速改變系統(tǒng)的構(gòu)形，以適應(yīng)不斷變化的生產(chǎn)需求，對(duì)布局問題的求解時(shí)間和求解質(zhì)量提出很高的要求。Meng等[3]提出可重構(gòu)布局問題。本文針對(duì)基于AGV的RMS的布局設(shè)計(jì)要求，綜合考慮AGV空載和負(fù)載路程，提出高效、求解質(zhì)量高的變鄰域遺傳算法。

1 布局設(shè)計(jì)問題模型

本文作如下假設(shè)：每個(gè)工作站s有一個(gè)加載點(diǎn)Ps和一個(gè)卸載點(diǎn)Ds；車間中可分配的位置數(shù)量與待分配的工作站數(shù)量相等，每個(gè)位置只能分配一個(gè)工作站。AGV在工作站之間的路徑段可雙向行走。工作站w到工作站u之間的負(fù)載流量fwu給定，Ps、Dt之間的最短路徑長(zhǎng)度為L(zhǎng)PsDt，工作站的單位重構(gòu)成本為CR，系統(tǒng)上一生產(chǎn)周期的初始布局為工作站w到工作站u之間的空載流量為

決策變量為Hws。假如工作站w分配到位置s，則Hws＝1，否則為0。

布局設(shè)計(jì)問題的目標(biāo)是最小化包括物流路程和工作站重構(gòu)成本在內(nèi)的總物流成本J：

其中Δw為工作站w是否重構(gòu)的指示變量：

需要滿足以下的約束條件：

位置約束：

流量約束：

布局設(shè)計(jì)問題是一個(gè)復(fù)雜的非線性規(guī)劃問題，最優(yōu)化方法難以求解大規(guī)模的問題，這里采用啟發(fā)式方法：遺傳算法（GA）。針對(duì)一般GA局部搜索能力的不足，提出變鄰域遺傳算法（VNS/GA）。

2 變鄰域遺傳算法

GA是一種有效的啟發(fā)式方法，得到廣泛應(yīng)用[4,5]。GA方法是并行搜索，可以得到多個(gè)不同的較高質(zhì)量的解，但是局部搜索能力較差，為此借鑒文獻(xiàn)[5]的方法，在局部搜索中增加變鄰域（VNS）搜索策略。根據(jù)GA的一般設(shè)計(jì)步驟，設(shè)計(jì)如圖1所示的處理過程。

1） 染色體編碼

GA的個(gè)體編碼采用工作站排序編碼的方法，編碼長(zhǎng)度等于工作站的數(shù)量NW。某個(gè)編碼為：π＝(Wi1，Wi2， ，WiNW)，表示在位置Sk上分布的工作站為Wik。假設(shè)種群數(shù)量為Np，則種群可以表示為 Π ＝ (π1，π2， ，πNp)。

2） 適應(yīng)度值計(jì)算

根據(jù)個(gè)體染色體編碼計(jì)算其對(duì)應(yīng)的總物流成本，將總成本的倒數(shù)作為個(gè)體的適應(yīng)度值。

3） 交叉操作

染色體的交叉采用部分映射交叉的方法。在選定的兩個(gè)位置中間的基因，其排序按照另一個(gè)體中的基因排序。

4） 變異操作

變異采用隨機(jī)選擇染色體的兩個(gè)位置，交換這兩個(gè)位置上的基因。

5） 選擇操作

根據(jù)適應(yīng)度值按輪盤賭的方式選擇個(gè)體。

6） 小生境淘汰運(yùn)算

比較個(gè)體編碼之間的相似度，對(duì)編碼距離較小的個(gè)體，其中適應(yīng)度值更小的個(gè)體進(jìn)行一定的排擠，即小生境淘汰運(yùn)算。這為了產(chǎn)生較多的相異個(gè)體，避免種群過早收斂。

7） 變鄰域搜索

由于GA的局部搜索能力較差，采用VNS局部搜索策略對(duì)產(chǎn)生的個(gè)體進(jìn)行局部搜索，以提高解的質(zhì)量。為了降低搜索時(shí)間，以一個(gè)較小的概率pv對(duì)個(gè)體進(jìn)行搜索。

編碼πi與πj之間的海明距離H π(πi，πj)定義為不同放置不同工作站的位置數(shù)量。對(duì)于一個(gè)編碼π，其鄰域定義為：

對(duì)某編碼πi的VNS搜索過程如下：

（1）初始化： 根據(jù)海明距離定義鄰域結(jié)構(gòu)Nk，k＝1， ，kmax，設(shè)置局部搜索次數(shù)LSIt為停止條件。

（2）設(shè)置初始解為π＝πi,令l＝0。

（3）令k＝1。

（6）ifk≤kmax轉(zhuǎn) Step 4。

（7）ifl＜LSIt,l＝l＋1，轉(zhuǎn)Step 3。

（8）Setπi＝π；

返回πi。

8） 停止條件

完成一定進(jìn)化代數(shù)Ng后停止。

9） 參數(shù)設(shè)置

GAL算法的主要參數(shù)有：進(jìn)化代數(shù)Ng，種群數(shù)量Np，交叉概率pc，變異概率pm，小生境參數(shù)h，變鄰域搜索參數(shù)kmax，pv。經(jīng)過一定嘗試，將各個(gè)參數(shù)設(shè)置為：Ng＝150，Np＝20，pc＝0.8，pm＝ 0.2，h＝ max ([1，NW/8])，kmax＝ [NW/3]，pv＝ 0.1。

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

為了驗(yàn)證所提出方法的效果，設(shè)計(jì)了工作站數(shù)量分別為9和15的兩個(gè)計(jì)算實(shí)例。實(shí)例1采用窮舉方法得到最優(yōu)解。而實(shí)例2由于規(guī)模較大，不能得到最優(yōu)解，只給出GA方法的運(yùn)行結(jié)果。

對(duì)每個(gè)實(shí)例，首先假設(shè)在初始生產(chǎn)周期，在給定的初始負(fù)載流量表（稱為流量表1）情況下，不考慮工作站重構(gòu)成本，進(jìn)行初始布局設(shè)計(jì)。然后假設(shè)系統(tǒng)在初始布局情況下，在新的生產(chǎn)周期，根據(jù)新的生產(chǎn)任務(wù)得到新的負(fù)載流量表（稱為流量表2），進(jìn)行新的生產(chǎn)周期的布局設(shè)計(jì)，這時(shí)需要考慮工作站的重構(gòu)成本，針對(duì)不同重構(gòu)成本進(jìn)行算例的比較分析。

1） 實(shí)例 1

本實(shí)例的工作站數(shù)量為9，各位置布局如圖2所示，流量表1如表1所示，流量表2如表2所示。首先采用窮舉法，得到各種設(shè)置情況下的最優(yōu)解，然后GA方法分別10次，以得到平均物流成本和平均計(jì)算時(shí)間。本實(shí)例兩種方法的計(jì)算結(jié)果如表3所示。

計(jì)算結(jié)果分析：窮舉法的計(jì)算時(shí)間明顯比GA方法更長(zhǎng)。在不同的工作站單位重構(gòu)成本條件下，有不同的最優(yōu)布局。GA方法在各種設(shè)置下都能得到最優(yōu)解。

表1 實(shí)例1的初始負(fù)載流量表

表2 實(shí)例1新的負(fù)載流量表

2） 實(shí)例 2

本實(shí)例的工作站數(shù)量為15，系統(tǒng)位置布局為3行5列的格子布局，同樣根據(jù)不同流量表進(jìn)行布局求解。由于本實(shí)例的工作站數(shù)量較多，無法用窮舉法求得最優(yōu)結(jié)果，所以只給出GA方法的結(jié)果，如表4所示。

表3 實(shí)例1兩種方法的結(jié)果

表 4 實(shí)例2 GA方法的結(jié)果

計(jì)算結(jié)果分析：在問題規(guī)模較大的情況下，窮舉法不能在有限時(shí)間內(nèi)完成，所以只能采用啟發(fā)式方法。GAL方法的運(yùn)行效果較好。

通過由以上計(jì)算實(shí)例說明， GA方法比窮舉時(shí)間更短，在問題規(guī)模較大的情況下，GA方法能在有限時(shí)間內(nèi)完成計(jì)算，得到較好結(jié)果，這說明GA方法是一種快速高效的求解方法。

4 結(jié)論

本文根據(jù)基于AGV的RMS布局設(shè)計(jì)特點(diǎn)，提出了變鄰域遺傳算法的布局設(shè)計(jì)方法，設(shè)計(jì)了兩個(gè)計(jì)算實(shí)例進(jìn)行計(jì)算分析。計(jì)算結(jié)果表明：在問題規(guī)模較小時(shí)，GA方法都能得到最優(yōu)結(jié)果，在問題規(guī)模較大時(shí)，GA方法能在有限時(shí)間內(nèi)完成計(jì)算，這說明GA方法是一種快速高效的求解方法。

[1] Z.M.Bi, et al., Reconfigurable manufacturing systems:the state of the art.International Journal of Production Research, 2008, 46(4): 967-992.

[2] A.Drira, H.Pierreval, and S.Hajri-Gabouj, Facility layout problems: A survey.Annual Reviews in Control,2007, 31(2): 255-267.

[3] G.Meng, S.S.Heragu, and H.Zijm, Reconfigurable layout problem.International Journal of Production Research, 42:22, 4709-4729.

[4] 周明, 孫樹棟, 遺傳算法原理及應(yīng)用[M].北京: 國(guó)防工業(yè)出版社, 1999.

[5] 管賢平, 戴先中, 李俊, 基于變鄰域小生境遺傳算法的AGV路徑網(wǎng)絡(luò)設(shè)計(jì)方法[J].中國(guó)機(jī)械工程, 2009, 20(21):2581-2586.