BOM超網(wǎng)絡(luò)的建模與特性分析

萬 能 王福紅 葉春明

(1.上海理工大學(xué) 管理學(xué)院, 上海理工大學(xué) 超網(wǎng)絡(luò)研究中心，上海 200093； 2.上海建橋?qū)W院，上海 201306)

1 超網(wǎng)絡(luò)概念

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

1.1 超圖的定義

設(shè)V={v1,v2,…,vn}是一個(gè)有限集，若

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

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

圖1 普通圖

圖2 超圖H

V1V2V3V4V5V6E111E2111E3111E411E511

1.2 超圖H的對(duì)偶超圖H*

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

超網(wǎng)絡(luò)是超圖的推廣，假設(shè)Ω={(V，Eh),|(V,Eh)是有限超圖}，G是從T=[0，+∞)到Ω的映射，對(duì)于任意給定的t≥0,G(t)=(V(t),Eh(t))是一個(gè)有限超圖，指標(biāo)t通常被認(rèn)為是時(shí)間。超網(wǎng)絡(luò){G(t)|t∈T}是指超圖的集合，節(jié)點(diǎn)vi的超度被定義為連接節(jié)點(diǎn)vi的數(shù)目，從超網(wǎng)絡(luò)的定義可以看出，超網(wǎng)絡(luò)是超圖概念的推廣和一般化。

1.3 超網(wǎng)絡(luò)的指標(biāo)

1) 節(jié)點(diǎn)超度(Node Hyperdegrees)

節(jié)點(diǎn)i的點(diǎn)超度DH表示包含該節(jié)點(diǎn)的超邊條數(shù)。如在圖2中，DHv1=2,DHv3=2,DHv5=3。

2) 超邊度(Hyperedge Degrees)

超網(wǎng)絡(luò)中，同一節(jié)點(diǎn)可能在多條超邊中出現(xiàn)。超邊度DEi被定義為與超邊Ei直接鄰接的其他超邊條數(shù)。如在圖2中，v5同時(shí)屬于超邊E1、E3、E5，則E1、E3、E5是鄰接的，v4同時(shí)屬于超邊E1、E2、E4，則E1、E2、E4是鄰接的，DE1=4,DE5=2。

3) 超邊超度(Hyperedge Hyperdegrees)

超邊Ei的超邊超度DHEi表示該超邊所包含的節(jié)點(diǎn)個(gè)數(shù)。如在圖2中，v5同時(shí)屬于超邊E1、E3、E5，則E1、E3、E5是鄰接的，v4同時(shí)屬于超邊E1、E2、E4，則E1、E2、E4是鄰接的，DE1=4，DE5=2。

4)超邊相似性(Hyperedge similarity)

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

(1)

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

5)基于超網(wǎng)絡(luò)關(guān)聯(lián)矩陣的SVD分解

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

A=U∑VT

(2)

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

2 超網(wǎng)絡(luò)建模

2.1 數(shù)據(jù)來源

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

表2 A公司呼叫器BOM

2.2 超網(wǎng)絡(luò)建模

以A公司所用物料為節(jié)點(diǎn)，以包含該物料的產(chǎn)品BOM為超邊，即超邊可包含若干個(gè)節(jié)點(diǎn)(物料)，該數(shù)據(jù)集描述了A公司的10種產(chǎn)品和26種采購物料。建立的BOM超網(wǎng)絡(luò)示意圖如圖4所示。

該BOM超網(wǎng)絡(luò)含26個(gè)節(jié)點(diǎn)，以編號(hào)v1Lv26表示；含12條超邊，以編號(hào)E1LE12表示。為了研究的簡化，如果在同一個(gè)產(chǎn)品(同一超邊中)使用了多個(gè)同種物料，將使用該物料的數(shù)量作為該物料的權(quán)重。為了研究的簡化，不考慮重邊。 所建立的基于簡單超圖的BOM超網(wǎng)絡(luò)模型如圖4所示。

圖4 基于無向超圖的BOM超網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

在圖4所示的拓?fù)浣Y(jié)構(gòu)中，A公司BOM超網(wǎng)絡(luò)可表示為G=(V,E)。其中，V={v1,v2,Lv132}，是頂點(diǎn)的集合，也就是A公司所使用物料的集合；V={E1,E2,L,E12}是超邊的集合，即A公司所生產(chǎn)的產(chǎn)品種類。如果一個(gè)產(chǎn)品使用了多個(gè)同種物料，將使用數(shù)量視為該物料的權(quán)重。如在3層3色塔燈成品中，使用燈泡(白光)的數(shù)量為2，2即該物料在該種產(chǎn)品中的權(quán)重。

2.3 BOM超網(wǎng)絡(luò)的關(guān)聯(lián)矩陣表示法

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

當(dāng)只考慮每種產(chǎn)品中所用的物料種類而不考慮物料的用量時(shí)，該BOM超網(wǎng)絡(luò)的關(guān)聯(lián)矩陣用矩陣B表示如下：

當(dāng)考慮某種產(chǎn)品所用物料的數(shù)量時(shí)，該BOM超網(wǎng)絡(luò)的關(guān)聯(lián)矩陣如圖6所示。

圖6 A公司BOM超網(wǎng)絡(luò)的關(guān)聯(lián)矩陣示意圖

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

3 實(shí)證與數(shù)據(jù)分析

3.1 節(jié)點(diǎn)超度

根據(jù)矩陣A12×132，對(duì)BOM超網(wǎng)絡(luò)關(guān)聯(lián)矩陣的每一列求和，得到每一個(gè)節(jié)點(diǎn)的超度。節(jié)點(diǎn)超度表示該物料在A公司的12種產(chǎn)品中, 節(jié)點(diǎn)超度前三位的是V61(100nF貼片電容)、V87(1K貼片電阻)、V103(10nF貼片電容)。100nF貼片電容用量最大，它雖然價(jià)格不高，但也是該公司的關(guān)鍵物料。

3.2 物料通用度

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

(3)

表3 節(jié)點(diǎn)超度較大的物料

表4 通用度較大的物料

3.3 超邊度

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

表4 超邊度較大的產(chǎn)品

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

3.4 超邊超度

超邊Ei的超邊超度DHEi表示該超邊所包含的節(jié)點(diǎn)個(gè)數(shù)。超邊超度即每條超邊包含的節(jié)點(diǎn)個(gè)數(shù)，從圖4和關(guān)聯(lián)矩陣可以看出，每一個(gè)BOM的超邊超度，就是其所用物料總數(shù)量。超邊超度指標(biāo)可評(píng)價(jià)該產(chǎn)品的復(fù)雜度。A公司超邊超度較大的有E4(新主機(jī)控制器)，E11(讀卡器)，E12(四子看板)。超邊超度大的產(chǎn)品也是A公司重點(diǎn)管控的產(chǎn)品BOM。物料數(shù)量多的MOM是應(yīng)該格外關(guān)注的BOM。

表5 A公司12種產(chǎn)品的超邊超度

3.5 超邊相似性(Hyperedge similarity)

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

3.6 BOM 超網(wǎng)絡(luò)關(guān)聯(lián)矩陣的SVD分解

根據(jù)A=USVT，對(duì)關(guān)聯(lián)矩陣A12×132進(jìn)行SVD分解，進(jìn)行BOM超網(wǎng)絡(luò)的降維及聚類分析。 A公司BOM超網(wǎng)絡(luò)的SVD分解后為所對(duì)應(yīng)的對(duì)角矩陣S的非零特征值由圖8所示。S特征值矩陣中的非零特征值表示左奇異矩陣的一行與右奇異矩陣的一列的重要性與重要程度，特征值越大表示所對(duì)應(yīng)的左奇異矩陣U的某行或右奇異矩陣V的某列越重要。

表5 超邊相似系數(shù)矩陣(即產(chǎn)品的Jcarrd相似系數(shù))

圖8 BOM超網(wǎng)絡(luò)關(guān)聯(lián)矩陣SVD分解后對(duì)角矩陣S(SVD分解后的A132×12部分矩陣)

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

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

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

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

同樣，SVD分解后的右奇異矩陣為V12×12，與左奇異矩陣U132×5的前五列數(shù)據(jù)相對(duì)應(yīng)，只分析右奇異矩陣V12×12的前五行V12×5，右奇異向量V表示產(chǎn)品的一些特性。

根據(jù)SVD的原理，我們只要對(duì)BOM關(guān)聯(lián)矩陣進(jìn)行一次分解，就可以同時(shí)完成產(chǎn)品分類和物料相似性分類，同時(shí)還能得到每個(gè)產(chǎn)品和每個(gè)物料之間的相關(guān)性。其次，右奇異向量中第一行表示每種產(chǎn)品中出現(xiàn)的物料個(gè)數(shù)的近似值。

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

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

4 BOM對(duì)偶超網(wǎng)絡(luò)的數(shù)據(jù)分析

以物料為超邊，以產(chǎn)品為節(jié)點(diǎn)，建立對(duì)偶超網(wǎng)絡(luò)模型如圖10所示。進(jìn)行對(duì)偶超圖的超網(wǎng)絡(luò)建模后，發(fā)現(xiàn)超邊重邊較多。超圖超網(wǎng)絡(luò)是基于無重邊的簡單超圖的研究，而A公司BOM的對(duì)偶超圖超網(wǎng)絡(luò)分析重邊較多，分析比較復(fù)雜。BOM超網(wǎng)絡(luò)不適用于對(duì)偶超網(wǎng)絡(luò)的數(shù)據(jù)分析。

圖10 A公司BOM超網(wǎng)絡(luò)的對(duì)偶超圖

5 結(jié)論與展望

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

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

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

表8 超網(wǎng)絡(luò)方法與現(xiàn)有物料管理方法的對(duì)比

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