基于NSGAⅡ的生產(chǎn)線緩存與設(shè)備布局協(xié)同優(yōu)化

李愛平， 于海斌， 傅 翔， 范國良

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

李愛平， 于海斌， 傅 翔， 范國良

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

為解決因布局過程忽略或粗略設(shè)置緩沖區(qū)占地面積而造成的生產(chǎn)擁擠或空間浪費(fèi)問題，針對(duì)緩存配置與設(shè)備布局問題展開協(xié)同優(yōu)化.基于連續(xù)時(shí)間Markov隨機(jī)過程原理建立排隊(duì)網(wǎng)節(jié)點(diǎn)狀態(tài)模型，求解生產(chǎn)線設(shè)備平均利用率.以設(shè)備利用率、物料搬運(yùn)距離和占地面積為優(yōu)化目標(biāo)，建立緩存配置與設(shè)備布局協(xié)同優(yōu)化模型.通過改進(jìn)的NSGA-Ⅱ算法對(duì)該模型進(jìn)行優(yōu)化.最終，通過某柴油機(jī)缸體生產(chǎn)線實(shí)例驗(yàn)證了本文提出方法的有效性.

設(shè)備布局； 緩存配置； 協(xié)同優(yōu)化； Markov隨機(jī)過程； 排隊(duì)網(wǎng)； NSGA-Ⅱ算法

設(shè)備布局問題(facility layout problem，F(xiàn)LP)是制造系統(tǒng)中的研究重點(diǎn)和熱點(diǎn)，合理的設(shè)備布局設(shè)計(jì)可提高生產(chǎn)效率、降低制造成本、縮短生產(chǎn)周期.因此，設(shè)備布局設(shè)計(jì)理論在新建、擴(kuò)建、改建制造企業(yè)中具有廣闊應(yīng)用前景[1].自Muther[2]提出系統(tǒng)布局規(guī)劃方法以來，國內(nèi)外學(xué)者對(duì)FLP進(jìn)行了大量研究.Wang等[3]和Hernandez等[4]先后采用改進(jìn)的遺傳算法對(duì)占地面積不同的設(shè)備展開生產(chǎn)線布局優(yōu)化.Yang等[5]對(duì)柔性制造系統(tǒng)中的設(shè)備布局問題進(jìn)行研究，并基于空間填充曲線對(duì)傳統(tǒng)模擬退火算法進(jìn)行改進(jìn).Kazi等[6]以物料搬運(yùn)成本及非物流關(guān)系為優(yōu)化目標(biāo)，曾強(qiáng)等[7]以物料搬運(yùn)成本、非物流關(guān)系及占地面積為優(yōu)化目標(biāo)，Giuseppe等[8]以物料搬運(yùn)成本、設(shè)備長寬比、非物流關(guān)系及距離要求為優(yōu)化目標(biāo)分別對(duì)設(shè)備布局進(jìn)行多目標(biāo)優(yōu)化.鄭永前等[9]采用一種協(xié)同粒子群算法對(duì)生產(chǎn)線設(shè)備進(jìn)行單元布局設(shè)計(jì).

同樣，緩存配置問題(Buffer Allocation Problem，BAP)也是制造系統(tǒng)中的一個(gè)研究熱點(diǎn).近幾十年來，國內(nèi)外學(xué)者也進(jìn)行了較多深入的研究.文獻(xiàn)[9]指出，由于生產(chǎn)線各工位的實(shí)際作業(yè)時(shí)間一般屬于隨機(jī)變化量，因此會(huì)造成局部堵塞，嚴(yán)重時(shí)甚至造成全線中斷，而生產(chǎn)線中緩沖區(qū)配置則能很好地解決工位間的不平衡性.Malathronas等[10]為雙工位單機(jī)床及單緩沖區(qū)的簡單問題建立了可用度解析模型，但串行生產(chǎn)線的狀態(tài)會(huì)隨著機(jī)床的增加呈指數(shù)增長，使得該方法只適用于小規(guī)模的問題求解.Yeralan等[11]提出一種基于分解法的多級(jí)串行生產(chǎn)線可用度與緩沖區(qū)容量的關(guān)聯(lián)模型.宋士剛等[12]根據(jù)緩沖區(qū)容量、機(jī)床可用度和任務(wù)需求之間的關(guān)系，在滿足生產(chǎn)任務(wù)的前提下，提出一種改進(jìn)的粒子群算法，對(duì)緩沖區(qū)容量進(jìn)行優(yōu)化.李翔等[13]針對(duì)多級(jí)流水生產(chǎn)線緩沖區(qū)容量優(yōu)化問題，考慮各工序節(jié)點(diǎn)間的耦合關(guān)系，基于馬爾可夫隨機(jī)過程原理建立流水生產(chǎn)線排隊(duì)網(wǎng)節(jié)點(diǎn)模型，求解緩沖區(qū)容量和任務(wù)拒絕率之間的關(guān)系，并提出一種啟發(fā)式優(yōu)化算法對(duì)生產(chǎn)線緩沖區(qū)容量進(jìn)行優(yōu)化.

然而，單獨(dú)考慮FLP時(shí)，一般為簡化問題，僅在工位間預(yù)設(shè)固定的安全距離以滿足物流緩存的要求，卻忽略了不同工位對(duì)緩存配置面積的需求差異性，導(dǎo)致對(duì)生產(chǎn)線占地面積與物料搬運(yùn)距離等生產(chǎn)線關(guān)鍵目標(biāo)參數(shù)的錯(cuò)誤估算，使優(yōu)化結(jié)果不再具備實(shí)際意義.因此，針對(duì)FLP與BLP的協(xié)同優(yōu)化存在較大意義.近年來，國內(nèi)外也有少量研究協(xié)同考慮了該問題.Yamamoto等[14]先求解合理的緩存配置，然后將緩沖區(qū)的占地面積加以考慮進(jìn)行布局設(shè)計(jì).Irohara等[15]以物料搬運(yùn)距離為優(yōu)化目標(biāo)對(duì)設(shè)備布局進(jìn)行優(yōu)化，再以生產(chǎn)率為優(yōu)化目標(biāo)對(duì)已得到布局方案進(jìn)行緩存配置的優(yōu)化.陳行豐等[16]構(gòu)建了隨時(shí)間變化的緩沖區(qū)面積計(jì)算模型，并對(duì)離散型加工生產(chǎn)線的存放待加工工件的緩沖區(qū)域面積進(jìn)行分配.

上述文獻(xiàn)均對(duì)FLP 和BAP兩問題進(jìn)行了分步優(yōu)化，未將2個(gè)問題的優(yōu)化真正結(jié)合.黃君政等[17]以在制品持有費(fèi)用、緩沖區(qū)配置費(fèi)用和物料搬運(yùn)費(fèi)用的總和為優(yōu)化目標(biāo)，提出與空間填充曲線結(jié)合的遺傳算法，對(duì)考慮緩沖區(qū)面積的串聯(lián)生產(chǎn)線布局進(jìn)行優(yōu)化，但未考慮生產(chǎn)線中常見的并行工位.

因此，本文在前人研究的基礎(chǔ)上，針對(duì)FLP與BAP兩問題展開協(xié)同優(yōu)化.針對(duì)存在并行工位的生產(chǎn)線，提出并行設(shè)備的排隊(duì)網(wǎng)模型構(gòu)建方法，在傳統(tǒng)布局優(yōu)化目標(biāo)物料搬運(yùn)距離和占地面積的基礎(chǔ)上，引入緩存配置直接影響的設(shè)備利用率作為協(xié)同優(yōu)化目標(biāo)，建立協(xié)同優(yōu)化模型，改進(jìn)NSGA-Ⅱ算法并用以求解模型，進(jìn)而實(shí)現(xiàn)FLP與BAP的協(xié)同優(yōu)化.

1 緩存配置與設(shè)備布局的協(xié)同優(yōu)化模型

1.1 問題描述

假設(shè)生產(chǎn)線由至少K臺(tái)設(shè)備及與之對(duì)應(yīng)的前置緩沖區(qū)組成，如圖1所示.Mi表示第i臺(tái)設(shè)備，Bi表示第i臺(tái)設(shè)備前置緩沖區(qū).整線加工任務(wù)到達(dá)率均為服從參數(shù)為λ的泊松分布，各設(shè)備的加工時(shí)間服從參數(shù)為μ1，μ2，…，μK的負(fù)指數(shù)分布.生產(chǎn)線為長寬已知的矩形區(qū)域，各設(shè)備及緩沖配置區(qū)的形狀均為矩形.設(shè)備尺寸已知，緩沖區(qū)尺寸則隨相應(yīng)配置容量伸縮.生產(chǎn)線采用多行布局形式，設(shè)備及其前置緩存配置區(qū)平行于生產(chǎn)線邊界放置.設(shè)備及緩沖區(qū)的最小水平間距和最小縱向間距視生產(chǎn)線的實(shí)際情況確定.

圖1 生產(chǎn)線緩存配置模型Fig.1 Buffer allocation model in production line

1.2 模型優(yōu)化目標(biāo)

物料搬運(yùn)距離和占地面積是生產(chǎn)線布局優(yōu)化最常見的2個(gè)優(yōu)化目標(biāo)，減小物流搬運(yùn)距離和占地面積都是為了使生產(chǎn)線能夠更高效地生產(chǎn).當(dāng)緩存配置不合理時(shí)，生產(chǎn)線會(huì)出現(xiàn)不同程度的堵塞和空閑，設(shè)備利用率大幅度下降.所以，生產(chǎn)線所有設(shè)備的平均利用率也能很大程度上反映整個(gè)生產(chǎn)線的生產(chǎn)效率，對(duì)生產(chǎn)線的設(shè)計(jì)規(guī)劃有一定的指導(dǎo)意義.因此，將設(shè)備利用率(F1)和物料搬運(yùn)距離(F2)、占地面積(F3)作為優(yōu)化目標(biāo)，具體如下.

1.2.1F1最大

李翔等[13]對(duì)串聯(lián)模型中的設(shè)備利用率進(jìn)行了求解.然而，生產(chǎn)線中普遍存在并行工位，本文在串聯(lián)模型研究的基礎(chǔ)上，建立存在并聯(lián)設(shè)備的排隊(duì)網(wǎng)模型.模型中的設(shè)備分為正常設(shè)備和并聯(lián)設(shè)備2類，正常設(shè)備的狀態(tài)轉(zhuǎn)移速率平衡方程如式(1)所示.

(1)

(2)

(3)

(4)

式中：Pv,i為設(shè)備i處于阻塞狀態(tài)的概率；P0,i為設(shè)備i處于空閑狀態(tài)的概率；λi為設(shè)備i的工件平均到達(dá)速率.

對(duì)模型中正常設(shè)備和并聯(lián)設(shè)備參數(shù)計(jì)算進(jìn)行總結(jié)，如表1所示.

表1 設(shè)備參數(shù)Tab.1 Parameters of facilities

在求出設(shè)備的各種狀態(tài)后，可得所有設(shè)備的平均利用率求解公式，如式(5)所示.

(5)

式中：Πn,ω,i表示設(shè)備i對(duì)應(yīng)的概率.

1.2.2F2最小

物料搬運(yùn)距離決定著物流成本，關(guān)系到企業(yè)的經(jīng)濟(jì)效益，一個(gè)工件在設(shè)備間總的搬運(yùn)距離可描述為

(6)

式中：Δi,j為物料在設(shè)備i及其緩沖區(qū)和設(shè)備j及其緩沖區(qū)之間搬運(yùn)的次數(shù)；Γi,j為設(shè)備i及其緩沖區(qū)與設(shè)備j及其緩沖區(qū)之間的矩形距離，Γi,j=|xi-xj|+|yi-yj|.

1.2.3F3最小

設(shè)備布局應(yīng)考慮緊湊性原則，即應(yīng)降低生產(chǎn)線的占地面積，占地面積可描述為

(7)

式中：Lline為生產(chǎn)線的長度；s為設(shè)備及緩沖區(qū)的縱向行間距；s0為設(shè)備及緩沖區(qū)和生產(chǎn)線的上邊界及下邊界之間的縱向最小距離；C為布局方案中設(shè)備的總行數(shù)；ω1，ω2分別為第1行設(shè)備和最后1行設(shè)備的寬度.

2 緩存配置與設(shè)備布局的協(xié)同優(yōu)化算法設(shè)計(jì)

多目標(biāo)優(yōu)化算法的核心在于協(xié)調(diào)各目標(biāo)函數(shù)之間的關(guān)系，Deb[18]提出的NSGA-Ⅱ算法可以較好地求解多目標(biāo)問題.本文采用該算法，并根據(jù)協(xié)同優(yōu)化模型的特點(diǎn)，對(duì)傳統(tǒng)NSGA-Ⅱ算法的編碼、交叉和變異操作分別進(jìn)行改進(jìn).其中，對(duì)染色體編碼過程進(jìn)行改造，引入緩沖區(qū)容量部分，交叉和變異過程則根據(jù)染色體3個(gè)優(yōu)化目標(biāo)的值進(jìn)行調(diào)整.

2.1 協(xié)同優(yōu)化算法的流程設(shè)計(jì)

流程步驟為：①迭代次數(shù)t=0，初始化種群P0，種群規(guī)模為U，對(duì)其進(jìn)行擁擠度及非支配排序值計(jì)算.②根據(jù)初始化種群P0中個(gè)體的擁擠度及非支配排序值大小進(jìn)行選擇操作，經(jīng)過交叉及變異后得到規(guī)模為U的子種群Q0.③合并Pt和Qt(t為迭代次數(shù))，形成種群規(guī)模為2U的種群Rt.④對(duì)Rt進(jìn)行非支配排序，得到k個(gè)非支配集E1，E2，…，Ek，其中E1為最優(yōu)非支配解集，E2為次優(yōu)非支配解集，依次類推.⑤從E1起依次取染色體個(gè)體直到總數(shù)超過U個(gè)，此時(shí)的非支配集為Ei.⑥由于E1，E2，…，Ei中染色體個(gè)體數(shù)量之和大于U，則對(duì)Ei中的染色體個(gè)體進(jìn)行擁擠度計(jì)算.選擇E1至Ei-1中的全部個(gè)體和Ei中較好的個(gè)體一起組成規(guī)模為U的新種群Pt+1.⑦對(duì)新種群Pt+1進(jìn)行選擇、交叉和變異，形成Qt+1.重復(fù)③至⑦，直至t=G(G為最大迭代次數(shù))，即可得到優(yōu)化解集.

2.2 協(xié)同優(yōu)化算法的操作設(shè)計(jì)

2.2.1 編碼

在傳統(tǒng)設(shè)備布局問題遺傳算法的編碼中，只對(duì)設(shè)備編號(hào)進(jìn)行編碼，本文在染色體設(shè)備編號(hào)的序列后加入設(shè)備對(duì)應(yīng)緩沖區(qū)容量大小的序列，如下：

(8)

式中：Ni取值范圍為[Nmin，Nmax].

2.2.2 交叉

傳統(tǒng)的交叉操作是按照設(shè)定的交叉概率pc，用PMX(部分映射交叉)方法對(duì)染色體進(jìn)行交叉操作.但由于染色體中M對(duì)F2響較大、對(duì)F1和F3影響較小，而染色體中N對(duì)F1影響較大、對(duì)F2和F3較小，所以，本文提出一種選擇性的染色體分段交叉策略.

在分段交叉過程中，分別針對(duì)F1，F(xiàn)2和F3在整個(gè)種群中的優(yōu)劣進(jìn)行排序(從優(yōu)到劣)，第α條染色體各目標(biāo)在種群的排序中所處位置為R1,α，R2,α，R3,α，第β條為R1,β，R2,β，R3,β.此處引入函數(shù)f(x)，其表示隨機(jī)生成介于0與x之間一個(gè)小數(shù).在第α條和第β條染色體交叉過程中，作如下判斷：若f(R1，α)+f(R1，β)≥f(R2，α)+f(R2，β)，則對(duì)N進(jìn)行交叉，若f(R1，α)+f(R1，β)

2.2.3 變異

同樣，傳統(tǒng)的變異操作是按照設(shè)定的概率pm對(duì)染色體進(jìn)行變異操作.變異操作的改進(jìn)如下:對(duì)于i條染色體，若f(R1,α)≥f(R2，α)，則對(duì)N進(jìn)行變異，若f(R1,α)

2.2.4 解碼

為使一個(gè)染色體對(duì)應(yīng)唯一的布局方案，解碼方式設(shè)計(jì)如下：按照染色體[M，N]從最上方的一行開始，對(duì)設(shè)備及緩沖區(qū)進(jìn)行布局，如果同一行內(nèi)的各設(shè)備長度、緩沖區(qū)長度及間距之和大于生產(chǎn)線的長度，那么最后1臺(tái)設(shè)備及其緩沖區(qū)到下一行進(jìn)行布局.

生產(chǎn)線設(shè)備及緩沖區(qū)的具體布局解碼方法如圖2所示，li為設(shè)備i的長度；di為設(shè)備i的寬度；Li為緩沖區(qū)Bi的長度；Di為緩沖區(qū)Bi的寬度；h0,i為設(shè)備i及其緩沖區(qū)與生產(chǎn)線邊界間的橫向最小距離；hi,j為設(shè)備i及其緩沖區(qū)和設(shè)備j及其緩沖區(qū)間的橫向最小距離.

設(shè)備的坐標(biāo)(xi，yi)及緩沖區(qū)坐標(biāo)(Xi，Yi)的求解公式為

圖2 考慮緩沖區(qū)面積的設(shè)備布局Fig.2 Facility layout considering buffer space

(9)

要求一臺(tái)設(shè)備只能出現(xiàn)一次(設(shè)備i在q行上時(shí)zi,q=1，其他情況下zi,q=0)，即

(10)

同時(shí)，每臺(tái)設(shè)備的坐標(biāo)及設(shè)備的前置緩沖區(qū)的坐標(biāo)均為非負(fù)值.

(11)

2.2.5 懲罰函數(shù)

生產(chǎn)線設(shè)備布局時(shí)一般會(huì)產(chǎn)生2種非法解：超出生產(chǎn)線邊界和設(shè)備重疊.本布局方法只會(huì)產(chǎn)生最后1行設(shè)備在y方向上超過生產(chǎn)線的最大縱向?qū)挾萕的情況.P表示y方向超出生產(chǎn)線縱向最大寬度W時(shí)的懲罰項(xiàng)，如式(12)所示，式中δ=(C-1)s+s0+0.5max(ω1)-(s0-0.5max(ω2)).對(duì)于每條染色體，在利用NSGA-Ⅱ進(jìn)行非支配排序時(shí)，目標(biāo)1除以P，目標(biāo)2和目標(biāo)3的值分別乘以P，從而達(dá)到淘汰不合格染色體的目的.

(12)

式中：T為一個(gè)按實(shí)際情況所取的大于1的數(shù).

3 實(shí)例仿真分析

某企業(yè)擬新建柴油發(fā)動(dòng)機(jī)缸體加工生產(chǎn)線，該生產(chǎn)線長為38 m，寬為30 m，根據(jù)生產(chǎn)綱領(lǐng)及工藝要求，該生產(chǎn)線預(yù)計(jì)將投入組合自動(dòng)線、加工中心等共計(jì)12臺(tái)設(shè)備，各設(shè)備尺寸、類型及其加工內(nèi)容如表2所示.

表2 設(shè)備尺寸及類型Tab.2 Size and type of facilities

設(shè)備i旁并排放置Ci個(gè)貨架，貨架用于存放待加工缸體(即緩存配置區(qū))，其中單個(gè)貨架的長度L0=0.4 m，寬度D0=2.8 m，容量n0=1.則緩存配置區(qū)寬度即貨架長度L0、貨架數(shù)目Ci及緩存配置區(qū)長度Li如式(13)至(14)所示.

(13)

(14)

設(shè)備與生產(chǎn)線上下邊界的距離為1.5 m，設(shè)備縱向行間距為6 m，生產(chǎn)線設(shè)備拓?fù)淙鐖D3所示.外部工件到達(dá)率為9個(gè)·h-1，即工件的到達(dá)服從參數(shù)λ為9的泊松分布，各工位名義加工時(shí)間服從參數(shù)為μ1，μ2，…，μK的負(fù)指數(shù)分布，如表2所示.

圖3 加工設(shè)備拓?fù)銯ig.3 Topological graph of facilities

物料在設(shè)備i和設(shè)備j之間搬運(yùn)次數(shù)Δi,j如表3，設(shè)備i及其緩沖區(qū)和設(shè)備j及其緩沖區(qū)間的橫向最小距離hi,j=1.5 m，設(shè)備i及其緩沖區(qū)與生產(chǎn)線邊界間的橫向最小距離h0,i=2.染色體中緩沖區(qū)容量的最小值Nmin=0，最大值Nmax=6.在優(yōu)化時(shí)種群數(shù)量U取100，最大遺傳代數(shù)G取100，交叉率pc取0.7，變異率pm取0.2，懲罰函數(shù)P中T的值取2.

表3 物料在各設(shè)備間的搬運(yùn)次數(shù)矩陣Tab.3 Material handing times between facilities

為驗(yàn)證本文協(xié)同優(yōu)化模型和算法改進(jìn)的有效性，此處采用傳統(tǒng)NSGA-Ⅱ算法分別對(duì)文獻(xiàn)[15]模型和協(xié)同優(yōu)化模型進(jìn)行求解，再采用針對(duì)協(xié)同優(yōu)化模型改進(jìn)的NSGA-Ⅱ算法對(duì)協(xié)同優(yōu)化模型進(jìn)行求解.

選用計(jì)算機(jī)的硬件參數(shù)為Intel i7處理器、4GB內(nèi)存，通過MATLAB 7.0軟件實(shí)現(xiàn)算法運(yùn)算，采用傳統(tǒng)NSGA-Ⅱ算法分別求解文獻(xiàn)[15]模型和協(xié)同優(yōu)化模型20次，再采用本文改進(jìn)算法求解協(xié)同優(yōu)化模型20次，結(jié)果如表4所示.表4中Frmean和Frbest(r=1，2，3)分別表示3個(gè)目標(biāo)函數(shù)在20次求解中的平均值和最值.圖4為求解仿真實(shí)例所得3個(gè)目標(biāo)函數(shù)平均值和最值得分布情況.

表4 模型與算法比較Tab.4 Comparison between models and algorithms

a 設(shè)備利用率

b 物料搬運(yùn)距離

c 占地面積圖4 3個(gè)優(yōu)化目標(biāo)平均值在不同模型及算法下的分布Fig.4 Average values of 3 objectives in different models and algorithms

(1)觀察表4中傳統(tǒng)NSGA-Ⅱ求解部分及圖4中3個(gè)優(yōu)化目標(biāo)平均值分布可得：采用傳統(tǒng)NSGA-Ⅱ分別對(duì)兩模型進(jìn)行求解，協(xié)同優(yōu)化模型3個(gè)優(yōu)化目標(biāo)的平均值均略優(yōu)于文獻(xiàn)[15]模型，且單純觀察F1和F2兩目標(biāo)的最優(yōu)值較文獻(xiàn)[15]模型也有一定的提升，證明協(xié)同優(yōu)化模型的有效性.

(2)觀察表4中本文協(xié)同優(yōu)化模型求解部分及圖4中3個(gè)優(yōu)化目標(biāo)平均值分布可得：本文算法所得3個(gè)優(yōu)化目標(biāo)的平均值均優(yōu)于傳統(tǒng)NSGA-Ⅱ算法，其單純觀察目標(biāo)F2的最優(yōu)值也好于傳統(tǒng)NSGA-Ⅱ算法，證明本文算法較傳統(tǒng)NSGA-Ⅱ算法具有更好的尋優(yōu)能力.圖5給出了本文算法及傳統(tǒng)NSGA-Ⅱ算法對(duì)協(xié)同優(yōu)化模型求解時(shí)的收斂圖.隨著遺傳代數(shù)的增加，本文算法中F1的平均值和最大值總體上逐漸上升，F(xiàn)2和F3的平均值和最小值總體上逐漸下降.采用本文算法求解時(shí)，3個(gè)目標(biāo)在分別進(jìn)化50代、80代和85代后趨于平穩(wěn)，說明本文算法可以使3個(gè)目標(biāo)同時(shí)得到優(yōu)化.

a 設(shè)備利用率

b 物料搬運(yùn)距離

c 占地面積圖5 優(yōu)化過程Fig.5 Optimization procedure

圖6為采用改進(jìn)算法對(duì)協(xié)同優(yōu)化模型進(jìn)行求解時(shí)的Pareto解集.如表5所示，實(shí)例的3個(gè)優(yōu)化目標(biāo)的最優(yōu)解分別為F1best=81.92%(方案b)，F(xiàn)2best=74.15(方案a)，F(xiàn)3best=760(方案c)，沒有一個(gè)方案可以使3個(gè)目標(biāo)同時(shí)達(dá)到最優(yōu).方案a設(shè)備利用率最優(yōu)，但物料搬運(yùn)距離過大.方案b設(shè)備利用率較高，物料搬運(yùn)距離最優(yōu)，但占地面積過大.方案c占地面積最優(yōu)，但縮小了緩沖區(qū)容量且沒有盡量保證整個(gè)生產(chǎn)線的平衡，設(shè)備利用率很低.方案d和方案e是整體上3個(gè)目標(biāo)值都較優(yōu)的方案，方案e在占地面積上略好于方案d，而方案d在設(shè)備利用率和物料搬運(yùn)距離上都明顯好于方案e，所以為生產(chǎn)線選用了布局方案d，如表6及圖7所示.圖7中刻度值表示生產(chǎn)線的長度采用Plant Simulation軟件對(duì)企業(yè)擬選方案的設(shè)備利用等關(guān)鍵參數(shù)展開了仿真驗(yàn)證，仿真模型如圖8所示.設(shè)備利用率仿真結(jié)果如圖9所示，其整線設(shè)備的平均利用率為81.19%，與前文協(xié)同優(yōu)化模型求解結(jié)果(80.92%)基本一致，誤差約為0.3%.采用分析物流常用的Sankey圖，對(duì)物流路徑的物流負(fù)荷進(jìn)行分析，線段的粗細(xì)代表物流負(fù)荷的大小，如圖10，物流負(fù)荷比較均勻，證明了方案布局的合理性.

圖6 協(xié)同優(yōu)化模型的Pareto解集Fig.6 Pareto optimal set of collaborative optimization model 表5 協(xié)同優(yōu)化備選方案Tab.5 Optional solutions

方案染色體F1/%F2F3a[{1，12，11，10，2，6，8，9，4，5，7，3}{6，6，6，6，4，6，6，6，6，6，4，3}]81．6374．151020b[{1，3，11，10，2，7，8，9，6，5，12，4}{6，6，6，6，6，6，6，6，6，6，6，6}]81．92106．60790c[{1，3，9，10，2，6，12，11，4，5，8，7}{6，6，6，6，5，5，2，4，6，4，2，2}]78．2384．45760d[{1，12，11，10，2，3，6，9，4，5，7，8}{6，6，6，6，4，5，5，5，4，4，5，6}]80．9275．30780e[{1，6，11，10，2，3，12，9，4，5，7，8}{6，6，6，6，4，6，3，4，3，4，5，4}]80．2577．20770

表6 企業(yè)選用方案設(shè)備坐標(biāo)Tab.6 Coordinates of facilities

圖7 企業(yè)擬選方案Fig.7 Adopted solution

圖8 擬選方案的仿真

Fig.8 Simulation of adopted solution

圖9 擬選方案仿真結(jié)果界面Fig.9 Simulation results interface of adopted solution

4 結(jié)語

對(duì)緩沖區(qū)的實(shí)際占地面積加以考慮，使設(shè)備布局更接近生產(chǎn)線實(shí)際情況.引入同樣能夠較好反映生產(chǎn)線效率的設(shè)備利用率，結(jié)合物料搬運(yùn)距離、占地面積作為優(yōu)化目標(biāo)，建立協(xié)同優(yōu)化模型.設(shè)計(jì)基于NSGA-Ⅱ的協(xié)同優(yōu)化算法對(duì)模型進(jìn)行求解，得到協(xié)同優(yōu)化方案.該方法在設(shè)計(jì)階段可為決策者提供同時(shí)考慮緩存配置和設(shè)備布局的規(guī)劃方案，能夠精簡生產(chǎn)線空間，提升生產(chǎn)效率，具備較大優(yōu)勢(shì).

圖10 物流強(qiáng)度Sankey圖

Fig.10 Sankey diagram of material handling

[1] 鎖小紅. 基于制造系統(tǒng)功能的設(shè)施布局設(shè)計(jì)研究[D]. 濟(jì)南：山東大學(xué), 2008.

SUO Xiaohong. Investigation on facility layout design based on manufacturing system functionality[D]. Jinan: Shandong University, 2008.

[2] Muther R A. Systematic layout planning[M]. 2nd ed. Boston: Management and Industrial Research Publications, 1973.

[3] Wang Ming-Jaan, Hu Michael H, Ku Meei-Yuh. A solution to the unequal area facilities layout problem by genetic algorithm[J]. Computers in Industry, 2005, 56(2): 207.

[4] Garcia-Hernandez L, Pierreval H, Salas-Morera L,etal. Handling qualitative aspects in unequal area facility layout problem: An interactive genetic algorithm[J]. Applied Soft Computing Journal, 2013, 13: 1718.

[5] Yang Taho, Peters Brett A, Tu Mingan. Layout design for flexible manufacturing systems considering single-loop directional flow patterns[J]. European Journal of Operational Research, 2005, 164:440.

[6] Kazi Shah Nawaz Ripon, Kyrre Glette, Kashif Nizam Khan,etal. Adaptive variable neighborhood search for solving multi-objective facility layout problems with unequal area facilities[J]. Swarm and Evolutionary Computation, 2013, 8: 1.

[7] 曾強(qiáng), 沈玲, 潘啟東, 等. 基于NSGA-Ⅱ的多目標(biāo)車間設(shè)施布局優(yōu)化方法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2012, 48(27): 223.

ZENG Qiang, SHEN Ling, PAN Qidong,etal. Multi-objective optimization method for workshop facility layout based on NSGA-Ⅱ[J]. Computer Engineering and Applications, 2012, 48(27): 223.

[8] Giuseppe Aiello, Giada La Scalia, Mario Enea. A multi objective genetic algorithm for the facility layout problem based upon slicing structure encoding[J]. Expert Systems with Applications, 2012, 39: 10352.

[9] 鄭永前, 丁奎學(xué), 王陽. 基于協(xié)同粒子群算法的單元集成布局方法[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2012, 18(5): 950.

ZHENG Yongqian, DING Kuixue, WANG Yang. Integrated cellular layout design based on cooperative particle swarm optimizaztion[J]. Computer Integrated Manufacturing Systems, 2012, 18(5): 950.

[10] Malathronas J P, Perkins J D, Smith R L. The availability of a system of two unreliable machines connected by an intermediate storage tank[J]. AIIE Transactions, 1982, 15(3): 195.

[11] Yeralan S, Feanck W E, Quasem M A. A continuous materials flow production line with station breakdown [J]. European Journal of Operational Research, 1986, 27(3): 289.

[12] 宋士剛, 李愛平, 徐立云. 可重組制造系統(tǒng)緩沖區(qū)容量的優(yōu)化研究[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2008, 14(10): 1951.

SONG Shigang, LI Aiping, XU Liyun. Buffer capacity optimization in reconfigurable manufacturing system[J]. Computer Integrated Manufacturing Systems, 2008, 14(10): 1951.

[13] 李翔, 陳慶新, 毛寧. 基于排隊(duì)網(wǎng)模型的流水車間緩沖區(qū)容量優(yōu)化[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2014, 20(4): 890.

LI Xiang, CHEN Qingxin, MAO Ning. Buffer allocation on optimization of flow shop based on queering network model[J]. Computer Integrated Manufacturing Systems, 2014, 20(4): 890.

[14] Yamamoto H, Qudeiri J, Jamali M. Concurrent production engineering system for buffer size and flexible transfer line layout design[J]. Journal of Systems Science and Systems Engineering, 2008, 17: 187.

[15] Irohara T, Yamashita H, Ishizuka Y. Facility layout problem with buffer space allocation for throughput and material handling cost[J]. Journal of Japan Industrial Management Association, 2007, 53(2): 363.

[16] 陳行豐, 魯建廈, 李英德. 離散型制造企業(yè)車間布局緩沖區(qū)面積設(shè)置仿真決策研究[J]. 浙江工業(yè)大學(xué)學(xué)報(bào), 2010, 38(3): 246.

CHEN Xingfeng, LU Jiansha, LI Yingde. Simulation decision-making study of buffer area allocation in workshop layout of a discrete manufacturing enterprise[J]. Journal of Zhejiang University of Technology, 2010, 38(3): 246.

[17] 黃君政, 李愛平, 劉雪梅, 等. 考慮緩沖區(qū)配置的生產(chǎn)線布局優(yōu)化設(shè)計(jì)[J]. 同濟(jì)大學(xué)學(xué)報(bào)：自然科學(xué)版, 2015, 43(7): 1075.

HUANG Junzheng, LI Aiping, LIU Xuemei,etal. Optimal design of production line layout considering buffer allocation[J]. Journal of Tongji University: Natural Science, 2015, 43(7): 1075.

[18] Deb K. A fast and elitist multi-objective genetic algorithm: NSGA-Ⅱ[J]. IEEE Transaction on Evolutionary Computation, 2002, 6(2): 180.

Collaborative Optimization Method of Buffer and Facility Layout in Production Lines Based on NSGA-Ⅱ Algorithm

LIAiping，YUHaibin，F(xiàn)UXiang，F(xiàn)ANGuoliang

(School of Mechanical Engineering, Tongji University, Shanghai 201804, China)

To reduce the congestion or wasted space caused by neglected space of buffer, the collaborative optimization of buffer allocation problem and facility layout problem was presented. Based on continuous-time Markov stochastic process theory, a queuing network node state model was established to solve utilization rate of facilities. A collaborative optimization model was built considering the utilization rate of facilities, material handling distance and floor area. The collaborative optimization model was calculated using improved NSGA-Ⅱ. A case study of diesel engine cylinder block processing line was provided to prove the effectiveness of the proposed method.

facility layout; buffer allocation; collaborative optimization; Markov stochastic process; queuing network; NSGA-Ⅱ algorithm

2016-01-25

國家高檔數(shù)控機(jī)床與基礎(chǔ)制造裝備科技重大專項(xiàng)(2011ZX04015-022)

李愛平(1951—)，女，教授，博士生導(dǎo)師，工學(xué)博士，主要研究方向?yàn)橹圃煜到y(tǒng)與自動(dòng)化、數(shù)字化設(shè)計(jì)與制造等. E-mail：limuzi@#edu.cn

TB491

A