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

唐秋華,陳 立,王雪蘭

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

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

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

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

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

1 問題描述

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

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

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

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

1.2 數(shù)學模型

目標函數(shù)為

約束條件為

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

2 改進的遺傳算法

2.1 染色體編碼

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

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

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

2.3 遺傳算子

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

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

圖2 交叉算子Fig.2 Crossover operator

隨機選擇交叉位n,如果n

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

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

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

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

3 實例分析

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ū)域進行編碼,如表2所示。

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

從圖4中可以看出,緩存區(qū)13存在多個半成品物流匯聚,有可能導致物料混亂,在運送物料到下一個工位之前需要重新審查其類型,給運輸增加了不必要的麻煩。同時,車間布局雜亂、空間浪費、物流路線迂回、物流量較大的作業(yè)單位距離較遠,這都造成了物流成本的增加,而且目前的車間布局不適應多品種小批量生產(chǎn)模式,生產(chǎn)柔性較差。當該車間需要提升產(chǎ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è)效率,擬定以S形混合流水線組織生產(chǎn),所以車間布局主要考慮生產(chǎn)加工設(shè)備的布局,而不考慮暫存區(qū)的位置和大小。在車間長度尺寸約束下,兩行布局即可完成既定任務,導致最后得到的生產(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臺機器的布局需要納入重構(gòu)范圍。提取這12臺機器的長、寬、高數(shù)據(jù),用矩陣[L,W,H]T表示;并用矩陣表示這12臺機器布置時不發(fā)生干涉的最小間距。

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

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

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

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

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

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

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

4 結(jié)語

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

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

[2] 唐秋華,肖飛,王雪蘭.基于SLP和Flexsim的車間重構(gòu)研究[J].武漢理工大學學報:交通科學與工程版,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].北京:科學出版社,2000:124-138.

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

[6] 王小娟,鈕志強.基于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科學計算[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.