基于改進(jìn)遺傳算法的車間布局重構(gòu)

唐秋華,陳 立,王雪蘭

(武漢科技大學(xué)機(jī)械自動化學(xué)院,湖北武漢,430081)

優(yōu)良的車間布局不僅可以提高生產(chǎn)效率,減少不必要的物流運(yùn)輸,還可以使工作人員在更加安全、健康和舒適的環(huán)境中工作。車間布局重構(gòu)是在現(xiàn)有車間布局基礎(chǔ)上,通過局部結(jié)構(gòu)調(diào)整,重新理順車間的工件流、材料流和人流等,特別是優(yōu)化設(shè)備之間的物流運(yùn)輸關(guān)系,重新確定其排列順序和位置,使物流運(yùn)輸邏輯與制造流程一致,從而最大限度地減少運(yùn)輸環(huán)節(jié)、降低物流運(yùn)輸成本和縮短制造周期[1]。

在車間布局重構(gòu)時,一般會考慮制造工藝流程、設(shè)備類型和數(shù)量、可用工作空間、設(shè)備幾何尺寸以及設(shè)備之間的運(yùn)輸頻率等影響因素。由于車間布局是多約束多目標(biāo)的全局優(yōu)化問題,很難用單一的數(shù)值優(yōu)化模型來描述,導(dǎo)致看似簡單的布局設(shè)計(jì)也往往是NP難問題[2]。

傳統(tǒng)的車間布局都是依靠人工設(shè)計(jì)。根據(jù)人工推理的各車間之間、同一車間內(nèi)各工段之間、同一工段各設(shè)備之間的邏輯關(guān)聯(lián),對車間布局進(jìn)行模糊規(guī)劃。受主觀經(jīng)驗(yàn)、自身知識及能力所限,采用該方法很難得到較優(yōu)解,最多能找到可行解。目前常用的布局方法為系統(tǒng)布局設(shè)計(jì)(systematic layout planning,SLP)方法,即根據(jù)車間內(nèi)各作業(yè)單位間的活動關(guān)系密切程度進(jìn)行布局,借助于圖解,將生產(chǎn)單位之間的聯(lián)系程度定量化,計(jì)算出評分值,為平面布局提供依據(jù)[3-4]。由于該方法主要是根據(jù)兩作業(yè)單位間的物流當(dāng)量來指定布局方案,結(jié)果雖優(yōu)于手工布局,但還需要進(jìn)一步評判。近年來研究人員開始將遺傳算法、模擬退火算法和Petri網(wǎng)等應(yīng)用于車間布局設(shè)計(jì)。在布局設(shè)計(jì)中采用模擬退火算法一般僅考慮單一的優(yōu)化目標(biāo)函數(shù),最常見的優(yōu)化準(zhǔn)則是最小化設(shè)備間的物流耗費(fèi)[5]。基于Petri網(wǎng)的布局優(yōu)化方法通常將目標(biāo)函數(shù)放在約束(如位置、距離、路徑、鄰接關(guān)系等)中,尋找一種能滿足一系列約束和關(guān)系的設(shè)計(jì)方案,所以其實(shí)質(zhì)是一種多目標(biāo)準(zhǔn)則[6]。

采用遺傳算法進(jìn)行車間布局優(yōu)化是基于設(shè)備間的鄰接關(guān)系產(chǎn)生空間關(guān)系圖,并以此作為設(shè)計(jì)骨架產(chǎn)生布局方案,其具有解集性能優(yōu)、計(jì)算速度快等優(yōu)點(diǎn)。本文以最小化車間物流總費(fèi)用為目標(biāo),研究基于遺傳算法的車間重構(gòu)策略,對車間設(shè)備布局方案進(jìn)行優(yōu)化。

1 問題描述

1.1 參數(shù)和變量定義

車間布局分為單行布局和多行布局,其中單行布局可看作是多行布局的特例,所以研究車間布局一般都是針對多行布局。在構(gòu)造車間布局的數(shù)學(xué)模型之前,要對車間制造系統(tǒng)類型、主要加工對象和產(chǎn)量、現(xiàn)有工藝流程、設(shè)備幾何尺寸以及使用頻次等進(jìn)行分析,并定義相關(guān)參數(shù)和變量[7]。圖1為車間布局重構(gòu)示意圖,圖中所有機(jī)器按照相互之間的物流關(guān)系,以S形完成多行布置。

定義M臺機(jī)器構(gòu)成的集合I={i|i=1,2,…,M},定義這些機(jī)器所組成的一種序列J={j|j=1,2,…,M},將這些機(jī)器布置在Q行,定義行數(shù)集合為N={n|n=1,2,…,Q}。假設(shè)mj為布置在第j(j∈J)位的機(jī)器,li為機(jī)器i(i∈I)的長度,hi為機(jī)器i的寬度,dmjmj+1為機(jī)器mj與機(jī)器mj+1的最小間距,(xi,yi)為機(jī)器i的中點(diǎn)坐標(biāo)為各行間的平均行間距,sn為布置在第n行的機(jī)器數(shù),Sn為從第1行至第n行累計(jì)的機(jī)器數(shù),并令S0=0,L與H分別為車間的長與寬,fii′為機(jī)器i(i∈I)到機(jī)器i′(i′∈I)之間的往返行程次數(shù),cii′為機(jī)器i到機(jī)器i′之間往返耗費(fèi)的單位物流費(fèi)用,Φ(x)為物流總費(fèi)用。定義參數(shù)G為無窮大。考慮約束情況,引入決策變量vijn,如果機(jī)器i位于機(jī)器序列的第j位,且機(jī)器i位于第n行,則vijn=1,否則vijn=0。

圖1 車間布局重構(gòu)示意圖Fig.1 Schematic diagram of workshop reconfiguration

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

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

約束條件為

式(1)表示車間布局重構(gòu)的目標(biāo)為最小化物流總費(fèi)用;式(2)限制一臺機(jī)器只能布置在一行中;式(3)約束在圖1所示的機(jī)器序列中,每個位置j只能布置一臺機(jī)器;式(4)和式(5)確定每一行布置的機(jī)器數(shù)量和累計(jì)機(jī)器數(shù)量;通過界定每行機(jī)器的起止順序,式(6)保證所有機(jī)器按線性遞增方式排列;式(7)和式(8)確定機(jī)器每行之間的平均行間距,同時也確保機(jī)器布局的長、寬方向總尺寸不超過限定值;式(9)和式(10)表示位于奇數(shù)行的機(jī)器x坐標(biāo)向右按增序排列,而位于偶數(shù)行的機(jī)器x坐標(biāo)向左按增序排列,從而保證所有機(jī)器按S形布局,同時,式(9)和式(10)要求位于同一行的機(jī)器之間滿足最小間距約束,以保證其相互之間不出現(xiàn)干涉或重疊;式(11)和式(12)共同保證每臺機(jī)器的y坐標(biāo)即為該行坐標(biāo)。

2 改進(jìn)的遺傳算法

2.1 染色體編碼

染色體編碼是利用遺傳算法求解車間布局重構(gòu)問題的關(guān)鍵,它不僅影響遺傳算子的設(shè)計(jì),還決定了搜索空間基因向解空間轉(zhuǎn)換的對應(yīng)關(guān)系[8-9]。對于多行布局,采用一組數(shù)字作為行分隔符,表示設(shè)備將在幾行間進(jìn)行分配。對于機(jī)器排序則采用直接編碼的方式。一個染色體的完整編碼為{(s1,s2,…,sn,…,sQ),(m1,m2,…,mj,…,mM)},其中,(s1,s2,…,sn,…,sQ)為每行的機(jī)器數(shù)目;(m1,m2,…,mj,…,mM)為布置在(1,2,…,j,…,M)位置上的機(jī)器所構(gòu)成的序列。該編碼中隱含約束關(guān)系為:所有機(jī)器分配在預(yù)先設(shè)定的Q行,且

2.2 染色體初始化和適應(yīng)度函數(shù)值

初始種群隨機(jī)產(chǎn)生。對于每個染色體編碼,可以根據(jù)式(7)～式(8)確定機(jī)器間的最小間距和平均行間距,再根據(jù)式(9)～式(12)計(jì)算出所有機(jī)器的坐標(biāo),得到車間實(shí)際布局。根據(jù)式(1)計(jì)算出物流總費(fèi)用,并以此作為染色體的適應(yīng)度函數(shù)值。

2.3 遺傳算子

(1)選擇算子。采用常見的排序選擇算子產(chǎn)生下一代,同時采用精英策略確保最優(yōu)個體不被淘汰,這樣可以加快算法的收斂速度。

(2)交叉算子。隨機(jī)選擇兩個染色體,當(dāng)且僅當(dāng)兩個染色體的Q值相同時進(jìn)行交叉,如圖2所示。

圖2 交叉算子Fig.2 Crossover operator

隨機(jī)選擇交叉位n,如果n

步驟1 計(jì)算兩個染色體前n個片段的機(jī)器數(shù)量之差Cn。

步驟2 如果Cn=0,則前后片段完整交換;如果Cn>0,則隨機(jī)選擇在+1,…,s′Q)片段中去掉Cn臺機(jī)器,在(sn,sn+1,…,sQ)片段內(nèi)增加Cn臺機(jī)器,然后相互交換;如果Cn<0,則進(jìn)行與上述相反的操作。

如果n>Q,則限定交叉范圍為(m1,m2,…,mj,…,mM),如圖2中虛線框所示,即改變機(jī)器分配方式。取第一個染色體左邊部分,同時在第二個染色體中刪除與第一個染色體左邊部分相同的基因,剩余的基因按照原來的順序排列。以第一個染色體左邊部分和第二個染色體處理得到的基因?yàn)橛疫叢糠?重組為一個新的染色體。

(3)變異算子。針對每個染色體,采用兩種變異方式。第一種變異是針對各行分配的機(jī)器數(shù)量,即在染色體的1～N位之間隨機(jī)選擇兩個數(shù),其中一個數(shù)加1,另一個數(shù)減1;第二種變異是針對設(shè)備編碼序列,即在染色體的N+1～N+M位之間隨機(jī)選擇兩個數(shù),相互交換。

3 實(shí)例分析

3.1 某凸輪軸加工車間概況

某加工車間主要生產(chǎn)3個系列的凸輪軸,3種產(chǎn)品共線生產(chǎn),主要工藝流程基本相同,如表1所示。車間平面布局如圖3所示。

表1 凸輪軸主要加工工序Table 1 Key processes of cam shaft machining

圖3 凸輪軸加工車間布局現(xiàn)狀Fig.3 Current layout of the cam shaft workshop

結(jié)合表1和圖3,對車間平面區(qū)域進(jìn)行編碼,如表2所示。

根據(jù)對生產(chǎn)現(xiàn)場的調(diào)研及車間平面編碼,繪制如圖4所示的車間物流流程圖,圖中符號內(nèi)的數(shù)字表示區(qū)域編碼,箭頭上的數(shù)字表示區(qū)域之間單位時間的物流量。圖4中的物流流程同時也反映了該凸輪軸車間的工藝路線。

從圖4中可以看出,緩存區(qū)13存在多個半成品物流匯聚,有可能導(dǎo)致物料混亂,在運(yùn)送物料到下一個工位之前需要重新審查其類型,給運(yùn)輸增加了不必要的麻煩。同時,車間布局雜亂、空間浪費(fèi)、物流路線迂回、物流量較大的作業(yè)單位距離較遠(yuǎn),這都造成了物流成本的增加,而且目前的車間布局不適應(yīng)多品種小批量生產(chǎn)模式,生產(chǎn)柔性較差。當(dāng)該車間需要提升產(chǎn)量時,上述問題就變得比較突出,因此不得不耗資進(jìn)行車間布局重構(gòu)。

表2 車間平面區(qū)域編碼Table 2 Codes of the workshop plane

圖4 凸輪軸車間物流流程圖Fig.4 Logistics flowchart of the cam shaft workshop

3.2 車間布局重構(gòu)

為保證物流運(yùn)輸順暢,提高車間作業(yè)效率,擬定以S形混合流水線組織生產(chǎn),所以車間布局主要考慮生產(chǎn)加工設(shè)備的布局,而不考慮暫存區(qū)的位置和大小。在車間長度尺寸約束下,兩行布局即可完成既定任務(wù),導(dǎo)致最后得到的生產(chǎn)線變成了典型的U形線。布局重構(gòu)時限定車間可布置長度為25 m,并根據(jù)設(shè)備尺寸和物流配送等要求,選定行距單元為4 m。首先將表2中{1,7,8,9,10,13,16,17,20,21,24,26,27}在制品庫存位置去除,得到表3所示精煉后的車間區(qū)域編碼。

表3 精煉后的車間區(qū)域編碼Table 3 Refined codes of the workshop

不考慮表3中毛坯區(qū)、成品區(qū)位置,于是僅剩下12臺機(jī)器的布局需要納入重構(gòu)范圍。提取這12臺機(jī)器的長、寬、高數(shù)據(jù),用矩陣[L,W,H]T表示;并用矩陣表示這12臺機(jī)器布置時不發(fā)生干涉的最小間距。

目前車間主要采用人力運(yùn)輸,根據(jù)多耗費(fèi)的勞動力成本,折算為各機(jī)器、庫存間的單位物流費(fèi)用,用矩陣[cmm′]表示。由于全部是人力運(yùn)輸,故可假設(shè)矩陣中每個元素都是1。

提取加工每根凸輪軸時物料在各臺機(jī)器間的往返行程次數(shù),用矩陣[fmm′]表示。

改進(jìn)遺傳算法的參數(shù)設(shè)為:群體規(guī)模Pop=40,遺傳代數(shù)Gen=100,交叉概率Pc=0.8,變異概率Pw=0.06。計(jì)算得到最優(yōu)個體為{(6,6),(2,3,4,5,6,7,8,9,10,11,12,13)},最小物流費(fèi)用為16 226.64。重構(gòu)之后的車間布局如圖5所示。車間重構(gòu)前后的物流費(fèi)用如表4所示。

從表4中可以看出,車間布局重構(gòu)后物料搬運(yùn)總距離減少了22.50m,物流總費(fèi)用從21 395.05降至16 226.64,減少了5 168.41。

另外,該車間目前采用人工推動料車送料,每車裝載20根凸輪軸。根據(jù)重構(gòu)后的車間布局,建議采用傳送帶送料,這樣不但可以減輕工人的勞動強(qiáng)度,還可以提高生產(chǎn)效率。

圖5 重構(gòu)之后的車間布局Fig.5 Reconfigured layout of the workshop

表4 車間重構(gòu)前后的物流費(fèi)用對比Table 4 Comparison of logistics costs before and after reconfiguration

4 結(jié)語

合理的車間布局可以減少運(yùn)輸環(huán)節(jié),縮短物料運(yùn)送時間和生產(chǎn)周期,降低生產(chǎn)成本。本文針對設(shè)備多行布局,建立了以最小化物流總費(fèi)用為目標(biāo)的車間布局重構(gòu)數(shù)學(xué)模型,并設(shè)計(jì)了改進(jìn)遺傳算法進(jìn)行求解。通過某凸輪軸加工車間布局重構(gòu)前后物流費(fèi)用的對比,驗(yàn)證了該模型和算法的有效性。

[1] 蔣祖華.工業(yè)工程典型案例分析[M].北京:清華大學(xué)出版社,2005:208-215.

[2] 唐秋華,肖飛,王雪蘭.基于SLP和Flexsim的車間重構(gòu)研究[J].武漢理工大學(xué)學(xué)報(bào):交通科學(xué)與工程版,2008,32(5):895-898.

[3] Ma Zhengyuan.Research on virtual enterprise’s technology fo r supply-oriented system[C]//Proceedings of IE&EM 2001,Tianjin.Beijing:Machinery Industry Press,2001:357-363.

[4] 玄光南,程潤偉.遺傳算法與工程優(yōu)化[M].北京:科學(xué)出版社,2000:124-138.

[5] 王金敏,馬豐寧,劉黎.模擬退火算法在布局求解中的應(yīng)用[J].機(jī)械設(shè)計(jì),2000(2):6-9.

[6] 王小娟,鈕志強(qiáng).基于OOPN的港口集裝箱堆場作業(yè)流程仿真優(yōu)化研究[J].物流技術(shù),2010(5):48-51.

[7] Chase R B,Aquilano N J,Jacobs F R.Operations management for competitive advantage[M].New Yo rk:McGraw-Hill/Irwin,2004:86-97.

[8] 王正林,龔純,何倩.精通MA TLAB科學(xué)計(jì)算[M].北京:電子工業(yè)出版社,2007:360-364.

[9] Caruana R A,Schaffer JD.Representation and hidden bias:gray vs.binary coding for genetic algorithm s[C]//Proc 5th Int Conf Machine Learning,Ann Arbor,Michigan.San Fransisco:Morgan Kaufmann Publishers Inc,1988:153-161.