基于改進(jìn)和聲搜索算法的車間布局優(yōu)化

劉冠權(quán),沈汝清,潘丹丹

(青島理工大學(xué) 管理工程學(xué)院,山東 青島 266525)

車間作為制造企業(yè)的基本生產(chǎn)單位,車間設(shè)施布局的合理性決定了生產(chǎn)的可行性和車間的經(jīng)濟(jì)效益。國內(nèi)外研究將其視為降低生產(chǎn)成本和提高生產(chǎn)效率的關(guān)鍵因素。因此,在現(xiàn)有設(shè)施和場地的情況下,要降低生產(chǎn)成本,增加空間利用率,提高生產(chǎn)制造企業(yè)的生產(chǎn)效率,最好的措施是優(yōu)化和改善現(xiàn)有廠房的布局。

目前,車間設(shè)施布局的方法主要有傳統(tǒng)方法和啟發(fā)式算法,具有代表性的傳統(tǒng)方法是SLP法[1]。而啟發(fā)式算法主要有遺傳算法、粒子群算法、模擬退火算法等。鄧兵等[2]針對(duì)多品種類產(chǎn)品,將改進(jìn)的SLP和遺傳算法相結(jié)合進(jìn)行車間設(shè)備布局的優(yōu)化。王亞良等[3]以物料搬運(yùn)費(fèi)用最小、單元移動(dòng)費(fèi)用最小、作業(yè)單元包絡(luò)矩形面積最小及非物流關(guān)系最大為目標(biāo),利用引入動(dòng)態(tài)變異策略的動(dòng)態(tài)差分元胞多目標(biāo)遺傳算法進(jìn)行布局模型的求解。張青雷等[4]以降低車間物料搬運(yùn)成本為目標(biāo),通過動(dòng)態(tài)改變慣性因子大小的動(dòng)態(tài)多目標(biāo)粒子群優(yōu)化算法求解布局模型。葛曉梅等[5]以最小作業(yè)單元間物料搬運(yùn)費(fèi)用和最短搬運(yùn)時(shí)間為優(yōu)化目標(biāo),運(yùn)用引入進(jìn)化逆轉(zhuǎn)操作的改進(jìn)遺傳算法進(jìn)行布局模型的求解。靳國偉等[6]提出和聲搜索算法和Dijkstra算法相結(jié)合的混合算法求解鐵路物流中心分層選址分配模型。于紅麗[7]以物料搬運(yùn)費(fèi)用最小和非物流關(guān)系密切度最大為目標(biāo)函數(shù),提出了基于SLP+和聲搜索算法的工廠布局優(yōu)化辦法。谷培義等[8]提出一種改進(jìn)的多目標(biāo)和聲搜索算法,引入自適應(yīng)操作,并選取4個(gè)測試函數(shù)驗(yàn)證該算法的有效性。徐文星等[9]針對(duì)FJSP,以最大完工時(shí)間為優(yōu)化目標(biāo),提出一種采用兩段組合編碼的改進(jìn)和聲搜索算法。QIAO等[10]提出一種同時(shí)考慮物料搬運(yùn)成本和車間面積利用率的目標(biāo)函數(shù),并采用遺傳算法進(jìn)行布局模型的求解。TALAPATRA[11]將物料搬運(yùn)成本最小設(shè)為目標(biāo)函數(shù),利用遺傳算法求解布局模型。HONG等[12]提出一種對(duì)交叉率和變異率進(jìn)行非線性處理的自適應(yīng)交叉和變異策略得到的自適應(yīng)遺傳算法,并將其應(yīng)用到求解車間布局模型問題。LI等[13]利用SLP和遺傳算法求解船舶艙室設(shè)備布局模型。ZHANG等[14]構(gòu)建配送中心布局優(yōu)化模型,并采用SLP結(jié)合遺傳算法進(jìn)行求解。LENIN等[15]利用和聲搜索算法來求解同時(shí)滿足產(chǎn)品流動(dòng)距離和布局面積最小化的雙目標(biāo)車間布局模型。

綜上所述,大多數(shù)車間設(shè)施布局優(yōu)化只將物流搬運(yùn)費(fèi)用作為單一優(yōu)化目標(biāo),忽略了實(shí)際生產(chǎn)中非物流密切因素的影響,故筆者建立以最小物流搬運(yùn)成本和最大非物流關(guān)系密切度為雙目標(biāo)函數(shù)的車間設(shè)施布局?jǐn)?shù)學(xué)模型,針對(duì)和聲搜索算法解決離散性問題時(shí)易陷入局部最優(yōu)的問題,在標(biāo)準(zhǔn)和聲搜索算法的基礎(chǔ)上,引入遺傳算法的交叉、變異算子代替微調(diào)帶寬,以增強(qiáng)和聲搜索算法的全局尋優(yōu)能力,并通過6個(gè)規(guī)模不同的生產(chǎn)案例驗(yàn)證了算法的有效性。

1 車間布局問題描述

1.1 模型假設(shè)

筆者著重于多行設(shè)備布局問題,在實(shí)際生產(chǎn)中,作業(yè)單位的大小、形狀各有不同,因此在構(gòu)建簡化后的布局模型時(shí)做出以下假設(shè):①坐標(biāo)原點(diǎn)設(shè)定在生產(chǎn)車間的左下角,X軸為車間長度方向,Y軸為車間寬度方向,車間長度為L,寬度為W;②假設(shè)車間各個(gè)作業(yè)單位均為面積固定的矩形,且長寬已知,令車間第i個(gè)作業(yè)單位為mi,i=1,2,…,n,其長度為li,寬度為wi;③作業(yè)單位進(jìn)出點(diǎn)為其中心點(diǎn),作業(yè)單位間的距離是指中心間的曼哈頓距離,且各作業(yè)單位間的物料運(yùn)輸路線平行于車間的長度方向或?qū)挾确较颉?/p>

基于以上模型假設(shè),建立車間設(shè)施布局模型示意圖,如圖1所示。以作業(yè)單位mi為例,作業(yè)單位mi中心點(diǎn)的橫坐標(biāo)、縱坐標(biāo)為xi、yi;dxij為作業(yè)單位i與j在X軸方向的距離,dyik為作業(yè)單位i與k在Y軸方向的距離。

圖1 車間設(shè)施布局模型

1.2 目標(biāo)函數(shù)

建立以車間物料搬運(yùn)總費(fèi)用P1最小和車間面積利用率P2最大為優(yōu)化目標(biāo)的函數(shù):

(1)

(2)

式中:P1為生產(chǎn)車間作業(yè)單位間物料搬運(yùn)成本;P2為生產(chǎn)車作業(yè)單位間的非物流關(guān)系;Qij為作業(yè)單位i與j之間的單次物料搬運(yùn)成本;Fij為作業(yè)單位與之間的物料搬運(yùn)頻率;Dij為作業(yè)單位i與j之間的距離,這里采用的是曼哈頓距離,計(jì)算公式為Dij=|xi-xj|+|yi-yj|;Tij為作業(yè)單位i與j之間的非物流關(guān)系值,其值根據(jù)作業(yè)單位之間的密切程度等級(jí)進(jìn)行定量化,具體數(shù)值如表1所示;bij為作業(yè)單位i與j之間的接近程度,稱為關(guān)聯(lián)度,其值由Dij決定,具體對(duì)應(yīng)值如表2所示。

表1 密切程度量化表

表2 關(guān)聯(lián)度值

由于兩個(gè)目標(biāo)的量化標(biāo)準(zhǔn)有所差異,故采用加權(quán)因子α和β來調(diào)整兩個(gè)目標(biāo)函數(shù)所占比重,其中α+β=1;采用歸一化因子λ1和λ2來統(tǒng)一式(1)和式(2)的量綱,轉(zhuǎn)化后的目標(biāo)函數(shù)為:

(3)

(4)

(5)

式中:P為加權(quán)后的目標(biāo)函數(shù);α為物料搬運(yùn)費(fèi)用所占比重;β為面積利用率所占比重。

1.3 約束條件

在對(duì)車間設(shè)施進(jìn)行布局優(yōu)化時(shí),需要考慮車間的實(shí)際生產(chǎn)情況進(jìn)行約束,主要包括固定約束、邊界約束和間距約束。

(1)固定約束。在生產(chǎn)加工過程中各作業(yè)單位需與墻壁之間保持一定的間距。

(6)

(7)

(2)邊界約束。同一行作業(yè)單位在X軸方向的長度之和不超過車間的長度,同一列作業(yè)單位在Y軸方向的的長度之和不超過車間的寬度。

(8)

(9)

(3)間距約束。各個(gè)作業(yè)單位之間需保持一定的間距,且作業(yè)單位不能重疊:

(10)

(11)

(12)

2 改進(jìn)和聲搜索搜索算法

2.1 標(biāo)準(zhǔn)和聲搜索算法

和聲搜索算法(harmony search,HS)是由韓國學(xué)者GEEM等[16]提出的一種基于音樂演奏和聲原理的仿人智能優(yōu)化算法,算法模擬了音樂創(chuàng)作過程中樂師們憑借自己的記憶,通過反復(fù)調(diào)整樂隊(duì)中各樂器的音調(diào),最終達(dá)到一個(gè)美妙的和聲狀態(tài)的過程。和聲搜索算法包含了現(xiàn)有的啟發(fā)式算法結(jié)構(gòu),保留了類似禁忌搜索算法的初始向量元素,對(duì)應(yīng)著和聲搜索算法中的和聲記憶庫,從計(jì)算的開始到結(jié)束能夠以類似模擬退火算法的方式改變適應(yīng)率,即對(duì)應(yīng)著和聲記憶庫保留概率,且以類似遺傳算法的方式同步處理多個(gè)向量元素。

2.2 改進(jìn)和聲搜索算法設(shè)計(jì)

車間設(shè)施布局優(yōu)化問題經(jīng)證實(shí)是具有離散優(yōu)化和非線性特性的NP-Hard問題,標(biāo)準(zhǔn)的和聲搜索算法是針對(duì)離散問題設(shè)計(jì)的,但由于其對(duì)和聲庫、取值概率及微調(diào)概率的依賴性較強(qiáng),筆者在基礎(chǔ)和聲搜索算法的基礎(chǔ)上,引入遺傳算法的交叉變異操作,將遺傳算法的逆序變異代替和聲搜索算法的微調(diào)帶寬,即在編碼長度內(nèi)生成兩個(gè)位置,對(duì)兩個(gè)位置間的基因進(jìn)行逆序變換。

(2)確定適應(yīng)度函數(shù)。在遺傳算法中,種群個(gè)體的適應(yīng)度越大,表示種群個(gè)體的優(yōu)越性越好,由于優(yōu)化目標(biāo)是求最小值,因此設(shè)定適應(yīng)度函數(shù)為:

(13)

(3)設(shè)定編碼方式。采用實(shí)數(shù)編碼的方式,具體編碼樣式設(shè)計(jì)為[m1,m2,…,mn],表示從車間生產(chǎn)區(qū)域左下角開始,依次沿X軸正方向布置作業(yè)單位,如果在同一行內(nèi)的作業(yè)單位長度和相互之間的距離之和超過生產(chǎn)車間總長度,則采取自動(dòng)換行策略,由Y軸正方向另起一行,依次布置即可得到最終的車間布局圖。

(14)

(15)

圖2 交叉操作

(16)

變異算子可以維持染色體的多樣性,避免進(jìn)化中早期成熟,改善算法的局部搜索能力。在實(shí)數(shù)編碼下,采用互換變異的方式進(jìn)行變異操作,其基本思想為:隨機(jī)選擇編碼長度內(nèi)的兩個(gè)位置,并將這兩個(gè)位置上的基因進(jìn)行互換。筆者采用遺傳算法的逆序變異代替和聲搜索算法的微調(diào)帶寬,即在編碼長度內(nèi)隨機(jī)生成兩個(gè)位置a和b。對(duì)兩個(gè)位置間的基因進(jìn)行逆序變換,從而提高和聲搜索算法的整體尋優(yōu)能力,互換變異及逆序變異如圖3所示。

圖3 變異操作

2.3 算法步驟

改進(jìn)和聲搜索算法流程如圖4所示,具體算法步驟為:①隨機(jī)初始和聲記憶庫和參數(shù),隨機(jī)初始多個(gè)布局編碼,解碼得到對(duì)應(yīng)的目標(biāo)函數(shù)值,將其作為和聲庫HMS;②隨機(jī)產(chǎn)生(0,1)之間的隨機(jī)數(shù)rand1,如果隨機(jī)數(shù)rand1小于HMCR,隨機(jī)挑選HMS中的一個(gè)個(gè)體,繼續(xù)進(jìn)行步驟③,反之則另外隨機(jī)生成一個(gè)新編碼,轉(zhuǎn)入步驟④;③隨機(jī)產(chǎn)生(0,1)之間的隨機(jī)數(shù)rand2,如果rand2小于PAR,則對(duì)挑選的個(gè)體進(jìn)行遺傳算法的逆序變異,得到新編碼,反之則不調(diào)整;④解碼得到新編碼的目標(biāo)函數(shù)值,如果該目標(biāo)函數(shù)值小于和聲庫的最劣解(最大目標(biāo)函數(shù)值對(duì)應(yīng)的解),取代最劣解,反之則不取代;⑤判斷是否達(dá)到創(chuàng)作次數(shù)Tmax,達(dá)到輸出結(jié)果,否則轉(zhuǎn)到步驟①。

圖4 改進(jìn)和聲搜索算法流程圖

3 算例分析

按照設(shè)施數(shù)目將其分成3種規(guī)模不同的算例,其中小規(guī)模算例為Z12[17]、T12[18],中規(guī)模算例為C16[19]、M18[20],大規(guī)模算例為Cy23[21]、A23[22]。文獻(xiàn)中給出了每個(gè)算例具體的物流量、車間的尺寸、非物流關(guān)系密切度等。3種不同規(guī)模算例的設(shè)施數(shù)目和車間尺寸如表3所示。

表3 算例的設(shè)施數(shù)目和車間尺寸

對(duì)于上述算例,采用改進(jìn)和聲搜索算法(HS-GA)和遺傳算法(GA)與原始布局進(jìn)行對(duì)比。設(shè)施布置優(yōu)化中的主要目的是最大限度地減少物料搬運(yùn),因此根據(jù)專家打分法得出α=0.6,β=0.4。通過大量實(shí)驗(yàn)數(shù)據(jù)驗(yàn)證、廣泛的模擬以及參考已有文獻(xiàn)[23],將和聲記憶庫的大小HMS設(shè)置為50,和聲記憶庫的取值概率HMCR設(shè)置為0.95,音調(diào)微調(diào)概率PAR設(shè)置為0.1,迭代次數(shù)Tmax設(shè)置為1 000,遺傳算法中交叉概率Pc設(shè)置為0.9,變異概率Pm設(shè)置為0.1。在Intel(R) Core(TM) i5-6200U CPU @2.40 GHz、4.00 GB、Win10系統(tǒng)運(yùn)行環(huán)境下,利用Matlab 2016b分別運(yùn)行30次,算法終止條件為算法迭代次數(shù)達(dá)到Tmax,具體結(jié)果對(duì)比如表4所示。

表4 算例結(jié)果對(duì)比

根據(jù)表4的計(jì)算結(jié)果可以得出,改進(jìn)和聲搜索算法在解決小規(guī)模、中規(guī)模、大規(guī)模布局優(yōu)化問題上,大都能夠?qū)ふ业礁鼉?yōu)解,具有高效性,僅在中規(guī)模算例C16中出現(xiàn)遺傳算法布局非物流關(guān)系密切度更優(yōu)的情況。為了證明求解得到的優(yōu)化方案的合理性,以Cy23為具體案例,根據(jù)文獻(xiàn)中數(shù)據(jù),計(jì)算得出目標(biāo)函數(shù)中歸一化因子λ1=1.844×10-8、λ2=6.250×10-3。隨著迭代次數(shù)的增加,目標(biāo)函數(shù)最優(yōu)解會(huì)逐漸趨于穩(wěn)定,利用標(biāo)準(zhǔn)遺傳算法與改進(jìn)和聲搜索算法分別求解車間布局模型,其適應(yīng)度值及迭代曲線如圖5所示,標(biāo)準(zhǔn)遺傳算法在迭代到736次時(shí)完成收斂,其最優(yōu)目標(biāo)函數(shù)值為0.039 1;改進(jìn)和聲搜索算法在迭代到233次時(shí)目標(biāo)函數(shù)達(dá)到最優(yōu)值0.007 5;原始布局的物料搬運(yùn)費(fèi)用為17 660 698.25元,遺傳算法求解的費(fèi)用為16 504 655.00元,利用改進(jìn)和聲搜索算法優(yōu)化后的費(fèi)用為14 963 323.00元,優(yōu)化后布局在遺傳算法布局的基礎(chǔ)上物料搬運(yùn)費(fèi)用降低了9.34%;原始布局的非物流關(guān)系密切度為60.8%,遺傳算法求解的密切度為57.4%,利用改進(jìn)和聲搜索算法優(yōu)化后的密切度為63.2%,優(yōu)化后布局在遺傳算法布局的基礎(chǔ)上非物流關(guān)系密切度提升了10.1%。優(yōu)化后得到的車間布局作業(yè)單位布局如圖6所示。

圖5 兩種算法迭代曲線

圖6 優(yōu)化后車間布局圖

根據(jù)圖6和Matlab運(yùn)行結(jié)果,得出各個(gè)作業(yè)單位的位置坐標(biāo)如表5所示。

表5 優(yōu)化后作業(yè)單位位置坐標(biāo)

4 結(jié)論

(1)針對(duì)多目標(biāo)車間布局優(yōu)化問題,同時(shí)考慮物流與非物流關(guān)系對(duì)車間布局的影響,提出了建立以物料搬運(yùn)費(fèi)用最小和非物流關(guān)系密切度最大為目標(biāo)函數(shù)的優(yōu)化模型,并利用改進(jìn)和聲搜索算法和遺傳算法分別進(jìn)行模型求解。

(2)為了避免標(biāo)準(zhǔn)和聲搜索算法過早收斂陷入局部最優(yōu)情況,引入了遺傳算法的交叉、逆序變異操作,提高了和聲搜索算法的全局尋優(yōu)能力。

(3)通過6個(gè)不同規(guī)模的算例驗(yàn)證了改進(jìn)和聲搜索算法的有效性,并通過對(duì)算例Cy23的具體求解,發(fā)現(xiàn)利用改進(jìn)和聲搜索算法得出的優(yōu)化后車間布局方案比利用標(biāo)準(zhǔn)遺傳算法得出的物料搬運(yùn)費(fèi)用降低了9.34%,非物流關(guān)系密切度提高了10.10%,從而證明該方法具有較強(qiáng)的尋優(yōu)能力。

(4)在實(shí)際生產(chǎn)中,影響設(shè)施布局的因素眾多,為了簡化計(jì)算筆者主要考慮了固定約束、邊界約束和間距約束,布局優(yōu)化的數(shù)學(xué)模型還需要結(jié)合實(shí)際生產(chǎn)情況進(jìn)一步完善。