廣義BOM時間建模

閆崇京

南京航空航天大學,南京,210016

廣義BOM時間建模

閆崇京

南京航空航天大學,南京,210016

針對廣義BOM建模中的時間模糊性和約束多樣性問題，提出了BOM時間的多色圖描述方法。采用模糊數表達BOM時間，通過圖的“著色”實現多種時間約束的表達；建立了BOM時間到時間約束網絡的映射規則，給出了BOM時間一致性的判定和求解方法；最后通過實例對BOM時間模型及其求解方法進行了驗證。

BOM；時間約束網絡；模糊時間；生產計劃

0　引言

飛機、艦船等大型復雜裝備具有構型變化和歷史狀態變化多而復雜的特點,產品生命周期中的數據一致性很難保證。基于單一產品數據源的思想,波音公司構建了DCAC/MRM系統,空客公司隨后跟進了該技術的研究。國內對單一產品數據源技術也展開了相關研究，文獻[1]提出一種單一企業物料清單，提高了信息共享的效率；文獻[2]提出主-子模型的集成模型， 基于歷史狀態驅動模型變化,解決了構型管理的問題。擴展型物料清單[3]、制造過程語義模型[4]等則通過BOM語義的擴展以提升對制造過程的描述能力。現有研究給出了解決BOM一致性的思路和方法，但仍采用傳統的時間表達方法,如文獻[1]中的計劃開工日期、計劃完工日期、實際開工日期、實際完工日期。工程實際中,由于信息量的不足,BOM時間具有模糊性[5]，僅能給出一個可能的時間范圍。此外,現有方法難以區分不同的時間約束類型,增加了計算機求解難度。本文針對BOM時間的模糊性和時間約束的多樣性，提出一種BOM時間的多色圖模型，并給出基于時間約束網絡的求解方法。

1　BOM時間模型

1.1BOM時間參數選擇

BOM模型往往會給出BOM節點(制造活動)的基本運行時間，以滿足各級生產計劃編制的需要。傳統方法中，制造活動的運行時間為確定值，在此基礎上，可以計算物料需求的提前期、制造活動的開工日期和完工日期、項目的總工期等時間參數。BOM建模時，由于許多工作缺少經驗，或者任務信息難以獲取,從而使得活動運行時間存在隨機性、不知性和模糊性，制造活動運行時間的不確定性通常是這三者的綜合反映[6]。由于制造活動運行時間的不確定性并不是其本身信息的不確定性，而是工程人員對該不確定性信息的主觀反映，因此，采用模糊數學表達制造活動運行時間更為合理。一般地,定義制造活動運行時間為三角模糊數：

(1)

式中,dmin、dmst、dmax分別為最短運行時間、最可能運行時間和最長運行時間。

BOM時間參數同時包含了時間點和時間區間兩種類型,如制造活動的開始時間和結束時間為時間點,而活動的運行時間、活動開始時間范圍為時間區間。因此，在建模和計算過程中需要區別對待。BOM中除了制造活動運行時間外，還需要描述活動之間的約束關系。根據Allen的時間區間代數，對其13種關系進行整理可以得到BOM中兩個制造活動之間的4種約束關系:開始-開始時間約束(start-to-start,STS)、開始-結束時間約束(start-to-finish,STF)、結束-開始時間約束(finish-to-start,FTS)和結束-結束時間約束(finish-to-finish,FTF)，如圖1所示。

圖1　BOM時間約束

在BOM中需要表達制造活動運行時間和4種時間約束。4種時間約束可采用式(1)描述，而活動運行時間可以轉換為STF時間約束，則BOM中的時間參數為4種時間約束，隸屬度函數統一表達為

式中,dcs,min、dcs,mst、dcs,max分別為最短時間約束、最可能時間約束和最長時間約束。

1.2BOM模糊時間模型

定義1BOM時間模型是一個多色圖:

BOM=(ACTIVITY,LINK,TIME)

其中,ACTIVITY=A={ai|i=1，2,…，n}是BOM節點的集合,表示制造活動,i為節點序號。LINK={L,F,L×F}為BOM聯系的多色集合,L={〈ai,aj〉|i,j=1,2,…,n}是BOM聯系的集合,表示制造活動之間的關聯關系；F={logical，Ⅰ，Ⅱ，Ⅲ，Ⅳ}是聯系的“顏色”，表示關聯關系的屬性：邏輯聯系logical、Ⅰ類時間約束、Ⅱ類時間約束、Ⅲ類時間約束和Ⅳ類時間約束；L×F表示邊的“著色”,即確定聯系的類型。關聯關系的屬性之間為“或取”關系，即一個關聯關系可以同時具有多種屬性，或者沒有屬性，任意一聯系的屬性表達為F(l)=F1(L)∨F2(L)∨F3(L)∨F4(L)∨F5(L),l∈L。TIME={D,L×D]}是BOM時間約束的多色集合,D={〈dcs,min,i,j,dcs,mst,i,j,dcs,max,i,j〉|i,j=1,2,…,m}是時間約束集合,i,j為節點序號。

2　BOM時間網絡

2.1BOM時間網絡模型

時間約束網絡能較好地描述時間知識和時間約束，并采用圖論方法對約束滿足問題進行推理和求解。相較于模糊時間BOM的普通求解方法，時間約束網絡在求解時間參數的同時,實現了BOM時間約束的沖突檢測。

定理1BOM時間是一致的,當且僅當對應的BOM時間約束網絡GT中不存在負環。

2.2BOM模型變換

令λ為模糊時間隸屬度函數的截集閾值。

規則2若F2(li,j)∨F3(li,j)∨F4(li,j)∨F5(li,j)=1,有以下四種情況：

i,j=1,2,…,n

規則4若F1(li,j)∨F2(li,j)∨F3(li,j)∨F4(li,j)∨F5(li,j)=0,則有

定義DT為BOM最小時間距離矩陣,di,j為活動節點i到活動節點j的最小時間距離。DT的求解是圖論中的最短距離問題，選擇算法時需考慮圖中的負環。若di,j≥0,則BOM時間約束是一致的,且

式中,tS i、tF i分別為i節點的開始時間和結束時間。

若di,j<0,則BOM時間約束存在沖突。此時,需松弛相關時間約束,最小松弛量為

3　應用實例

某大型裝備部件A的基本結構和時間約束如圖2所示,其BOM時間模型為

A={0010,1001,1002,1003,2001,2002}

圖2　BOM模糊時間模型實例

對圖2所示的BOM映射后得到圖3所示的時間約束網絡，其中,S0、F0分別為總開始節點和總終止節點；內部節點中，S表示開始節點，F表示結束節點，如S1001為BOM中1001對應的開始節點，F1002為BOM中1002對應的結束節點。根據規則1得到時間約束網絡。

圖3　BOM時間約束網絡

基于Floyd-Warshall算法[7]求解該BOM時間約束網絡：

float Dis[n][n];//BOM時間約束網絡

for( int k = 1; k〈n; k + + )

for( int i = 1; i〈n; i + + )

for( int j = 1; j〈n; j + + )

Dis[i][j] = min ( Dis[i][j]，Dis[i][k] + Dis[k][j])

λ=0.8時的時間約束矩陣為

矩陣中空白處的元素為0;dS1001,S1001、dF1001,F1001、dS1002,S1002、dF1002,F1002、dS010,S0010、dF010,F0010均小于0,即時間約束網絡中存在負環,由定理2可知BOM中的時間約束存在沖突。由式(3)逐步調整,并使BOM匯點協調時差為0,有

調整后的矩陣中無負環。因此,可得λ=0.8時的制造活動的時間范圍；同理，可求出λ=0.9時BOM中各制造活動的時間范圍,如表1所示。

表1　BOM活動節點的時間范圍(λ=0.8，0.9)

4　結語

針對廣義BOM建模中的4類BOM時間約束和模糊時間表達問題，建立了基于多色圖的BOM時間數學模型，給出了一種BOM模糊時間的轉換規則和基于最小時間距離的求解方法，建立了基于負環判定的BOM時間一致性判定方法。下一步的工作將研究BOM時間優化問題，分析各種BOM時差與BOM時間網絡的內在聯系，提出BOM時間調整的備選方案。

[1]李洲洋,田錫天,賈曉亮,等.基于SEBOM的飛機制造過程管理體系研究[J].西北工業大學學報,2008,26(6)：771-776．LiZhouyang,TianXitian，JiaXiaoliang，etal.SingleEnterpriseBOM-basedProcessManagementSystemforAircraftManufacturing[J].JournalofNorthwesternPolytechnicalUniversity，2008，26(6)：771-776.

[2]盧鵠，于勇，楊五兵，等．飛機單一產品數據源集成模型研究[J].航空學報,2010，31(4)：836-841.

LuHu，YuYong，YangWubing，etal.ResearchonIntegrationModelofSingleSourceAircraftProductData[J].ACTAAeronauticaEtAstronauticaSinica，2010，31(4)：836-841.

[3]趙巖，莫蓉，常智勇，等. 擴展型制造物料清單視圖構建及其演繹機制[J]. 中國機械工程，2007,18(19):2334-2339.

ZhaoYan，MoRong，ChangZhiyong，etal.ConstitutionofanExtendedMBOMViewandItsDeductionMechanism[J].ChinaMechanicalEngineering，2007，18(19)：2334-2339.

[4]呂盛坪,喬立紅,劉威.制造過程數據形式化語義建模[J].機械工程學報,2012,48(10):184-191.

LüShengping,QiaoLihong,LiuWei.FormalizedandSemanticModelingofManufacturingProcessData[J].JournalofMechanicalEngineering,2012,48(10):184-191.

[5]CaramiaM,GuerrieroF.ANoteontheModelingofProjectNetworkswithTimeConstraints[J].EuropeanJournalofOperationalResearch,2011,211(3):666-670.

[6]李若剛，王國祥，李躍，等．關于網絡計劃模型中的時間不確定性的討論[J]. 系統工程與電子技術，1997，40(8)：40-45．

LiRuogang，WangGuoxiang，LiYue，etal.StudyonUncertaintyofActivityDurationofPERT[J].SystemEngineeringandElectronicTechnology，1997，40(8)： 40-45.

[7]徐瑞，徐曉飛，崔平遠.基于時間約束網絡的動態規劃調度算法[J]. 計算機集成制造系統-CIMS，2004，10(2)：188-194．

XuRui，XuXiaofei，CuiPingyuan.DynamicPlanningandSchedulingAlgorithmBasedonTemporalConstraintNetwork[J].ComputerIntegratedManufacturingSystems，2004，10(2)：188-194.

[8]ZwickU.AllPairsShortestPathsinWeightedDirectedGraphs-exactandAlmostExactAlgorithms[C]//Proceedingsofthe39thIEEEAnnualSymposiumonFoundationsofComputerScience.LosAlamitos,CA:1998:310-319.

(編輯張洋)

Generalized BOM Time Modeling

Yan Chongjing

Nanjing University of Aeronautics and Astronautics,Nanjing,210016

A polygraph based method was proposed to describe time constraints and fuzzy time in one BOM.The time attributes was represented with fuzzy number and pigmentation of polychromatic set.Rules and approach were put forward to check and calculate the time consistency from BOM to time network.A case study was illustrated for evaluating the proposed method.

bill of material(BOM);time constraint network;fuzzy time;production schedule

2013-09-09

江蘇省產學研聯合創新基金資助項目(BY2014003-16);江蘇省精密與微細制造技術重點實驗室開放基金資助項目(JSPM201307)

TH166DOI：10.3969/j.issn.1004-132X.2015.02.009

閆崇京,男,1976年生。南京航空航天大學機電學院講師。主要研究方向為數字化設計制造。發表論文10篇。