H型生產(chǎn)線平衡研究

潘曉勇，巫 江，石宇強(qiáng)，石小秋

PAN Xiao-yong1,WU Jiang1,SHI Yu-qiang2,SHI Xiao-qiu2

（1.四川長(zhǎng)虹電器股份有限公司 工程技術(shù)中心，綿陽(yáng) 621000；2.西南科技大學(xué) 制造科學(xué)與工程學(xué)院，綿陽(yáng) 621010）

0 引言

生產(chǎn)線平衡問題（Line Balancing Problem,簡(jiǎn)稱LBP）是一個(gè)組合優(yōu)化問題，1954年由美國(guó)人Bryton B提出并開始著手解決。在此之后，許多學(xué)者發(fā)表大量論文以解決這類組合優(yōu)化問題，平衡方法有：數(shù)學(xué)最優(yōu)化方法、啟發(fā)式算法以及工業(yè)工程的工作研究方法；對(duì)生產(chǎn)線類型的研究包括直線型和U型生產(chǎn)線。

文獻(xiàn)[1]和[2]提出了遺傳算法和改進(jìn)遺傳算法求解生產(chǎn)線平衡問題；文獻(xiàn)[3]提出了生產(chǎn)線平衡問題的多目標(biāo)優(yōu)化問題等。這些論文都是解決直線型生產(chǎn)線平衡的組合優(yōu)化問題，但直線型生產(chǎn)線有明顯的不足，文獻(xiàn)[4]提出的U型生產(chǎn)線克服了直線型生產(chǎn)線的不足。但在某些情況下，直線型和U型生產(chǎn)線并不適合，本文提出將兩條平行的生產(chǎn)線改成H型生產(chǎn)線的優(yōu)化方法。許多文獻(xiàn)提出遺傳算法求解線平衡組合優(yōu)化問題[1,2,5,6]，但作業(yè)元素順序之間存在先后關(guān)系，在遺傳變異時(shí)，不能保證變異后是可行解，這增加了算法實(shí)現(xiàn)的難度。在分析比較各種智能算法的基礎(chǔ)上，鑒于TS（禁忌搜索算法）算法的特點(diǎn)，在鄰域解產(chǎn)生候選解時(shí)，加入了先后關(guān)系矩陣，保證了候選解的可行性。通過設(shè)定合理的禁忌頻率來自動(dòng)平衡集中性和多樣性搜索。最后應(yīng)用MATLAB編程實(shí)現(xiàn)算法并利用Flexsim仿真驗(yàn)證。

1 H型生產(chǎn)線的提出

直線型生產(chǎn)線有分工細(xì)、員工熟練度高等優(yōu)點(diǎn)，但過細(xì)的分工容易使工人產(chǎn)生心理疲勞并且工位間相隔較遠(yuǎn)，員工不易交流。Miltenburg和Wijngaard在文獻(xiàn)[4]中提出的U型生產(chǎn)線很好的解決了上述缺點(diǎn)。U型生產(chǎn)線的工位之間相距較近，并且入口和出口在同一個(gè)位置，可以利用這個(gè)特點(diǎn)實(shí)現(xiàn)彈性作業(yè)人數(shù)（少人化技術(shù)）[6]。

但某些情況下，直線型和U型生產(chǎn)線并不適合。例如某些組裝生產(chǎn)線，由于上游產(chǎn)量大，組裝車間為了達(dá)到產(chǎn)量的需要，通常設(shè)計(jì)為平行的兩條直線型生產(chǎn)線（如圖1所示），但在線平衡率和人員利用率的雙重壓力下，這種設(shè)計(jì)顯然是不合理的。直線型生產(chǎn)線有其固有的缺點(diǎn)，又由于有空間和產(chǎn)量的要求，U型生產(chǎn)線也不適合。針對(duì)這類情況，本文提出將兩條平行的生產(chǎn)線改成H型生產(chǎn)線的優(yōu)化方法。H型生產(chǎn)線即共用平行的兩條生產(chǎn)線的某些工位（如圖2所示），共用工位處，我們稱之為結(jié)點(diǎn)。如在機(jī)器控制節(jié)拍，人員操作時(shí)間不足節(jié)拍的一半；某個(gè)工位隨機(jī)性強(qiáng)，容易造成瓶頸，則在這個(gè)工位的下一道工位空閑的概率增大等這些情況可以成為結(jié)點(diǎn)。H型生產(chǎn)線的優(yōu)點(diǎn)在于兩條線之間的工位相距較近，便于交流互助；共用了某些工位，節(jié)約了人員；由于共用工位，可以更好的提高線平衡率。

圖1 直線型生產(chǎn)線

圖2 H型生產(chǎn)線

2 H型生產(chǎn)線平衡的數(shù)學(xué)模型及算法

2.1 模型假設(shè)

為了簡(jiǎn)化問題，做如下假設(shè)：

1）把作業(yè)劃分為不能再分的作業(yè)元素，并且考慮了拿工具和配件的時(shí)間，用先后關(guān)系矩陣表示作業(yè)元素間的固有順序。

2）確一個(gè)作業(yè)元素順序，在滿足作業(yè)順序的前提下，一個(gè)作業(yè)元素可以被分配到任何一個(gè)工位。

3）確定了作業(yè)順序之后，依次把作業(yè)元素分配到各個(gè)工位，并滿足一個(gè)工位作業(yè)元素時(shí)間之和不超過給定的固定節(jié)拍，結(jié)點(diǎn)處節(jié)拍為整體節(jié)拍的一半。

2.2 模型的建立

記n為H型生產(chǎn)線業(yè)元素個(gè)數(shù)；m為工位個(gè)數(shù)；C 為生產(chǎn)線節(jié)拍；作業(yè)元素的集合為；ti為各個(gè)作業(yè)元素的時(shí)間；為作業(yè)元素的一個(gè)排列；Sk為第k個(gè)工位的作業(yè)元素集合，Sl第l 個(gè)結(jié)點(diǎn)的作業(yè)元素集合；η為生產(chǎn)線平衡率：

1）目標(biāo)函數(shù)

2）約束條件

（1）在確定作業(yè)元素順序時(shí)，要滿足優(yōu)先關(guān)系矩陣A ={aij}，A是只有-1,0,1,2四種元素的矩陣。aij=1表示作業(yè)元素Ti優(yōu)先于作業(yè)元素Tj；aij=0表示作業(yè)元素Ti與Tj無優(yōu)先關(guān)系；aij=-1表示作業(yè)元素Ti后與作業(yè)元素Tj；aii=2是矩陣對(duì)角元素的值，不參與判斷先后關(guān)系。

（2）若Ti∈ Sk，Tj∈ Sh且Ti優(yōu)先于Tj，則?Ti∈ Sk優(yōu)先于?Tj∈ Sh。

（3）對(duì)于任何的Sk，,且若，則。

（4）對(duì)于任何的Sl，,且若，則。

2.3 模型的TS算法

TS（禁忌搜索算法）算法是美國(guó)科羅拉多大學(xué)（University of Colorado）的Glover教授提出的。禁忌搜索算法是對(duì)人的思維模式的一種模擬，其應(yīng)用領(lǐng)域不僅涵蓋了組合優(yōu)化問題的各個(gè)方面，而且在函數(shù)優(yōu)化方面也取得了成就。

本文在傳統(tǒng)TS算法的基礎(chǔ)上進(jìn)行了如下改進(jìn)：在鄰域解產(chǎn)生候選解時(shí)，因有作業(yè)順序的約束，加入了先后關(guān)系矩陣，保證了產(chǎn)生的候選解的可行性；通過設(shè)定合理的禁忌頻率來自動(dòng)平衡集中性和多樣性搜索的矛盾，解決了局部最優(yōu)解和全局最優(yōu)解的矛盾。

3 實(shí)例驗(yàn)證

C公司是國(guó)內(nèi)一家生產(chǎn)等離子顯示器（PDP）的公司，該公司采用進(jìn)口生產(chǎn)線，技術(shù)先進(jìn)自動(dòng)化程度高。但該公司屏車間下游平行的兩條組裝生產(chǎn)線，人員密集，線平衡率低，人員利用率低，造成了巨大的浪費(fèi)。需要對(duì)此進(jìn)行改善，以期提高線平衡率和人員利用率。

首先，利用秒表測(cè)時(shí)采集相關(guān)數(shù)據(jù)，對(duì)現(xiàn)行生產(chǎn)線進(jìn)行Flexsim仿真，分析可能存在的問題。其次，應(yīng)用上述數(shù)學(xué)模型對(duì)工位進(jìn)行組合優(yōu)化計(jì)算。最后，利用Flexsim仿真改善后的方案，進(jìn)行前后對(duì)比。

表1 現(xiàn)行工位工時(shí)及人力

3.1 Flexsim對(duì)現(xiàn)行生產(chǎn)線仿真

C公司屏車間下游的兩條平行的組裝生產(chǎn)線，涉及到27個(gè)人，13個(gè)工位。通過秒表測(cè)時(shí)，得出現(xiàn)行的一條生產(chǎn)線工位工時(shí)及人力如表1、對(duì)現(xiàn)行組裝線仿真如圖3、各工位人員利用率如表2。

圖3 現(xiàn)行組裝生產(chǎn)線仿真

通過計(jì)算，現(xiàn)行組裝線平衡率為68.90%，還有很大的改善空間。從數(shù)據(jù)中發(fā)現(xiàn)，工位平均利用率為54.68%。其中工位1的人員利用率為38.40%，其原因是2個(gè)人員為輔助作業(yè)，人員操作時(shí)間為10S，固定節(jié)拍為26S，所以工位1可以節(jié)約一個(gè)人力。工位2人員利用率為18.90%，操作為將屏搬上機(jī)器手，時(shí)間為5S，另外一個(gè)工作人員將屏搬運(yùn)到工位附近暫存區(qū)。因此，我們把兩條線的工位合并，即H型生產(chǎn)線的結(jié)點(diǎn)，節(jié)約人力2人。工位3和工位是沒有人員，保持原樣。對(duì)工位5到工位13進(jìn)行作業(yè)元素劃分，如表3。

表2 工位人員利用率

3.2 TS算法實(shí)現(xiàn)

TS算法具體參數(shù)設(shè)計(jì)描述如下：初始解為原始作業(yè)順序；適配值函數(shù)為；鄰域結(jié)構(gòu)為對(duì)換，鄰域大小為4*P_size（本文的P_size為48）；禁忌對(duì)象為解的狀態(tài)，即作業(yè)元素的順序；候選解的選擇是結(jié)合先后關(guān)系矩陣（由于本文是48個(gè)作業(yè)元素，先后關(guān)系矩陣為48*48的矩陣），隨機(jī)選擇20個(gè)為候選集；禁忌長(zhǎng)度為靜態(tài)禁忌長(zhǎng)度2*P-size；特赦準(zhǔn)則為基于適配值得原則，當(dāng)優(yōu)于Best so far時(shí)，解禁禁止?fàn)顟B(tài)，當(dāng)候選解全部被禁止時(shí)，選擇適配值最好的狀態(tài)解禁作為當(dāng)前解；集中性和多樣性矛盾處理為：當(dāng)某個(gè)狀態(tài)的禁忌頻率達(dá)到2時(shí)候，以此狀態(tài)初始化，重新搜索，當(dāng)經(jīng)過200步后，還沒有出現(xiàn)禁忌頻率為2狀態(tài)時(shí)，重新初始化算法；終止準(zhǔn)則為算法運(yùn)行2000步。用MATLAB編程實(shí)現(xiàn)，解得作業(yè)順序?yàn)椋篢=[1,2,13,3,5,6,4,14,15,7,8,9,10,12,11,29,16,17,20,18,19,21,22,25,23,24,28,26,27,31,32,34,35,33,37,36,41,42,44,43,40,38,39,45,46,47,48]，目標(biāo)函數(shù)F=0.0911。作業(yè)順序分配到工位之后如表4所示。

表4 作業(yè)元素分配到工位表

3.3 Flexsim對(duì)優(yōu)化后組裝線的仿真

對(duì)優(yōu)化后的組裝線進(jìn)行Flexsim仿真分析（圖4）。

圖4 優(yōu)化后組裝線仿真

改善后的人員利用率及節(jié)拍如表5所示。

表5 人員利用率及節(jié)拍

3.4 優(yōu)化效果分析

改善前人力為27，改善后的人力為19；改善前人員利用率40.06%，改善后人員利用率79.70%；改善前線平衡率為68.90%，改善后線平衡率93.76%。前后比較如圖5～圖7所示。

圖5 人力

圖6 人員利用率

圖7 線平衡率

4 結(jié)論

針對(duì)某一類生產(chǎn)線，提出將平行的兩條生產(chǎn)線改成H型生產(chǎn)線的優(yōu)化方法并建立線平衡模型，用TS算法求解。通過對(duì)C公司現(xiàn)場(chǎng)調(diào)研，抽象出上述線平衡模型并求解之。再利用Flexsim對(duì)優(yōu)化后的方案進(jìn)行仿真，表明線平衡率和人員利用率都有所提高。但本文建立的數(shù)學(xué)模型沒有考慮到H型生產(chǎn)線兩條線中節(jié)拍和工位的不同，對(duì)模型稍加改進(jìn)就可以應(yīng)用于兩條線中節(jié)拍和工位不同的情況。在TS算法設(shè)計(jì)中，將先后關(guān)系矩陣引進(jìn)鄰域解產(chǎn)生候選解階段，雖然保證了解的可行性，但增加了算法的時(shí)間復(fù)雜性。在算法的集中性和多樣性的平衡問題上用禁忌頻率來自動(dòng)調(diào)整，但是并沒有給出不同情況下的不同禁忌頻率。

[1]扈靜,蔣增強(qiáng),等.基于改進(jìn)遺傳算法的混合裝配生產(chǎn)線平衡問題研究[J].合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版,2010,33(7)：1006-1009.

[2]蘭月政,魯建廈,等.基于遺傳算法的混流生產(chǎn)線產(chǎn)品分組指派問題研究[J].浙江工業(yè)大學(xué)學(xué)報(bào),2011,39(3)：312-316.

[3]宋華明,韓玉啟.多目標(biāo)裝配線平衡的優(yōu)化算法[J].運(yùn)籌與管理,2002,11(3)：55-62.

[4]Miltenburg G J,Wijngaard J.The U-line balancing problem[J].Management Science,1994,40(10)：1378-1388.

[5]宋華明,韓玉啟.基于遺傳算法的U型生產(chǎn)線平衡[J].系統(tǒng)工程學(xué)報(bào),2002,17(5)：424-429.

[6]Moden Y.Toyota Production Systems[M].Norcross：Industrial Engineering and Management Press,Institute of Industrial Engineers,1993,159-179.