（計(jì)算機(jī)軟件與理論專(zhuān)業(yè)論文）基于與或樹(shù)的柔性bom結(jié)構(gòu)及其自動(dòng)診斷方法.pdf

中山大學(xué)碩士學(xué)位論文 基于與或樹(shù)的柔- 眭b o m 結(jié)構(gòu)及其自動(dòng)診斷方法 專(zhuān)業(yè)：計(jì)算機(jī)軟件與理論 碩士生：劉裕 指導(dǎo)老師：姜云飛教授 摘要 物料清單( b o m ) 是企業(yè)產(chǎn)品制造過(guò)程中不同部門(mén)、不同流程間傳遞數(shù)據(jù)的 基本形式，是企業(yè)集成管理的信息紐帶。因此，b 叫的結(jié)構(gòu)設(shè)計(jì)及其數(shù)據(jù)正確性 的維護(hù)都是企業(yè)信息管理中十分重要的內(nèi)容。 針對(duì)b 伽的變型設(shè)計(jì)問(wèn)題，本文首先分析了產(chǎn)品的組成成分，然后從產(chǎn)品結(jié) 構(gòu)的柔性特征出發(fā)，通過(guò)對(duì)傳統(tǒng)樹(shù)形產(chǎn)品結(jié)構(gòu)的擴(kuò)展，形式化定義了一種基于與 或樹(shù)的產(chǎn)品結(jié)構(gòu)形式，并給出了相關(guān)的b o m 數(shù)據(jù)表設(shè)計(jì)和面向任務(wù)的產(chǎn)品配置方 法。事實(shí)表明，這種柔性b o m 結(jié)構(gòu)不僅可以實(shí)現(xiàn)動(dòng)態(tài)的產(chǎn)品結(jié)構(gòu)配置，體現(xiàn)了產(chǎn) 品管理的一致性，還能顯著地減少產(chǎn)品變型設(shè)計(jì)中的數(shù)據(jù)冗余，使統(tǒng)一的b o m 數(shù)據(jù)管理得到保障。 針對(duì)b o m 的數(shù)據(jù)維護(hù)問(wèn)題，本文將基于模型的診斷技術(shù)與b o m 的錯(cuò)誤診斷相 結(jié)合，實(shí)現(xiàn)了對(duì)產(chǎn)品結(jié)構(gòu)中語(yǔ)義錯(cuò)誤的自動(dòng)診斷。為了使模型診斷技術(shù)得以應(yīng)用， 本文定義了b o m 的一種診斷模型，給出了產(chǎn)品結(jié)構(gòu)及其產(chǎn)品配置的邏輯描述形 式，并引入產(chǎn)品配置樣例集合作為系統(tǒng)的期望結(jié)果，通過(guò)相關(guān)的模型診斷算法， 從而實(shí)現(xiàn)了對(duì)b o m 的錯(cuò)誤診斷。在此基礎(chǔ)上，本文還實(shí)現(xiàn)了一個(gè)診斷系統(tǒng)原型， 其測(cè)試結(jié)果表明，這是一種行之有效的診斷方法。 關(guān)鍵詞：物料清單，變型設(shè)計(jì)，與或樹(shù)，錯(cuò)誤診斷，基于模型診斷 中山大學(xué)碩士學(xué)位論文 af l e x i b l eb o ms 仃u m l r eb a s e do na n d o rt r e ea n di t sa u t o m a t i c m e m o do fd i a g n o s i s m a j o r ：c o m p u t e rs o f 【、v a r ea n dt h e o r y n a m e ： l i u y u s u p e r v i s o r ：p r o f e s s o rj i a n gy u n - f e i a b s t r a c t b i l lo fm a t e r i a l s ( b o m ) i so n eo ft l eb a s i cf o r m sf o rd a t ae x c h a i l g eb e t w e c n d i 丘b r e n td e p a m n e n t so fe n t e r p r i s e ，a i l db e t 、e e nd i 盤(pán)b r e n ti n a n u f k t u r ep r o c e s s e s ， w h i c ha l s oi sm ei n f o m l a t i o n 晡d g ef o ri m e g r a t i n ge n t e r p r i s e sm a n a g e m e n t t h e d e s i g no fb o ms t m c t u r ca n d 恤m a i n t e n a i l c eo fb o md a 詛c o r r e c t n e s sh a v eb c e na g r o w i n gi n t e r e s tf o rr e s e a i h e r s t oa d d r e s st h ec h a l l e n g eo fv 撕a n t d e s i 9 1 lo fb o m ，t h i sw o r ki n v e s t i g a t e st h e c o i n p o s i t o no fp r o d u c t 誦mt h er e q u i r e df l e x i b i l i t yf e a t u r e s ，a n dd e f i n e sp r o d u c t s t r u c t u r e sb a s e do n 也ee x t e l 試e da n d o r 慨t h ed e s i g no fr e l a t e db o mf o na n d t h ec o i r c l a t e dp r o d l l c t - c o i g i l r a t i o na l g o r i t l l ma r ea l s dp r e s e n t e d i ti ss h o w nt 1 1 a t ，t h e n e x i b i l i t yd e s i g i lo fb o m c a i lp r o v i d ed ”a m i cp r o d u c tc o n f i g i l r a t i o n ，a n ds u 雎c ef o r m a i n t a i n i n gm ec o n s i s t e n c yo f p r o d u c tm a i l a g e m e m t h en e x i b i l i 妙d e s i g nc a nr e d u c e d a t ar e d u n d a n c yo nv a r i a n td e s i g n ，e n s u r i n gc o n s i s t e n tm a i l a g e m e n to f b o md a t a d u ct ot h cs i g n i f i c a n ti m p o r i a n c eo fc o r r e c t l l e s sm a i n t e n a n c eo fb o m ，t h i sp a p e r a l s oe n l p l o y sm o d a l - b a s e dd i a g f l o s i sm e t h o di ne 玎o rd i a g n o s i so fb o m ，a i l l l i n gt o i d e r n i f ys e m a n t i ce r r o r so fp r o d u c ts t n l c t u r e t ba p p l yt 1 1 em o d e l - b a s e dd i 姆l o s i s t e c h n o l o gy ，t i l i sp a p e rp r e s e n t sad i a g n o s i sm o d a lo fb o ma sw e l la s t h el o g i c d e s c r i p t i o no fp m d u c ts t n l c l = u r ea n dp r o d u c tc o n f i g u r 砒i o n ，a n dm e nw o f k so ma s o l u f i o no fb o md i a 印o s i s 、v i mr e l e v 刪c o m p u t 缸ga l g o 枷1 n l sb yi m p o n i n gp r o d u c t c o n f i g w a t i o ns a m p l e sa se x p e c t e do m c o m e f i n a l l y ap m t o t y p eo fd i a g n o s i ss y s t e m h a sb e e ni n u d d u c e da sw e l l ，w h o s et e s t i n ge n s u r e st h ee 婦b c t i v e n e s sa n de m c i e n c yo f t h j sm e t h o d k e yw o r d s ：b i l lo fm a t e r i a l s ，v a r i a n cd e s i g n ，a n d o rt r e e ，f a u l td i a g n o s i s ， m o d a l l b a s e dd i a 掣m s i s i i 中山大學(xué)碩士學(xué)位論文 1 1 引言 第一章緒論 在現(xiàn)代制造、加工業(yè)中，很多復(fù)雜的成套電子設(shè)備、機(jī)械設(shè)備都由數(shù)以萬(wàn)計(jì) 的自制件、外協(xié)件、外購(gòu)件及原材料等各種各樣的零部件所組成，為了形成各種 型號(hào)的產(chǎn)品，要對(duì)這些零部件進(jìn)行合理的組合，這就是產(chǎn)品結(jié)構(gòu)配置。基于這種 思想，人們提出了物料清單b o m ( b i l lo f 腑t e r i a l s ) 這個(gè)概念。 隨著以信息集成為核心的c i m 技術(shù)和企業(yè)自動(dòng)化程度的進(jìn)一步提高，將產(chǎn)生 大量與產(chǎn)品相關(guān)的重要數(shù)據(jù)和信息，如何有效地管理好這些產(chǎn)品信息，以及實(shí)現(xiàn) 好信息共享和信息集成，成為企業(yè)界和學(xué)術(shù)界有待解決的問(wèn)題。其中，采用數(shù)據(jù) 格式來(lái)描述產(chǎn)品結(jié)構(gòu)的物料清單文件即b 伽，更是集成管理系統(tǒng)的基礎(chǔ)，幾乎與 企業(yè)中所有的職能部門(mén)都有關(guān)系，其主要用途有： ( 1 ) 是計(jì)算機(jī)識(shí)別物料的基礎(chǔ)依據(jù)； ( 2 ) 是編制生產(chǎn)制造計(jì)劃，配套和領(lǐng)料的依據(jù)； ( 3 ) 可以根據(jù)它進(jìn)行加工過(guò)程的跟蹤： ( 4 ) 是采購(gòu)和外協(xié)的依據(jù)，且可進(jìn)行物料追溯； ( 5 ) 根據(jù)它進(jìn)行成本的計(jì)算，作為報(bào)價(jià)參考： ( 6 ) 使設(shè)計(jì)系列化，標(biāo)準(zhǔn)化，通用化。 b o m 不僅是物料資源計(jì)劃( m r p ) 系統(tǒng)中重要的輸入數(shù)據(jù)，還是c i m s m i s 與 c a d ，c a p p 等子系統(tǒng)的主要接口，是財(cái)務(wù)部門(mén)核算成本。制造部門(mén)組織生產(chǎn)等的重 要依據(jù)，其組織格式設(shè)計(jì)合理與否直接影響到系統(tǒng)的處理性能。因此，根據(jù)實(shí)際 的使用環(huán)境，靈活地設(shè)計(jì)合理且有效的b o m 是十分重要的。若給b o m 一個(gè)柔性定 義，可以更好地適應(yīng)企業(yè)部門(mén)的不同需求，有效地減少b o m 表的數(shù)量，從而能更 好地消除產(chǎn)品數(shù)據(jù)的不一致性，促進(jìn)企業(yè)信息集成，提高企業(yè)的快速反應(yīng)能力。 與此同時(shí)，正因?yàn)樵诨A(chǔ)數(shù)據(jù)中b o m 的影響面最大，對(duì)它的準(zhǔn)確性要求也最 高。一般來(lái)說(shuō)，要使m r p 系統(tǒng)順利實(shí)施并提供有用信息，要求( 】l ： ( 1 ) 產(chǎn)品物料清單b o m 的準(zhǔn)確性達(dá)到9 8 ： ( 2 ) 產(chǎn)品物料清單b 伽的合法性達(dá)到l o o ； 第一章緒論 ( 3 ) 庫(kù)存狀態(tài)數(shù)據(jù)的準(zhǔn)確性達(dá)到9 5 。 以上三個(gè)指標(biāo)不容易達(dá)到但又是必須努力達(dá)到的，否則m r p i i 便會(huì)失去意義， 同時(shí)也會(huì)給企業(yè)的集成帶來(lái)很多困難。而b o m 通常是在關(guān)系數(shù)據(jù)模型的支持下， 以數(shù)據(jù)表的形式存放，不僅數(shù)據(jù)量大，而且容易出錯(cuò)，靠人工檢查或根據(jù)實(shí)際中 出現(xiàn)的問(wèn)題再定位錯(cuò)誤，將導(dǎo)致很大的工作量且會(huì)帶來(lái)許多不必要的損失。所以， 對(duì)b o m 的正確性檢查和診斷也是一個(gè)非常有意義的課題。 本文主要針對(duì)上述領(lǐng)域，首先對(duì)b o m 的柔性定義和產(chǎn)品配置問(wèn)題進(jìn)行了相關(guān) 研究，然后把人工智能中的基于模型診斷技術(shù)應(yīng)用到b 叫數(shù)據(jù)的錯(cuò)誤診斷中，最 后介紹了其系統(tǒng)實(shí)現(xiàn)。本文的主要結(jié)構(gòu)安排如下：第一章主要介紹b 和模型診 斷技術(shù)的基本概念和背景知識(shí)，以及相關(guān)的一些研究現(xiàn)狀；第二章主要提出一種 基于與或樹(shù)的柔性b 嗍結(jié)構(gòu)的設(shè)計(jì)及其產(chǎn)品配置方法；第三章主要闡述一種基于 產(chǎn)品結(jié)構(gòu)模型的，對(duì)b o m 中產(chǎn)品結(jié)構(gòu)錯(cuò)誤進(jìn)行自動(dòng)的診斷方法：第四章則主要總 結(jié)本文的工作。 1 2 物料清單( b o m ) 的介紹 b o m 即物料清單，也被稱(chēng)為產(chǎn)品結(jié)構(gòu)表或產(chǎn)品結(jié)構(gòu)樹(shù)。物料一詞在企業(yè)中有 著廣泛的含義，它是所有產(chǎn)品、半成品、在制品、原材料、裝配件、協(xié)作件、易 耗品等與生產(chǎn)有關(guān)物料的統(tǒng)稱(chēng)1 2 】。從物理裝配和組成關(guān)系的空間角度分析，b o m 反映了產(chǎn)品與其構(gòu)成的部件、部件與其子部件之間的層次關(guān)系，是一種代表各部 件構(gòu)成關(guān)系的樹(shù)形結(jié)構(gòu)數(shù)據(jù)文件，還可包括有關(guān)產(chǎn)品及其零部件的編碼、規(guī)格、 材料、質(zhì)量等方面的信息。b 咖可以直觀的表示成一種根部在上的倒置樹(shù)狀圖， 即產(chǎn)品結(jié)構(gòu)樹(shù)( 如圖卜1 ) 。 2 圖卜1 產(chǎn)品結(jié)構(gòu)樹(shù) 中山大學(xué)碩士學(xué)位論文 這種產(chǎn)品結(jié)構(gòu)樹(shù)是一個(gè)包含一個(gè)元素以上的有限集合，其中： 1 ) 有一個(gè)特殊的元素是根元素，該元素的代表用戶感興趣的對(duì)象，如一個(gè) 產(chǎn)品、一個(gè)裝配件等； 2 ) 其余元素又被分成若干產(chǎn)品結(jié)構(gòu)樹(shù)，他們是其根元素的子樹(shù)； 3 ) 產(chǎn)品結(jié)構(gòu)樹(shù)中任一個(gè)元素也稱(chēng)節(jié)點(diǎn)都由其名稱(chēng)標(biāo)志、屬性及訪問(wèn)特性組 成。名稱(chēng)標(biāo)志是唯一的，用來(lái)識(shí)別該部件：屬性?xún)?nèi)容是用戶定制的，可以包括該 部件的一切相關(guān)信息；訪問(wèn)特性是對(duì)節(jié)點(diǎn)的操作控制信息，如讀、寫(xiě)權(quán)限等。 在企業(yè)管理中，產(chǎn)品b o m 的應(yīng)用可分為兩步3 】：一是在開(kāi)始實(shí)施e r p 時(shí)，由 設(shè)計(jì)部門(mén)將企業(yè)產(chǎn)品結(jié)構(gòu)、數(shù)量信息輸入到p d m 系統(tǒng)或e r p 的數(shù)據(jù)庫(kù)中，形成了 設(shè)計(jì)b o m ( b o mf o rd e s i g n ，b o m 4 d ) ，它是系統(tǒng)啟動(dòng)的基礎(chǔ)數(shù)據(jù)之一。由于這項(xiàng) 工作的量非常大，故在這一階段需考慮系統(tǒng)啟動(dòng)的快速性和系統(tǒng)開(kāi)始后的數(shù)據(jù)易 維護(hù)性。二是系統(tǒng)啟動(dòng)后，根據(jù)m r p i i 的思想，將產(chǎn)品b o m 用于企業(yè)的采購(gòu)、投 料、生產(chǎn)、倉(cāng)庫(kù)等生產(chǎn)部門(mén)。首先，工藝部門(mén)收到訂單后，根據(jù)設(shè)計(jì)b o m ，制定 符合客戶要求以及本企業(yè)條件的生產(chǎn)加工前的準(zhǔn)備工作文件，產(chǎn)生工藝b o m ；供 應(yīng)采購(gòu)部門(mén)根據(jù)工藝b o m 以及庫(kù)存情況，確定需要購(gòu)買(mǎi)的零部件清單；財(cái)務(wù)部門(mén) 根據(jù)工藝要求、加工產(chǎn)品的復(fù)雜度、購(gòu)買(mǎi)材料的費(fèi)用以及產(chǎn)品管理所需的費(fèi)用計(jì) 算成本；銷(xiāo)售部門(mén)以工藝b o m 為基礎(chǔ)，加上客戶的需求，制定裝箱清單。其在生 產(chǎn)管理流程中的應(yīng)用可如圖卜2 所示： 設(shè)計(jì)部門(mén) 圖1 - 2b o m 在生產(chǎn)管理流程中的應(yīng)用 有關(guān)b o m 的研究工作很多，目前的主要方向有：b o m 在p d m 和e r p 中的應(yīng)用 第一章緒論 及其集成管理【4 甜，b o m 數(shù)據(jù)的存儲(chǔ)和表示方法【6 ， ，基于產(chǎn)品b o m 的生產(chǎn)制造過(guò) 程規(guī)劃和優(yōu)化【8 吼，基于b o m 驅(qū)動(dòng)的工作流配置方法及改進(jìn)( 1 0 】，對(duì)b o m 數(shù)據(jù)進(jìn)行 相關(guān)應(yīng)用的智能數(shù)據(jù)挖掘1 1 ，12 1 ，b o m 數(shù)據(jù)一致性和規(guī)則完備性的檢查阻1 4 1 等等。 1 3 基于模型診斷技術(shù)的介紹 基于模型診斷( m o d e l 咄a s e dd i a g n o s i s ) 是人工智能領(lǐng)域近年來(lái)發(fā)展起來(lái)的 一個(gè)活躍的分支，其基本任務(wù)是從待診斷系統(tǒng)模型和觀測(cè)到的現(xiàn)象出發(fā)進(jìn)行推 理，根據(jù)觀測(cè)現(xiàn)象與期望結(jié)果之間的差異，從而決定出哪些部件產(chǎn)生故障，才能 夠解釋出現(xiàn)的所有差異。 基于模型診斷的方法與傳統(tǒng)診斷推理方法的主要區(qū)別在于 1 5 】：一方面系統(tǒng)的 行為可以被觀測(cè)到；另一方面，需建立描述系統(tǒng)內(nèi)部結(jié)構(gòu)和行為方式的模型，并 可預(yù)言其預(yù)期行為。如果系統(tǒng)的實(shí)際行為( 觀測(cè)) 和期望行為( 預(yù)言) 出現(xiàn)了差 異，就產(chǎn)生了診斷問(wèn)題。一般來(lái)說(shuō)，模型診斷中使用的模型可用標(biāo)準(zhǔn)a i 技術(shù)構(gòu) 造，如謂詞邏輯、框架、約束等。實(shí)現(xiàn)模型化技術(shù)的診斷算法也是基于標(biāo)準(zhǔn)a i 技術(shù)的，如定理證明、啟發(fā)式搜索、定性仿真和貝葉斯網(wǎng)絡(luò)等。 總的來(lái)說(shuō)，基于模型診斷的基本思想可如圖卜3 所示【16 】：根據(jù)組成元件與元 件之間的連接關(guān)系建起待診斷系統(tǒng)的模型( 如結(jié)構(gòu)、功能、行為) ，這種模型通 常用階邏輯語(yǔ)句來(lái)描述，根據(jù)系統(tǒng)的邏輯模型以及系統(tǒng)的輸入，可以通過(guò)邏輯 的推理理論推導(dǎo)出系統(tǒng)在正常情況下的預(yù)期行為，如果觀測(cè)到的系統(tǒng)實(shí)際行為與 系統(tǒng)預(yù)期行為有差異，就說(shuō)明系統(tǒng)存在故障，利用邏輯推理理論，便能夠確定引 發(fā)故障的元件集合。 圖l - 3基于模型診斷的基本思想 在理論上，基于模型診斷過(guò)程已經(jīng)形式化，根據(jù)不同的邏輯定義，基于一致 性診斷和溯因診吲1 8 1 是其中兩個(gè)具有代表性的研究流派。目前各種各樣的基 4 中山大學(xué)碩士學(xué)位論文 于模型診斷的理論，對(duì)診斷知識(shí)的表示與描述方法也正在不斷發(fā)展，如c o n s o l e 等將診斷看成是帶一致性約束的溯因問(wèn)題i i ，并提出了一個(gè)統(tǒng)一的定義，使得不 同的邏輯定義都可在這一定義中進(jìn)行表示，并能夠進(jìn)行比較；歐陽(yáng)丹彤等提出的 關(guān)于廣義因果理論的基于模型診斷與中心診斷的方法f 2 0 】，以及對(duì)擴(kuò)展的因果理論 中的測(cè)試問(wèn)題的研究 2 i 】；g e f f n e r 等將系統(tǒng)行為的因果知識(shí)用信念網(wǎng)表示，并 用b a y e s 推理來(lái)實(shí)現(xiàn)診斷。正是由于這些理論和方法的不斷出現(xiàn)促進(jìn)了基于模型 診斷理論的發(fā)展，并使其在實(shí)踐中得到越來(lái)越廣泛的應(yīng)用。 實(shí)際應(yīng)用中，比較經(jīng)典的診斷系統(tǒng)是g d e 系統(tǒng)【2 3 l 和d a r t 系統(tǒng)【2 4 1 ，它們將測(cè) 試和診斷很好地結(jié)合了起來(lái)。在應(yīng)用領(lǐng)域方面，基于模型診斷系統(tǒng)最初主要應(yīng)用 于硬件電路故障診斷，用來(lái)診斷電子電路系統(tǒng)等硬件設(shè)備中的錯(cuò)誤行為，及發(fā) 現(xiàn)v h d l 【2 5 】等硬件設(shè)計(jì)描述語(yǔ)言中的邏輯錯(cuò)誤等。后來(lái)類(lèi)似的診斷框架同樣地被 應(yīng)用到邏輯程序【2 6 】，函數(shù)型程序【2 刀等軟件方面的錯(cuò)誤診斷，以及j a v a 【2 8 1 等高級(jí) 語(yǔ)言程序的診斷。此外，基于模型診斷的系統(tǒng)目前已逐漸地被應(yīng)用到各行各業(yè)。 如在工程領(lǐng)域，m o s t e r m e n 等【2 9 】成功地把動(dòng)態(tài)系統(tǒng)的監(jiān)視與診斷相結(jié)合的方法應(yīng) 用到反應(yīng)堆輔助冷卻循環(huán)系統(tǒng)的故障上；在醫(yī)學(xué)領(lǐng)域，t r a u a i d 【3 0 】系統(tǒng)可以幫助 醫(yī)生診斷與修復(fù)外傷治療：在經(jīng)濟(jì)領(lǐng)域，ha i i l s c h e r i3 1 】成功地開(kāi)發(fā)出決策系統(tǒng) c r 0 s b y ，把基于模型診斷理論應(yīng)用于財(cái)會(huì)審計(jì)上等等。 總的來(lái)說(shuō)，與傳統(tǒng)的診斷方法相比，基于模型診斷的技術(shù)具有以下優(yōu)點(diǎn)f 3 2 】： ( 1 ) 具有發(fā)現(xiàn)系統(tǒng)設(shè)計(jì)者所不能預(yù)見(jiàn)的故障的能力； ( 2 ) 模型可重用和易于維護(hù)，在結(jié)構(gòu)調(diào)整時(shí)，以前的模型可以繼承下來(lái)； ( 3 ) 知識(shí)獲取相對(duì)容易，可利用系統(tǒng)的設(shè)計(jì)和技術(shù)規(guī)格信息； ( 4 ) 較強(qiáng)的解釋能力，推理系統(tǒng)具有較強(qiáng)的系統(tǒng)獨(dú)立性。 但是，由于基于模型診斷的方法需要對(duì)實(shí)際系統(tǒng)進(jìn)行模型抽象，目前在模型 的構(gòu)建、選擇、推理，應(yīng)用的廣度，處理復(fù)雜行為等方面還有許多待解決的問(wèn)題 p ”。其中，如何選擇合適的模型是至關(guān)重要的，因?yàn)槿绻Ｐ驼_，那么觀測(cè)和 預(yù)言行為之間的所有差異都可以通過(guò)具有因果關(guān)系的路徑往回追蹤，一定能找到 故障部件。但從理論上看，模型永遠(yuǎn)不是完備的，只是系統(tǒng)的抽象和近似，因此 診斷系統(tǒng)必須在復(fù)雜性和完備性衡量。正因?yàn)槿绱?，目前基于模型診斷系統(tǒng)還主 要應(yīng)用在電子電路方面，在其他如機(jī)械制造，水利設(shè)備等方面所做工作較少。 第一章緒論 1 。4 相關(guān)研究工作的介紹 由于本文主要針對(duì)基于模型診斷技術(shù)在b o m 錯(cuò)誤診斷中的應(yīng)用，并對(duì)b o m 的 柔性定義和配置問(wèn)題進(jìn)行了一些探討。下面主要介紹一些相關(guān)的研究工作和研究 成果，以及本文從中得到的借鑒和參考： 為了使企業(yè)產(chǎn)品的設(shè)計(jì)能適應(yīng)客戶定制的要求，實(shí)現(xiàn)產(chǎn)品結(jié)構(gòu)的動(dòng)態(tài)配囂， w o l f r a m 【4 9 j 通過(guò)擴(kuò)展傳統(tǒng)關(guān)系數(shù)據(jù)庫(kù)的操作規(guī)則，設(shè)計(jì)了一種由規(guī)則驅(qū)動(dòng)的產(chǎn)品 配置器，這種配置器能根據(jù)所定義的規(guī)則庫(kù)，在查詢(xún)時(shí)產(chǎn)生滿足各種變型設(shè)計(jì)要 求的產(chǎn)品結(jié)構(gòu)。由于產(chǎn)品部件的變型組合是由外部規(guī)則約束的，這種方法可以顯 著地減少b o m 中的數(shù)據(jù)記錄量，并可以有效地減少數(shù)據(jù)冗余和數(shù)據(jù)不致的情 況。a l e x a n d e r 也提出了一種實(shí)現(xiàn)產(chǎn)品結(jié)構(gòu)的動(dòng)態(tài)定制的配置器，該配鼉器主 要根據(jù)一組描述客戶需求的輸入?yún)?shù)來(lái)實(shí)現(xiàn)產(chǎn)品結(jié)構(gòu)的變型設(shè)計(jì)，具體方法是通 過(guò)b o m 數(shù)據(jù)與輸入?yún)?shù)之間的計(jì)算與邏輯比較，便可構(gòu)造出符合要求的產(chǎn)品零部 件組合。文獻(xiàn) 5 1 則把產(chǎn)品配置分解為模型庫(kù)和產(chǎn)品定制庫(kù)兩個(gè)層次結(jié)構(gòu)，并將 相似產(chǎn)品的相關(guān)信息加以綜合，提取其中的結(jié)構(gòu)信息構(gòu)建模型庫(kù)，然后將具體產(chǎn) 品與模型產(chǎn)品的轉(zhuǎn)換信息集成在定制庫(kù)中，使產(chǎn)品結(jié)構(gòu)和組成零部件在一定程度 得到分離，極大地降低了產(chǎn)品結(jié)構(gòu)數(shù)據(jù)的記錄量。由此可見(jiàn)，產(chǎn)品變型設(shè)計(jì)的關(guān) 鍵在于降低變型設(shè)計(jì)中相似產(chǎn)品結(jié)構(gòu)問(wèn)的數(shù)據(jù)冗余，上述的方法實(shí)質(zhì)就是把變型 結(jié)構(gòu)從產(chǎn)品數(shù)據(jù)中分離出來(lái)，或以規(guī)則，或以參數(shù)、模型等方式來(lái)實(shí)現(xiàn)動(dòng)態(tài)定制。 b o m 系統(tǒng)另一個(gè)重要的內(nèi)容就是對(duì)b o m 數(shù)據(jù)的維護(hù)和檢查。文獻(xiàn) 1 4 闡述了 m r p 系統(tǒng)運(yùn)算中數(shù)據(jù)完備性和準(zhǔn)確性的要求，指出了b o m 合法性檢查的主要內(nèi)容 及其錯(cuò)誤的類(lèi)型。文獻(xiàn) 5 2 則給出了諸如b o m 表死鎖( 循環(huán)引用) 等相關(guān)b o m 語(yǔ) 法錯(cuò)誤的檢查算法。文獻(xiàn) 1 3 針對(duì)b o m 的一致性維護(hù)問(wèn)題，形式化定義了部件關(guān) 系、部件約束以及部件配置等基本概念，并用邏輯謂詞表示的約束關(guān)系來(lái)檢查 b o m 數(shù)據(jù)的一致性?？傊?，目前b o m 檢測(cè)的研究還是主要在數(shù)據(jù)完備性和一致性 等語(yǔ)法錯(cuò)誤的檢查方面，在語(yǔ)義錯(cuò)誤檢查乃至診斷方面所做工作不多。 在模型診斷技術(shù)方面，文獻(xiàn) 5 4 進(jìn)一步刻畫(huà)了基于模型的診斷問(wèn)題的分解， 為具有樹(shù)型結(jié)構(gòu)的系統(tǒng)診斷效率的提高提供了理論依據(jù)。文獻(xiàn) 5 5 研究了對(duì)知識(shí) 庫(kù)的一致性診斷問(wèn)題，采用了正例和反例來(lái)檢測(cè)知識(shí)庫(kù)中的配置沖突，從而實(shí)現(xiàn) 對(duì)知識(shí)庫(kù)中規(guī)則不致性的診斷，給本文的研究工作提供了很多參考依據(jù)。 6 中山大學(xué)碩士學(xué)位論文 2 1 引言 第二章基于與或樹(shù)的b o m 設(shè)計(jì) 物料清單b o m 實(shí)質(zhì)上是一種描述部件裝配關(guān)系的結(jié)構(gòu)化零件表，其中包括所 有的子裝配件、零件、原材料清單，以及制造一個(gè)裝配件所需物料的數(shù)量等。要 想用計(jì)算機(jī)來(lái)管理企業(yè)的這些繁多而又關(guān)聯(lián)的物料，首先要使系統(tǒng)能夠知道企業(yè) 所制造產(chǎn)品的結(jié)構(gòu)，為了便于計(jì)算機(jī)識(shí)別，還必須把產(chǎn)品結(jié)構(gòu)圖轉(zhuǎn)換成規(guī)范的數(shù) 據(jù)結(jié)構(gòu)，而這種規(guī)范的數(shù)據(jù)結(jié)構(gòu)就是所謂的b o m 結(jié)構(gòu)。 2 1 1 常見(jiàn)的b o m 結(jié)構(gòu) 一、多層b o m 結(jié)構(gòu)( _ m ) 多層b o m 結(jié)構(gòu)【習(xí)( 以下簡(jiǎn)稱(chēng)為娓o m ) 采用“單父一多子”的數(shù)據(jù)結(jié)構(gòu)，它詳 細(xì)記錄了產(chǎn)品的結(jié)構(gòu)信息，即便是同樣的零部件結(jié)構(gòu)，只要存在于不同的裝配關(guān) 系中，也要再記錄一次。在關(guān)系數(shù)據(jù)庫(kù)中，其結(jié)構(gòu)可如表2 1 。 表2 一l 多表b o m 結(jié)構(gòu) 名稱(chēng)類(lèi)型含義 p r o d u c t i n i e g e r產(chǎn)品代碼 c o d e i n t e g e r部件代碼 v b 船i o nc h a r 部件版本 s e q u e n c ei n t e g e r 順序碼 h i e 闞r c h y i n t e g e r 層次碼 u n i tc h 盯 計(jì)量單位 a m o u n tn u m e r i c單位用量 b o m 表中的順序碼表示該部件出現(xiàn)在該產(chǎn)品的產(chǎn)品樹(shù)中的行位置；層次碼表 示該部件出現(xiàn)在產(chǎn)品樹(shù)的列位置。層次碼從l 開(kāi)始，l 表示最終產(chǎn)品的層次，大 于1 的層次碼表示該部件為其緊挨著的，層次碼比它小1 的部件的子部件。由此， 在查詢(xún)?cè)摦a(chǎn)品結(jié)構(gòu)時(shí)，只需以要查的產(chǎn)品代碼為條件按順序碼排序即可一次查出 產(chǎn)品的完整結(jié)構(gòu)。 惦o m 結(jié)構(gòu)的特點(diǎn)是產(chǎn)品間結(jié)構(gòu)不互相影響，各個(gè)產(chǎn)品之間的數(shù)據(jù)記錄沒(méi)有交 7 第二章基于與或樹(shù)的b o m 設(shè)計(jì) 叉。查詢(xún)也簡(jiǎn)單快捷，產(chǎn)品分解時(shí)只需根據(jù)產(chǎn)品的i d 查詢(xún)出最底層零件( 需采 購(gòu)的原材料) 的i d 和數(shù)目即可。 但 【b o m 也存在很多不足之處，主要有： ( 1 ) 順序號(hào)的維護(hù)非常困難。例如，在表中插入一個(gè)零件，其后的零件號(hào)也 必須相應(yīng)的變化： ( 2 ) 數(shù)據(jù)冗余大，不同裝配關(guān)系中相同的零部件結(jié)構(gòu)需要重復(fù)定義； ( 3 ) b o m 結(jié)構(gòu)的設(shè)計(jì)必須按從部件到子部件再到零件，由大到小的順序完成。 二、單層b o m 結(jié)構(gòu)( s b o m ) 單層b o m 結(jié)構(gòu)f 5 】( 簡(jiǎn)稱(chēng)s b o m ) 采用“單父一單子”的數(shù)據(jù)結(jié)構(gòu)，只是記錄了各 個(gè)父件和子件之間的對(duì)應(yīng)關(guān)系，特點(diǎn)是相同的零部件裝配關(guān)系只需記錄一次，其 中表2 2 就描述了種單層b o m 的結(jié)構(gòu)。 表2 2 單層b 0 l i 結(jié)構(gòu) 名稱(chēng)類(lèi)型 含義 c o d e c h a r 部件代碼 1 沌r s b nc l a r 部件版本 n o d ec l i a r 節(jié)點(diǎn)代碼 f a t h e r n o d ec h a r 父節(jié)點(diǎn)代碼 u n i t c h a r 計(jì)量單位 a m o u n tn u i i i e r i c 單位用量 s b o m 表中部件代碼和節(jié)點(diǎn)代碼為主關(guān)鍵字，節(jié)點(diǎn)代碼把不同部件映射到產(chǎn)品 結(jié)構(gòu)樹(shù)中的對(duì)應(yīng)節(jié)點(diǎn)，通過(guò)父節(jié)點(diǎn)標(biāo)識(shí)指向其所屬的父部件。由于是單層b o m ， 產(chǎn)品樹(shù)的生成需要使用遞歸的查詢(xún)方法f 7 】，即首先查找產(chǎn)品第一層子項(xiàng)，再查找 所有以第一層子項(xiàng)為父項(xiàng)的第二層予項(xiàng)，如此遞歸查找直至其下再無(wú)子項(xiàng)為止。 在實(shí)際使用中，單層b o m 具有以下優(yōu)點(diǎn)： ( 1 ) b o m 表修改簡(jiǎn)單，相同的裝配關(guān)系只需修改一次； ( 2 ) 數(shù)據(jù)庫(kù)冗余小，對(duì)相同的層次結(jié)構(gòu)只定義一次，大大節(jié)省了存儲(chǔ)空間。 ( 3 ) 清晰定義了產(chǎn)品結(jié)構(gòu)的樹(shù)形關(guān)系。 但它也有以下缺點(diǎn)： ( 1 ) 容易產(chǎn)生b o m 表中的層次循環(huán)錯(cuò)誤： ( 2 ) b o m 生成速度比多層b o m 要慢些。 中山大學(xué)碩士學(xué)位論文 三、復(fù)合式b o m 結(jié)構(gòu)( c b o m ) 復(fù)合式b o m 結(jié)構(gòu)( c b o m ) 1 3 】綜合了多層b 洲和單層b o m 的構(gòu)造方法，用以平衡 b o m 數(shù)據(jù)維護(hù)和運(yùn)行效率的問(wèn)題。在結(jié)構(gòu)上，c b o m 和s b o m 類(lèi)似，仍然采用“單 父一單子”的數(shù)據(jù)結(jié)構(gòu)，只是在每個(gè)子件的表示中又加上了所對(duì)應(yīng)的最終產(chǎn)品。 復(fù)合式b o m 在構(gòu)造時(shí)采用單層b o m 的構(gòu)造方法，而在b o m 分解時(shí)，又與多層b o m 的方法相同，其實(shí)質(zhì)就是通過(guò)增加數(shù)據(jù)冗余項(xiàng)來(lái)綜合s b o m 和m b o m 的構(gòu)造方法， 在形式上同時(shí)具有設(shè)計(jì)用b o m 和生產(chǎn)用b o m 的特點(diǎn)，滿足了在一個(gè)系統(tǒng)中只使用 一套b o m 的基本思想。但是，由于復(fù)合式b o m 存在著數(shù)據(jù)冗余，數(shù)據(jù)更新的一致 性問(wèn)題仍然存在。 由于計(jì)算機(jī)硬件技術(shù)的飛速發(fā)展和c p u 運(yùn)算速度的不斷提高，b o m 的分解速 度和運(yùn)行效率在大多數(shù)情形下已不是瓶頸問(wèn)題。因此，目前大多數(shù)b o m 結(jié)構(gòu)設(shè)計(jì) 依然是以單層b o m 結(jié)構(gòu)為主。 2 1 2b o m 的變型設(shè)計(jì)問(wèn)題 激烈的市場(chǎng)競(jìng)爭(zhēng)迫使企業(yè)的經(jīng)營(yíng)管理強(qiáng)調(diào)“以客戶為中心”，提供“個(gè)性化 服務(wù)”，以期實(shí)現(xiàn)滿足客戶個(gè)性化條件下的產(chǎn)品規(guī)模生產(chǎn)，實(shí)現(xiàn)產(chǎn)品定制，從而 在降低成本前提下提高企業(yè)的競(jìng)爭(zhēng)力，這就提出了b o m 的變型設(shè)計(jì)問(wèn)題。 根據(jù)設(shè)計(jì)活動(dòng)中的創(chuàng)造性程度，設(shè)計(jì)行為可以分成原始的創(chuàng)新設(shè)計(jì)、適應(yīng)性 設(shè)計(jì)和變型設(shè)計(jì)，其中變型設(shè)計(jì)是指在產(chǎn)品的系統(tǒng)工作原理、功能和結(jié)構(gòu)不變的 情況下，在預(yù)定選定的范圍內(nèi)，對(duì)現(xiàn)有產(chǎn)品的局部組成部件的屬性變更。如同樣 一種尺寸的自行車(chē)，除了顏色不同，其余設(shè)計(jì)都相同，對(duì)客戶的這一需求，映射 到自行車(chē)這種產(chǎn)品，體現(xiàn)在其顏色屬性的變化【2 1 。在這類(lèi)設(shè)計(jì)中，新產(chǎn)品的定義 完全可以從已有的設(shè)計(jì)模板獲取。隨著大批量生產(chǎn)模式轉(zhuǎn)向小批量生產(chǎn)模式甚至 單間生產(chǎn)模式，此時(shí)，變型設(shè)計(jì)在設(shè)計(jì)活動(dòng)中占有主導(dǎo)地位。 如果b o m 管理的方式是為每種產(chǎn)品建立一個(gè)這b o m 表，這種方式在面向客戶 需求的變型設(shè)計(jì)中，倘若要將類(lèi)似產(chǎn)品的所有明細(xì)表的全部信息儲(chǔ)存起來(lái)，數(shù)據(jù) 量就會(huì)猛增。例如，一輛完整的自行車(chē)由1 0 0 0 多個(gè)零件組成，只要其中個(gè)零 件的尺寸、顏色、材料及規(guī)格等不一樣，該自行車(chē)作為產(chǎn)品的明細(xì)表就與其他產(chǎn) 品的明細(xì)表不同，如果有5 種用戶選擇的參數(shù)，如顏色( 1 0 種) 、車(chē)輪大小( 3 種) 、 9 第二章基于與或樹(shù)的b o m 設(shè)計(jì) 車(chē)身大小( 3 種) 、車(chē)鈴式樣( 3 種) 、車(chē)座式樣( 5 種) 、腳踏式樣( 2 種) ，就可能產(chǎn) 生出l o 3 3 3 5 木2 = 2 7 0 0 種不同的選擇方案，如果新增一種自行車(chē)的速度是否為 變速的屬性，那么將產(chǎn)生種不同的2 7 0 0 術(shù)2 = 5 4 0 0 種不同的選擇方案。雖然在實(shí)際 的選擇中不是所有的組合都會(huì)被選中，但如果每使用一種變型產(chǎn)品就存儲(chǔ)一種獨(dú) 立的b o m ，只要多考慮幾種變型方式就會(huì)使b o m 文檔出現(xiàn)數(shù)據(jù)爆炸現(xiàn)象【3 4 】。 2 1 3b o m 的變型設(shè)計(jì)要求 既然客戶個(gè)性化的大規(guī)模定制已經(jīng)成為企業(yè)面臨的一項(xiàng)重要課題，產(chǎn)品供應(yīng) 方與消費(fèi)者之間也正在建立這么一種新型的關(guān)系，那么企業(yè)產(chǎn)品設(shè)計(jì)和生產(chǎn)組織 都必須適應(yīng)這種變化，這就對(duì)b o m 的構(gòu)造提出了更高的柔性要求，主要體現(xiàn)在如 下幾個(gè)方面： ( 1 ) 客戶定制的快速響應(yīng)； ( 2 ) 網(wǎng)上定制的可支持性； ( 3 ) 較高的運(yùn)作速度： ( 4 ) 產(chǎn)品結(jié)構(gòu)的直觀化、形象化； ( 5 ) 產(chǎn)品設(shè)計(jì)的客戶需求化。 然而，目前在作b o m 的柔性設(shè)計(jì)時(shí)，通常都采用規(guī)劃性b 刪( p l a n n i n gb o m ) 的形式，即將特性件和可選件都建立在該產(chǎn)品的b o m 中，并依虛擬件來(lái)計(jì)算各種 特性件、選用件的供應(yīng)計(jì)劃3 5 l 。這種方法在實(shí)現(xiàn)上首先利用虛擬件定義各主料和 特性件( 可替換件) 、選用件的適當(dāng)組合；然后按照定義的規(guī)則以及可選件表、 可替換件表中的內(nèi)容，系統(tǒng)自動(dòng)在基本物料表中選擇符合條件的零部件來(lái)替換產(chǎn) 品結(jié)構(gòu)上的節(jié)點(diǎn)，形成產(chǎn)品結(jié)構(gòu)樹(shù)。然而，利用這種規(guī)劃性b 伽作產(chǎn)品的變型設(shè) 計(jì)時(shí)，存在以下問(wèn)題： ( 1 ) 沒(méi)有一種清晰、直觀的數(shù)據(jù)結(jié)構(gòu)反映產(chǎn)品結(jié)構(gòu)中替換件或可選件的特性 及其組合關(guān)系，具體表現(xiàn)為在產(chǎn)品結(jié)構(gòu)樹(shù)中難以反映替換件或可選件的組成； ( 2 ) 在規(guī)劃b o m 設(shè)計(jì)時(shí)，需要定義基本物料( 零件) 表、特性件表、可選件 表等來(lái)區(qū)分不同的零部件屬性1 4 】，產(chǎn)品的零部件缺少統(tǒng)一的表示形式和存儲(chǔ)結(jié) 構(gòu)，造成了對(duì)b o m 表中產(chǎn)品結(jié)構(gòu)或零部件關(guān)系修改的困難，且容易導(dǎo)致不一致性； ( 3 ) 相關(guān)的產(chǎn)品變型特性難以用形式化的語(yǔ)言描述。 1 0 中山大學(xué)碩士學(xué)位論文 顯然，利用規(guī)劃性b o m 表示變型設(shè)計(jì)的方法與上面提到的新型產(chǎn)品定制的柔 性要求還有一定的距離。更重要的是，為了適應(yīng)快速的市場(chǎng)變化和需求，產(chǎn)品結(jié) 構(gòu)在面向企業(yè)的任務(wù)定制方面的要求也愈加迫切。例如，一件產(chǎn)品或半成品可以 由不同廠家或型號(hào)的零部件的不同組合構(gòu)成，如何根據(jù)產(chǎn)品結(jié)構(gòu)提取出成本最低 的零部件組合。又譬如，不同零部件的采購(gòu)周期、裝配件的生產(chǎn)周期都各不相同， 如何從中選擇出限定工期內(nèi)可完成的產(chǎn)品結(jié)構(gòu)類(lèi)似的需求還有很多。 鑒于這種需求，針對(duì)b o m 表示的產(chǎn)品結(jié)構(gòu)柔性的提高，下一節(jié)本文將開(kāi)始闡 述一種基于與或樹(shù)模型的b o m 結(jié)構(gòu)。 2 2 基于與或樹(shù)的b o m 結(jié)構(gòu) 2 2 1 產(chǎn)品結(jié)構(gòu)與或樹(shù) 與或樹(shù)【3 6 1 是人工智能中用于表示問(wèn)題歸約及其求解過(guò)程的一種方法，它把復(fù) 雜的多階問(wèn)題分解成多個(gè)子問(wèn)題。下面利用與或樹(shù)的形式來(lái)表示產(chǎn)品的結(jié)構(gòu)組 成，使其可以表示產(chǎn)品部件的替換關(guān)系和可選關(guān)系。假設(shè)產(chǎn)品p 可由部件p 。、p ： 組成，那么他們之間存在下面兩種基本關(guān)系： ( 1 ) 產(chǎn)品p 由兩個(gè)子部件p t 、p 2 的組合制造而成，則稱(chēng)p 。和p ：之間存在“與” 關(guān)系，如圖2 1 所示的“與”樹(shù)的形式，用邏輯公式可表示為：p p ，八p ：。 ( 2 ) 產(chǎn)品p 可由子部件p t 和p ：中的其中一個(gè)制造而成，則稱(chēng)p 。和p ：之間存在 “或”關(guān)系( 用圓弧線連接) ，如圖2 2 所示的“或”樹(shù)形式，用邏輯公式可表 示為p ，( p - 八一p 2 ) v ( 呻i 八p 2 ) 。 p ，p p i ap 1 -。p 2 圖2 1 與樹(shù)圖2 2 或樹(shù) 定義2 1 ( 產(chǎn)品與或樹(shù)) 本文定義的產(chǎn)品結(jié)構(gòu)與或樹(shù)是一個(gè)六元組g _ ( 0 ，a ，t n ，e ，r 0 ) 。其中0 是“或”節(jié)點(diǎn)的兄弟關(guān)系集合；a 是“與”節(jié)點(diǎn)的兄弟關(guān)系集合； 1 與一般的與或樹(shù)定義不同，這里“或”關(guān)系是n 中選一的選擇關(guān)系，為了突出這種部件閫的替換選擇關(guān) 系用圓弧線將相關(guān)的“或”結(jié)點(diǎn)連接 第二章基于與或樹(shù)的b o m 設(shè)計(jì) t 是終端葉節(jié)點(diǎn)集合，n 是非終端葉節(jié)點(diǎn)集合；e 是樹(shù)的邊集即n ( t u n ) 的子集， 其元素是由父節(jié)點(diǎn)指向子節(jié)點(diǎn)的有向??；r 0 是樹(shù)g 的根節(jié)點(diǎn)：若邊含權(quán)值，則從節(jié) 點(diǎn)n 到節(jié)點(diǎn)m 的邊代價(jià)記為c o s t ( n ，m ) 。 顯然，對(duì)一棵產(chǎn)品結(jié)構(gòu)與或樹(shù)而言，根節(jié)點(diǎn)r o 表示用戶感興趣的對(duì)象如一個(gè)產(chǎn) 品等。“或”節(jié)點(diǎn)集合o 代表可替換件集；“與”節(jié)點(diǎn)集合a 代表必選件集；終端 葉節(jié)點(diǎn)t 代表原材料或零件，是產(chǎn)品的最終組成成分；非終端葉節(jié)點(diǎn)n 表示概念 件( 或虛擬件) ，代表產(chǎn)品的半成品和裝配件。邊集e 表示產(chǎn)品結(jié)構(gòu)中的父項(xiàng)子項(xiàng) 關(guān)系，即父項(xiàng)部件由哪些子項(xiàng)部件直接組成。顯然，產(chǎn)品與或樹(shù)本身是一種遞歸 定義，通過(guò)定義不同的與或關(guān)系，可以表示出產(chǎn)品部件的不同組合結(jié)構(gòu)。 例2 1 產(chǎn)品a 由裝配件b 和裝配件c 所組成，而裝配 ： 件c 既可由零件d 和零件e 組合而成。又可以由零件d 和 。 、b。c f 組合而成，即o ；“e ，b ) ，a = b ，c ) ， d ) ) ，對(duì)應(yīng)的邏輯 l 公式為 a b c ，c d ( ( e 一f ) v ( f 飛) ) ) 。這種產(chǎn)品結(jié) 1 d ，ef 構(gòu)就對(duì)應(yīng)于圖2 3 所示的與或樹(shù)。 圖2 3 產(chǎn)品與或樹(shù)示例 定義2 2 ( 子與或樹(shù)) 若與或樹(shù)g = ( o7 ，a ，t ，n ：e ，r 0 ) 是g = ( 0 ，a ，t ，n ，e ，r o ) 的一個(gè)子樹(shù)，可表示為g ，c g ，則g 對(duì)以下條件均成立。 ( 1 ) v o o 3 0 o 有o o ，且va ，a ，3 a a 有一2 a ； ( 2 ) t 三t ，n 三n ，e e ，且r o kr o ： ( 3 ) v n n ，則可，m xl ( n ，x ) e e 即對(duì)n 在g 中的所有孩子節(jié)點(diǎn)m ，同時(shí)滿足下 面兩個(gè)條件： ( i )若3 a e a ，使得m o 【，則v k a ，有( n ，k ) e f ； ( i i ) 若j p e o ，使得m p 。貝歸k p ，有( n ，k ) e 。 從以上定義可知，子樹(shù)關(guān)系c ”是一種偏序關(guān)系。若g 7 是g 的子與或樹(shù)，則g 和g 是同構(gòu)的，且g 必須包含g 中所有的“與”關(guān)系節(jié)點(diǎn)，而位于g 中同一“或” 關(guān)系集的節(jié)點(diǎn)，g 應(yīng)至少包含一個(gè)。對(duì)產(chǎn)品結(jié)構(gòu)與或樹(shù)而言，它的一棵子與或樹(shù) 就對(duì)應(yīng)于一個(gè)有效的產(chǎn)品結(jié)構(gòu)，因?yàn)槠浒诉@個(gè)產(chǎn)品的所有必要成分。本質(zhì)上， 產(chǎn)品結(jié)構(gòu)與或樹(shù)在語(yǔ)義上擴(kuò)展了傳統(tǒng)上的產(chǎn)品結(jié)構(gòu)樹(shù)，增加了在孩子分支上的選 擇語(yǔ)義，若一棵產(chǎn)品結(jié)構(gòu)與或樹(shù)不包含任何“或”關(guān)系，其就相當(dāng)于一棵傳統(tǒng)意 義上的產(chǎn)品結(jié)構(gòu)樹(shù)。 1 2 中山大學(xué)碩士學(xué)位論文 例2 2 例2 1 中的與或樹(shù)( 圖2 3 ) 就包含了如圖2 4 所示的兩個(gè)子與或樹(shù)。 圖2 4 例2 1 的子與或樹(shù) 定義2 3 ( 極小子與或樹(shù)) 若與或樹(shù)g ，c g ，且不存在g ，cg ，則稱(chēng)g 7 為g 的 極小子樹(shù)。 顯然，極小子與或樹(shù)對(duì)應(yīng)的是產(chǎn)品的極小產(chǎn)品結(jié)構(gòu)即最基本的組成成分。 棵與或樹(shù)可能有多棵極小予樹(shù)，類(lèi)似地，一個(gè)產(chǎn)品也可能有多個(gè)基本組成結(jié)構(gòu)。 根據(jù)定義2 2 和2 3 ，也容易有以下推論。 推論2 1 極小子與或樹(shù)必定不包含“或”關(guān)系節(jié)點(diǎn)即0 = 由。 由定義可知，若存在“或”關(guān)系節(jié)點(diǎn)，“或”關(guān)系節(jié)點(diǎn)集合應(yīng)至少包含兩個(gè) 節(jié)點(diǎn)，則刪去其中一個(gè)節(jié)點(diǎn)所成的與或樹(shù)也必定是原與或樹(shù)的予樹(shù)。因此，極小 子與或樹(shù)的“或”關(guān)系節(jié)點(diǎn)集必定為空。 定理2 1 一個(gè)產(chǎn)品的所有的變型設(shè)計(jì)結(jié)構(gòu)都可以用棵產(chǎn)品結(jié)構(gòu)與或樹(shù)所 表示。( 完備性) 證明：用數(shù)學(xué)歸納法，驗(yàn)證任意層次的產(chǎn)品結(jié)構(gòu)均可由與或樹(shù)表示。 ( 1 ) 當(dāng)產(chǎn)品結(jié)構(gòu)只有1 層時(shí)，顯然對(duì)應(yīng)于只有一個(gè)根節(jié)點(diǎn)的產(chǎn)品結(jié)構(gòu)與或樹(shù)。 ( 2 ) 假設(shè)當(dāng)產(chǎn)品的組成結(jié)構(gòu)為k ( k 1 ) 層時(shí)，均可由一棵產(chǎn)品結(jié)構(gòu)與或樹(shù)表示。 那么當(dāng)產(chǎn)品組成結(jié)構(gòu)為k + l 層時(shí)，由假設(shè)可知，前k 層的產(chǎn)品結(jié)構(gòu)均可表示 為一棵產(chǎn)品結(jié)構(gòu)與或樹(shù)。在此基礎(chǔ)上，我們構(gòu)造k + l 層產(chǎn)品結(jié)構(gòu)的與或樹(shù)： 不失一般性地，我們假設(shè)a 為其第k 部件中的任意一個(gè)，若a 不由任何一個(gè) k + 1 層的子部件所構(gòu)成，則a 作為與或樹(shù)的葉子節(jié)點(diǎn)。若a 的組成包含k + l 層的 子部件b ，而b 是屬于沒(méi)有可替換件的必選件，則在與或樹(shù)增加一個(gè)“與”節(jié)點(diǎn) b ，其父親節(jié)點(diǎn)為a ；如果b 有若干可替換件，則這些可替換件和b 一起構(gòu)成一 個(gè)“或”節(jié)點(diǎn)集，其父親節(jié)點(diǎn)同樣為a ；如果b 是可選件，則b 可與“空”節(jié)點(diǎn) 一起構(gòu)成一個(gè)父親節(jié)點(diǎn)為a 的“或”節(jié)點(diǎn)集。 因此，k 十1 層的產(chǎn)品結(jié)構(gòu)就可以由構(gòu)成的產(chǎn)品結(jié)構(gòu)與或樹(shù)所表示。 ，c a ， b c a b 第二章基于與或樹(shù)的b o m 設(shè)計(jì) 2 2 2b o m 表的數(shù)據(jù)設(shè)計(jì) 產(chǎn)品結(jié)構(gòu)與或樹(shù)可以看作由結(jié)構(gòu)相似的產(chǎn)品結(jié)構(gòu)樹(shù)所耦合而成，其實(shí)質(zhì)是將 相同的裝配結(jié)構(gòu)抽取出來(lái)，用相應(yīng)的與或關(guān)系來(lái)表示不同的變型成分。從數(shù)據(jù)庫(kù) 設(shè)計(jì)的角度，可以把基本( 必選件) 表、可替換件表、可選件表( 可選件可通過(guò)部 件與一個(gè)空節(jié)點(diǎn)存在“或”關(guān)系來(lái)表示) 等統(tǒng)一到同種b o m 表結(jié)構(gòu)，從而可以 方便的對(duì)產(chǎn)品結(jié)構(gòu)進(jìn)行修改和定制，減少b 叫表設(shè)計(jì)的復(fù)雜度和所需的存儲(chǔ)空 間。下面表2 3 和表2 4 就描述了一種基于與或樹(shù)b o m 的基本結(jié)構(gòu)： 表2 3 與或樹(shù)節(jié)點(diǎn)表 名稱(chēng)類(lèi)型含義 t 琳i d i m e g e r所屬樹(shù)標(biāo)識(shí) n o d e i d i n t e g e r 節(jié)點(diǎn)標(biāo)識(shí) p a r e n t i d i n t e g e r 父節(jié)點(diǎn)標(biāo)識(shí) r e l a t i o n i d i n 魄e r 所屬關(guān)系標(biāo)識(shí) c o d ec i l a r 對(duì)應(yīng)部件代碼 表2 4 部件屬性表 名稱(chēng)類(lèi)型含義 c o d ec h a r 部件代碼 n 鋤ec h a r 部件名稱(chēng) v b r s i o nc h a r 部件版本 t y p e c h a r 部件類(lèi)型 u n i tc h a r 計(jì)量單位 a m o 眥nn u m e c 單位用量 其中，與或樹(shù)節(jié)點(diǎn)表反映的是產(chǎn)品與或樹(shù)的結(jié)構(gòu)，主鍵是t r e e i d 和n o d e i d ， 樹(shù)標(biāo)識(shí)( t r e e i d ) 是節(jié)點(diǎn)所屬與或樹(shù)的唯一標(biāo)識(shí)，節(jié)點(diǎn)標(biāo)志( n o d e i d ) 是對(duì)應(yīng)節(jié)點(diǎn)的 唯一標(biāo)識(shí)。父節(jié)點(diǎn)標(biāo)識(shí)( p a r e n t i d ) 指向當(dāng)前節(jié)點(diǎn)的父親節(jié)點(diǎn)；關(guān)系標(biāo)識(shí) ( r e l a t i o n i d ) 表示節(jié)點(diǎn)間的“與或”關(guān)系，屬于同一“或”關(guān)系集合的節(jié)點(diǎn)屬 于同一關(guān)系( 即r e l a t i o n i d 的值相同) ，不同的“與”節(jié)點(diǎn)及不同的“或”關(guān)系 節(jié)點(diǎn)集合以不同的關(guān)系( 即不同的r e l a t i o n i d ) 相區(qū)別。例如圖2 3 所示的產(chǎn) 品結(jié)構(gòu)，節(jié)點(diǎn)e 和f 的關(guān)系標(biāo)識(shí)r e l a t i o n i d 應(yīng)相同而e 和d 的關(guān)系標(biāo)識(shí)必須不 同；部件代碼( c o d e ) 是外鍵，是該節(jié)點(diǎn)所對(duì)應(yīng)的產(chǎn)品部件的編號(hào)。 當(dāng)需要修改產(chǎn)品的配置結(jié)構(gòu)時(shí)，只需要修改反映結(jié)構(gòu)關(guān)系的與或樹(shù)節(jié)點(diǎn)表， 中山大學(xué)碩士學(xué)位論文 更改部件屬性則只需修改部件屬性表及節(jié)點(diǎn)表與屬性表問(wèn)的對(duì)應(yīng)關(guān)系。整個(gè)產(chǎn)品 的結(jié)構(gòu)可由通過(guò)部件代碼關(guān)聯(lián)節(jié)點(diǎn)表和屬性表所得到的視圖來(lái)反映，完整的產(chǎn)品 結(jié)構(gòu)關(guān)系可以通過(guò)遞歸的方法獲得，具體可參考文獻(xiàn)f 7 】。 與或樹(shù)結(jié)構(gòu)在程序設(shè)計(jì)語(yǔ)言中可有多種表示方法，下面就是其中一種： s t r u c ta o _ n o d e i n tn r e l a t i o n ： 節(jié)點(diǎn)所屬的關(guān)系 a o _ n o d 黔p p a r e n t ：父親節(jié)點(diǎn)的指針 a o _ n o d e 木p f i r s t c h i l d ； 第一個(gè)孩子節(jié)點(diǎn)的指針 a 0 _ n o d 脅p n e x t b r o t h e r ：鄰近的兄弟節(jié)點(diǎn)的指針 2 3 面向任務(wù)的b o m 配置算法 2 3 1 基本定義和公式 產(chǎn)品與或樹(shù)可看作一個(gè)超圖，節(jié)點(diǎn)問(wèn)用超弧線( 或連接符) 來(lái)連接，求與或 子樹(shù)的過(guò)程可等效為求對(duì)應(yīng)與或圖解圖的過(guò)程。如果給與或樹(shù)的每條邊權(quán)值賦予 一定的意義如生產(chǎn)成本、生產(chǎn)周期等，那么類(lèi)似于成本最低、工期最短等面 向任務(wù)的產(chǎn)品結(jié)構(gòu)配囂可看作為尋找權(quán)值總和最小的子與或樹(shù)( 解圖) 。 在搜索子與或樹(shù)的過(guò)程中，還要進(jìn)行代價(jià)值的計(jì)算，設(shè)子樹(shù)g 中節(jié)點(diǎn)n 的代 價(jià)值為k ( n ，g ) ，則可遞歸計(jì)算如下： ( 1 ) 若n t 即n 為終端節(jié)點(diǎn)，則k ( n ，g ) = o ： ( 2 ) 若n n 即n 有連接符指向其孩子節(jié)點(diǎn) n l ，n 2 ，n 。) ，則 k ( n ，g ) = c o s t ( n ，n 。) + k ( n ；，g ) i _ 1i = l 其中，c o s t ( n ，n i ) 為從n 到n i 的邊的權(quán)值，實(shí)際意義為生產(chǎn)部件n 所需耗費(fèi)子 部件n ，的代價(jià)，即成本或工期等。 定義2 4 ( 最佳子與或樹(shù)) 根節(jié)點(diǎn)其有最小代價(jià)值的子與或樹(shù)我們稱(chēng)為最佳 子與或樹(shù)，采用g 表示。 易知，若所有權(quán)值為正的話，g 必定為極小子與或樹(shù)，g + 的代價(jià)值稱(chēng)為g 第二章基于與或樹(shù)的b o m 設(shè)計(jì) 的最小代價(jià)值，表示為h + ( g ) ?？紤]權(quán)值為正的情況，由定義可知，最佳與或予 樹(shù)必定由全部“與”節(jié)點(diǎn)及“或”關(guān)系集合中各個(gè)代價(jià)值最小的“或”節(jié)點(diǎn)所組 成。設(shè)以n 為根節(jié)點(diǎn)的與或樹(shù)的最小代價(jià)值為h ( n ) ，則有 ( 1 ) 若n t 即n 沒(méi)孩子節(jié)點(diǎn)，則h ( n 1 = 0 ： ( 2 ) 若n n ，設(shè)節(jié)點(diǎn)n 的“與”關(guān)系的孩子節(jié)點(diǎn)集合為 a l a 2 ，a p a ，所 有“或”關(guān)系的孩子節(jié)點(diǎn)集合為 o i i ，0 1 2 ，o m l o ， 0 2 i ，0 2 2 ，o m 2 0 ， o q l ，o q 2 ，o m q o ，則