柔性車間的多工藝路線與布局聯(lián)合優(yōu)化

湯洪濤，梁佳炯，陳青豐

(浙江工業(yè)大學(xué) 機(jī)械工程學(xué)院，浙江 杭州 310023)

0 引言

隨著制造技術(shù)的不斷發(fā)展，傳統(tǒng)工藝規(guī)劃開始向柔性工藝規(guī)劃轉(zhuǎn)變[1]。在柔性工藝規(guī)劃中，每一種產(chǎn)品可以選擇多條工藝路線，工藝路線主要通過3種柔性方式產(chǎn)生：①工藝流程柔性，即產(chǎn)品的部分加工工藝本身可選擇替換，例如某道工序既可以通過拉伸實(shí)現(xiàn)，也可以通過擠壓實(shí)現(xiàn)；②工藝順序柔性，即部分加工工藝的先后順序可以交換；③加工機(jī)器柔性，即部分工序使用的機(jī)器可以選擇替換。柔性工藝使得對(duì)柔性車間進(jìn)行布局優(yōu)化設(shè)計(jì)時(shí)需要將工藝路線同時(shí)作為優(yōu)化對(duì)象，從而產(chǎn)生多工藝路線與車間布局聯(lián)合優(yōu)化的概念和需求。

國(guó)內(nèi)外學(xué)者針對(duì)各種車間布局類型進(jìn)行了大量研究[2]。在各類布局問題建模上，通常將問題局限于將若干設(shè)施分配到若干區(qū)域，即二次分配問題(Quadratic Assignment Problem, QAP)，并將其他約束作為獨(dú)立約束條件[3]，僅有少量研究將設(shè)施布置以外的約束作為非獨(dú)立變量(即變量之間相互影響)納入問題模型[4]。

多工藝路線與車間布局聯(lián)合優(yōu)化將工藝路線作為非獨(dú)立變量，而產(chǎn)品的不定需求會(huì)影響多工藝路線規(guī)劃，因此需要在動(dòng)態(tài)環(huán)境下進(jìn)行聯(lián)合優(yōu)化。針對(duì)動(dòng)態(tài)環(huán)境下的車間布局研究主要有動(dòng)態(tài)設(shè)施規(guī)劃問題(Dynamic Facility Layout Problem ，DFLP)和魯棒布局規(guī)劃兩種技術(shù)路線。前者通過時(shí)間分段，將動(dòng)態(tài)環(huán)境轉(zhuǎn)化為一系列不同時(shí)間段上的靜態(tài)環(huán)境[5]，從而將DFLP轉(zhuǎn)換為靜態(tài)設(shè)施規(guī)劃問題[6](Static Facility Layout Problem ，SFLP)，同時(shí)附加不同時(shí)間段重新布局的轉(zhuǎn)換成本[7]；后者不追求某個(gè)時(shí)間段布局的目標(biāo)函數(shù)最優(yōu)，而是追求整個(gè)時(shí)間段的總體布局目標(biāo)函數(shù)最優(yōu)[8]，以減少重新布局對(duì)生產(chǎn)的影響。相比之下，魯棒布局規(guī)劃更適用于設(shè)施位置變動(dòng)比較困難的工廠。

針對(duì)魯棒布局規(guī)劃，MOSLEMIPOUR等[9]提出基于QAP的制造系統(tǒng)隨機(jī)動(dòng)態(tài)環(huán)境下魯棒機(jī)械布局設(shè)計(jì)的數(shù)學(xué)模型，然而其中等設(shè)備面積的假設(shè)不切實(shí)際；周娜等[10]、馬淑梅等[11]、ZHA等[12]針對(duì)產(chǎn)品需求不確定性引起的動(dòng)態(tài)設(shè)施布局問題，各自提出面向不等面積設(shè)備的魯棒布局設(shè)計(jì)方法。在實(shí)際生產(chǎn)中，產(chǎn)品需求變化會(huì)對(duì)工藝路線選擇產(chǎn)生影響，但目前的魯棒布局研究較少將多工藝路線納入優(yōu)化模型，李聰波等[13]、DEEP等[14]各自提出基于所選擇的最優(yōu)零件工藝路線并考慮產(chǎn)品需求的魯棒車間布局模型。上述研究將多工藝路線規(guī)劃作為影響車間布局的參數(shù)因素體現(xiàn)在模型中，忽略了多工藝路線與車間布局之間的相互影響，為了對(duì)兩者進(jìn)行整體優(yōu)化，需要將多工藝路線作為變量來(lái)設(shè)計(jì)模型。因此，基于魯棒布局方法研究，本文提出面向不等面積設(shè)備的多工藝路線與車間布局聯(lián)合優(yōu)化模型。

車間布局問題的求解方法可以歸為精確方法、啟發(fā)式、元啟發(fā)式和混合方法4類[15]。設(shè)施布局問題屬于NP難問題，各類元啟發(fā)方法和混合方法是目前求解車間布局問題常用的方法。傳統(tǒng)的設(shè)施規(guī)劃問題只需求解一個(gè)變量，而聯(lián)合優(yōu)化問題中存在多個(gè)需要求解的非獨(dú)立變量。以往的聯(lián)合優(yōu)化問題研究一般有兩種求解方法：①將非獨(dú)立變量進(jìn)行整合編碼[16]，即在算法求解時(shí)將多個(gè)變量看作單一變量進(jìn)行尋優(yōu)求解；②將聯(lián)合優(yōu)化問題拆解成多個(gè)單獨(dú)優(yōu)化問題，借助元啟發(fā)方法分階段對(duì)聯(lián)合優(yōu)化問題進(jìn)行求解。例如文笑雨等[17]提出工藝路線規(guī)劃與車間調(diào)度集成優(yōu)化方法；李言等[18]提出以加工時(shí)間、成本和設(shè)備負(fù)載為優(yōu)化目標(biāo)的工藝規(guī)劃與調(diào)度集成優(yōu)化模型。然而，兩種優(yōu)化求解方法均忽略了變量之間的影響，理論上縮小了解空間。因此，本文針對(duì)聯(lián)合優(yōu)化問題提出多決策變量智能優(yōu)化算法，該算法以整體函數(shù)優(yōu)化為導(dǎo)向，單獨(dú)、同時(shí)對(duì)各變量的解進(jìn)行優(yōu)化迭代，迭代過程中不同變量的解之間相互沒有影響，防止出現(xiàn)各子問題先后迭代至最優(yōu)，總優(yōu)化目標(biāo)卻不為最優(yōu)的情況，同時(shí)各決策變量采用不同的優(yōu)化迭代方法，保證了整體解的尋優(yōu)效率和多樣性，并對(duì)多工藝路線與車間布局聯(lián)合優(yōu)化模型進(jìn)行了優(yōu)化求解和驗(yàn)證。

1 多工藝路線與車間布局聯(lián)合優(yōu)化模型

1.1 問題描述

問題源自浙江某鍋具制造龍頭企業(yè)的柔性車間布局設(shè)計(jì)項(xiàng)目。以該企業(yè)的A車間為例，車間生產(chǎn)的產(chǎn)品共有11種，涉及加工設(shè)備15種，涉及工藝19道。柔性車間的生產(chǎn)柔性主要體現(xiàn)在工藝流程柔性、工藝順序柔性和加工機(jī)器柔性3方面。不同設(shè)備在不同時(shí)刻可以用于加工多個(gè)工件的多道工序，工件的加工設(shè)備也具有可選擇性。這類柔性車間一般以降低總體物流成本為目標(biāo)進(jìn)行兩階段布局與工藝規(guī)劃[19]：①基于工藝約束構(gòu)建模型，求解得到各工件的工藝路線；②以第一階段求解得到的工藝路線為基礎(chǔ)進(jìn)行車間布局建模，再求解得到方案。兩階段優(yōu)化設(shè)計(jì)方法將復(fù)雜的聯(lián)合優(yōu)化問題拆解為易于求解的兩個(gè)子問題進(jìn)行逐步求解，然而求解過程中忽略了子問題之間的相互影響，以一階段最優(yōu)工藝路線為參數(shù)得到的車間布局方案的總體物流成本并不一定是最低的[20]。多工藝路線與車間布局聯(lián)合優(yōu)化模型以總體物流成本最低為優(yōu)化目標(biāo)，同時(shí)求解多工藝路線與車間布局，避免了先后求解上述兩個(gè)子問題所產(chǎn)生的問題。

1.2 模型變量

記m為車間的產(chǎn)品種類，n為車間工藝路線中涉及的設(shè)備數(shù)量(包括加工設(shè)備和倉(cāng)庫(kù))，t為車間加工設(shè)備的數(shù)量(由于包含關(guān)系，有t

定義模型中的各個(gè)變量參數(shù)，如表1所示。

表1 模型變量參數(shù)及其含義

1.2.1 工藝路線

記n階0-1矩陣Pn×n,i為車間第i類產(chǎn)品的工藝路線，i=1,2,3,…,m。例如，車間共有5個(gè)設(shè)備，其第1類產(chǎn)品的工藝路線為2-1-4-3，則P5×5,1矩陣如圖1a所示，圖中每一元素的的行為上一工序的設(shè)備編號(hào)，列為下一工序的設(shè)備編號(hào)。當(dāng)某種產(chǎn)品工藝路線中不同工序使用同一臺(tái)設(shè)備，如該類產(chǎn)品的工藝路線為2-1-4-1-3時(shí)，工藝路線的矩陣如圖1b所示；當(dāng)一種產(chǎn)品連續(xù)出入同一臺(tái)設(shè)備，如該類產(chǎn)品的工藝路線為2-1-1-4-3時(shí)，矩陣如圖1c所示，因?yàn)檫B續(xù)進(jìn)入同一臺(tái)設(shè)備進(jìn)行加工并不產(chǎn)生物流成本，所以該情況下的工藝路線矩陣和圖1a相同；當(dāng)相同的配送段多次出現(xiàn)在一條產(chǎn)品工藝路線中，如該類產(chǎn)品工藝路線為2-1-4-2-1-3時(shí)，矩陣如圖1d所示。

1.2.2 設(shè)備間距

d12=|x1-x2|+|y1-y2|。

(1)

1.2.3 設(shè)備換模

在實(shí)際生產(chǎn)中，隨著產(chǎn)品種類和數(shù)量的增加，加工設(shè)備的換模物流成本也會(huì)增加。記列向量d1×t為車間各加工設(shè)備與模具庫(kù)的距離。設(shè)車間模具庫(kù)s出入口坐標(biāo)為(xs,ys)，則t維模具庫(kù)與各設(shè)備間距的列向量d1×t=(d1s,d2s，…，dts)T，其中設(shè)備與模具庫(kù)距離為

dis=|xi-xs|+|yi-ys|，i=1,2,…,t。

(2)

1.3 模型參數(shù)

1.3.1 工藝約束參數(shù)

記ki,j為工藝j在第i類產(chǎn)品工藝路線中的序號(hào)，i=1,2,3,…,m，j=1,2,3,…,p。假設(shè)車間第1類產(chǎn)品的工藝路線為2-1-4-3，則其中2號(hào)工藝的序號(hào)k1,2=1，4號(hào)工藝的序號(hào)k1,4=3。

1.3.2 工藝的加工設(shè)備約束參數(shù)

記pi,j為工藝j在第i類產(chǎn)品工藝路線中選擇的設(shè)備，i=1,2,3,…,m，j=1,2,3,…,p。假設(shè)在車間第1類產(chǎn)品的工藝路線中，2號(hào)工藝的設(shè)備選擇3號(hào)，則p1,2=3。

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

(3)

ki,jj,r=1,2,…,p,j≠r;

(4)

pi,j∈Ωj,i=1,2,…,m,j=1,2,…,p;

(5)

(6)

(7)

xe=E,ye=E′,e∈B,E,E′∈R′。

(8)

其中：式(4)為工藝約束，表示在第i類產(chǎn)品工藝路線中，工藝j的序號(hào)小于工藝r的序號(hào)，即在第i類產(chǎn)品生產(chǎn)過程中，工藝j必須先于工藝r進(jìn)行；式(5)為工藝設(shè)備選擇約束，表示在第i類產(chǎn)品工藝路線中，工藝j選擇的設(shè)備必須屬于其可選設(shè)備的集合Ωj；式(6)為設(shè)備區(qū)域間距約束，表示車間布局中各設(shè)備區(qū)域之間橫坐標(biāo)之差的絕對(duì)值必須大于設(shè)備e與設(shè)備q的區(qū)域長(zhǎng)度之和的1/2，或者縱坐標(biāo)之差的絕對(duì)值大于寬度之和的1/2，即各設(shè)備區(qū)域不能有重合的情況；式(7)為設(shè)備區(qū)域邊界約束，即設(shè)備e區(qū)域的橫坐標(biāo)必須大于設(shè)備e區(qū)域長(zhǎng)度的1/2且小于車間長(zhǎng)度與設(shè)備e區(qū)域長(zhǎng)度的1/2之差，同時(shí)設(shè)備e區(qū)域的縱坐標(biāo)必須大于設(shè)備e區(qū)域?qū)挾鹊?/2且小于車間寬度與設(shè)備e區(qū)域?qū)挾鹊?/2之差，即各設(shè)備區(qū)域不能超出車間邊界；式(8)為特殊固定約束，表示由于特殊需要，設(shè)備e必須布置在坐標(biāo)為(E,E′)的地方，如倉(cāng)庫(kù)和一些需要通風(fēng)的設(shè)備。

2 多決策變量?jī)?yōu)化算法設(shè)計(jì)

2.1 基于智能優(yōu)化算法的多決策變量模型求解

目前針對(duì)多決策變量模型的算法求解，一般是將各個(gè)變量整合編碼后利用統(tǒng)一的優(yōu)化迭代思路求解。然而，智能優(yōu)化算法的本質(zhì)是搜索算法[21]，將多種變量整合為一個(gè)變量進(jìn)行尋優(yōu)會(huì)在一定程度上降低整體解的搜索效率和多樣性。多決策變量?jī)?yōu)化算法以種群分散度和種群休整策略為基礎(chǔ)，通過在解的不同維度設(shè)計(jì)不同特點(diǎn)的優(yōu)化算法對(duì)多決策變量模型進(jìn)行優(yōu)化求解。

全局搜索和局部尋優(yōu)是智能優(yōu)化算法的兩大特點(diǎn)，算法特點(diǎn)不同決定了解的搜索方向不同。如果在解的兩個(gè)維度都采用全局搜索，雖然能夠保證解的多樣性，但是犧牲了尋優(yōu)效率，如圖2a所示；如果兩個(gè)維度都采用局部尋優(yōu)，則會(huì)喪失大量解的可能性并陷入局部最優(yōu)，如圖2b所示；如果兩個(gè)維度采用不同特點(diǎn)的算法，則能在理論上解決上述難題，即在初始種群個(gè)體足夠分散的前提下兼顧全局搜索與局部尋優(yōu)之間的協(xié)同問題，如圖2c所示。

各維度算法的主要特點(diǎn)體現(xiàn)在解的產(chǎn)生(搜索)規(guī)則方面。智能優(yōu)化算法設(shè)計(jì)主要是解的產(chǎn)生方式和選擇規(guī)則[22]，但在上述多決策變量?jī)?yōu)化算法的求解思路中，需要保留每次優(yōu)化迭代中任何維度的任何解，若缺失某次迭代的解，則將減小整體解空間，甚至導(dǎo)致優(yōu)化迭代無(wú)法進(jìn)行，因此主要設(shè)計(jì)解的選擇規(guī)則的算法不適用于多決策變量?jī)?yōu)化算法。

智能優(yōu)化算法大致可以分為模擬退火算法、禁忌搜索算法、神經(jīng)網(wǎng)絡(luò)算法、進(jìn)化類算法和群智能算法5類[23]。其中，模擬退火算法的主要特點(diǎn)為以小概率接受劣解的方式來(lái)體現(xiàn)算法的全局搜索能力，被摒棄的劣解會(huì)減小整體解的多樣性，因此并不適合作為多決策變量?jī)?yōu)化算法中某個(gè)變量維度的尋優(yōu)算法；禁忌搜索算法通過設(shè)置禁忌表的方式避免產(chǎn)生重復(fù)解，從而提高尋優(yōu)效率，但在某維度解的搜索過程中使用禁忌搜索算法同樣會(huì)缺失整體解，也可能喪失最優(yōu)解，因此從整體角度來(lái)看，該算法也不適合作為多決策變量?jī)?yōu)化算法中某個(gè)變量維度的尋優(yōu)算法；神經(jīng)網(wǎng)絡(luò)算法本身需要大量數(shù)據(jù)支撐，而且“黑匣子”無(wú)法探究其邏輯性問題，因此不適合解決規(guī)劃類問題；雖然進(jìn)化類算法中也有最優(yōu)解的選擇，但其主要通過設(shè)計(jì)交叉、變異等算子對(duì)解進(jìn)行不斷搜索與迭代，因此可以用于整體設(shè)計(jì)，本文選擇運(yùn)用最廣的遺傳算法；群智能算法主要通過模擬動(dòng)物群體的行為對(duì)解進(jìn)行搜索，個(gè)體之間信息的互聯(lián)互通使得群智能算法在迭代中一直受已知最優(yōu)解的影響而不需要主動(dòng)對(duì)解進(jìn)行選擇，因此群智能算法是不剔除劣解且具有突出局部尋優(yōu)特點(diǎn)的算法，符合本節(jié)提出的多決策變量?jī)?yōu)化算法的思路。群智能算法中粒子群優(yōu)化算法和蟻群算法的運(yùn)用最廣，因?yàn)榱Ｗ尤簝?yōu)化算法相對(duì)于蟻群算法的收斂速度更快，對(duì)解空間的探索能力更強(qiáng)，所以選擇粒子群優(yōu)化算法。

2.2 初始種群的分散度

上一節(jié)提到只有在初始種群足夠分散的情況下，多決策變量?jī)?yōu)化算法才能在求解過程中既保證局部尋優(yōu)能力又不喪失解的可能性，因此需要對(duì)初始種群的分散度進(jìn)行數(shù)學(xué)定義并提出優(yōu)化方法。二維解空間中點(diǎn)的集合即為解種群，點(diǎn)的分散程度即為解種群的分散度，在經(jīng)過不斷迭代之后，解種群將越來(lái)越密集于一點(diǎn)(解種群覆蓋范圍內(nèi)的最優(yōu)解)，即分散度越來(lái)越小，因此初始解種群的分散度越大，迭代后的最優(yōu)解越好。以聯(lián)合優(yōu)化為例，設(shè)解空間的x軸對(duì)應(yīng)車間設(shè)備布局方案，y軸對(duì)應(yīng)工藝路線方案，則解r=(x1,x2,…,xm,y1,y2,…,yn)在二維解空間中的坐標(biāo)為(X,Y)：

X=α1x1+α2x2+…+αmxm-
(α1L1+α2L2+…+αmLm)；

(9)

Y=β1y1+β2y2+…+βnyn-
(β1l1+β2l2+…+βnln)；

(10)

Li≤xi≤Ui,i=1,2,3,…,m；

(11)

lj≤yj≤uj,j=1,2,3,…,n。

(12)

式中：α1,α2,…,αm,β1,β2,…,βn為常數(shù)系數(shù)；Ui,Li分別為xi的上界和下界，uj,lj分別為yj的上界和下界，均為常量。

設(shè)某次優(yōu)化的初始解種群為R=(r1,r2,…,rk)，當(dāng)其中任意兩個(gè)解之間的距離都不小于實(shí)數(shù)ε時(shí)，認(rèn)為該初始種群足夠分散。記任意兩個(gè)解rc,rd在解空間中的坐標(biāo)分別為(Xc,Yc),(Xd,Yd)，其中rc,rd∈R,c,d

(13)

(14)

式中χ為種群大小，當(dāng)種群中兩個(gè)個(gè)體之間的距離過小時(shí)，可以隨機(jī)調(diào)整其中某一個(gè)體某一維度的解，使其符合分散度要求。

2.3 種群休整

古代軍隊(duì)行軍時(shí)會(huì)通過駐扎休整來(lái)保持戰(zhàn)力，由此得到啟發(fā)，以進(jìn)一步提高多決策變量?jī)?yōu)化算法的全局搜索能力。假設(shè)初始種群中有兩個(gè)個(gè)體(如圖3)，基于2.2節(jié)種群初始化分散度的概念設(shè)計(jì)，結(jié)合種群個(gè)體的交叉變異范圍，理論上能覆蓋到盡可能多的可行解。然而在實(shí)際迭代過程中，個(gè)體某一維度的解不斷逼近當(dāng)前最優(yōu)解，例如圖3種群個(gè)體的X軸坐標(biāo)在迭代中不斷靠近最優(yōu)個(gè)體坐標(biāo)，個(gè)體的變異交叉范圍雖然很大，但是迭代中實(shí)際能搜索到的可行解卻很少。

(15)

率的最小值；h0為最大迭代次數(shù)；h為當(dāng)前代數(shù)，初始化種群時(shí)h=0。初始化種群時(shí)的個(gè)體分散度高，迭代中丟失可行解的可能性更大，因此休整概率的初始值最大；隨著迭代的進(jìn)行，種群個(gè)體越來(lái)越密集，個(gè)體的搜索范圍重疊度增加，可行解的丟失概率不斷下降，休整概率相應(yīng)下降。

2.4 編碼

工藝路線規(guī)劃由多條工藝路線和多臺(tái)工藝設(shè)備組合而成，在對(duì)其進(jìn)行染色體編碼時(shí)，需要采用實(shí)數(shù)編碼方式將多段工藝路線染色體組合成一條染色體，作為與一種車間布局方案相配的工藝路線規(guī)劃。如圖4所示，每一條染色體分為m段，每一段從左到右的順序表示一類產(chǎn)品的工藝路線，每一段的長(zhǎng)度由該產(chǎn)品所需的工藝步驟數(shù)量決定，實(shí)數(shù)序號(hào)為每一步涉及的設(shè)備編號(hào)。

車間布局方案即設(shè)備布局方案，主要由各個(gè)設(shè)備的布局坐標(biāo)組成，整段編碼由2n個(gè)實(shí)數(shù)組成，n為車間的設(shè)備數(shù)量，前n個(gè)實(shí)數(shù)依次表示各個(gè)編號(hào)設(shè)備的橫坐標(biāo)，后n個(gè)實(shí)數(shù)依次表示各個(gè)編號(hào)設(shè)備的縱坐標(biāo)，如圖5所示。

因?yàn)樵撃Ｐ蜕婕霸O(shè)備的布置方向，所以除了上述兩段編碼，還需對(duì)n臺(tái)設(shè)備的布置方向進(jìn)行n維0-1編碼。如圖6所示，整段編碼由n個(gè)0-1變量組成，依次表示各個(gè)設(shè)備的布置方式，1表示設(shè)備橫放(即橫長(zhǎng)豎寬)，0表示設(shè)備豎放(即橫寬豎長(zhǎng))。

2.5 進(jìn)化與更新

經(jīng)典遺傳算法中的進(jìn)化算子包括選擇算子、交叉算子和變異算子，其中交叉與變異算子用于實(shí)現(xiàn)遺傳算法良好的全局搜索能力，選擇算子盡可能地為交叉和變異提供良好的父代染色體，即增強(qiáng)尋優(yōu)能力。在求解車間布局方案中，已經(jīng)使用尋優(yōu)能力極強(qiáng)的粒子群算法，在工藝路線的優(yōu)化求解中應(yīng)充分接受劣解以進(jìn)一步提高整體解的全局搜索能力。因此在工藝路線規(guī)劃解的迭代進(jìn)化過程中剔除了選擇算子，只保留提高全局搜索能力的交叉和變異算子。

因?yàn)楣に嚶肪€規(guī)劃染色體由不等長(zhǎng)的多段染色體組成，分別代表不同產(chǎn)品的工藝路線，所以交叉過程中禁止不同段染色體之間交叉，每一段染色體只能與與其對(duì)應(yīng)的同段染色體交叉。如圖7所示，因?yàn)榻徊娌僮鞯囊饬x在于交換彼此染色體包含的信息，而路徑規(guī)劃問題中的單一節(jié)點(diǎn)沒有任何實(shí)際意義，至少需要兩個(gè)節(jié)點(diǎn)才能構(gòu)成路徑信息，所以兩條染色體中的同段染色體之間選擇兩點(diǎn)交叉的方式。

同理，由于不同段染色體代表不同產(chǎn)品的工藝路線，變異過程也不允許發(fā)生在不同段染色體之間。如圖8所示，交換發(fā)生變異的同段染色體中的兩個(gè)節(jié)點(diǎn)構(gòu)成新的染色體。與一般染色體變異不同，該染色體的每一段都有相同的變異概率，即n段染色體有n次變異的可能，從而大大提高了全局搜索能力。

粒子群優(yōu)化算法中解的更新方法為：以粒子個(gè)體的歷史最優(yōu)位置和種群歷史最優(yōu)位置為參考，通過改變粒子速度對(duì)種群個(gè)體進(jìn)行動(dòng)態(tài)調(diào)整。在上文提到的工藝路線規(guī)劃不斷變化的情況下，即使某一代解的車間布局方案足夠好，也會(huì)因工藝路線規(guī)劃變化引起適應(yīng)度變化而自動(dòng)跳出車間布局方案的局部最優(yōu)解，因此對(duì)于車間布局部分的粒子群更新并不需要進(jìn)行過多的優(yōu)化處理。更新方法的具體內(nèi)容如式(16)和式(17)所示：

vi=wvi-1+j1rand(0,1)(pi-1-oi-1)+
j2rand(0,1)(gi-1-oi-1);

(16)

oi=oi-1+vi。

(17)

式中：vi表示各個(gè)車間布局種群個(gè)體的速度，為矢量；w為繼承上一代種群個(gè)體速度更新的程度，w較大時(shí)算法的全局搜索能力較強(qiáng)，w較小時(shí)局部尋優(yōu)能力較強(qiáng)，與上文提到的加強(qiáng)遺傳算法的全局搜索能力相應(yīng)，該算法應(yīng)著重體現(xiàn)其局部尋優(yōu)能力，因此應(yīng)將w設(shè)置得相對(duì)較?。籶i為每個(gè)個(gè)體歷史最優(yōu)的設(shè)備布局方案粒子；oi為某個(gè)設(shè)備布局方案粒子；gi為種群全局最優(yōu)的設(shè)備布局方案粒子；j1,j2為粒子向歷史最優(yōu)與全局最優(yōu)學(xué)習(xí)的程度，通常設(shè)j1=j2=2。

對(duì)采用二進(jìn)制編碼的設(shè)備布置方向種群適合用遺傳算法變異算子中的單點(diǎn)變異方法進(jìn)行迭代更新，如圖9所示。其中，每次迭代中發(fā)生變異的染色體節(jié)點(diǎn)應(yīng)不超過一定數(shù)量，以避免過多變異導(dǎo)致車間布局的最優(yōu)解被掩蓋。

2.6 多決策變量?jī)?yōu)化算法步驟與流程

根據(jù)以上對(duì)多決策變量?jī)?yōu)化算法的分析與設(shè)計(jì)總結(jié)算法流程，如圖10所示，具體步驟如下：

(1)對(duì)工藝路線種群、車間布局種群和設(shè)備布置方向種群進(jìn)行初始化。

(2)對(duì)工藝路線種群與車間布局種群的種群分散度進(jìn)行判定與優(yōu)化，達(dá)到初始化種群分散度的要求后執(zhí)行(3)。

(3)對(duì)工藝路線種群和車間布局種群的工藝約束和布局約束進(jìn)行判定修正，即符合特定工藝順序需求，同時(shí)設(shè)備間距大于零且各設(shè)備不超出車間邊界才能執(zhí)行(4)。

(4)計(jì)算初始化種群的適應(yīng)度，對(duì)個(gè)體和全局最優(yōu)種群(p和g)進(jìn)行初始化賦值。

(5)判斷是否執(zhí)行種群休整，是則在后續(xù)迭代更新中跳過(7)，否則依次執(zhí)行以下步驟。

(6)對(duì)工藝路線種群進(jìn)行交叉和變異操作，完成工藝路線種群進(jìn)化。

(7)對(duì)車間布局種群的更新和設(shè)備布置方向進(jìn)行變異操作。

(8)再次對(duì)工藝路線種群和車間布局種群的工藝約束和布局約束進(jìn)行判定修正，完全符合約束后執(zhí)行(9)。

(9)計(jì)算種群適應(yīng)度，并更新個(gè)體與全局最優(yōu)種群。

(10)判斷是否達(dá)到最大迭代次數(shù)，是則結(jié)束該優(yōu)化過程，否則重復(fù)(5)～(9)。

3 實(shí)例驗(yàn)證

3.1 實(shí)例數(shù)據(jù)

將問題描述中提到的A車間作為實(shí)例對(duì)象對(duì)模型和算法進(jìn)行驗(yàn)證。該柔性車間進(jìn)行設(shè)備布局規(guī)劃的面積為長(zhǎng)90 m、寬50 m，生產(chǎn)涉及的產(chǎn)品種類共11項(xiàng)，歷史產(chǎn)量與預(yù)測(cè)量以及所含工藝步驟如表2所示，其中產(chǎn)品產(chǎn)量按20件為一托盤折算為托盤數(shù)。已知更換一臺(tái)加工設(shè)備模具產(chǎn)生的物流量為0.17托/h，以設(shè)備一天工作20 h，一年工作300 d計(jì)算得一臺(tái)加工設(shè)備一年的換模物流量為1 020托/年。另外，該柔性車間以潛入式自動(dòng)導(dǎo)引小車(Automated Guided Vehicle，AGV)為主要運(yùn)輸方式，該AGV的動(dòng)力電池為鋰電池，參考文獻(xiàn)[24]可得單位物流成本系數(shù)c=0.083元/m。各類產(chǎn)品、產(chǎn)量及其工藝步驟如表2所示。

表2 各產(chǎn)品相關(guān)產(chǎn)量與工藝步驟表

該車間生產(chǎn)涉及的工藝設(shè)備共15種，其中多種設(shè)備可采用不同的加工工藝，如表3所示。各設(shè)備區(qū)域面積如表4所示。

表3 各工藝步驟柔性約束

表4 各設(shè)備區(qū)域面積的長(zhǎng)和寬

3.2 輸出分析

以MATLAB為運(yùn)算環(huán)境，設(shè)定變異概率為0.9，交叉概率為0.1，繼承系數(shù)為0.4，學(xué)習(xí)系數(shù)為0.6，根據(jù)2.1節(jié)內(nèi)容，為了進(jìn)一步增強(qiáng)遺傳算法的全局搜索，將交叉概率從0.05提高到0.1，同理為了進(jìn)一步加強(qiáng)粒子群算法的局部尋優(yōu)，將繼承系數(shù)從0.5下調(diào)至0.4，而將學(xué)習(xí)系數(shù)從0.5提高到0.6；對(duì)于休整概率的選取，在考慮到算法優(yōu)化速度的情況下，選擇初始值0.7和最小值0.3。最后，將3.1節(jié)實(shí)例數(shù)據(jù)作為多工藝路線與車間布局聯(lián)合優(yōu)化模型的輸入，進(jìn)行30次最大迭代次數(shù)為300的優(yōu)化算法計(jì)算，結(jié)果如表5所示。其中最優(yōu)值即最低年物流費(fèi)用為4 035 838元，其優(yōu)化迭代的收斂曲線如圖11所示。最優(yōu)工藝路線規(guī)劃如表6所示，所得最優(yōu)車間布局簡(jiǎn)圖如圖12所示。

表5 多工藝路線與車間布局聯(lián)合優(yōu)化結(jié)果統(tǒng)計(jì)表 元

表6 最優(yōu)多工藝路線規(guī)劃

續(xù)表6

3.3 對(duì)比分析

3.3.1 多工藝路線已確定的車間布局優(yōu)化

為了驗(yàn)證工藝路線與車間布局聯(lián)合優(yōu)化的必要性，將工藝路線作為模型固定參數(shù)輸入(即多工藝路線已經(jīng)規(guī)劃完畢)，同樣對(duì)該車間布局進(jìn)行30次優(yōu)化計(jì)算，結(jié)果如表7所示。

從最優(yōu)值看，表5中多工藝路線與車間布局聯(lián)合優(yōu)化方法的最優(yōu)值為4 035 838元，表7中考慮工藝路線車間布局優(yōu)化方法的最優(yōu)值為4 527 334元，前者最多每年節(jié)省約49萬(wàn)元物流費(fèi)用。從平均值看，表5中聯(lián)合優(yōu)化方法的年物流費(fèi)用平均值4 594 768元比表7中考慮工藝路線的車間布局優(yōu)化方法的年物流費(fèi)用平均值4 769 548元節(jié)省約18萬(wàn)元。兩種優(yōu)化結(jié)果的對(duì)比如圖13所示，統(tǒng)計(jì)結(jié)果如表8所示。

表7 考慮多工藝路線的車間布局優(yōu)化結(jié)果統(tǒng)計(jì)表 元

表8 兩種優(yōu)化的統(tǒng)計(jì)結(jié)果

3.3.2 算法性能對(duì)比

將上述聯(lián)合優(yōu)化的運(yùn)行結(jié)果作為多決策變量?jī)?yōu)化算法的優(yōu)化結(jié)果，同時(shí)采用粒子群優(yōu)化算法和遺傳算法對(duì)實(shí)例進(jìn)行整合編碼設(shè)計(jì)并優(yōu)化求解，對(duì)3種算法性能進(jìn)行對(duì)比，如表9所示。因?yàn)闀r(shí)間在實(shí)際規(guī)劃設(shè)計(jì)中相對(duì)充裕，所以沒有對(duì)比優(yōu)化迭代時(shí)間。3種優(yōu)化算法的平均優(yōu)化結(jié)果和對(duì)比如圖14所示。

表9 3種優(yōu)化算法的30次優(yōu)化結(jié)果 元

表10 3種優(yōu)化算法的平均優(yōu)化結(jié)果統(tǒng)計(jì)表

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

多工藝路線與車間布局聯(lián)合優(yōu)化模型是以降低總體物流成本的車間布局方法為基礎(chǔ)，結(jié)合柔性車間三大工藝柔性特點(diǎn)，對(duì)多工藝路線和車間布局進(jìn)行同步優(yōu)化，具有廣泛適用性的設(shè)計(jì)方法。本文將多工藝路線規(guī)劃和車間布局規(guī)劃均作為模型的決策變量，根據(jù)不同產(chǎn)品的訂單量決定該種產(chǎn)品工藝路線在總體規(guī)劃中的影響程度，同時(shí)將與日常制造生產(chǎn)密切相關(guān)的出入庫(kù)物流和換模物流納入總體物流成本的考量之中，以使該模型更加貼近實(shí)際生產(chǎn)情況。通過實(shí)例驗(yàn)證，多工藝路線與車間布局聯(lián)合優(yōu)化模型求解的平均結(jié)果優(yōu)于分別優(yōu)化的平均結(jié)果，證明了該聯(lián)合優(yōu)化模型的可行性。

算法是求解數(shù)學(xué)模型的工具，為數(shù)學(xué)模型設(shè)計(jì)符合其特點(diǎn)的算法具有必要性[14]。多工藝路線與車間布局聯(lián)合優(yōu)化模型的求解特點(diǎn)在于，兩種變量可以在各自維度上對(duì)解進(jìn)行搜索。本文針對(duì)該問題提出多決策變量?jī)?yōu)化算法，當(dāng)初始種群的量與分散度足夠大時(shí)，在解的兩個(gè)維度上分別采用具有全局搜索特點(diǎn)與局部尋優(yōu)特點(diǎn)的算法，從而在對(duì)函數(shù)目標(biāo)值快速求解的過程中保持較強(qiáng)的全局搜索能力，實(shí)例驗(yàn)證通過采用T檢驗(yàn)對(duì)兩種優(yōu)化結(jié)果的平均值進(jìn)行驗(yàn)證，在全局搜索和局部尋優(yōu)兩個(gè)角度證明了該聯(lián)合優(yōu)化算法的適用性和有效性。

智能工廠建設(shè)的浪潮剛剛興起，對(duì)智能柔性車間規(guī)劃進(jìn)行設(shè)計(jì)優(yōu)化的需求會(huì)越來(lái)越大，多工藝路線與車間布局聯(lián)合優(yōu)化模型是將工藝路線和車間布局聯(lián)合優(yōu)化的初步嘗試，而與車間布局優(yōu)化相關(guān)的規(guī)劃設(shè)計(jì)不只有工藝路線，有必要構(gòu)建整體性、系統(tǒng)性的智能工廠設(shè)計(jì)理論，與此相關(guān)的多元非線性約束優(yōu)化算法也是需要進(jìn)行深入研究的領(lǐng)域。