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

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

(同濟(jì)大學(xué)現(xiàn)代制造技術(shù)研究所,上海 201804)

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

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

(同濟(jì)大學(xué)現(xiàn)代制造技術(shù)研究所,上海 201804)

研究一類裝配支線的物料輸送與緩沖問題,論文將傳送輥道作為緩沖區(qū)的補(bǔ)充,構(gòu)建基于輥道-緩沖區(qū)滿足總裝線產(chǎn)出率且最小化裝配支線緩沖區(qū)總?cè)萘康膬?yōu)化模型.考慮到裝配支線緩沖區(qū)容量配置與總線產(chǎn)出率之間不存在解析解,且裝配支線緩沖區(qū)總?cè)萘恳欢〞r工位間不同緩沖區(qū)配置也影響著總線的生產(chǎn).提出一種兩階段求解算法:第一階段,采用遺傳算法求解支線有限緩沖區(qū)總?cè)萘肯碌目傃b線最大產(chǎn)出率;第二階段,根據(jù)Gershwin關(guān)于緩沖區(qū)-產(chǎn)出率的研究理論,獲得總裝線產(chǎn)出率所對應(yīng)的裝配支線緩沖區(qū)總?cè)萘?并進(jìn)行支線緩沖區(qū)容量的合理分配.最后,通過案例分析驗(yàn)證該方法的有效性.

裝配支線; 輥道; 緩沖區(qū); 兩階段求解

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

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

1 問題描述

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

對于異步式裝配線而言,工位之間物料的運(yùn)送是通過輥道由人工啟動和停止,輥道的運(yùn)行是獨(dú)立的.所以,對于該類裝配支線緩沖區(qū)的配置,可以利用傳送輥道來承擔(dān)緩沖區(qū)的部分功能,而在輥道邊建立各工位之間的緩沖區(qū),這樣,不僅提高了裝配支線的產(chǎn)出率,而且提高了產(chǎn)出的穩(wěn)定性,大大降低兩線間的緩沖區(qū)容量.輥道一方面作為物料運(yùn)輸?shù)耐ǖ?另一方面可以在一定程度上承擔(dān)物料緩沖的功能.例如,物料放置在托盤,托盤放在輥道上,可根據(jù)輥道和托盤的長度來折算可容納的托盤總數(shù),即作為緩沖區(qū)的容量.在本文總-支線問題中,構(gòu)建基于異步式裝配線輥道-緩沖區(qū)的優(yōu)化模型,以滿足總裝線產(chǎn)出率且最小化支線緩沖區(qū)總?cè)萘繛榍蠼饽繕?biāo),并對支線緩沖區(qū)容量進(jìn)行合理配置.在保證總線產(chǎn)出的同時,降低了總、支線間緩沖區(qū)容量大小,提高了生產(chǎn)的穩(wěn)定性.

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

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

2.1 定義變量

K為裝配支線工位數(shù);B為裝配支線緩沖區(qū)容量配置的矢量;Bi為裝配支線第i個緩沖區(qū)的容量(i=1,2,…,K-1);B′i為裝配支線第i個輥道折算為緩沖區(qū)的容量(i=1,2,…,K-1);Li為裝配支線第i個輥道的長度(i=1,2,…,K-1);P為托盤沿輥道方向的長度;f(B)為裝配支線在緩沖區(qū)容量配置為B時的產(chǎn)出率;f*為裝配支線的目標(biāo)產(chǎn)出率,即總裝線產(chǎn)出率;ui為裝配支線第i個輥道旁允許設(shè)置的緩沖區(qū)最大容量(i=1,2,…,K-1);BT為裝配支線緩沖區(qū)的總?cè)萘?fmax為裝配支線緩沖區(qū)總?cè)萘克鶎?yīng)的最大產(chǎn)出率.

2.2 假設(shè)條件

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

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

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

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

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

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

在滿足總裝線的產(chǎn)出率的前提下,裝配支線利用輥道的輔助緩沖功能,配合線邊緩沖區(qū)的配置以最小化支線緩沖區(qū)總?cè)萘?符合第2類緩沖區(qū)配置問題模型.

(1)

(2)

(3)

(4)

(5)

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

3 算法求解

GERSHWIN在文獻(xiàn)8中對緩沖區(qū)與生產(chǎn)線產(chǎn)出率之間的關(guān)系進(jìn)行了分析和總結(jié),指出生產(chǎn)線緩沖區(qū)的總?cè)萘颗c其最大產(chǎn)出率之間滿足如圖2所示的關(guān)系.

圖2 緩沖區(qū)總?cè)萘?BT)與最大產(chǎn)出率(fmax)的關(guān)系Fig.2 Relationship between BT and fmax

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

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

3.1 第一階段求解

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

Maximizef(B)

(6)

(7)

(8)

(9)

(10)

式(6)是目標(biāo)優(yōu)化函數(shù),旨在求解裝配支線的最大產(chǎn)出率;約束條件(7)表示緩沖區(qū)總?cè)萘康扔谝粋€特定值BT,由上述試驗(yàn)得出的緩沖區(qū)-產(chǎn)出率關(guān)系可知,有限緩沖區(qū)容量與其對應(yīng)的最大產(chǎn)出率成線性關(guān)系,所以,獲得特定BT對應(yīng)的fmax,以便第二階段算法的線性迭代;式(8)表示輥道折算為緩沖區(qū)的數(shù)目;式(9)，(10)表示工位間緩沖區(qū)容量的取值范圍.

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

3.2 第二階段求解

由于裝配支線采用輥道連接前后工位,輥道能夠承擔(dān)部分緩沖區(qū)的功能.根據(jù)上述實(shí)驗(yàn)結(jié)果,采用線性迭代方法以獲得最佳緩沖區(qū)總?cè)萘?

基于BT與fmax之間的單調(diào)線性關(guān)系,算法需要確定兩個初始解B0、B1,對于B0,令B0=0,由仿真實(shí)驗(yàn)獲得對應(yīng)的fmax(B0),用上述遺傳算法求解B1下的fmax(B1),根據(jù)兩點(diǎn)(B0,fmax(B0))(B1,fmax(B1))確定一條直線,將f*帶入直線方程,用來估計(jì)B2的取值.對于j≥2,fmax的取得依靠遺傳算法的搜索,隨著j的增加算法迭代,每次迭代依賴于Bj-1和Bj來構(gòu)造下一個緩沖區(qū)總?cè)萘?直到fmax充分接近目標(biāo)產(chǎn)出率f*.

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

(12)

其中

(13)

(14)

取

(15)

則Bj可表示為

(16)

其中

(17)

(18)

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

3.3 兩階段算法流程

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

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

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

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

4 案例分析

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

圖4 發(fā)動機(jī)裝配線布局圖Fig.4 Layout of the engine assembly line

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

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

表1 輥道可用作緩沖區(qū)的容量

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

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

根據(jù)所構(gòu)建的工位-緩沖區(qū)-輥道模型,提出發(fā)動機(jī)缸蓋裝配支線問題的緩沖區(qū)配置模型:

(19)

(20)

(21)

1≤Bi≤10

(22)

(23)

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

按照表2對于缸蓋裝配支線系統(tǒng)參數(shù)進(jìn)行設(shè)置,其中設(shè)備故障的發(fā)生和修復(fù)符合指數(shù)分布,故障率表示設(shè)備故障發(fā)生的數(shù)學(xué)期望,平均修復(fù)時間MTTR表示設(shè)備故障修復(fù)的數(shù)學(xué)期望的倒數(shù),各工位的操作時間符合正態(tài)分布.

表2 各工位參數(shù)設(shè)置

按照上述的求解目標(biāo)設(shè)計(jì)了相應(yīng)求解步驟,首先確定B0=0為不設(shè)置線邊緩沖區(qū),只利用輥道作為緩沖區(qū),進(jìn)行一次仿真實(shí)驗(yàn)得出B0所對應(yīng)的產(chǎn)出率fmax(B0);

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

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

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

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

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

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

5 結(jié)論

分析總裝線與裝配支線的關(guān)系,針對一類異步式裝配支線,在線邊設(shè)置緩沖區(qū),并且利用傳送輥道作為緩沖區(qū)的補(bǔ)充,建立輥道-緩沖區(qū)的裝配支線模型,以最小化裝配支線緩沖區(qū)總?cè)萘繛閮?yōu)化目標(biāo),設(shè)計(jì)兩階段算法進(jìn)行求解,第一階段選擇遺傳算法求解特定緩沖區(qū)總?cè)萘肯碌淖畲螽a(chǎn)出率,第二階段根據(jù)Gershwin的研究結(jié)果,設(shè)計(jì)線性迭代算法,案例分析顯示在與遺傳算法進(jìn)行結(jié)合使用時,能夠有效的對第2類緩沖區(qū)配置問題進(jìn)行求解.

[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ī)器人自動化生產(chǎn)線緩沖區(qū)容量分配方法[J].機(jī)械工程學(xué)報(bào),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] 高貴兵,岳文輝,張道兵等.基于馬爾可夫過程的混流裝配線緩沖區(qū)容量研究[J].中國機(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] 宋士剛,李愛平,徐立云.可重組制造系統(tǒng)緩沖區(qū)容量的優(yōu)化研究[J].計(jì)算機(jī)集成制造系統(tǒng),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] 高瑋.現(xiàn)代智能仿生算法及其應(yīng)用[M].北京：科學(xué)出版社, 2011.

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

[10] MICHALEWICZ Z,FOGEL D B.如何求解問題: 現(xiàn)代啟發(fā)式方法[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

上海市科委科技攻關(guān)項(xiàng)目(15111105502);上海市重大技術(shù)裝備研制專項(xiàng)(ZB-ZBYZ-01-14-1562)

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

TH 181

A

1672-5581(2016)05-0449-06