基于網絡截集的裝配生產線瓶頸識別模型

劉桂林，趙東平

LIU Gui-lin1, ZHAO Dong-ping2

（1.西安飛機工業（集團）有限責任公司，西安 710089；2.西北工業大學 CAPP與制造工程軟件研究所，西安 710072）

0 引言

約束理論（Theroy of Constrains, TOC）[1]認為，任何系統都存在制約其發展的約束因素，瓶頸因素控制著整個系統的運作。在飛機裝配生產線中，由于工裝和工位數量眾多，瓶頸工位的存在嚴重制約著整個裝配生產線的產出率。重視對瓶頸的控制作用，通過提高瓶頸工位的裝配能力，實現整個飛機裝配生產線效率的提升。但在裝配生產線瓶頸控制之前，必須識別出的瓶頸所在的工位。因此，瓶頸識別技術成為解決裝配生產線瓶頸問題的關鍵所在。

針對瓶頸識別問題，很多學者進行了大量的研究。喬非針對多重制造系統的特點，提出了系統瓶頸和層瓶頸的概念，并以最高負荷為原則來識別系統瓶頸[2]；蘇國軍等通過設備利用率實現系統瓶頸的識別[3,4]；文翟穎妮提出一種基于關鍵路徑的瓶頸識別方法[5]；劉明周等提出瓶頸度及瓶頸指數這一動態指標，以全面衡量各個制造單元成為瓶頸的能力，進而實現瓶頸的動態預測[6]；陳友玲提出了擴展產能最小的制造單元即為瓶頸[7]。這些現有的瓶頸識別屬于事后瓶頸識別方法，大多是在生產系統運行一段時間后，通過對生產過程數據的采集和仿真分析進行瓶頸識別。在飛機裝配生產線中，這種事后瓶頸識別方法無法滿足飛機研制對成本和周期控制的需求。

為此，提出基于網絡截集的裝配生產線瓶頸識別模型，在飛機裝配生產線設計階段，充分考慮瓶頸的識別問題，為裝配生產線的瓶頸控制和優化奠定基礎。

1 裝配生產線瓶頸定義

1.1 最大流最小截理論

給定一個有向網絡D=(V，A)，在V中指定了三個點集合，分別稱為發點集（記為Vs），和收點集（記為Vt），其余的點稱為中間點集。任意兩點vi到vj的連接線稱為網絡的有向線，對于每一個有向線對應一個c(vi,vj)≥0(或簡寫為cij)，稱為有向線的容量[8]。

對于一個網絡，最大流問題就是求D上的一個可行流{Fij}，使其流量v(f)達到最大，并且滿足：

最大流最小截理論是指在任一個網絡D中，從Vs到Vt的最大流的流量等于分離Vs，Vt的最小截集的容量，即最大流最小截理論。最小截集可通過求解網絡的最大流得到。最小截集上的容量對網絡總容量的影響最為明顯。為提高網絡總容量，必須首先考慮改善最小截集中各有向線的容量，提高它們的通過能力。因此，最小截集上的有向線段是整個網絡上的瓶頸環節，它制約著網絡性能的提高。

1.2 裝配生產線瓶頸定義

對于一個產品從零件到成品組成的裝配網絡，根據最小截集理論，可定義如下概念：

1）發點集Vs：裝配網絡的發點集Vs為裝配線的起點集；

2）收點集Vt：裝配網絡的收點集Vt為裝配線終點集；

3）有向線(vi,vj)：裝配網絡的有向線描述有裝配工位件的約束關系；

4）有向線的容量cij：裝配網絡有向線的容量cij描述各工位的裝配能力（用工位裝配時間來表征）；

5）最大流v(f)：裝配網絡最大流為裝配線的最大裝配能力（用生產線最小裝配周期來表征）。

通過求解裝配網絡的最大裝配能力（即最小裝配周期），可以到網絡的一個最小截集。最小截上的容量（工位裝配時間）對整個裝配線的效率影響最大。所以，裝配生產線的瓶頸為最小截集所在的工位。裝配生產線瓶頸可描述為：

其中，CB為裝配線瓶頸；

CPi為裝配網絡最小截集上第i個工位的裝配時間；

2 裝配生產線瓶頸識別模型構建

2.1 有向裝配網絡

通過分析裝配生產線上各工位的裝配序列、工位關聯關系和零組件裝配優先級的基礎上，針對多工位裝配生產線，構建的裝配有向網絡如圖1所示。

圖1 有向裝配網絡

圖中各符號及其含義如表1所示。

表1 有向裝配網絡符號及其含義

2.2 基于有向裝配網絡的瓶頸識別數學模型

對于有向裝配網絡G=(V,A)，V為網絡G的頂點集，代表裝配網絡中的節點工位，A為網絡G的有向線集，表示各工位間的關系。將頂點集分為三部分：發點集、收點集和中間點集，設X為網絡的發點集（裝配線起點），Y為網絡的收點集（裝配線終點），W為中間點集（工位節點），則有以下性質：

對于發點集X中的每一個頂點xi，它都是網絡G中有向線的起點，對于收點集中的每一個頂點yi，它都是網絡G中有向線的終點，對于中間點集中的每一個頂點vk，它既是網絡G中有向線的起點，也是有向線的終點。

若M(G)中aij=1，則有向線(vi,vj)的容量為cij；若aij=0，則有向線(vi,vj)的容量為0。

按照網絡截集的定義，若頂點集V被剖分為兩個空集合Vs、Vt，使得那么有向線集(vi,vj)稱為是(分離Vs、Vt)的一個截集。為此，建立截集矩陣Kt。在容量矩陣C(G)中以截集起點集Vs所對應的行為截集矩陣Kt的行，在C(G)中以截集終點集Vt所對應的列為截集矩陣Kt的列。假設Vs等于裝配網絡發點集X及網絡中任意t個中間點則截集矩陣為：

截集矩陣的容量C(G)為：

根據最大流最小截定理，在網絡G中，從發點集X到收點集Y的最大流的流量等于分離X，Y的最小截集的容量。因此可得到裝配線網絡的最小裝配周期為：

通過“最大流最小截”定理將裝配線瓶頸識別問題轉化為裝配網絡頂點集的組合優化問題，即隨著頂點組合的改變而截集容量不斷改變的組合優化問題。

3 應用實例

某產品裝配線共有7個工位，根據已知條件和所提出的裝配有向網絡概念，構建的裝配有向網絡圖如圖2所示。

圖2 裝配有向網絡模型

根據有向裝配網絡，建立的鄰接矩陣M(G)如下：

容量矩陣C(G)如下：

任意t個中間點的截集矩陣為：

截集矩陣的容量Ct為：

根據所提方法的原理，網絡G中，從發點集X到收點集Y的最大流的流量等于分離X，Y的最小截集的容量，可得到裝配網絡的最小裝配周期為：

應用遺傳算法對上式進行求解，當進化到第17代時適值收斂。各次運行結果的最優適值均為74，如圖3（a）所示。即裝配網絡的最小裝配時間為74h。最優染色體為：1 1 0 1 0 1 1。

圖3 收斂曲線

采用Longest Queue方法求解本例的收斂曲線如圖3（b）所示，由圖可看出優化目標在26代收斂于74，驗證了所提方法的有效性。

故截集起點集Vs為截集終點集Vt為則有向裝配網絡的最小截集為

據前面的分析，截集各有向線容量即為工位裝配時間，要提高整個裝配線的效率，就必須減小最小截集中有向線的容量，即工位裝配時間。當截集中各有向線容量每增加1%的時，對裝配線效率的影響度如表2所示。

表2 截集有向線容量（工位裝配時間）對生產線效率的影響（單位：h）

從表2中可看出，各工位裝配時間減小相同幅度時，對生產線效率的影響度不同，結合裝配線瓶頸的定義式（2）可知，工位v5對裝配線效率的影響最大，因此它是裝配線瓶頸，對v5進行合理配置，能提高裝配線作業效率和平衡率。

4 結束語

針對飛機裝配生產線設計階段瓶頸識別困難的問題，提出了基于網絡截集的裝配生產線瓶頸識別模型。以一個7裝配生產線瓶頸識別為例，給出了瓶頸的定義，構建了裝配有向網絡模型，在最小截集和鄰接矩陣的基礎上，建立了基于最小截集的裝配生產線瓶頸識別模型，該模型完全避開了飛機裝配生產線的復雜約束條件，將瓶頸識別問題轉化為大規模的組合優化問題，為后續智能算法的求解奠定了基礎。工位裝配時間可變動情況下，復雜產品裝配線瓶頸識別算法的研究將是下一步的研究方向。

[1] WATSO NK J,BLACKS TONEJH,GARDINER S C.The evolution of a management philosophy： the theory of con-strains [J].Journal of O pertain M management, 2007,25(2)：387-402.

[2] 喬非,馬玉敏,李莉,等.基于分層瓶頸分析的多重制造系統調度方法[J].計算機集成制造系統,2010,16(04)：855-860.

[3] 蘇國軍,汪雄海.半導體制造系統改進Petri網模型的建立及優化調度[J].系統工程理論與實踐,2011,31(7)：1372-1377.

[4] ZHOU Z G, ROSE O. A bottleneck detection and dynamic dispatching strategy for semiconductor wafer fabrication facilities [A].Proceedings of the 2009 Winter Simulation Conference. Washington, D. C.,USA：IEEE[C],2009：1646-1656.

[5] 翟穎妮,孫樹棟,王軍強,王萌.基于正交試驗的作業車間瓶頸識別方法[J].計算機集成制造系統,2011,17(7)：1945-1952.

[6] 劉明周,單暉,蔣增強,等.不確定條件下車間動態重調度優化方法[J].機械工程學報,2009,45(10)：137-142.

[7] 陳友玲,張永陽,孫亞南,等.基于Petri網的敏捷化生產調度建模方法[J].計算機集成制造系統,2010,16(3)：598-62.

[8] L. Li, Q. Chang, and J. Ni.Data driven bottleneck detection of manufacturing systems[J].International Journal of Production Research,2009,47(18)：5019-5036.