李孟澤，盛健超，李玉鵬，亓文輝

（中國(guó)礦業(yè)大學(xué)礦業(yè)工程學(xué)院工業(yè)工程系，江蘇 徐州 221116）

1 引言

復(fù)雜產(chǎn)品的設(shè)計(jì)變更對(duì)于企業(yè)快速適應(yīng)市場(chǎng)變化，響應(yīng)多樣化的客戶需求起著舉足輕重的作用[1]。企業(yè)為了保持核心競(jìng)爭(zhēng)力，經(jīng)常要對(duì)產(chǎn)品進(jìn)行設(shè)計(jì)變更。變更的傳播可能會(huì)影響產(chǎn)品研發(fā)進(jìn)度和產(chǎn)品質(zhì)量。另外，復(fù)雜產(chǎn)品的零部件之間結(jié)構(gòu)關(guān)系錯(cuò)綜復(fù)雜，變更的傳播會(huì)使開(kāi)發(fā)過(guò)程的難度提高，增加設(shè)計(jì)成本和風(fēng)險(xiǎn)。

針對(duì)設(shè)計(jì)變更問(wèn)題，國(guó)內(nèi)外學(xué)者開(kāi)展了深入的研究。如文獻(xiàn)[2]提出了公理化設(shè)計(jì)矩陣與設(shè)計(jì)結(jié)構(gòu)矩陣（Design Structure Matrix，DSM）同步演化的思想，并闡述了其演化的內(nèi)在機(jī)制。文獻(xiàn)[3]運(yùn)用網(wǎng)絡(luò)層次分析法評(píng)估模塊化產(chǎn)品設(shè)計(jì)變更傳播的影響，該方法僅僅適用于解決模塊化產(chǎn)品問(wèn)題，而對(duì)于難以實(shí)現(xiàn)模塊化的產(chǎn)品其優(yōu)勢(shì)并不明顯。文獻(xiàn)[4]對(duì)產(chǎn)品設(shè)計(jì)變更進(jìn)行了并行處理，以變更處理時(shí)間作為判據(jù)來(lái)搜索最優(yōu)的傳播路徑。文獻(xiàn)[5]以累積變更傳播強(qiáng)度最小為目標(biāo)，根據(jù)零部件參數(shù)連接關(guān)系建立設(shè)計(jì)變更分析模型，運(yùn)用改進(jìn)的蟻群算法進(jìn)行求解。總之，雖然有關(guān)設(shè)計(jì)變更傳播的研究較為豐富，但針對(duì)復(fù)雜產(chǎn)品設(shè)計(jì)變更多目標(biāo)路徑優(yōu)化問(wèn)題，沒(méi)有進(jìn)行針對(duì)性的研究。

近年來(lái)，復(fù)雜網(wǎng)絡(luò)理論的興起為解決復(fù)雜產(chǎn)品設(shè)計(jì)變更問(wèn)題提供了新思路，復(fù)雜產(chǎn)品的零部件可以抽象為網(wǎng)絡(luò)的節(jié)點(diǎn)，物理或功能關(guān)聯(lián)關(guān)系可以抽象為網(wǎng)絡(luò)中的邊。目前，常見(jiàn)的復(fù)雜網(wǎng)絡(luò)有隨機(jī)網(wǎng)絡(luò)（ER模型）[6]、無(wú)標(biāo)度網(wǎng)絡(luò)（BA模型）[7]以及小世界網(wǎng)絡(luò)（WS模型）[8]。文獻(xiàn)[9]將有向加權(quán)網(wǎng)絡(luò)看作復(fù)雜產(chǎn)品的形式化表達(dá)，對(duì)設(shè)計(jì)變更的影響進(jìn)行分析。文獻(xiàn)[10]基于BBV無(wú)標(biāo)度網(wǎng)絡(luò)演化模型，對(duì)復(fù)雜產(chǎn)品設(shè)計(jì)變更傳播影響進(jìn)行定量化評(píng)估。

鑒于以上研究，首先根據(jù)復(fù)雜產(chǎn)品零部件的物理連接關(guān)系構(gòu)建復(fù)雜網(wǎng)絡(luò)，根據(jù)變更傳播特點(diǎn)建立設(shè)計(jì)變更多目標(biāo)路徑優(yōu)化模型，運(yùn)用蟻群算法求解得到最優(yōu)傳播路徑，所得最優(yōu)方案可有效節(jié)省設(shè)計(jì)時(shí)間和成本，降低變更影響。

2 復(fù)雜產(chǎn)品設(shè)計(jì)變更網(wǎng)絡(luò)模型構(gòu)建

2.1 小世界網(wǎng)絡(luò)模型

Watts等在1998年提出了一種介于規(guī)則網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)之間的小世界網(wǎng)絡(luò)模型，該理論的提出是復(fù)雜網(wǎng)絡(luò)研究的一項(xiàng)開(kāi)創(chuàng)性成果。小世界網(wǎng)絡(luò)有兩個(gè)重要的特征參數(shù)：特征路徑長(zhǎng)度L和聚類(lèi)系數(shù)C。

（1）特征路徑長(zhǎng)度是任意兩個(gè)節(jié)點(diǎn)之間最短距離的平均值，表示為：

式中：dij—任意兩個(gè)連通節(jié)點(diǎn)間的最短距離。

（2）聚類(lèi)系數(shù)用于衡量相鄰節(jié)點(diǎn)聯(lián)系緊密程度，表示為：

式中：di—節(jié)點(diǎn)vi的度；ti—節(jié)點(diǎn)vi的相鄰節(jié)點(diǎn)之間存在的邊數(shù)。小世界網(wǎng)絡(luò)具有很高的聚類(lèi)系數(shù)和較小的平均距離?？梢?/p>

表示為：

式中：Cr、Lr—對(duì)應(yīng)隨機(jī)網(wǎng)絡(luò)的聚類(lèi)系數(shù)和平均距離。

2.2 變更傳播模型構(gòu)建

為了建立變更傳播模型，首先將復(fù)雜產(chǎn)品分解為有著物理連接關(guān)系的零部件。將零部件之間的關(guān)系映射為n×n階方陣，即產(chǎn)品的DSM。若零件ai的變更會(huì)引起零件aj的變更，則aij=1（i≠j），反之a(chǎn)ij=0。一個(gè)包含6個(gè)零部件的產(chǎn)品，容易發(fā)現(xiàn)，若零部件a1發(fā)生設(shè)計(jì)變更，則零部件a2和a6有可能會(huì)受到影響，如圖1所示。

圖1 設(shè)計(jì)結(jié)構(gòu)矩陣Fig.1 Design Structure Matrix

依據(jù)產(chǎn)品的DSM構(gòu)建變更傳播模型，其網(wǎng)絡(luò)模型可以表示為 G=（V，E），V=（v1，v2，…，vn）為節(jié)點(diǎn)的集合，E=｛eij|i，j=1，2，…，n，i≠j｝為邊的集合。節(jié)點(diǎn)代表DSM中的元素，節(jié)點(diǎn)間的連接邊代表元素之間的關(guān)系，從而確定節(jié)點(diǎn)之間是否存在連接關(guān)系。

2.3 變更傳播強(qiáng)度評(píng)估

從工程變更角度看，復(fù)雜產(chǎn)品可以由大量節(jié)點(diǎn)與邊構(gòu)成的復(fù)雜網(wǎng)絡(luò)表示，網(wǎng)絡(luò)中的節(jié)點(diǎn)代表產(chǎn)品的零部件，邊代表零部件之間的物理連接關(guān)系。在對(duì)產(chǎn)品的復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的統(tǒng)計(jì)特征進(jìn)行分析后發(fā)現(xiàn)，其特征路徑長(zhǎng)度和聚類(lèi)系數(shù)滿足式（3），具有小世界特性[11]。在該網(wǎng)絡(luò)中，網(wǎng)絡(luò)節(jié)點(diǎn)的度對(duì)設(shè)計(jì)變更的傳播起著重要作用[12]，某個(gè)節(jié)點(diǎn)度越大，它對(duì)應(yīng)的傳播路徑越多，擴(kuò)散范圍就越大。

定義變更傳播強(qiáng)度與傳播概率和節(jié)點(diǎn)的度有關(guān)。傳播概率Pij表示節(jié)點(diǎn)vi傳播到節(jié)點(diǎn)vj的可能性大小。當(dāng)節(jié)點(diǎn)vi和節(jié)點(diǎn)vj之間沒(méi)有連接邊，則Pij=0；當(dāng)節(jié)點(diǎn)之間傳播概率越大，變更傳播越傾向經(jīng)過(guò)該連接邊。dj表示節(jié)點(diǎn)vj的度。度大的節(jié)點(diǎn)擁有較多連接邊，變更傳播的影響范圍比較大。用Fk表示傳播第k步可達(dá)到節(jié)點(diǎn)集合。變更傳播強(qiáng)度定義為：

式中：ωp+ωd=1，ωp和ωd—傳播概率和節(jié)點(diǎn)度對(duì)應(yīng)的權(quán)重。在與相關(guān)專家確定后ωp=ωd=0.5較為合適。在上述分析中，變更傳播強(qiáng)度的大小代表復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)之間的邊權(quán)，權(quán)重越大，表示變更通過(guò)此邊進(jìn)行傳播產(chǎn)生越大的影響。

3 設(shè)計(jì)變更傳播路徑搜索算法

3.1 設(shè)計(jì)變更傳播方式

零部件的變更傳播存在兩種方式：串行傳播和并行傳播。對(duì)于串行傳播，如圖2（a）所示。零件變更的傳播是依次進(jìn)行的；對(duì)于并行傳播，如圖2（b）所示。一個(gè)零件的變更可以同時(shí)影響多個(gè)零件，其傳播路徑是由多個(gè)串行傳播路徑組成。在實(shí)際傳播中，兩種變更傳播方式都存在。

圖2 變更傳播方式Fig.2 Change Propagation Patterns

3.2 設(shè)計(jì)變更傳播最優(yōu)路徑搜索

設(shè)計(jì)變更傳播路徑的搜索是一個(gè)NP-hard問(wèn)題[13]，運(yùn)用啟發(fā)式算法求解此類(lèi)問(wèn)題有較好的效果。蟻群算法是文獻(xiàn)[14]提出的一種啟發(fā)式智能優(yōu)化算法，已成功應(yīng)用于求解許多NP問(wèn)題、組合優(yōu)化問(wèn)題等，如旅行商問(wèn)題、車(chē)輛調(diào)度問(wèn)題。因此，采用蟻群算法求解復(fù)雜產(chǎn)品的設(shè)計(jì)變更傳播路徑優(yōu)化問(wèn)題?；谝呀⒌膹?fù)雜網(wǎng)絡(luò)模型，以變更傳播強(qiáng)度、零件設(shè)計(jì)成本和設(shè)計(jì)時(shí)間為多個(gè)優(yōu)化目標(biāo)，將復(fù)雜產(chǎn)品設(shè)計(jì)變更多目標(biāo)路徑優(yōu)化的數(shù)學(xué)模型描述為：

式中：Ci—零件ai的設(shè)計(jì)成本；Ti—零件ai的設(shè)計(jì)時(shí)間，目標(biāo)函數(shù)為傳播路徑上的變更傳播強(qiáng)度、零件的設(shè)計(jì)成本和設(shè)計(jì)時(shí)間的加權(quán)總和最小。Δρu—初始變更節(jié)點(diǎn)的初始變更影響。為了讓變更傳播停止，定義ρi為節(jié)點(diǎn)vi的變更吸收能力，k為變更傳播的步數(shù)。

在尋找最優(yōu)路徑的過(guò)程中，螞蟻會(huì)在其經(jīng)過(guò)的路徑上留下信息素，之后的螞蟻會(huì)根據(jù)這些信息素的強(qiáng)弱選擇路徑。每一次循環(huán)迭代，螞蟻的信息素更新按如下規(guī)則：

式中：Q—常數(shù)；Dl—第l只螞蟻在本次循環(huán)的目標(biāo)函數(shù)值；γ—信息揮發(fā)系數(shù)；Δτlij—在本次循環(huán)中第l只螞蟻留在邊eij上的信息素；Δτij—在本次循環(huán)中邊eij上的信息素的增量。因?yàn)樽兏鼉?yōu)先選擇傳播影響小的邊進(jìn)行傳播，所以定義啟發(fā)因子為：

式中：傳播影響Aij=ω1Iii+ω2Ci+ω3Ti，該啟發(fā)因子表示螞蟻從節(jié)點(diǎn)vi到節(jié)點(diǎn)vj的期望程度。第l只螞蟻從節(jié)點(diǎn)vi到節(jié)點(diǎn)vj的轉(zhuǎn)移概率為：

式中：α（α≥0）—信息素的相對(duì)重要程度，即軌跡的相對(duì)重要性；β（β≥0）—啟發(fā)因子的相對(duì)重要程度，即能見(jiàn)度的相對(duì)重要性；—第l只螞蟻在節(jié)點(diǎn)vi下一步允許選擇的節(jié)點(diǎn)集合。運(yùn)用蟻群算法尋找變更傳播最優(yōu)路徑的搜索步驟，如圖3所示。

圖3 最優(yōu)變更傳播路徑搜索算法框架Fig.3 Algorithm Framework of Optimal Change Propagation Path Searching

（1）通過(guò)對(duì)復(fù)雜產(chǎn)品各零部件之間連接關(guān)系分析，將零部件映射為節(jié)點(diǎn)，物理連接關(guān)系映射為邊，建立復(fù)雜產(chǎn)品網(wǎng)絡(luò)模型。

（2）依據(jù)復(fù)雜網(wǎng)絡(luò)模型，計(jì)算每個(gè)節(jié)點(diǎn)的出入度；通過(guò)從數(shù)據(jù)庫(kù)中提取節(jié)點(diǎn)與節(jié)點(diǎn)之間傳播概率。利用式（4），計(jì)算每條邊的變更傳播強(qiáng)度。

（3）輸入初始變更節(jié)點(diǎn)。評(píng)估每個(gè)節(jié)點(diǎn)變更吸收能力，設(shè)置初始變更節(jié)點(diǎn)影響，運(yùn)用蟻群算法進(jìn)行求解，得到最優(yōu)的傳播路徑。

4 案例分析

為了驗(yàn)證所建模型和算法的有效性，以某型號(hào)摩托車(chē)發(fā)動(dòng)機(jī)為例進(jìn)行分析。產(chǎn)品由汽缸蓋，氣門(mén)，氣門(mén)固定螺母，曲柄銷(xiāo)，氣缸墊片，氣門(mén)固定軸，曲軸箱，活塞等30種零部件組成。根據(jù)該發(fā)動(dòng)機(jī)零部件間的物理連接關(guān)系，得到產(chǎn)品的DSM，并建立零部件結(jié)構(gòu)網(wǎng)絡(luò)模型，如圖4所示。

圖4 零部件結(jié)構(gòu)網(wǎng)絡(luò)模型Fig.4 Structure Network Model of Parts

在設(shè)計(jì)變更傳播的路徑搜尋過(guò)程中，根據(jù)設(shè)計(jì)變更歷史數(shù)據(jù)庫(kù)得到經(jīng)過(guò)每條邊的概率，如圖5所示。圖中為30階方陣，每一方格的顏色深淺代表傳播概率的大小，顏色越深表示概率越大，變更傳播越容易經(jīng)過(guò)這條路徑。依據(jù)式（4）計(jì)算得到每條邊的變更傳播強(qiáng)度以及由產(chǎn)品設(shè)計(jì)變更數(shù)據(jù)庫(kù)得到的每個(gè)零部件的設(shè)計(jì)成本和設(shè)計(jì)時(shí)間，經(jīng)過(guò)計(jì)算得到的發(fā)動(dòng)機(jī)變更傳播影響矩陣，如圖6所示。氣缸體是摩托車(chē)發(fā)動(dòng)機(jī)的重要零部件，且在現(xiàn)實(shí)生活中容易發(fā)生變更，故選取節(jié)點(diǎn)編號(hào)為22的氣缸體為初始變更節(jié)點(diǎn)，初始變更影響設(shè)置為0.30，運(yùn)用蟻群算法求解。算法通過(guò)VisualStudio2013進(jìn)行開(kāi)發(fā)，運(yùn)行算法的計(jì)算機(jī)配置為IntelR CoreTMi5-3210M CPU（2.5 GHz），4GB RAM，得到最路徑為 22→30→21→19→4→25。為說(shuō)明所提方法的有效性，僅考慮變更傳播強(qiáng)度單個(gè)目標(biāo)所得最優(yōu)路徑為22→1→30→19→10→21。由以上結(jié)果比較得出，如果僅考慮變更傳播強(qiáng)度，單目標(biāo)設(shè)計(jì)變更傳播最優(yōu)路徑的變更傳播強(qiáng)度（2.52）小于多目標(biāo)求解時(shí)變更傳播強(qiáng)度（2.80）。但在比較其設(shè)計(jì)成本和設(shè)計(jì)時(shí)間時(shí)，發(fā)現(xiàn)后者的設(shè)計(jì)總成本和總時(shí)間分別為2220元和23天，都遠(yuǎn)高于前者的設(shè)計(jì)總成本和總時(shí)間：1970元，18天。如果在變更傳播強(qiáng)度沒(méi)有很大差距的情況下，對(duì)前者路徑上的零件進(jìn)行變更，將會(huì)節(jié)省大量的設(shè)計(jì)時(shí)間和設(shè)計(jì)成本，提高設(shè)計(jì)的敏捷性。

圖5 傳播概率矩陣Fig.5 Matrix of Propagation Likelihood

圖6 發(fā)動(dòng)機(jī)變更傳播影響矩陣Fig.6 Matrix of Change Propagation Impact on Engine

5 結(jié)論

針對(duì)復(fù)雜產(chǎn)品設(shè)計(jì)變更傳播多目標(biāo)優(yōu)化問(wèn)題，提出了一種基于小世界網(wǎng)絡(luò)的方法。該方法考慮了節(jié)點(diǎn)的度和節(jié)點(diǎn)間的傳播概率兩個(gè)變量計(jì)算變更傳播強(qiáng)度，又引入零件的設(shè)計(jì)成本和設(shè)計(jì)時(shí)間，建立設(shè)計(jì)變更傳播多目標(biāo)路徑優(yōu)化模型，運(yùn)用蟻群算法求解得到一條傳播影響最小的路徑。在實(shí)例研究中，以某型號(hào)摩托車(chē)發(fā)動(dòng)機(jī)為例，對(duì)上述模型和算法進(jìn)行了驗(yàn)證。所提方法僅從零件層次考慮，對(duì)設(shè)計(jì)變更傳播的影響進(jìn)行了分析，得出有效的結(jié)論。由于變更的執(zhí)行必須要從零部件的設(shè)計(jì)參數(shù)著手，未來(lái)我們將會(huì)從復(fù)雜產(chǎn)品零部件的參數(shù)角度考慮展開(kāi)研究。