（計算機軟件與理論專業(yè)論文）基于與或樹的柔性bom結構及其自動診斷方法.pdf

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