BOM超網絡的建模與特性分析

萬 能 王福紅 葉春明

(1.上海理工大學 管理學院, 上海理工大學 超網絡研究中心，上海 200093； 2.上海建橋學院，上海 201306)

1 超網絡概念

復雜網絡和超網絡都是研究復雜系統建模的有力工具。隨著超大規模網絡系統、多層網絡、網絡中網絡等復雜網絡系統的出現，國內外學者掀起了超網絡研究的熱潮。目前，超網絡的研究尚處于起步階段，關于超網絡的概念尚沒有統一的定義。超網絡的定義主要分為兩類：一類是網絡中的網絡NON(Networks of Networks)，即Supernetworks和多層網絡，另一類是用超圖表示的超網絡，即hypernetwork。本文是基于超圖超網絡的研究。超圖是對普通圖的擴展，與普通圖的主要區別在于：普通圖的一條“邊”只能連接兩個節點，只能表示一對節點之間的兩元關系，而超圖中的一條“超邊”可以包含多個節點，可用來表示多個節點之間的多元關系。與復雜網絡相比，超網絡是更高階的建模工具，在大數據和超大規模網絡背景下，超網絡理論的提出為描述和分析大型復雜系統提供了理論基礎和新的思路。

1.1 超圖的定義

設V={v1,v2,…,vn}是一個有限集，若

(1)Ei≠φ(不=1，2，…,m)，

則稱二元關系H=(V,Eh)為超圖，簡記為(V,Eh)或H。其中，V的元素被稱為超圖的節點，Eh中的元素被稱為超圖的超邊。如果兩個節點屬于同一條超邊，則稱這兩個節點鄰接；如果兩條超邊的交集不空，稱之為這兩條超邊鄰接。如果每條超邊中的頂點數都相等, 則稱為均勻超圖或一致超圖。如果|V|和|Eh|均有限，則稱H為有限超圖，H=(V,Eh)退化為圖，不含重邊的超圖為簡單超圖。超圖G=(V,E)的關聯矩陣是一個矩陣((aij))，其中m行表示G的超邊，n列表示G的頂點。如果使Vj∈Ei,aji=1，Vj?Ei,aji=0.最簡單超圖(普通圖)如圖1所示，超網H的關聯矩陣如表1所示。

圖1 普通圖

圖2 超圖H

V1V2V3V4V5V6E111E2111E3111E411E511

1.2 超圖H的對偶超圖H*

如果對所有的j，Vj={ei|i≤m,vj∈Ei},vj≠φ，?j，UjVj=E,那么超圖H*=(E;V1,V2LVn)稱為H的對偶超圖。(H*)*=H。圖2的對偶超圖H*如圖3所示。

超網絡是超圖的推廣，假設Ω={(V，Eh),|(V,Eh)是有限超圖}，G是從T=[0，+∞)到Ω的映射，對于任意給定的t≥0,G(t)=(V(t),Eh(t))是一個有限超圖，指標t通常被認為是時間。超網絡{G(t)|t∈T}是指超圖的集合，節點vi的超度被定義為連接節點vi的數目，從超網絡的定義可以看出，超網絡是超圖概念的推廣和一般化。

1.3 超網絡的指標

1) 節點超度(Node Hyperdegrees)

節點i的點超度DH表示包含該節點的超邊條數。如在圖2中，DHv1=2,DHv3=2,DHv5=3。

2) 超邊度(Hyperedge Degrees)

超網絡中，同一節點可能在多條超邊中出現。超邊度DEi被定義為與超邊Ei直接鄰接的其他超邊條數。如在圖2中，v5同時屬于超邊E1、E3、E5，則E1、E3、E5是鄰接的，v4同時屬于超邊E1、E2、E4，則E1、E2、E4是鄰接的，DE1=4,DE5=2。

3) 超邊超度(Hyperedge Hyperdegrees)

超邊Ei的超邊超度DHEi表示該超邊所包含的節點個數。如在圖2中，v5同時屬于超邊E1、E3、E5，則E1、E3、E5是鄰接的，v4同時屬于超邊E1、E2、E4，則E1、E2、E4是鄰接的，DE1=4，DE5=2。

4)超邊相似性(Hyperedge similarity)

超邊相似性是兩條超邊所含共同元素的個數除以兩條超邊所包含的元素之和。超邊相似性的公式為

(1)

VREi代表超邊Ei所包含的元素，VREj代表超邊Ej所包含的元素。

5)基于超網絡關聯矩陣的SVD分解

任意的矩陣An×m都可以分解成三個矩陣

A=U∑VT

(2)

U是一個n×n的方陣(里面的向量是正交的，U里面的向量被稱為左奇異向量)，∑是一個n×m的矩陣(除了對角線的元素被都是0，對角線上的元素稱為奇異值)，VT(V的轉置)是一個n×n的矩陣，里面的向量也是正交的，V里面的向量被稱為右奇異向量)。

2 超網絡建模

2.1 數據來源

以A公司BOM數據為例：A公司是中國領先的工業物聯網解決方案供應商，提供基于工業物聯網的云平臺，面向工業4.0下制造業的轉型與升級，提供制造物聯網整體解決方案及相關軟硬件產品與服務。公司主營業務包括：智慧物聯(車間級無線工業物聯網平臺及車間應用的數據采集與管理監控系統)、兩化融合(精益智能化工廠系列軟硬件產品和Andon、MES、EAM等運營管理系統)、智能集成(行業定制標準型智能制造整體解決方案如服裝成衣、光電纜等)。A公司有自己的設計研發部門、生產制造部門(SMT, DIP., 組裝)、采購部、銷售部、工程安裝調試、售后服務部門。共有20多種產品，既有物料BOM，又有結構BOM。表2為A公司呼叫器成品的BOM。

表2 A公司呼叫器BOM

2.2 超網絡建模

以A公司所用物料為節點，以包含該物料的產品BOM為超邊，即超邊可包含若干個節點(物料)，該數據集描述了A公司的10種產品和26種采購物料。建立的BOM超網絡示意圖如圖4所示。

該BOM超網絡含26個節點，以編號v1Lv26表示；含12條超邊，以編號E1LE12表示。為了研究的簡化，如果在同一個產品(同一超邊中)使用了多個同種物料，將使用該物料的數量作為該物料的權重。為了研究的簡化，不考慮重邊。 所建立的基于簡單超圖的BOM超網絡模型如圖4所示。

圖4 基于無向超圖的BOM超網絡拓撲結構

在圖4所示的拓撲結構中，A公司BOM超網絡可表示為G=(V,E)。其中，V={v1,v2,Lv132}，是頂點的集合，也就是A公司所使用物料的集合；V={E1,E2,L,E12}是超邊的集合，即A公司所生產的產品種類。如果一個產品使用了多個同種物料，將使用數量視為該物料的權重。如在3層3色塔燈成品中，使用燈泡(白光)的數量為2，2即該物料在該種產品中的權重。

2.3 BOM超網絡的關聯矩陣表示法

超網絡的關聯矩陣Am×n由12行和132列組成，行代表一條超邊Em，每一列代表一個節點vn，Em超邊中若含有節點vn，則Bm×n元素的值為1，否則值為0。于是得到BOM超網絡的關聯矩陣Bm×n,在關聯矩陣B中，(m=12,n=132)。

當只考慮每種產品中所用的物料種類而不考慮物料的用量時，該BOM超網絡的關聯矩陣用矩陣B表示如下：

當考慮某種產品所用物料的數量時，該BOM超網絡的關聯矩陣如圖6所示。

圖6 A公司BOM超網絡的關聯矩陣示意圖

在圖6中，每一行代表一種產品(如呼叫器)及其所用物料。如呼叫器產品由呼叫器外殼、呼叫器控制板、9V電池、 電池扣、貼膜等五種物料組成，每一行即代表一種產品的BOM清單。 該超網絡的關聯矩陣用矩陣A表示如下：

3 實證與數據分析

3.1 節點超度

根據矩陣A12×132，對BOM超網絡關聯矩陣的每一列求和，得到每一個節點的超度。節點超度表示該物料在A公司的12種產品中, 節點超度前三位的是V61(100nF貼片電容)、V87(1K貼片電阻)、V103(10nF貼片電容)。100nF貼片電容用量最大，它雖然價格不高，但也是該公司的關鍵物料。

3.2 物料通用度

根據矩陣B12×132，根據公式(3)計算每種物料的通用度：

(3)

表3 節點超度較大的物料

表4 通用度較大的物料

3.3 超邊度

在BOM超網絡中超邊度是指BOM和BOM之間的鄰接關系，當BOM之間有共同的物料節點時，我們認為兩種產品BOM之間是鄰接的。經過統計分析，BOM超網絡超邊度的統計情況如表4所示。超邊度大的產品與其他產品有較多的關聯物料，或者有與其他產品有相同的模塊，是A公司的核心BOM，也是A公司重點管理的BOM，在備料時或半成品生產時可以考慮共同部分有庫存。 如圖7所示，E6產品BOM的超邊度為6，說明該產品的6種物料在A公司的其他產品也有使用。 超邊度大的產品BOM與其他產品的BOM關聯度大。超邊度較大的產品為E8(控制器)、E7(刷卡器)、E9(計數器)、E5(主機控制器)、E11(讀卡器)。

表4 超邊度較大的產品

圖7E6語音主機產品的超邊度為6，表明該產品的6種物料在A公司的其他產品使用，超邊度大的BOM也是該公司的核心BOM

3.4 超邊超度

超邊Ei的超邊超度DHEi表示該超邊所包含的節點個數。超邊超度即每條超邊包含的節點個數，從圖4和關聯矩陣可以看出，每一個BOM的超邊超度，就是其所用物料總數量。超邊超度指標可評價該產品的復雜度。A公司超邊超度較大的有E4(新主機控制器)，E11(讀卡器)，E12(四子看板)。超邊超度大的產品也是A公司重點管控的產品BOM。物料數量多的MOM是應該格外關注的BOM。

表5 A公司12種產品的超邊超度

3.5 超邊相似性(Hyperedge similarity)

Jcarrd相似性系數主要用來衡量兩個產品BOM之間的相似度，有兩個不同的BOM共同具有的特征。如果兩條超邊所含共同元素的個數除以兩條超邊所包含的元素之和。根據統計分析，不同超邊之間的超邊相似性矩陣如表5所示。從表5中可以看出：超邊相似系統最大的E5(中繼器)和E6(語音主機)產品為0.44。這兩個產品的物料組成有較多的重疊，即E6產品是E5產品中的一個重要的模塊。從表5中可以看出：A公司是物聯網企業，E5、E6與E7、E8、E9、E12產品比較相似，屬于同一類產品，E1和E3產品比較相似，E7與E9、E10、E12產品相似，有共同的屬性。如果兩種產品的BOM相似度較大，說明兩種產品所用物料很相似，關注其加工工藝是否相同，如果加工工藝相同，則可歸為同一類型產品。

3.6 BOM 超網絡關聯矩陣的SVD分解

根據A=USVT，對關聯矩陣A12×132進行SVD分解，進行BOM超網絡的降維及聚類分析。 A公司BOM超網絡的SVD分解后為所對應的對角矩陣S的非零特征值由圖8所示。S特征值矩陣中的非零特征值表示左奇異矩陣的一行與右奇異矩陣的一列的重要性與重要程度，特征值越大表示所對應的左奇異矩陣U的某行或右奇異矩陣V的某列越重要。

表5 超邊相似系數矩陣(即產品的Jcarrd相似系數)

圖8 BOM超網絡關聯矩陣SVD分解后對角矩陣S(SVD分解后的A132×12部分矩陣)

計算圖8中SVD分解后的非零特征值及非零特征值所占總特征值之和的百分比，計算過程如表6所示。

表6 SVD分解后對角矩陣S的非零特征值的占比計算

由表6可以看出：前5個特征值之和占了全部特征值之和的95%。因此，只看SVD分解后的左奇異矩陣U132×132的前五列數據，即左奇異矩陣U132×5表示某種物料的在A公司整個BOM表中出現的頻率。物料在A公司整體BOM表中出現的頻度值如表7所示。從表7中可以看出：V61、V87、V103、V18、V15、V16、V17、V4、V5這幾種物料出現的頻率最高，是A公司最通用和最重要的物料。

表7 根據SVD分解后的U132×132數值所得到的物料重要性

同樣，SVD分解后的右奇異矩陣為V12×12，與左奇異矩陣U132×5的前五列數據相對應，只分析右奇異矩陣V12×12的前五行V12×5，右奇異向量V表示產品的一些特性。

根據SVD的原理，我們只要對BOM關聯矩陣進行一次分解，就可以同時完成產品分類和物料相似性分類，同時還能得到每個產品和每個物料之間的相關性。其次，右奇異向量中第一行表示每種產品中出現的物料個數的近似值。

根據SVD分解，只看V12×12前五行的數據，從圖9中可以看出，E11(刷卡器)和E4(新主機)產品所用物料的數目最多，其次為E12、E7、E8、E9產品，這與采用超網絡的超邊超度分析指標所得到的結論是一致的。因此，同時也驗證了SVD分解的有效性。

圖9 SVD分解后的右奇異矩陣

4 BOM對偶超網絡的數據分析

以物料為超邊，以產品為節點，建立對偶超網絡模型如圖10所示。進行對偶超圖的超網絡建模后，發現超邊重邊較多。超圖超網絡是基于無重邊的簡單超圖的研究，而A公司BOM的對偶超圖超網絡分析重邊較多，分析比較復雜。BOM超網絡不適用于對偶超網絡的數據分析。

圖10 A公司BOM超網絡的對偶超圖

5 結論與展望

BOM是制造業的基因，BOM數據是企業的重要資源,數據集成是智能化生產的重要基礎。隨著云制造和大數據時代的到來，BOM數據也集成在云制造平臺上，BOM數據中的數據挖掘及關鍵資源管理成為制造型企業日益關注的對象。采用更先進的BOM分析方法，識別出BOM大數據中的關鍵物料這一基礎性工作，可給企業的物料采購、庫存、設計選型、工程變更、售后維修備品備件等帶來管理上的參考和便捷，進行物料的組合優化、風險預防、聯合采購、備品備件，可降低物料管理的復雜度，提升企業以BOM數據驅動運營管理的水平和效率，降低成本，提高企業的競爭力。

本文通過計算加權超網絡的節點超度、物料通用率、超網絡關聯矩陣的SVD分解，可以從宏觀上得知哪些物料是公司的關鍵(Critial)物料，通過計算超邊相似性、超邊度、超邊超度可以比較宏觀地掌握公司的關鍵產品及其復雜性與相似性。綜合文中表1、表2、表7中的物料再結合傳統的ABC物料管理方法(按照物料的成本)、傳統的物料分類法(按照物料在產品中功能的重要性分類如Minior、Major、Critical等方法)，可以更全面地管理公司的物料。超網絡BOM管理方法和傳統物料管理方法的對比如圖8所示。在大數據背景，傳統的物料管理方法基于某一微觀視角，而超網絡BOM建模方法基于宏觀視角與系統工程理論。微觀視角和宏觀視角相結合，才能更有效地促進物料管理效率的提升。

本文基于超網絡節點的重要性、超邊重要性理論、找到核心的元器件和節點，基于超邊度、超邊超度、超邊相似度，得到該公司類似的產品及產品的復雜度、產品之間的相似度。本文基于系統工程的視角，為現有的BOM管理研究提供了一種新的研究視角，相關研究結論為A公司的物料管理提供了一種新的參考和借鑒，提高了A公司物料管理的效率。在研究中發現：基于超網絡關聯矩陣的SVD分解，可以一次性得到關鍵物料，得到產品的相似性與物料的相似性；超網絡關聯矩陣SVD分解所得到的關鍵物料結論，與BOM超網絡建模所得到的統計參數指標分析結論是一致的。在大數據背景下，為了研究的簡單，也可以采用超網絡關聯矩陣的SVD分解來得到關鍵物料和關鍵產品。

表8 超網絡方法與現有物料管理方法的對比

因此，在人工智能和大數據時代，基于超網絡的關聯矩陣的SVD分解，為BOM物料管理提供了一種新的研究視角和管理啟示。識別出少數但對企業發展起決定性作用的關鍵物料種類和產品，可以為企業物料成本的降低、物料的聯合采購、物料的替代、產品設計時物料的選型、產品的升級換代、物料的安全庫存等方面的管理提供參考和借鑒，為提高物料的管理效率提供借鑒。采用超網絡理論對BOM數據進行挖掘，識別關鍵物料和產品，降低了對樣本數據的要求，為未來深度學習和智能制造技術打下基礎。未來將進行智能制造背景下BOM驅動作用機制的研究。