潘曉勇，巫 江，石宇強，石小秋

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

（1.四川長虹電器股份有限公司 工程技術中心，綿陽 621000；2.西南科技大學 制造科學與工程學院，綿陽 621010）

0 引言

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

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

1 H型生產線的提出

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

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

圖1 直線型生產線

圖2 H型生產線

2 H型生產線平衡的數學模型及算法

2.1 模型假設

為了簡化問題，做如下假設：

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

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

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

2.2 模型的建立

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

1）目標函數

2）約束條件

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

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

（3）對于任何的Sk，,且若，則。

（4）對于任何的Sl，,且若，則。

2.3 模型的TS算法

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

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

3 實例驗證

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

首先，利用秒表測時采集相關數據，對現行生產線進行Flexsim仿真，分析可能存在的問題。其次，應用上述數學模型對工位進行組合優(yōu)化計算。最后，利用Flexsim仿真改善后的方案，進行前后對比。

表1 現行工位工時及人力

3.1 Flexsim對現行生產線仿真

C公司屏車間下游的兩條平行的組裝生產線，涉及到27個人，13個工位。通過秒表測時，得出現行的一條生產線工位工時及人力如表1、對現行組裝線仿真如圖3、各工位人員利用率如表2。

圖3 現行組裝生產線仿真

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

表2 工位人員利用率

3.2 TS算法實現

TS算法具體參數設計描述如下：初始解為原始作業(yè)順序；適配值函數為；鄰域結構為對換，鄰域大小為4*P_size（本文的P_size為48）；禁忌對象為解的狀態(tài)，即作業(yè)元素的順序；候選解的選擇是結合先后關系矩陣（由于本文是48個作業(yè)元素，先后關系矩陣為48*48的矩陣），隨機選擇20個為候選集；禁忌長度為靜態(tài)禁忌長度2*P-size；特赦準則為基于適配值得原則，當優(yōu)于Best so far時，解禁禁止狀態(tài)，當候選解全部被禁止時，選擇適配值最好的狀態(tài)解禁作為當前解；集中性和多樣性矛盾處理為：當某個狀態(tài)的禁忌頻率達到2時候，以此狀態(tài)初始化，重新搜索，當經過200步后，還沒有出現禁忌頻率為2狀態(tài)時，重新初始化算法；終止準則為算法運行2000步。用MATLAB編程實現，解得作業(yè)順序為：T=[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]，目標函數F=0.0911。作業(yè)順序分配到工位之后如表4所示。

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

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

對優(yōu)化后的組裝線進行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 結論

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

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

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

[3]宋華明,韓玉啟.多目標裝配線平衡的優(yōu)化算法[J].運籌與管理,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型生產線平衡[J].系統(tǒng)工程學報,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.