申 寬,翟敬梅,張 鐵
(華南理工大學(xué) 機(jī)械與汽車工程學(xué)院,廣州 510641)
基于AGA的曲軸自動化生產(chǎn)車間多目標(biāo)優(yōu)化布局研究*
申 寬,翟敬梅,張 鐵
(華南理工大學(xué) 機(jī)械與汽車工程學(xué)院,廣州 510641)
為提高車間的生產(chǎn)效率、降低成本,對設(shè)備布局進(jìn)行優(yōu)化是十分必要的。基于物流費用最小和面積利用率最大的原則,并增加輔助設(shè)施(上下料機(jī)器人)對布局的約束,建立了曲軸自動化生產(chǎn)車間設(shè)備布局的多目標(biāo)優(yōu)化模型;采用自適應(yīng)遺傳算法(adaptive genetic algorithm,AGA)求解該問題時,交叉、變異概率基于Logistic曲線自適應(yīng)調(diào)整,有利于優(yōu)勝劣汰和全局最優(yōu)解的獲得。與改造前的布局相比較,加入機(jī)器人后的優(yōu)化布局使物流費用降低、占地面積減小,對企業(yè)降本增效具有一定現(xiàn)實意義。
設(shè)備布局;自適應(yīng)遺傳算法;多目標(biāo)優(yōu)化
設(shè)備布局問題(facility layout problem,F(xiàn)LP)是指在一定限制條件下(如車間面積形狀、物流方式等),將生產(chǎn)設(shè)備在給定空間內(nèi)布局,使目標(biāo)函數(shù)(如物流費用、面積使用率等)得到優(yōu)化。設(shè)備布局對企業(yè)降本增效具有重要意義,從時間成本上來看,物料從進(jìn)廠到出廠真正處于加工檢驗的時間僅占生產(chǎn)周期的5%~10%,而90%~95%的時間都處于搬運或等待狀態(tài)[1];從經(jīng)濟(jì)成本上來看,物料搬運費用在生產(chǎn)活動總開銷中所占比例高達(dá)20%~50%。良好的設(shè)備布局能使物料更加高效順暢的流通,減少搬運、等待時間,使物流費用至少降低10%~30%[2]。
目前,設(shè)備布局采用數(shù)學(xué)分析法建立的模型主要包括二次分配模型、二次集合覆蓋模型、線性整數(shù)規(guī)劃模型、混合整數(shù)規(guī)劃模型等[3]。Koopmans和Beckmann于1957年首次提出二次分配模型[4](quadratic assignment problem,QAP),描述n個設(shè)施和n個地點,要求給每個設(shè)施分配到一個位置,并使設(shè)施之間的總流量(或費用)最小。QAP模型的最優(yōu)求解算法,可以歸為分支定界法和割平面法兩類[5]。這兩種算法都需要較多的計算時間和較大的存儲空間,隨著布局規(guī)模的擴(kuò)大,最優(yōu)算法因“組合爆炸”問題已不再適用,20世紀(jì)80年代后研究者多轉(zhuǎn)向元啟發(fā)式算法求次優(yōu)解。其中,遺傳算法因其全局性并行搜索的特點,被廣泛運用于QAP求解。
李愛平[6]、趙建東[7]、徐立云[8]等人建立了多行直線布局的QAP模型,但所建立的模型中,行與行之間的距離均設(shè)為定值而與該行設(shè)備無關(guān),相鄰設(shè)備之間的凈間距采取初始隨機(jī)生成、后續(xù)算法優(yōu)化的方法確定,不僅增大了運算量,最終優(yōu)化結(jié)果還因為初始值的隨機(jī)性而波動較大[9]。本文從實際出發(fā),重新定義了行與行之間以及相同行相鄰設(shè)備之間的距離,并考慮增加的輔助設(shè)備(例如上下料機(jī)器人等)對原有設(shè)備優(yōu)化布局的約束影響,對多行直線布局的QAP模型進(jìn)行了改進(jìn)。在求解QAP過程中,對簡單遺傳算法作了自適應(yīng)改進(jìn),進(jìn)化參數(shù)可以根據(jù)個體自身的優(yōu)劣程度實時調(diào)整,對提高算法的效率和最優(yōu)解的改善作用明顯。
為方便計算,對多行直線布局做出以下假設(shè)(如圖1所示):①所有設(shè)備形狀均為其包絡(luò)矩形,忽略其細(xì)節(jié)形狀及高度;②同一行設(shè)備的中心點位于一條直線上,沿X軸正方向依次排列;③零件加工工藝確定;④各行之間有物流通道,與X軸平行,寬度WP為定值。
假設(shè)有n臺設(shè)備,給其固定編號為1~n,設(shè)備i的包絡(luò)矩形沿X軸、Y軸尺寸分別為Ai、Bi。參考設(shè)備的技術(shù)文檔,在其周邊留出最小安全距離Hi,用于設(shè)置安裝、操作、維修、工件緩沖區(qū)域等,相鄰擺放的兩個設(shè)備i、j之間的最小距離Hij=Hi+Hj。
圖1 線性多行設(shè)備布局示意圖
在車間長度的約束下,當(dāng)一個設(shè)備序列s確定后,則該序列在每行上的設(shè)備分布及設(shè)備中心點X軸坐標(biāo)值可按如下公式遞推計算:
xs(1)=Hs(1)+As(1)/2
(1)
xs(i)=xs(i-1)+Hs(i-1)s(i)+(As(i-1)+As(i))/2,i=2,3,…,n
(2)
當(dāng)xs(j)+As(j)/2+Hs(j)>L時(L為車間長度),將設(shè)備s(j)移至下一行第1位,并按照式(1)、式(2)繼續(xù)計算設(shè)備s(j)、s(j+1)的X軸坐標(biāo)值。
令hi=Hi+Bi/2,各行設(shè)備的中心點Y軸坐標(biāo)值可按如下公式確定:y1=max{hs(1),hs(2),…,hs(m)},s(1)、s(2)、…、s(m)為排在第1行的設(shè)備;y2=y1+max{hs(1),hs(2),…,hs(m)}+WP+max{hs(m+1),hs(m+2),…,hs(r)},s(m+1)、s(m+2)、…、s(r)為排在第2行的設(shè)備,WP為物流通道寬度。以此類推,直至求出最后一行設(shè)備的中心點Y軸坐標(biāo)值。
通常情況下,一個好的布局方案應(yīng)遵循滿足工藝流程、工件盡量直線前進(jìn)、減小移動距離、簡化搬運作業(yè)、充分利用空間、保持生產(chǎn)均衡等原則。為此,本文以物流費用最小和面積利用率最大為優(yōu)化目標(biāo)。
上述兩個目標(biāo)確定后,如何確定一個布局,使F、S均能取得理想的結(jié)果,這就是一個多目標(biāo)優(yōu)化問題。通常來講,求解多目標(biāo)優(yōu)化問題主要有3類方法[10]:①生成法,即先求出大量的非劣解,構(gòu)成非劣解的一個子集,然后按照決策者的意圖找出最終解;②交互法,不先求出很多的非劣解,而是通過分析者與決策者對話的方式逐步求出最終解;③歸一法,事先要求決策者提供目標(biāo)之間的相對重要程度,算法以此為依據(jù)將多目標(biāo)問題轉(zhuǎn)換為單目標(biāo)問題求解。本文采取第3類方法,用加權(quán)法構(gòu)造新的目標(biāo)函數(shù):
L=w1F/Fmin+w2S/Smin
(3)
w1、w2為加權(quán)因子,根據(jù)實際工程中對于物流和面積各自的側(cè)重程度來確定,要滿足加權(quán)條件w1+w2=1;F、S各除以它們的單目標(biāo)優(yōu)化最優(yōu)值,既消除量綱,又能反映它們偏離最優(yōu)值的程度。
(1)所有設(shè)備不超出車間長、寬范圍,即:
max{xi+Ai/2+Hi}≤L
(4)
max{yj+Bj/2+Hj}≤W
(5)
式(4)可由自動換行策略來保證;式(5)可對F和S設(shè)置罰函數(shù)來保證,例如:
(2)存在物流關(guān)系的兩臺設(shè)備不得跨行布置。由圖1可知,假如設(shè)備s(1)、s(j)之間存在物流關(guān)系,則1.2節(jié)中定義的dij將失去意義,因為物料不可能“穿越”中間行傳遞。此項約束條件如在布局設(shè)計階段實現(xiàn)將會比較復(fù)雜,采取的辦法是對布局結(jié)果進(jìn)行驗證排除。
(3)設(shè)備相鄰關(guān)系約束。大多數(shù)布局案例[6-8]均沒有考慮此類約束,在下文實例中由于車床M1-1/M1-2、磨床M5-1/M5-2要分別與機(jī)器人MH6組合使用,因此兩組設(shè)備要相鄰布置,同時還要考慮機(jī)器人工作半徑對設(shè)備間距的約束。本文的解決辦法是先對組合單元進(jìn)行布局,再將組合單元作為一個整體與其他設(shè)備布局。
在標(biāo)準(zhǔn)遺傳算法中[11],交叉、變異算子是固定的,不利于種群多樣化,可能會導(dǎo)致算法收斂緩慢,或是過早收斂甚至陷入局部最優(yōu)(“早熟”現(xiàn)象)。針對這一問題,采取自適應(yīng)遺傳算法,根據(jù)個體適應(yīng)度值的大小實時調(diào)整交叉、變異概率,保持進(jìn)化動力。自適應(yīng)遺傳算法有線型(LAGA)、余弦型(CAGA)和Logistic曲線型(LOAGA)等,由于LOAGA在進(jìn)化各階段均有不同側(cè)重,在個體多樣性和后期收斂性等方面具有優(yōu)勢[12],因此本文采取LOAGA求解FLP。
采用順序編碼方式,給n個設(shè)備各指定一個1~n之間的整數(shù)編號(一一對應(yīng)無重復(fù)),以1~n的一個排列作為1條染色體(代表一個設(shè)備序列)。根據(jù)1.1節(jié)中的遞推方法,求出該序列每個設(shè)備的X、Y坐標(biāo)值;再根據(jù)1.2節(jié)中式(3)求出加權(quán)統(tǒng)一的多目標(biāo)優(yōu)化函數(shù)值L。由于所求目標(biāo)為極小值,所以適應(yīng)度函數(shù)可設(shè)為f=1/L。隨機(jī)生成m個序列,作為算法的初始種群A。
采取隨機(jī)聯(lián)賽選擇方式[11],聯(lián)賽規(guī)模為N。具體過程是:①從A中隨機(jī)選取N條染色體,比較它們的適應(yīng)度函數(shù)值大小,將其中最大的保留進(jìn)入下一代群體;②重復(fù)上述過程M次,得到包含M條染色體的群體As。
交叉算子選用部分映射交叉(PMX)方式。如圖2所示,先選擇交叉位置(圖中帶框編號),交換兩個父代染色體對應(yīng)位置的編號,然后對交叉位置以外的重復(fù)編號(圖中帶下劃線編號)按交叉時建立的映射關(guān)系逐一替換,確保交叉產(chǎn)生的子代染色體的合法性(即不含重復(fù)編號)。將As中的染色體兩兩配對,按照自適應(yīng)交叉概率決定是否交叉,交叉后得到子代群體Ac。
圖2 部分映射交叉
自適應(yīng)交叉概率:
式中,pcmax、pcmin為設(shè)定的交叉概率的上、下限,f′為兩條配對染色體中較大的適應(yīng)度值,favg為當(dāng)代群體的平均適應(yīng)度值,fmax為當(dāng)代群體的最大適應(yīng)度值,a為常數(shù)。自適應(yīng)交叉概率的意義在于:當(dāng)配對染色體適應(yīng)度小于當(dāng)代群體的適應(yīng)度時,交叉率取上限,增大交叉發(fā)生的可能性;當(dāng)配對染色體適應(yīng)度大于當(dāng)代群體的適應(yīng)度時,交叉率會有所下降,減少交叉發(fā)生的可能性。這樣一方面提高進(jìn)化初期個體適應(yīng)度不高時的進(jìn)化速度,另一方面減少了進(jìn)化后期低適應(yīng)度值個體的數(shù)量,以節(jié)約計算時間和資源。
變異算子采用鄰域技術(shù),如圖3所示,對需要變異的染色體,隨機(jī)選擇3個基因位(圖中帶框編號),再互換它們的位置得到該染色體的一個鄰域,選擇鄰域中適應(yīng)度函數(shù)值最大的作為變異成果。為增加新染色體的數(shù)量,將As、Ac中的每條染色體都按照自適應(yīng)變異概率決定是否變異,并得到變異的群體Am。
圖3 變異產(chǎn)生的鄰域
自適應(yīng)變異概率:
式中,pmmax、pmmin為設(shè)定的變異概率的上、下限,f為當(dāng)前染色體的適應(yīng)度值。自適應(yīng)變異概率的意義在于:在進(jìn)化前期,較優(yōu)解和較差解都取小的變異概率,利于優(yōu)良基因保留和較差基因淘汰;在進(jìn)化后期,種群中各染色體的適應(yīng)度值相差越來越小,變異概率將會增大,有利于生成新解,防止進(jìn)化停滯不前。
將群體As、Ac、Am中的每個個體按照適應(yīng)度值大小排序,選取前m個個體作為當(dāng)前進(jìn)化的結(jié)果(更新群體A),然后進(jìn)行下一次進(jìn)化。遺傳算法終止條件有:①根據(jù)進(jìn)化次數(shù),一般取值范圍為100~500;②根據(jù)適應(yīng)度函數(shù)值的最小偏差;③根據(jù)適應(yīng)度函數(shù)值的變化趨勢(趨于緩和或不再變化)。本文以進(jìn)化次數(shù)作為終止條件。
本文主要研究W集團(tuán)壓縮機(jī)有限公司的冰箱壓縮機(jī)曲軸生產(chǎn)車間的設(shè)備布局。該曲軸由相互平行的主軸頸、曲軸頸以及中間的半圓形平衡塊組成(見圖4),主要特征有螺旋形油槽、直油槽、油孔、定位孔等,主軸頸為空心圓柱結(jié)構(gòu)。曲軸毛坯為鑄造件,主要工藝如圖5所示,加工過程需要車床、鉆床、銑床、磨床等9臺設(shè)備以及清洗、檢驗工位。生產(chǎn)車間長寬為22m×22m,改造前是按照工藝路線采取“S”形多行直線布局。為加快生產(chǎn)節(jié)拍、提高效率,公司引進(jìn)兩個6自由度機(jī)器人分別為兩臺車床和兩臺無心磨床自動上下料(圖5中虛線框部分),并且對加工設(shè)備重新布局,使物料流通更加順暢高效。
圖4 冰箱壓縮機(jī)曲軸結(jié)構(gòu)示意圖
圖5 冰箱壓縮機(jī)曲軸工藝路線
各設(shè)備的型號及外形尺寸如表1所示。公司選用機(jī)器人的型號為安川MOTOMAN-MH6,其最大工作半徑1422mm,基座回轉(zhuǎn)角度±170°。如果兩臺加工設(shè)備(M1-1、M1-2或M5-1、M5-2)采取“一一”型或“L”型布局,則機(jī)器人需要移動才能完成上下料,增加了行走模組和控制系統(tǒng)的成本。因此,將加工設(shè)備面對面擺放,機(jī)器人位于中間,這樣雖然設(shè)備的安全距離有所重疊,但因采取了機(jī)器人上下料,對安全生產(chǎn)的影響可以忽略。設(shè)備之間的距離取2.4m(<2×1422mm),則M1-1、M1-2和MH6組成的車削單元M1長度5.66m、寬度3.11m,M5-1、M5-2和MH6組成的磨削單元M5長度5.9m、寬度1.95m。
表1 曲軸加工設(shè)備尺寸 單位:m
物流通道寬度WP=2 m,方向與X軸平行。為便于取件,各設(shè)備的操作面與物流通道垂直。將車削單元、磨削單元均視為一個設(shè)備,根據(jù)加工工藝統(tǒng)計出設(shè)備之間的訪問次數(shù)矩陣:
由于曲軸在加工時損失的質(zhì)量不大,設(shè)備i、j之間單位距離上單位工件的物流費用qij可視為定值,不妨設(shè)其為1。
設(shè)備數(shù)n=9,取初始種群大小m=100,聯(lián)賽選擇的規(guī)模N=2、M=50,進(jìn)化代數(shù)T=300。先按照單目標(biāo)優(yōu)化,分別求出最小物流費用Fmin=85.9850、包絡(luò)矩形最小面積Smin=262.0072。再用兩種遺傳算法求解多目標(biāo)優(yōu)化布局:方法1采用簡單遺傳算法(SGA),交叉、變異概率為定值,交叉概率pc=0.75,變異概率pm=0.1;方法2采用自適應(yīng)遺傳算法(LOAGA),交叉概率pcmax=0.95、pcmin=0.55,變異概率pmmax=0.15、pmmin=0.05,常數(shù)a=9.903。
在Matlab中編寫SGA和LOAGA的程序,均從相同的初始群體出發(fā),運行6次的結(jié)果如圖6所示,橫坐標(biāo)為進(jìn)化代數(shù)(t),縱坐標(biāo)為每代最大適應(yīng)度值(fitbest)。從圖6可以看出,在解的質(zhì)量方面,LOAGA有5次得到了最佳值(fitbest=0.9233),SGA僅有2次(第4次、第5次還出現(xiàn)明顯的“早熟”現(xiàn)象),說明在進(jìn)化過程中LOAGA比SGA更容易跳出局部最優(yōu);在求得最佳值的速度方面,LOAGA仍然領(lǐng)先于SGA,除第6次外LOAGA均用較少的進(jìn)化代數(shù)得到了最佳值。
圖6 SGA與LOAGA優(yōu)化結(jié)果對比
在引入機(jī)器人之前,生產(chǎn)車間是根據(jù)圖5所示的工藝流程并按照“S”形路線進(jìn)行的布局,設(shè)備序列為[M2 M1-1 M1-2 M4 M5-1 M9 M8 M3 M5-2 M6 M7],如圖7所示(矩形內(nèi)數(shù)字為設(shè)備編號,矩形外數(shù)字為該設(shè)備完成的工序)。經(jīng)計算,此種布局物流費用F=118.675,其包絡(luò)矩形面積S=290.7628。
引入機(jī)器人后,由3.2節(jié)可得出多目標(biāo)優(yōu)化布局的設(shè)備序列為[M8 M3 M4 M2 M7 M9 M1-1 MH6 M1-2 M6 M5-1 MH6 M5-2],如圖8所示,此時的物流費用F=96.015、包絡(luò)矩形面積S=274.9956,比之前的布局分別減少了19.1%、5.4%,較好地實現(xiàn)了優(yōu)化布局的目標(biāo)。
表2為優(yōu)化之后的各設(shè)備中心點坐標(biāo)。另外由圖8可以看出,第1行與第3行的設(shè)備均沒有物流關(guān)系,滿足1.3的約束條件。
表2 布局優(yōu)化后的各設(shè)備中心點坐標(biāo)
圖7 加入機(jī)器人之前的S形布局
圖8 加入2個機(jī)器人之后優(yōu)化的布局
本文改進(jìn)了多行直線布局的QAP模型中行與行之間、相鄰設(shè)備之間距離的定義,使之更加符合生產(chǎn)實際;并考慮新引入輔助設(shè)備(2臺上下料機(jī)器人)的影響,先局部單元組合再車間整體優(yōu)化,盡管增加了設(shè)備但最終優(yōu)化的布局更加緊湊。在求解QAP過程中,基于Logistic曲線改進(jìn)的LOAGA優(yōu)于SGA,其原因在于LOAGA能夠根據(jù)個體適應(yīng)度值的大小,實時調(diào)整交叉、變異概率,減小“早熟”的可能性,使群體始終保持多樣性,有利于優(yōu)勝劣汰和全局最優(yōu)解的獲得。經(jīng)過多目標(biāo)優(yōu)化,生產(chǎn)車間的物流費用降低19.1%、占地面積減小5.4%,物流費用的降低是因為總的物流距離縮短;可以預(yù)見,工件的運輸時間、設(shè)備的等待時間都將縮短,因此優(yōu)化的布局可以有效提高生產(chǎn)效率,較好地實現(xiàn)了降本增效的目標(biāo)。
[1] 胡廣華. 制造車間布局優(yōu)化方法研究與系統(tǒng)實現(xiàn)[D]. 武漢:華中科技大學(xué), 2007.
[2] BragliaM, ZanoniS, ZavanellaL. Layout design in dynamic environments: Strategies and quantitative indices[J]. International Journal of Production Research, 2003,41(5):995-1016.
[3] 鎖小紅, 劉戰(zhàn)強(qiáng). 制造系統(tǒng)設(shè)備布局的建模理論與求解方法[J]. 計算機(jī)集成制造系統(tǒng),2007, 13(10):1941-1951.
[4] 張惠珍, 馬良, (西)羅佑. 二次分配問題及其線性化技術(shù)[M]. 上海: 上海人民出版社, 2013.
[5] Kusiak A, Heragu S S. The facility layout problem [J]. European Journal of Operational Research, 1987, 29(3):229-251.
[6] 李愛平, 鄢澤耀, 謝楠,等. 基于NSGA-Ⅱ的多目標(biāo)車間設(shè)備布局[J]. 機(jī)械設(shè)計與研究, 2012, 28(6):90-95.
[7] 趙建東, 鄭軍, 趙琪. 基于遺傳算法的TFT-LCD沖壓生產(chǎn)線布局優(yōu)化[J]. 北京交通大學(xué)學(xué)報, 2013, 37(1):172-176.
[8] 徐立云, 楊守銀, 李愛平,等. 生產(chǎn)車間布局多目標(biāo)優(yōu)化及其仿真分析[J]. 機(jī)械設(shè)計與研究, 2011, 27(6):55-59.
[9] 魏軍凱, 吳芳, 戚峰. 基于遺傳算法求解車間設(shè)備布局優(yōu)化問題[J]. 蘭州交通大學(xué)學(xué)報, 2011, 30(3):75-78.
[10] 肖曉偉, 肖迪, 林錦國,等. 多目標(biāo)優(yōu)化問題的研究概述[J]. 計算機(jī)應(yīng)用研究, 2011, 28(3):805-808.
[11] 雷英杰, 張善文, 李續(xù)武, 等. MATLAB遺傳算法工具箱及應(yīng)用[M]. 西安: 西安電子科技大學(xué)出版社, 2005.
[12] 徐明明, 宋宇博. LO型曲線的自適應(yīng)遺傳算法研究[J]. 電子技術(shù)應(yīng)用, 2015, 41(12):129-132.
AResearchofMulti-objectiveOptimizationBasedonAGAfortheFacilityLayoutinCrankshaftAutomationWorkshop
SHEN Kuan, ZHAI Jing-mei, ZHANG Tie
(School of Mechanical & Automotive Engineering, South China University of Technology, Guangzhou 510641, China)
It is necessary to optimize the facility layout, which can improve the production efficiency and reduce the cost. A multi-objective optimization model for the facility layout of crankshaft automation workshop was created: it was based on the principles of minimum material transport cost and maximum workshop area utilization, also added the constraint of auxiliary devices (loading and unloading robots). A kind of adaptive genetic algorithm (AGA) was used to find the best solution of this model. The crossover and mutation probability based on the Logistic curve could adjust adaptively, which was advantageous to the evolution and the global optimal solution. Compared with the old layout, the optimized layout including the added robots makes the logistics cost less and the footprint decrease, which has certain significance for the enterprise to reduce the cost and improve the efficiency.
facility layout;adaptive genetic algorithm;multi-objective optimization
TH181;TG506
A
1001-2265(2017)12-0151-05
10.13462/j.cnki.mmtamt.2017.12.038
2017-02-13;
2017-03-16
國家04科技重大專項(2015ZX04005006);廣東省科技重大專項(2014B090921004,2015B010918002);中山市科技重大項目(2016F2FC0006)
申寬(1986—),男,湖北襄陽人,華南理工大學(xué)碩士研究生,研究方向為機(jī)床與機(jī)器人一體化、設(shè)備優(yōu)化布局等,(E-mail)270710478@qq.com;通訊作者:翟敬梅(1967—),女,遼寧鞍山人,華南理工大學(xué)教授,博士,研究方向為機(jī)械系統(tǒng)建模與優(yōu)化、機(jī)電裝備與信息化、人工智能等,(E-mail)mejmzhai@scut.edu.cn。
(編輯李秀敏)