閆崇京

南京航空航天大學(xué),南京,210016

廣義BOM時間建模

閆崇京

南京航空航天大學(xué),南京,210016

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

BOM；時間約束網(wǎng)絡(luò)；模糊時間；生產(chǎn)計劃

0　引言

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

1　BOM時間模型

1.1BOM時間參數(shù)選擇

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

(1)

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

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

圖1　BOM時間約束

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

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

1.2BOM模糊時間模型

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

BOM=(ACTIVITY,LINK,TIME)

其中,ACTIVITY=A={ai|i=1，2,…，n}是BOM節(jié)點的集合,表示制造活動,i為節(jié)點序號。LINK={L,F,L×F}為BOM聯(lián)系的多色集合,L={〈ai,aj〉|i,j=1,2,…,n}是BOM聯(lián)系的集合,表示制造活動之間的關(guān)聯(lián)關(guān)系；F={logical，Ⅰ，Ⅱ，Ⅲ，Ⅳ}是聯(lián)系的“顏色”，表示關(guān)聯(lián)關(guān)系的屬性：邏輯聯(lián)系logical、Ⅰ類時間約束、Ⅱ類時間約束、Ⅲ類時間約束和Ⅳ類時間約束；L×F表示邊的“著色”,即確定聯(lián)系的類型。關(guān)聯(lián)關(guān)系的屬性之間為“或取”關(guān)系，即一個關(guān)聯(lián)關(guān)系可以同時具有多種屬性，或者沒有屬性，任意一聯(lián)系的屬性表達為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為節(jié)點序號。

2　BOM時間網(wǎng)絡(luò)

2.1BOM時間網(wǎng)絡(luò)模型

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

定理1BOM時間是一致的,當(dāng)且僅當(dāng)對應(yīng)的BOM時間約束網(wǎng)絡(luò)GT中不存在負環(huán)。

2.2BOM模型變換

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

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

i,j=1,2,…,n

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

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

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

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

3　應(yīng)用實例

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

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

圖2　BOM模糊時間模型實例

對圖2所示的BOM映射后得到圖3所示的時間約束網(wǎng)絡(luò)，其中,S0、F0分別為總開始節(jié)點和總終止節(jié)點；內(nèi)部節(jié)點中，S表示開始節(jié)點，F(xiàn)表示結(jié)束節(jié)點，如S1001為BOM中1001對應(yīng)的開始節(jié)點，F(xiàn)1002為BOM中1002對應(yīng)的結(jié)束節(jié)點。根據(jù)規(guī)則1得到時間約束網(wǎng)絡(luò)。

圖3　BOM時間約束網(wǎng)絡(luò)

基于Floyd-Warshall算法[7]求解該BOM時間約束網(wǎng)絡(luò)：

float Dis[n][n];//BOM時間約束網(wǎng)絡(luò)

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,即時間約束網(wǎng)絡(luò)中存在負環(huán),由定理2可知BOM中的時間約束存在沖突。由式(3)逐步調(diào)整,并使BOM匯點協(xié)調(diào)時差為0,有

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

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

4　結(jié)語

針對廣義BOM建模中的4類BOM時間約束和模糊時間表達問題，建立了基于多色圖的BOM時間數(shù)學(xué)模型，給出了一種BOM模糊時間的轉(zhuǎn)換規(guī)則和基于最小時間距離的求解方法，建立了基于負環(huán)判定的BOM時間一致性判定方法。下一步的工作將研究BOM時間優(yōu)化問題，分析各種BOM時差與BOM時間網(wǎng)絡(luò)的內(nèi)在聯(lián)系，提出BOM時間調(diào)整的備選方案。

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

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

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

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

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

[4]呂盛坪,喬立紅,劉威.制造過程數(shù)據(jù)形式化語義建模[J].機械工程學(xué)報,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]李若剛，王國祥，李躍，等．關(guān)于網(wǎng)絡(luò)計劃模型中的時間不確定性的討論[J]. 系統(tǒng)工程與電子技術(shù)，1997，40(8)：40-45．

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

[7]徐瑞，徐曉飛，崔平遠.基于時間約束網(wǎng)絡(luò)的動態(tài)規(guī)劃調(diào)度算法[J]. 計算機集成制造系統(tǒng)-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

江蘇省產(chǎn)學(xué)研聯(lián)合創(chuàng)新基金資助項目(BY2014003-16);江蘇省精密與微細制造技術(shù)重點實驗室開放基金資助項目(JSPM201307)

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

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