離散生產(chǎn)系統(tǒng)車間布置優(yōu)化研究

離散生產(chǎn)系統(tǒng)車間布置優(yōu)化研究

1單元面積不符解的消除在生產(chǎn)系統(tǒng)的運作過程中，材料的運輸成本占生產(chǎn)量（除原材料成本外）的20%50%，合理的生產(chǎn)系統(tǒng)布局可以降低生產(chǎn)生產(chǎn)成本的10%30%。在多品種生產(chǎn)條件下,生產(chǎn)車間由多個生產(chǎn)單元(或工段)組成,各單元之間存在著包括物料轉(zhuǎn)移、人員往采、信息傳遞等關(guān)系。車間平面布置的主要任務(wù)是確定各單元的合理位置和面積形狀,從而使各單元在運行過程中能緊密銜接,減小運作過程的物料運輸工作量,實現(xiàn)運作過程高效率、低占用、低成本。在非等面積單元的平面布置問題中,各單元位置及其面積形狀是影響目標函數(shù)的主要因素。設(shè)有m個單元,單元i可選面積形狀有ni種,則總方案數(shù)為(∏mi=1ni)(∏mi=1ni)!,顯然,如此大的解空間即使用計算機進行搜索也是相當困難的。RussellD.Meller采用空格填充曲線法(Space-fillingCurve)縮減解空間,先把布置場所劃分成若干單位面積塊,然后用空格填充線按一定的算法規(guī)則連續(xù)不斷地歷經(jīng)所有單元格,布置過程按預(yù)定的單元順序、沿填充線走向,連續(xù)不斷地為各單元分配單位面積塊,一個單元分配完再分配下一單元,直至所有單元分配完畢,得到一個布置方案,改變單元布置順序可得到不同的方案?？崭裉畛渚€法可把解空間從(∏mi=1ni)(∏mi=1ni)!縮減為m!,同時避免了同一單元被分割的現(xiàn)象,但該法可能產(chǎn)生單元面積不規(guī)則的方案。解空間縮減為m!后,該問題還是NP-Completed問題。對于NP-Completed問題,當m較大時,采用解析法求最優(yōu)解幾乎是不可能的。目前多采用啟發(fā)式方法或計算機搜索算法求較優(yōu)解。JannyLeung提出的平面相鄰圖法就是一種啟發(fā)式方法,該法用圖形方式,以結(jié)點表示每一部門,滿足相鄰關(guān)系的兩部門(結(jié)點)間用一條弧線連接,采用啟發(fā)式法尋求使連接各相鄰部門弧線上的物流量達到最大的方案。啟發(fā)式法只能處理較簡單的布置問題,優(yōu)化效果也相對較差;近年來,不少學者把智能優(yōu)化算法應(yīng)用于計算機優(yōu)化搜索過程,有效地提高了設(shè)施布置優(yōu)化效果。計算機輔助設(shè)施布置系統(tǒng),容易產(chǎn)生不規(guī)則的面積形狀布置方案,對此,文獻采用邊長與面積的比值作為面積形狀約束條件,可在一定程度上避免出現(xiàn)不規(guī)則面積方案。筆者則提出兩階段優(yōu)化法,解決面積不等條件下的生產(chǎn)單元平面布置優(yōu)化問題,更具實際意義。2約束條件及約束條件件定義生產(chǎn)系統(tǒng)空間布置的目標函數(shù)有多種形式,常用的有:物流運輸成本最小化,綜合指標最優(yōu)化,約束條件包括:車間面積及其形狀、生產(chǎn)單元面積及形狀要求、位置有特殊要求的生產(chǎn)單元限制等。2.1單元距離運輸成本的模型以物料運輸成本最小化為目標函數(shù),影響因素有:單元之間的物流量fi,j,(從部門i運往部門j的物流量);單位物料單位距離運輸成本Cij,(單位運輸成本);單元之間的距離dij.目標函數(shù)模型如下:minm∑j=1m∑i=1fi,jci,jdi,j∑j=1m∑i=1mfi,jci,jdi,j。(1)物料運輸成本目標函數(shù)模型只考慮了車間內(nèi)部的運輸工作量,而沒有考慮物料從車間入口至出口的固定運輸工作,因而其實際優(yōu)化效果受到一定的影響。2.2部門j不相鄰maxm∑j=1m∑i=1fi,jci,jxi,jxi,j={1?部門i與部門j相鄰鄰0?部門i與部門j不相鄰。(2)max∑j=1m∑i=1mfi,jci,jxi,jxi,j={1?部門i與部門j相鄰鄰0?部門i與部門j不相鄰。(2)相鄰單元物料運輸費用最大化,實質(zhì)上是總運輸費用最小化目標函數(shù)的簡化形式。這類目標函數(shù)忽略了非相鄰布置單元之間的物流對運輸成本的影響,因而優(yōu)化效果有一定的局限性。3單元內(nèi)部距離法單元間的距離是計算目標函數(shù)的主要依據(jù),隨布置方案變化而變化。單元之間的距離可采用不同的計量方法,但不管采用那種計量方法,均要求便于正確描述實際布置問題,常用方法有如下兩種:1)中心距離法。是指以兩單元的中心點作為計算相互間距離的依據(jù)。適用于生產(chǎn)單元的物料輸入、輸出口的位置未明確的情況下。2)出入口距離法。出入口距離法是指以單元物料出入口為計算距離的依據(jù)。這種方法忽略了單元內(nèi)各設(shè)備至物料出入口位置的距離,計算距離一般小于實際距離。上述兩種方法,均可采用如下兩種不同路徑計算距離:1)沿單元之間的通道(邊界線)計算距離。物料通常是沿通道運輸?shù)?因而這種方法計算的距離與實際情況較為接近,但計算較為復(fù)雜。2)直線距離法。按連接兩單元的中心(或出入口)點的直線距離作為兩單元之間的運輸距離。直線距離法相對較為簡單,但與實際運輸路線距離有一定偏差。4腦癱機械處的平面布置4.1空間內(nèi)兩階段布置法如前所述,盡管計算機運算速度很快,但由于搜索空間過大,找到最優(yōu)解的難度也就很大。筆者提出用兩階段優(yōu)化方法,即先縮減解空間,在縮減空間內(nèi)搜索較優(yōu)解,再分配單元面積的方法。以下通過實例介紹兩階段布置法。設(shè)車間有12個生產(chǎn)單元,面積分別為:A-55,B-36,C-35,D-66,E-30,F-28,G-55,H-60,I-30,J-35,K-27,L-42,各單元之間的物流量關(guān)系見表1,車間面積形狀為20×25,生產(chǎn)單元按三行布置,目標函數(shù)為總的物料運輸成本最小化。4.1.1運輸成本的確定1)統(tǒng)計各單元間的物流量,如表1:2)把布置場所(車間)劃分成與單元數(shù)相等的若干個等面積區(qū)域,每一單元對應(yīng)布置在一個區(qū)域,并確定一個初步位置方案如圖1:3)設(shè)相鄰區(qū)域為1個單位距離,構(gòu)造出各區(qū)域?qū)?yīng)的距離矩陣表,見表2:4)設(shè)單位物料單位距離的運輸費為1,把物流矩陣表與距離矩陣表中的對應(yīng)元素相乘后累加,計算出初始位置方案的物料運輸成本:m∑j=1m∑i=1fi,jci,jdi,j=4862∑j=1m∑i=1mfi,jci,jdi,j=4862。5)采用模擬退火算法搜索較優(yōu)位置方案,得到優(yōu)化位置方案(見圖2)及其物流矩陣表(見表3):6)計算優(yōu)化位置后的物料運輸成本:m∑j=1m∑i=1fi,jci,jdi,j=4063∑j=1m∑i=1mfi,jci,jdi,j=4063。4.1.2單元應(yīng)分配的列格數(shù)根據(jù)優(yōu)化后的單元位置方案,結(jié)合車間面積形狀,按式(3)計算各行應(yīng)分配的行格數(shù)Xj和各單元應(yīng)分配的列格數(shù)Xi。{Xj=R?∑nii=1Ai/∑Νi=1AiXi=Ai/XjXi?Xj≥X*?(3)式中:ni=第i行擬布置的部門數(shù);Ai=部門i所需面積;N=部門總數(shù);R=車間面積細分行數(shù);X*=部門允許的最小寬度和長度(根據(jù)具體需要確定):1+65+27+65+35A=∑Νi=1Ai=30+42+28+60+35+36+30+55+65+27+55+35=498X1=20×(65+60+35+30)/498=7.62X2=20×(28+55+42+35)/498=6.42X3=20×(55+36+30+27)/498=5.822細胞系統(tǒng)的計算XD=AD/X1=65/7.62=8.53;XF=AF/X2=28/6.42=4.36;XH=AH/X1=60/7.62=7.87;XA=AA/X2=55/6.42=8.57;XC=AC/X1=35/7.62=4.59;XL=AL/X2=42/6.42=6.54;XI=AI/X1=30/7.62=3.93;XJ=AJ/X2=35/6.42=5.45;XG=AG/X3=55/5.82=9.45;XE=AE/X3=30/5.82=5.15;XB=AB/X3=36/5.82=6,18;XK=AK/X3=27/5.82=4.64。3整平并滿足單元面積形狀4)在圖3方案基礎(chǔ)上,對各單元面積形狀進行規(guī)整化處理,結(jié)果如圖4:規(guī)整化后各單元面積形狀均為矩形,滿足預(yù)定的面積形狀要求,且基本保持第一步確定的單元優(yōu)化位置關(guān)系。5單元面積形狀不確定。根據(jù)特點,直接確定了