廣義BOM時(shí)間建模

閆崇京

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

廣義BOM時(shí)間建模

閆崇京

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

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

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

0　引言

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

1　BOM時(shí)間模型

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

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

(1)

式中,dmin、dmst、dmax分別為最短運(yùn)行時(shí)間、最可能運(yùn)行時(shí)間和最長運(yùn)行時(shí)間。

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

圖1　BOM時(shí)間約束

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

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

1.2BOM模糊時(shí)間模型

定義1BOM時(shí)間模型是一個(gè)多色圖:

BOM=(ACTIVITY,LINK,TIME)

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

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

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

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

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

2.2BOM模型變換

令λ為模糊時(shí)間隸屬度函數(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最小時(shí)間距離矩陣,di,j為活動(dòng)節(jié)點(diǎn)i到活動(dòng)節(jié)點(diǎn)j的最小時(shí)間距離。DT的求解是圖論中的最短距離問題，選擇算法時(shí)需考慮圖中的負(fù)環(huán)。若di,j≥0,則BOM時(shí)間約束是一致的,且

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

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

3　應(yīng)用實(shí)例

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

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

圖2　BOM模糊時(shí)間模型實(shí)例

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

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

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

float Dis[n][n];//BOM時(shí)間約束網(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時(shí)的時(shí)間約束矩陣為

矩陣中空白處的元素為0;dS1001,S1001、dF1001,F1001、dS1002,S1002、dF1002,F1002、dS010,S0010、dF010,F0010均小于0,即時(shí)間約束網(wǎng)絡(luò)中存在負(fù)環(huán),由定理2可知BOM中的時(shí)間約束存在沖突。由式(3)逐步調(diào)整,并使BOM匯點(diǎn)協(xié)調(diào)時(shí)差為0,有

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

表1　BOM活動(dòng)節(jié)點(diǎn)的時(shí)間范圍(λ=0.8，0.9)

4　結(jié)語

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

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

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

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

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

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

[4]呂盛坪,喬立紅,劉威.制造過程數(shù)據(jù)形式化語義建模[J].機(jī)械工程學(xué)報(bào),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ì)劃模型中的時(shí)間不確定性的討論[J]. 系統(tǒng)工程與電子技術(shù)，1997，40(8)：40-45．

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

[7]徐瑞，徐曉飛，崔平遠(yuǎn).基于時(shí)間約束網(wǎng)絡(luò)的動(dòng)態(tài)規(guī)劃調(diào)度算法[J]. 計(jì)算機(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)新基金資助項(xiàng)目(BY2014003-16);江蘇省精密與微細(xì)制造技術(shù)重點(diǎn)實(shí)驗(yàn)室開放基金資助項(xiàng)目(JSPM201307)

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

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