一類裝配支線緩沖區配置的兩階段求解方法研究

李愛平, 李 聰, 張燕紅, 劉雪梅, 徐立云

(同濟大學現代制造技術研究所,上海 201804)

一類裝配支線緩沖區配置的兩階段求解方法研究

李愛平, 李 聰, 張燕紅, 劉雪梅, 徐立云

(同濟大學現代制造技術研究所,上海 201804)

研究一類裝配支線的物料輸送與緩沖問題,論文將傳送輥道作為緩沖區的補充,構建基于輥道-緩沖區滿足總裝線產出率且最小化裝配支線緩沖區總容量的優化模型.考慮到裝配支線緩沖區容量配置與總線產出率之間不存在解析解,且裝配支線緩沖區總容量一定時工位間不同緩沖區配置也影響著總線的生產.提出一種兩階段求解算法:第一階段,采用遺傳算法求解支線有限緩沖區總容量下的總裝線最大產出率;第二階段,根據Gershwin關于緩沖區-產出率的研究理論,獲得總裝線產出率所對應的裝配支線緩沖區總容量,并進行支線緩沖區容量的合理分配.最后,通過案例分析驗證該方法的有效性.

裝配支線; 輥道; 緩沖區; 兩階段求解

緩沖區配置問題是生產線設計中的一個NP-hard問題,旨在尋找最優的緩沖區容量分配以達到特定的目標[1].張良安等[2]針對機器人裝配的自動化生產線,建立生產線的可用度模型,運用遺傳算法優化其緩沖區.高貴兵等[3]基于馬爾可夫過程原理,建立混流裝配線模型,并推導出裝配線可用度與緩沖區容量之間的關系.宋士剛等[4]針對可重組制造系統的緩沖區配置,提出了緩沖區容量、機床可用度和任務需求率之間的函數關系,并通過粒子群算法以求解緩沖區的最小容量.MAGHSOUD等[5]針對異步式生產線提出緩沖區配置的多目標優化問題,運用遺傳算法結合仿真實驗以求解緩沖區容量的最佳配置.THOMAS等[6]針對異步式非平衡生產線進行緩沖區的容量分配,設置多組仿真實驗,利用統計工具對生產線的產出率、空閑時間及平均緩沖區水平進行分析,并與平衡生產線進行比較研究.PRZEMYSLAW等[7]構建了帶有返回路徑的生產線緩沖區優化模型,采用改進模擬退火算法進行求解,以取得生產線收益的最大化.

在汽車發動機的生產中,其裝配線經常是由一條總裝線與多條裝配支線構成,如缸蓋、活塞連桿等部件在支線完成裝配后,送至總線完成與發動機的合裝.對于一類異步式裝配支線的緩沖區配置問題,裝配支線的主要特點是需滿足總裝線產出率的要求,裝配支線的傳輸輥道也可以起到緩沖區的作用.本文針對該類總-支裝配線,以滿足總線產出率且最小化支線緩沖區容量為優化目標,采用兩階段求解算法,提高了求解的精準性和效率.

1 問題描述

產品的總裝涉及到若干部件的裝配過程,這些部件在裝配支線上完成裝配后,進入總裝線完成產品的合裝.如圖1所示,圖中總裝線工位以{1,2,…,i-2,i-1,i}表示,裝配支線工位用字母{1,2,…,m-2,m-1,m}表示,線邊緩沖區以{B1,B2,…,Bm-1,Bm}表示,工位之間的傳送輥道以輥道長度{L1,L2,…,Lm-2,Lm-1,Lm}表示.一般而言,裝配支線的產出率必須能夠保證達到總裝線的產出要求,以避免出現總裝線的停工.針對裝配支線因設備故障等因素可能出現的產出率降低.傳統做法是對其提前投料生產,并在總裝線與裝配支線間保持足夠的緩沖以存放零部件.然而,裝配支線的平均故障率會隨著支線長度的增加而增加,導致兩線間所需設置的緩沖區容量增大.

對于異步式裝配線而言,工位之間物料的運送是通過輥道由人工啟動和停止,輥道的運行是獨立的.所以,對于該類裝配支線緩沖區的配置,可以利用傳送輥道來承擔緩沖區的部分功能,而在輥道邊建立各工位之間的緩沖區,這樣,不僅提高了裝配支線的產出率,而且提高了產出的穩定性,大大降低兩線間的緩沖區容量.輥道一方面作為物料運輸的通道,另一方面可以在一定程度上承擔物料緩沖的功能.例如,物料放置在托盤,托盤放在輥道上,可根據輥道和托盤的長度來折算可容納的托盤總數,即作為緩沖區的容量.在本文總-支線問題中,構建基于異步式裝配線輥道-緩沖區的優化模型,以滿足總裝線產出率且最小化支線緩沖區總容量為求解目標,并對支線緩沖區容量進行合理配置.在保證總線產出的同時,降低了總、支線間緩沖區容量大小,提高了生產的穩定性.

圖1 總裝線與裝配支線位置關系Fig.1 Position relationship between assembly line and the branch assembly line

2 數學模型

2.1 定義變量

K為裝配支線工位數;B為裝配支線緩沖區容量配置的矢量;Bi為裝配支線第i個緩沖區的容量(i=1,2,…,K-1);B′i為裝配支線第i個輥道折算為緩沖區的容量(i=1,2,…,K-1);Li為裝配支線第i個輥道的長度(i=1,2,…,K-1);P為托盤沿輥道方向的長度;f(B)為裝配支線在緩沖區容量配置為B時的產出率;f*為裝配支線的目標產出率,即總裝線產出率;ui為裝配支線第i個輥道旁允許設置的緩沖區最大容量(i=1,2,…,K-1);BT為裝配支線緩沖區的總容量;fmax為裝配支線緩沖區總容量所對應的最大產出率.

2.2 假設條件

(1) 緩沖區和輥道不會發生故障;

(2) 每個自動化設備均有可能發生故障,且設備MTBF和MTTR已知;

(3) 每個工位的操作時間符合隨機分布,均值已知;

(4) 不考慮托盤在緩沖區中的物流時間;

(5) 第一個工位保證物料上線的及時,最后一個工位保證完成裝配任務后物料及時下線.

2.3 數學模型

在滿足總裝線的產出率的前提下,裝配支線利用輥道的輔助緩沖功能,配合線邊緩沖區的配置以最小化支線緩沖區總容量,符合第2類緩沖區配置問題模型.

(1)

(2)

(3)

(4)

(5)

式(1)是問題目標函數,旨在最小化裝配支線緩沖區總容量;約束(2)表明裝配支線產出率不能低于總裝線產出率;約束(3)表示傳送輥道折算為緩沖區的容量大小;約束(4),(5)表示輥道旁緩沖區容量的取值范圍.

3 算法求解

GERSHWIN在文獻8中對緩沖區與生產線產出率之間的關系進行了分析和總結,指出生產線緩沖區的總容量與其最大產出率之間滿足如圖2所示的關系.

圖2 緩沖區總容量(BT)與最大產出率(fmax)的關系Fig.2 Relationship between BT and fmax

由圖2所示,緩沖區總容量在不大的情況下與生產線最大產出率存在近似線性的關系,論文在求解第2類緩沖區問題時,求解目標是在滿足總裝線產出率的情況下最小化裝配支線緩沖區的總容量,由于不存在緩沖區容量配置與目標函數的解析式關系,所以在運用一階段算法進行搜索時,勢必會對不同緩沖區總容量BT下的不同配置進行搜索,從而增加了搜索范圍.所以設計兩階段求解算法:如圖3所示,算法執行前,首先選定初始BT,第一階段,利用遺傳算法求解BT所對應的fmax,如果fmax已充分接近總裝線產出率f*,則輸出BT即為裝配支線最小緩沖區容量,否則進入第二階段;第二階段利用第一階段所獲得的點(BT,fmax)確定緩沖區總容量-最大產出率的線性方程,將總裝線產出率f*代入方程以確定所對應的BT,返回給第一階段.經過兩階段的循環迭代,最終確定裝配支線最小緩沖區總容量.其中Bj-1和Bj表示迭代過程中前后兩個點所代表的裝配支線緩沖區總容量BT,后面會有詳細說明.

圖3 兩階段算法求解流程Fig.3 Solving procedure of two-stage method

3.1 第一階段求解

第一階段求解問題描述如下.

Maximizef(B)

(6)

(7)

(8)

(9)

(10)

式(6)是目標優化函數,旨在求解裝配支線的最大產出率;約束條件(7)表示緩沖區總容量等于一個特定值BT,由上述試驗得出的緩沖區-產出率關系可知,有限緩沖區容量與其對應的最大產出率成線性關系,所以,獲得特定BT對應的fmax,以便第二階段算法的線性迭代;式(8)表示輥道折算為緩沖區的數目;式(9)，(10)表示工位間緩沖區容量的取值范圍.

采用遺傳算法結合計算機仿真進行第一階段問題的求解,遺傳算法利用小區間生成法[9]生成初始種群,經過確定性選擇、隨機線性交叉[10]和變異進行種群迭代.

3.2 第二階段求解

由于裝配支線采用輥道連接前后工位,輥道能夠承擔部分緩沖區的功能.根據上述實驗結果,采用線性迭代方法以獲得最佳緩沖區總容量.

基于BT與fmax之間的單調線性關系,算法需要確定兩個初始解B0、B1,對于B0,令B0=0,由仿真實驗獲得對應的fmax(B0),用上述遺傳算法求解B1下的fmax(B1),根據兩點(B0,fmax(B0))(B1,fmax(B1))確定一條直線,將f*帶入直線方程,用來估計B2的取值.對于j≥2,fmax的取得依靠遺傳算法的搜索,隨著j的增加算法迭代,每次迭代依賴于Bj-1和Bj來構造下一個緩沖區總容量,直到fmax充分接近目標產出率f*.

當j≥2,Bj由Bj-2和Bj-1決定,可以得出如下方程.

(12)

其中

(13)

(14)

取

(15)

則Bj可表示為

(16)

其中

(17)

(18)

如果BT比較大時,BT與fmax不能保證近似的線性關系,該方法需要進行修正.

3.3 兩階段算法流程

步驟1 設定B0=0,并通過仿真法得出該配置下的fmax(B0),確定初始解B1的值,并初始化遺傳算法參數,通過第一階段遺傳算法求解得出fmax(B1),若fmax(B1)≥f*,則輸出B1即為最小緩沖區容量,否則令j=2;

步驟2 通過公式(16)計算Bj;

步驟3 通過第一階段遺傳算法獲得Bj所對應的fmax(Bj);

步驟4 對fmax(Bj)進行判斷,如果fmax(Bj)≥f*且fmax(Bj-1)

4 案例分析

某工廠發動機裝配線如AutoCAD圖4所示,由發動機總裝線(左,只顯示內裝部分)和缸蓋裝配支線(右)組成,缸蓋裝配支線在完成缸蓋的裝配之后,通過機械手將缸蓋運送至總裝線與缸體進行合裝.總裝線要求生產節拍78 s,年產量30萬臺,每年開工300 d,三班制生產.缸蓋裝配支線為雙排直線環形布置形式,采用動力可積放式輥道輸送線,其上配置隨行托盤實現裝配的柔性流水裝配作業,各工位均設有托盤停止器,用于托盤?？?裝配操作為站內操作,即托盤/工件停止于工位內裝配,輥道邊各工位間均可設置緩沖區.

圖4 發動機裝配線布局圖Fig.4 Layout of the engine assembly line

缸蓋裝配支線共設置13個工位,配置6個自動站、1個半自動站、1個返修站、4個手動站及1個工件返修出入口;自動站分別完成OP30氣門油封壓裝、OP50止回閥壓裝、OP70氣門鎖夾的壓裝、OP80氣門鎖夾裝配狀態檢測、OP90氣門拍打和OP100氣門與油封及座圈密封性檢測、缸蓋異物排出;半自動站完成OP40氣門安裝前后的缸蓋翻轉;返修站完成OP110氣門油封、氣門及氣門鎖夾的返修更換;手動站OP10、OP130在缸蓋上下線工位設有兩臺單梁吊車分別完成缸蓋的上、下線.

考慮到返修工位的利用率與其他工位相比很小,對整線的物流影響有限,所以沒有必要在返修工位前設置額外的緩沖區,因此對該工藝流程稍作簡化,去掉返修工位及其相關輥道部分.則缸蓋裝配支線的工藝流程為:OP10缸蓋上線OP20拆卸凸輪軸蓋OP30裝氣門油封OP40裝缸蓋氣門OP50裝止回閥OP60裝氣門彈簧、擰緊火花塞OP70裝缸蓋氣門鎖夾OP80激光鎖夾檢測OP90氣門拍打OP100燃燒室密封性檢測OP130缸蓋下線.根據各工位前后輥道的可用長度,可以確定各輥道可用作緩沖區的容量,如表1所示.

表1 輥道可用作緩沖區的容量

則缸蓋裝配支線的工位-輥道-緩沖區模型可表示為如圖5所示,其中B1至B10表示在工位間輥道旁邊所建立的緩沖區.

圖5 缸蓋裝配支線緩沖區模型圖Fig.5 Buffer's Model of the cylinder head assembly line

根據所構建的工位-緩沖區-輥道模型,提出發動機缸蓋裝配支線問題的緩沖區配置模型:

(19)

(20)

(21)

1≤Bi≤10

(22)

(23)

其中B′i由表1得出,B′1表示OP10-OP20之間的輥道折算為緩沖區的容量,依次類推,f*表示總裝線的產出率,案例以一個月的產出為求解目標,即保證發動機的月產量為f*=33 000,最小化緩沖區的總容量,得出最佳的緩沖區配置方式B=(B′1,B1,...B′10,B10).

按照表2對于缸蓋裝配支線系統參數進行設置,其中設備故障的發生和修復符合指數分布,故障率表示設備故障發生的數學期望,平均修復時間MTTR表示設備故障修復的數學期望的倒數,各工位的操作時間符合正態分布.

表2 各工位參數設置

按照上述的求解目標設計了相應求解步驟,首先確定B0=0為不設置線邊緩沖區,只利用輥道作為緩沖區,進行一次仿真實驗得出B0所對應的產出率fmax(B0);

步驟1 令BT=B1=K-1,利用上述遺傳算法運算流程獲得對應的fmax(B1);

步驟2 利用公式(16)得出B2的值,返給第一階段的BT;

步驟3 一、二階段循環迭代,直到fmax(Bj)滿足總裝線產出率f*,且fmax(Bj-1)

遺傳算法運行代數設置為50,變異率0.2 交叉率0.8,每代個體30.將完成一次兩階段的算法實施過程稱為一次迭代過程,如圖6所示,經過3次迭代之后,獲得最小緩沖區容量為23,而且每次迭代所得結果滿足線性關系,所以,不需要對算法進行修正,即可得出在滿足發動機月產量為33 000(30 d無間斷生產)的要求下,缸蓋裝配支線緩沖區的最小容量為23,相應的最小緩沖區容量配置見表3所示.

圖6 兩階段算法迭代圖Fig.6 Iteration of two-stage method表3 裝配支線最小緩沖區容量配置Tab.3 Optimal buffer allocation of the branch assembly line

輥道輥道容量緩沖區容量輥道輥道容量緩沖區容量OP10-OP2016OP60-OP7001OP20-OP3012OP70-OP8001OP30-OP4031OP80-OP9022OP40-OP5021OP90-OP10020OP50-OP6016OP100-OP13013

5 結論

分析總裝線與裝配支線的關系,針對一類異步式裝配支線,在線邊設置緩沖區,并且利用傳送輥道作為緩沖區的補充,建立輥道-緩沖區的裝配支線模型,以最小化裝配支線緩沖區總容量為優化目標,設計兩階段算法進行求解,第一階段選擇遺傳算法求解特定緩沖區總容量下的最大產出率,第二階段根據Gershwin的研究結果,設計線性迭代算法,案例分析顯示在與遺傳算法進行結合使用時,能夠有效的對第2類緩沖區配置問題進行求解.

[1] DEMIR L,TUNALI S,ELIIYI D T.The state of the art on buffer allocation Problem:a comprehensive survey[J].Journal of Intelligent Manufacturing,2014,25(3):371-392.

[2] 張良安,梅江平,黃田.基于遺傳算法的機器人自動化生產線緩沖區容量分配方法[J].機械工程學報,2010,46(11):101-106.

ZHANGLiangan,MEI Jiangping,HUANG Tian.Genetic algorithm-based buffer allocation of a robot production line[J].Journal of Mechanical Engineering,2010,46(11):101-106.

[3] 高貴兵,岳文輝,張道兵等.基于馬爾可夫過程的混流裝配線緩沖區容量研究[J].中國機械工程,2013,24(18):2524-2528.

GAO Guibing,YUE Wenhui,ZHANG Daobing et al.Research on buffer capacity for mixed-model assembly lines based on markov Process[J].China Mechanical Engineering,2013,24(18):2524-2528.

[4] 宋士剛,李愛平,徐立云.可重組制造系統緩沖區容量的優化研究[J].計算機集成制造系統,2008(10):1951-1956.

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

[5] AMIRI M,MOHTASHAMI A.Buffer allocation in unreliable production lines based on design of experiments,simulation,and genetic algorithm[J].International Journal of Advanced Manufacturing Technology,2012,62(1-4):371-383.

[6] THOMAS MCNAMAR,SABRY SHAABAN,SARAH HUDSON.Simulation of unbalanced buffer allocation in unreliable unpaced production lines[J].International Journal of Production Research,2013,51(6):1922-1936.

[7] PRZEMYSLAW KORYTKOWSKI,TOMASZ WISNIEWSKI,OLEG ZAIKIN.Optimal buffer allocation in re-entrant job shop production using simulated annealing[J].Management and Production Engineering Review,2010,1(3)：30-40.

[8] GERSHWIN S B,Schor J E.Efficient algorithms for buffer space allocation[J].Annals of Operations Research,2000,93(4):117-144.

[9] 高瑋.現代智能仿生算法及其應用[M].北京：科學出版社, 2011.

GAO Wei. Modern intelligent algorithm and its application[M].Beijing: Science Press, 2011.

[10] MICHALEWICZ Z,FOGEL D B.如何求解問題: 現代啟發式方法[M].北京：中國水利水電出版社,2003.

MICHALEWICZ Z,FOGEL D B.How to solve it: modern heuristics[M].Beijing:China Water&Power Press,2003.

Two-tage solution on buffer allocationfor branch assembly line

LI Ai-ping, LI Cong, ZHANG Yan-hong, LIU Xue-mei, XU Li-yun

(Institute of Advanced Manufacturing Technology, Tongji University, Shanghai 201804)

To solve the material conveyance and buffer allocation problem on branch assembly line, the transfer roller is treated as a complement to buffer. Accordingly, a roller-buffer assembly line model is established for desired production rate with the minimum total buffer capacity. Due thatthe buffer allocation, along with production rate,cannot be expressed by analytical solution, specifically for limited total buffer capacity for stations, a two-stage solution is postulated. In the first stage, the maximum production rate of total buffer capacity is attained using genetic algorithm. In the secondary stage, the branch total buffer capacity, together with buffer allocation optimization,is obtained via Gershwin's theory. To this end, the casesare employed to demonstrate the effectiveness of this approach.

branch assembly line；roller；buffer；two-stage solution

上海市科委科技攻關項目(15111105502);上海市重大技術裝備研制專項(ZB-ZBYZ-01-14-1562)

李愛平(1951-),女,教授,博士生導師.E-mail:limuzi@#edu.cn

TH 181

A

1672-5581(2016)05-0449-06