基于有向加權網絡的混流生產線產能規劃方法

楊 挺 張定華 陳 冰 李 山

西北工業大學現代設計與集成制造技術教育部重點實驗室，西安，710072

0 引言

當前，市場競爭愈加激烈，汽車、飛機、航空發動機和機械產品等離散制造業需要快速靈活地組織生產來開發出高質量、低成本、高附加值的新產品，因此，柔性生產逐漸成為主導的生產組織模式。多品種混流生產線是柔性生產普遍采用的一種實現方式，混流生產線是在基本不改變現有生產手段、生產條件和生產能力的前提下，通過改變生產組織方式，在一定時間內，在同一條流水線上生產出多種不同型號、不同數量的產品的一種生產線［1－2］。

生產線代表了企業的基礎生產能力。混流生產線具有工藝環節多、結構復雜、工序分散、零件周轉路徑長等特點，是各種復雜因素相互作用和相互影響的復雜系統。生產線產能規劃是根據產品的產量與品種組合及其制造工藝，對制造資源進行優化配置的過程。目前，生產線產能規劃的方法主要包括隨機規劃方法［3－4］、基于投入－產出模型的能力規劃方法［5］、線性規劃方法［6］。這些方法都能從宏觀角度分析生產線的產品需求、制造能力和庫存策略［7］，并能以制造資源負載均衡或生產周期最短為目標進行產能規劃。生產線產能規劃不僅僅是一個頂層的規劃問題，在生產過程中設備的可靠性、故障率，操作人員的班次安排以及物料搬運系統的性能對生產線的整體狀態有著非常重要的影響，生產線的穩定性是產能規劃的基礎，只有穩定的生產才能有可靠的產能。特別是混流生產線中的某些設備承擔了多種產品的制造任務，設備故障往往會造成工藝路線的中斷和其他工位的負載波動。生產線的魯棒性和可靠性是不容忽視的問題，只有可靠的生產線才會有穩定的產能。因此，生產線產能規劃要在保證生產線穩定性的基礎上，對生產線進行設計與能力配置。

1 基于有向加權網絡的混流生產線模型

1．1 混流生產線的有向網絡模型

生產線是由制造資源、制造工藝和產品所組成的制造系統。制造資源在生產線中以一定的方式組成具備獨立制造能力的高內聚松耦合的工位，并在制造工藝的驅動下通過物料搬運系統實現工件在工位之間的流動來完成制造行為，得到滿足生產要求的最終產品。這樣多種產品的工藝路線就在各個工位之間形成了具有復雜特性的網絡結構。以網絡形式表現的復雜系統普遍存在于自然界與人類社會中，許多研究者通過構建網絡模型對復雜系統進行建模與仿真，并依據網絡結構的拓撲特性和基本特征來研究系統的運行狀態和動態行為［8－10］。文獻［11－12］指出，關鍵節點的失效會導致整個系統的災難性崩潰。

在機械制造領域，Tang等［13］提出了基于有向圖（directed diagram）的設計過程描述方法，實現了設計任務的重組與規劃。劉新華等［14］通過定義一個非負值的加權簡單有向圖給出了零件可行性工藝路線圖，從而將工藝路線規劃問題轉化為在可行性工藝路線圖中的路徑尋優問題，解決了多工藝路線的決策問題。

圖1所示為生產線有向網絡模型。針對混流生產線中多種產品工藝路線所表現出來的網絡特性，以工位為制造節點V，以節點之間的工藝關系為有向邊E，用權值w來表示多品種環境下節點之間的多重關系，從而把具有m個產品和n個節點的混流生產線簡化和抽象為G（V，E，w）形式的有向加權網絡模型，并以有向加權網絡的形式表現出來。

圖1 生產線有向網絡模型

1．2 混流生產線模型的數學描述

產品、工藝和制造資源是混流生產線的基本組成元素，在有向加權網絡模型G（V，E，w）中，對混流生產線進行如下的數學描述：

制造節點 本文以生產線中的制造工位為物理模型，把能夠獨立承擔制造任務的同一類型的設備、工具、工裝夾具、人員等制造資源所組成的集合定義為制造節點。在G（V，E，w）中以制造節點集合V｛vi｜vi＝i｝（i＝1，2，…，n）表示生產線中的n個工位，以1到n的整數對制造節點進行編碼，形成圖2所示的制造節點序列。

產品 產品集合P｛P｜Pi＝｝（i＝1，2，…，m），以1到m的整數對所有在生產線上運行的產品進行編碼得到產品序列，以yi表示混流生產線中的m個產品對象在規劃周期內的產量，并以此組織圖2所示的工藝矩陣的行向量。

有向邊 有向邊集合E｛Eij｜Eij＝ （0，1）｝（i，j＝1，2，…，n），以有向邊Eij表示產品從制造節點vi到制造節點vj的工藝路線，并以二元網絡描述有向邊的連通性，即節點之間的連接情況只有兩種情形：節點連接時Eij＝1，有向邊長度為1，不連接時Eij＝0。需要特別注意的是，因為邊的有向性，Eij≠Eji。

制造工藝 制造工藝是生產線狀態變化的起因和驅動力，產品通過對制造資源進行組織，驅動物料搬運系統完成各個工位之間的物料流動，形成產品的工藝路線。因此，制造工藝就決定了混流生產線網絡模型的基本結構。產品工藝矩陣Pr｛Pr，ij｜Pr，ij＝ （V，T）｝（i＝1，2，…，m，j＝1，2，…，Ni，其中Ni為第i個產品的工序數），以包含工序Pr，ij所在工位和所用工時（h）的一個二元組（V，T）來描述混流生產線上m個產品的制造信息。

圖2 混流生產線的工藝矩陣

如圖2所示，根據上述定義的制造節點序列，對產品k的制造工藝進行編碼得到工藝路線Pr，k＝ ｛（33，1）（3，2）（41，2）（16，0．5）（32，2）（51，4）… （n，0．5）｝來表示產品k先后經過33、3、41、16、32、51等制造節點，并花費相應的工時完成其制造過程。由此按照上述定義的產品序列對m個產品的工藝進行堆積就構成了整個生產線的工藝矩陣。

2 混流生產線有向加權網絡的拓撲特性

混流生產線的有向加權網絡模型主要通過定義和研究網絡在統計意義上的拓撲特性，描述節點與節點、節點與邊、邊與邊之間的關系來揭示生產線的結構、整體性能和運行狀態。在本文中需要定義的特征屬性包括：

權值矩陣 權值矩陣w｛wij｝（i，j＝1，2，…，n），在混流生產線的有向加權網絡模型中，用權值wij表示從一個制造節點vi到另一個節點vj的連接強度，權值代表了有向邊的重要性。通過對工藝矩陣Pr按行遍歷便可以得到權值矩陣，具體算法如下：

有向邊權值的分布情況可以用P（w）來描述，P（w）表示一個隨機選定的有向邊的權值恰好為w的概率。

鄰接矩陣 鄰接矩陣a｛aij＝ （0，1）｝（i，j＝1，2，…，n）表示制造節點之間的可連通性，可以通過對權值矩陣的布爾運算來得到：

節點負荷 節點負荷集合L｛Li｝（i＝1，2，…，n），節點負荷Lk定義為節點vk承擔的所有工序的總工時（h）。節點負荷通過對工藝矩陣Pr中與vk相關的多種不同產量產品工時的累加獲得。節點負荷表征了節點所承擔任務量的多少，描述了節點的負載狀態：

平均負荷〈L〉是網絡中所有節點負荷的平均值，代表了生產線的任務負荷。

節點度 節點度k｛ki｝（i＝1，2，…，n）是指與該節點連接的其他節點的數目［15］。有向網絡中的節點度分為出度和入度。出度是指從vi指向其他節點的邊的數目。入度是指從其他節點指向vi的邊的數目。節點度代表了節點在網絡中的重要性，度越高的節點說明它對其他節點的影響力越大。出度ki為鄰接矩陣每一行的和；入度kj為鄰接矩陣每一列的和：

路徑長度 路徑長度d｛dij｝（i，j＝1，2，…，n），連接兩個節點vi和vj最短路徑上有向邊的總長度定義為兩個節點之間的距離dij，其中節點之間最短路徑可以根據Dij kstra算法求取。網絡的平均路徑長度D為任意兩節點之間距離的平均值，即

聚類系數 聚類系數c｛ci｝（i ＝1，2，…，n）是與節點vi相連的k條有向邊之間實際存在的邊數Ei與總的可能邊數之比，其等價定義為與vi相連的三角形數量和與vi相連的三元組數量的比值［15-16］。因此通過對與節點相連的三元組的遍歷驗證三角形的有效性，便可以得到節點的聚類系數：

3 基于有向加權網絡的產能規劃方法和實例研究

3．1 混流生產線產能規劃方法

基于有向加權網絡的混流生產線產能規劃方法的步驟如下：

（1）根據生產線的實際數據建立混流生產線的產品序列P和制造節點序列V，并對產品的制造工藝進行編碼以生成生產線上多種產品的工藝矩陣Pr。

（2）通過對工藝矩陣的遍歷，按照式（1）、式（2）和式（3）分別得到網絡模型的權值矩陣w、鄰接矩陣a和節點負荷L，并計算權值的分布規律P（w）。

（3）根據鄰接矩陣a對制造節點可連通性的描述，按照If aij＝1 then Eij＝1給出有向邊集合E，并按照有向邊有效性在節點之間畫出混流生產線的工藝拓撲圖。

（4）根據鄰接矩陣a，按照式（4）得到網絡模型的節點度k和網絡的平均度K，計算節點的度分布P（k），并根據權值分布和度分布對節點和有向邊的狀態進行分析。如果網絡模型的度分布和權值分布表現出近似的冪律分布，則符合無標度網絡的分布特征（這種網絡絕大部分節點的度很低，但存在少量度相對很高的點和少量權值相對很高的有向邊），并以此作為節點和有向邊狀態的分析依據。

（5）按照式（5）和式（6）計算網絡的平均路徑長度D和聚類系數C，并通過與具有相同節點數和節點平均度的ER隨機網絡進行比較，研究網絡結構的整體性態，判斷網絡是否表現出小世界特性，并以此作為網絡模型是否具有高故障傾向的判斷依據。

（6）依據步驟（4）和步驟（5）對網絡整體性能和運行狀態的判斷，根據節點度的閾值把制造節點分為關鍵節點和一般節點，按照節點負荷確定制造節點的能力冗余數量，進行生產線的產能規劃。

3．2 混流生產線實例研究

本文以某機械產品零件生產線為研究對象。該生產線擁有224個工位，承擔10個型號361種零件的制造任務，是典型的多品種混流生產模式。以表1中UX21515和FP30732為例，可以看出這些零件的制造工藝比較復雜，需要經歷多個工藝步驟。兩種不同零件的工藝過程、加工工時和所涉及的制造工位有較大的差異，但也共同使用ZA8100、SAJO、SY375和熒光檢驗工位，因此，這4個工位就成為UX21515和FP30732工藝路線的交點，它們的狀態對兩個零件的制造過程均會產生影響，而且這些零件具有精度高、工期緊的特點，對生產線的穩定性要求非常高。因此，需要根據生產線的整體性能進行產能規劃，通過對節點的資源配置，獲得一定的能力冗余來保證生產線的穩定性。

對于上述生產線首先按照3．1節中的步驟（1）建立產品序列和制造節點序列，并對其制造工藝進行編碼生成工藝矩陣。然后按照步驟（2）和步驟（3）得到圖3所示的生產線工藝拓撲圖，從圖3可以看出，該網絡結構非常復雜，節點之間的連接存在一些度很高的點。

表1 零件工藝路線

圖3 混流生產線工藝拓撲圖

對于圖3所示網絡結構的拓撲特性，按照3．1節中的步驟（2）、步驟（4）和步驟（5）可以得到表2所示的網絡拓撲特性，從表2可以看出，節點度、節點負荷和權值的最大值比平均值大得多，網絡的拓撲特性呈現出不均衡性。

表2 混流生產線的拓撲特性

為此，我們需要研究節點度和有向邊權值的分布情況，按照3．1節中的步驟（2）和步驟（4）得到P（w）和P（k），并在雙對數坐標系中研究其分布規律，從圖4、圖5可大致看出，P（w）和P（k）均近似為一條直線。

圖4 有向邊權值的分布圖

圖5 節點度的分布圖

這就意味著其概率分布滿足形如式（7）和式（8）的冪律分布，說明網絡結構符合無標度網絡的分布特征。

科研合作網、世界機場航線網等很多實際網絡的分布也具有類似冪律分布的特征［15］，這些網絡絕大部分節點的度很低，但存在少量度相對很高的點，稱為“集線器（hub）”。同樣，對于生產線來說，這些hub由于工藝任務的集中而成為關鍵節點。因此，生產線在運行過程中必須優先保證這些關鍵節點的可靠性，否則，關鍵節點的失效會導致整個系統的災難性崩潰［11-12］。

接下來按照3．1節中的步驟（5）對網絡結構的整體性態進行研究，與具有相同節點數和節點平均度ER隨機網絡進行比較，生產線有向加權網絡的聚類系數為

平均路徑長度為

從式（9）和式（10）可以看出，生產線的網絡模型具有遠大于隨機網絡的聚類系數，且具有近似的較短平均路徑長度，因此可以判斷出網絡呈現出小世界特性，具有高故障傾向，對生產線的穩定性具有極大的威脅，即一旦某個關鍵節點出現失效，將會導致整個系統的嚴重震蕩甚至癱瘓，更有可能引起一場大災難。

因此，對于生產線而言需要在合理范圍內，增加關鍵節點的資源配置數量來降低節點負荷，使得在隨機失效發生時能夠有冗余產能的保障。按照機械工廠年時基數設計標準［17］，根據年時基數將節點負荷閾值設置為二班制［L］＝3750h，并以［k］＝30為節點度閾值，將節點分為關鍵節點和一般節點，關鍵節點以η＝20%的維護時間來保證安全性，一般節點的維護時間定為η＝10%。據此計算的vi的資源配置數量為

其中，［］＋為取整操作。本文中的零件生產線共能找出關鍵工位12個，按照式（11）對所有節點進行資源配置和冗余規劃后，獲得的節點最大負荷為3375h，平均負荷為1269．2h。這樣就在不改變網絡結構的情況下，通過增加節點冗余完成了生產線產能規劃，避免了單個節點失效所造成的系統崩潰，增強了系統的防御能力。

4 結束語

本文利用有向加權網絡對生產線的產品、工藝、制造資源進行了描述，建立了多產品混流生產線網絡模型，研究了在多產品環境下制造節點的狀態特征和生產線的整體性態。提出了通過增加冗余配置以保證節點可靠性和生產線穩定性的產能規劃方法。本文以一個擁有224個制造節點，承擔361種產品的實際生產線為例，給出了基于有向加權網絡的混流生產線建模過程和產能規劃方法，并用拓撲特性展示了網絡模型的整體狀態和節點的動態性能。

［1］ 宋華明，韓玉啟．混合裝配線上物料供應的平準化排序［J］．系統工程，2002，20（3）：15－19．

［2］ 王炳剛，饒運清，邵新宇，等．基于多目標遺傳算法的混流加工／裝配系統排序問題研究［J］．中國機械工程，2009，20（12）：1434－1438．

［3］ 耿娜，江志斌．用于晶圓制造產能規劃優化決策的改進隨機規劃方法［J］．上海交通大學學報，2007，41（8）：825－829．

［4］ Kai H，Shabbir A．A Stochastic Programming Approach for Planning Horizons of Infinite Horizon Capacity Planning Pr oblems［J］．European Jour nal of Operational Research，2010，200：74－84．

［5］ Kingsman B G．Modeling Input－output Workload Control f or Dynamic Capacity Planning in Production Planning Systems［J］．Inter national Jour nal of Production Econo mics，2000，68：73－93．

［6］ Leach man R C，Car mon T F．On Capacity Modeling for Production Planning with Alternative Machines［J］．IIE Transactions，1992，24（4）：62－72．

［7］ Cer yan O，Koren Y．Manufacturing Capacity Planningstrategies［J］．CIRP Annals－ Manufacturing Technology，2009，58（1）：403－406．

［8］ Barrat A，Barthélemy M，Pastor－Satorras R，et al．The Architect ure of Co mplex Weighted Networ ks［J］．Applied Physical Science，2004，101（11）：3747－3752．

［9］ 孫惠斌，江平宇．基于復雜加權網絡的移動協同空間分析［J］．西安交通大學學報，2006，40（5）：573－576．

［10］ 王哈力，單薏，王希鳳．組合邏輯電路的小世界網絡模型［J］．電機與控制學報，2006，10（4）：370－374．

［11］ Watts D J，Strogatz S H．Collective Dynamics of‘Small－ World’Net works［J］．Nature，1998，393：440－442．

［12］ Tu Y H．How Robust is the Inter net？［J］．Nature，2000，406：353－354．

［13］ Tang D B，Zheng L，Li Z Z，et al．Re－engineering of the Design Process for Concurrent Engineering［J］．Co mputers ＆ Industrial Engineering，2000，38：479－491．

［14］ 劉新華，張旭堂，劉文劍．基于改進最大－最小螞蟻系統的多工藝路線決策方法［J］．計算機集成制造系統，2008，14（12）：2414－2420．

［15］ 汪小帆，李翔，陳關榮．復雜網絡理論及其應用［M］．北京：清華大學出版社，2006．

［16］ Barrat A，Barthélemy M，Vespignani A．Modeling the Evolution of Weighted Net wor ks［J］．Physical Review E，2004，70（6）：066149．

［17］ 國家機械工業局．JBJ／T 2－2000機械工廠年時基數設計標準［S］．北京：機械工業出版社，2008．