1、一種改良的BOM展開及低層碼生成算法一種改良的BOM展開及低層碼生成算法余銳林吳順祥(廈門大學自動化系,廈門361005)摘要物料清單(BOM)和低層碼(LLC)是MRP系統的關鍵輸入,尋找一種高效的BOM遍歷和低層碼生成算法,是提高MRP方案編制效率的關鍵.傳統的單層BOM存儲格式描述的產品結構,通常采用遞歸算法進行BOM展開,但是遞歸算法的效率受到產品樹層數的限制.論文基于SQLServer存儲過程,libel建一個臨時堆棧表,使得BOM的遍歷算法用一個循環就得以實現.實踐證明,隨著產品結構復雜度增加,該算法相對于遞歸算法更顯示出其優越性.關鍵詞主生產方案MRP物料清單低層碼存儲過程文章編

2、號10028331一(2005)27010003文獻標識碼A中圖分類號TP311AKindofImprovedAlgorithmfortheBOMExpandednessandLLCCalculationYuRIliIinWuShunxiang(DepartmentofAutomation,XiamenUniversity,Xiamen361005)Abstract:BillofMaterial(BOM)andLowLevelCode(LLC)areimportantinputsoftIleMRPsystem,todesignaneffectivealgorithmfortheBOMexpan

3、dednessandLLCcalculationisakeythingtopromotetheefficiencyoftheMRPsystem.Thetraditionalproductstructuredescribedbytheformofsinglelevelb0mmaynormallybeexpandedwithrecursivealgorithmwhoseefficiencyisrestrictedbythelevelsoftheproductstructuretree.Thispaperpresents,byusingatempstacktable,aneffectivestore

4、d-procedurebasedalgorithmwhichisrealizedthroughacycle,nowitisprovedthatitissuperiortotherecursivealgorithm,especiallywhentheproductstructureisverycomplex.Keywords:MasterProductionSchedule(MPS),MaterialRequirementPlanning(MRP),BillofMaterial(BOM),LOwLevelCode(LLC),storedprocedure1引言物料需求方案(MaterialReq

5、uirementPlanning,簡稱MRP)是2O世紀7O年代提出的.目前世界上普遍采用的一種企業管理模式.MRP的根本原理是根據需求和預測來測定未來物料供給和生產方案,提供物料需求的準確時間和數量.物料需求方案MRP是一種優先方案的方法.它根據產品結構的具體特征.將主生產方案具體分解成零部件生產進度方案和原材料,外購件的采購進度方案.確定自制件的投產日期與完工日期,原材料,外購件的訂貨采購和入庫的日期.在MRP系統里,物料清單(BillofMaterial,BOM)是相當關鍵的根底數據,是系統的主要輸入之一.它是用來描述產品組成結構的.即描述了制造產品所需要的原材料與零件,部件,總裝件之間

6、的附屬關系.在物料清單中,存在著同一種物料項同時出現在產品不同層次的現象.這種工程稱為多層次通用件.一個多層次通用件可能出現在同一產品的不同層次上,也可能出現在不同產品的不同層次上.于是.在計算凈需求時不得不重新計算和處理不同層次上的總需求量,這將極大地影響MRP工作效率.目前.一種有效的解決方法就是引入最低層代碼.叫低層碼(LOwLevelCode.U)1.它是MRP運算的依據,有了它,我們就能控制MRP方案編制的順序,使得各種物料的MRP運算不重不漏,提高了系統的運行效率.文獻【4】采用傳統的單層BOM存儲格式描述產品結構,并采用遞歸算法進行BOM展開.而遞歸算法的效率卻受到產品結構樹級數

7、的限制.隨著產品結構復雜度增加,這種算法的效率明顯下降.本文通過創立一個臨時堆棧表.使得BOM的遍歷算法用一個循環就得以實現;其次,由于該算法是基于SQLServer存儲過程,在創立時即在效勞器上進行編譯.所以執行起來相當快,特別當需要應用該算法對所有產品結構樹進行遍歷時.由于只編譯一次.其性能的優越性更能得到表達.有了該遍歷算法,我們就可以對所有產品BOM進行遍歷.利用預處理的結果,只需一個SQL語句就可以方便計算各種物料的低層碼.2物料清單(BOM)2.1產品結構樹與物料清單一個產品由哪些物料(標準件,零部件,原材料)組成,以及這些物料在組成時的附屬關系,數量關系(也就是產品結構),是進行

8、MRP運算時首先必須明確的內容.產品結構樹直觀地表達了成品,標準件,零部件,原材料等物料之間的附屬關系和數量構成關系,為了便于計算機識別.把用圖示表達的產品結構轉化成某種數據格式,這種以數據格式來描述產品結構的文件就是物料清單,也即BOM是定義產品結構的技術文件,因此它又稱為產品結構樹,產品結構表或BOM表【l】.基金工程:福建省教育委員會科技工程(編號:JA022239);廈門市重點科技工程(編號:3502E20031056)作者簡介:余銳林(1979一),男,廣東汕頭人,碩士研究生,主要研究領域為智能信息系統,數據挖掘.吳順祥,男,博士,副教授,主要研究領域為數據庫系統,數據倉庫,數據挖掘

9、,智能信息系統,人工智能與機器學習.1002005.27計算機工程與應用圖1所示是一棵4級的X產品結構樹,其中,大寫字母表示加工件.小寫字母表示采購件,括號中數字表示父項與子項之間的數量關系(父項對子項的用量因子).由圖1,可以清晰地看到:產品X由6個h,3個A和2個D組成.而加工件A那么由4個e和2個b組成,以此類推.田第-3-層r一1一曲旦旦:由豳囪囪第層囪回一一個產品通常具有多層的結構.通過把多層的結構轉化成多個單層的結構,可以簡化BOM的存儲格式.一種常見的做法是:在B0M中,每一個關系都定義成父項,子項的形式.并給出父項對附屬子項的用量因子.同時,一個關系中的某個附屬子項也可以在其它

10、關系中充當父項,這樣一來.關于一個產品的所有父項/子項關系的集合.就完整地表達了產品的結構.父項代碼子項代碼父項對于項根據應用需要的用量因子的擴展信息圖2B0M的記錄結構在圖2的記錄結構模型中.有關物料的詳細信息獨立儲存在物料主文件中,而在BOM表中,父項和子項那么通過物料編碼來記錄,該編碼與物料主文件中的物料記錄相對應.假設圖1是以物料編碼表示的產品結構.那么,表達產品X結構的物料清單如下:表I產品X的物料清單(BOM)2.2BOM的展開在上面存儲格式的BOM表中,每條記錄只表示了父項與子項之間的附屬關系和數量關系,并沒有記錄一種物料相對于某個最終產品所處的層次.為了得到物料低層碼.我們必須

11、知道該物料在各個產品結構樹中相對于根節點所處的層次.通過對各個產品結構樹向下遍歷,求出各節點相對于根節點所處的層次,就可以實現.為此,我們給出另外一種記錄結構.用來存儲向下遍歷產品結構樹過程中生成的信息.相應地,采用類似深度優先遍歷算法可以得到產品X的B0M展開表如表2(表中記錄的先后次序表示了節點遍歷的先后順序.注意同一層的各節點遍歷順序不分先后):最終產品父項代碼子項代碼父項對于項子項在最終根據應用需要的用量因子產品結構樹的擴展信息中所處層次圖3BOM展開表的記錄結構表2產品X的BOM展開表(深度優先)3物料低層碼(LLC)3.1根本概念在產品結構樹中,存在著同一物料同時出現于結構樹中不同

12、層次的現象,這種物料稱為多層次通用件.一個物料不僅可以出現在同一種產品的不同層次.也可以存在于不同產品的不同層次上.如果缺乏有效的方法控制各種物料的方案優先順序,那么,就可能出現這種情況,當要計算某個時段內某個物料的總毛需求量的時候,發現該物料的上級物料在該時段內的計劃尚未形成,這樣導致該物料的方案無法繼續下去.而必須回溯到尚未方案的上級物料,而上級物料的方案編制過程.也可能會出現類似的情況,如果再加上時間維,問題將更為復雜,這導致MRP算法非常復雜,不僅容易出錯,且極大地影響MRP的運行效率.解決此問題的方法是引入最低層代碼.叫低層碼(wLevelCode),通過它就可以控制MRP方案的編制

13、順序,使得各物料的MRP運算不重不漏,提高了系統的效率.所謂低層碼是指某個物料在所有產品結構樹中所處的最低層次碼,每個物料有且僅有一個低層碼I1】.如圖1產品x的結構樹中,e分別處于產品結構樹的第2層和第3層.于是e的低層碼為3,而其它物料的低層碼分別與它們在該產品結構樹中所處的層次相同.如果還有其它產品使用材料e.且e處于該產品結構樹的第4層,那么e的低層碼就為4.3.2基于存儲過程的產品結構樹遍歷算法(深度優先)我們采用圖2和圖3所示的記錄結構作為BOM及其展開表的數據庫模式,分別記為:bd_bom(father.SOIl,dosage)和bd_bomExpand(TopItem.fath

14、er,son,dosage,leve1).下面給出基于SqlServer2000存儲過程的產品結構樹遍歷算法.該算法建立一個臨時堆棧來記錄當前正在處理的節點.它的本質是深度優先遍歷.算法1B0M展開算法CREATEPROCEDUREexpand(CWlophemvalhar(3O)as一創建存儲過程SETN0C0UNT0NDECLARElevelint,fatllelvatchar(30),donvarehar(30).dosagefloat(8)計算機工程與應用20o5.27101CREATETABLE#stack(fathervarchar(30),sonvarchar(30),dosag

15、efloat(8),levelint)DELETEFROMbd_BomExpandWHERETopltem=Topltem刪除該產品以前的遍歷信息.以免重復INSERTINTO#stackSELECTfather,son,dosage,1FR0Mbd_bomWHEREfather=-TopltemSEI正CTlevel=1WmLElevel>0一主循環開始BEGINIFEXISTS(SELECTFROM#stackWHERElevel=leve1)BEGINSELECTfather=father,son=son,dosage=dosageFROM#stackWHERElevel=

16、-levelINSERTINTObd_bomExpand(Topltem,Father,Son,Dosage,【Leve1)VALUES(Topltem,father,son,dosage,leve1)一從臨時堆棧中取出一個節點并把它保存到BOM展開表中DELIEFROM#stackWHERElevel=levelANDfather=fatherANDson=son一刪除當前節點信息.防止重復處理該節點INSERT#stackSELECTfather,son,dosage,level+1FROMbd_bomWHEREfather=son一把當前節點的所有子節點插入到堆棧中IFR0WC0UNIO

17、SELECTlevel=level+1一如果當前節點存在子節點.那么降到下一級繼續處理ENDELSESELECTlevel=level一1一如果當前層的所有節點都處理完畢.那么返回到上一層繼續處理END一主循環結束G0算法思路:輸入參數Topltem表示產品的根節點.使用的局部變量分別是level(用于跟蹤層次結構中的當前級別)和father,son,dosage(用于跟蹤主循環中的當前節點信息).SETNOCOUNTON語句防止輸出中夾雜每個SELECT產生的ROWCOUNT消息.使用產品結構樹的節點信息來創立和整理臨時表#stack.而level被設置為與之匹配.在上面的例如中,當leve

18、l大于0時,該過程執行以下步驟:(1)如果當前級別(leve1)的堆棧中有任何節點,該過程將選擇其中一個,并把相應信息用變量father,son,dosage記錄下來.(2)把該節點信息添加到BOM展開表bdbomExpand中.(3)從堆棧中刪除該節點以免重復處理它,然后將其所有子節點添加到堆棧的下一級(level+1)中.如果使用傳統的編程語言,就必須找到每個子節點并將其逐個添加到堆棧中.而使用TransactSQL,只用一個語句就能找到并添加所有的子節點,以免又使用一個嵌套循環.(4)如果當前節點有子節點(IFROWCOUNT>o).那么下降一級處理它們(level=lev

19、el+1);否那么,繼續在當前級別上10220o5.27計算機工程與應用處理.(5)最后,如果在當前級別的堆棧中沒有待處理的節點,那么返回到上一級(level=level一1),看上一級是否有待處理的節點.當再沒有上一級時,那么展開完畢.3-3低層碼生成對所有產品結構樹,應用算法1進行BOM展開.所產生的信息保存到以圖3這種結構儲存的產品BOM展開表.我們就可以輕易獲得物料的低層碼信息.例如:BOM展開結果如表2所示,要想得到某個物料的低層碼,我們只需要考慮Son和Level這兩列,通過在該表中對所有記錄掃描一遍.找出Son等于該物料編碼的所有記錄,那么這些記錄中Level的最大值就是該物料的

20、低層碼.例如要得到物料C的低層碼,根據表2知道,Son列的值等于C的記錄有兩條,而這兩條記錄的Level最大值為3,因此C的低層碼就是3.定義存放各物料低層碼的表模式如下:bd_lwLevelCode(ItemNo,l_owLevelCode),下面給出計算物料低層碼的算法:算法2低層碼生成算法CREATEPROCEDUREIlc_generate(Generate_TypeInt)asIFGenerate_Type=1BEGINDECLAREItemNovarchar(30)DECLAREFinishedProductsCURSORFORSELECTDISTINCThemNoFROMbd_g

21、oodsWHEREIs.PlanGts=l一從物料主文件中選出所有最終產品0PENFinishedProductsFETCHNEXTFROMFinishedProductsINT0ItemNoWHILEFETCHSTATUS=0一主循環開始BEGINEXECexpandItemNo一對每個最終產品.調用存儲過程expand進行BOM展開FETCHNEXTFROMFinishedProductsINTOIternNoEND一主循環結束CLOSEFinishedProductsDEAI工0CATEFinishedProductsENDDELETEFROMbdLowLevelCode一刪除記錄.防止

22、重復INSERTINTObdLowLevelCode(ItemNo,LowLevelCode)SELECTson,max(1eve1)FROMbd_bomexpandGROUPBYson一根據BOM展開表信息,計算所有物料的低層碼并保存G0算法思路:輸入參數CaenerateType表示低層碼生成方式,Gener-ate_Type=l表示重新生成,程序對每個最終產品,調用存儲過程expand進行BOM展開,然后再求物料低層碼.這種方式通常用于第一次計算物料低層碼,或者產品結構發生了變化,必須重新進行BOM展開;Generate_Type假設為其它值,那么直接利用已經存在的BOM展開表信息計算物

23、料低層碼.假設先前對每個最終產品均已經進行過BOM的展開,并且產品結構沒有發生任何變化,那么就以這種方式運行,以縮短運行時間.4結論低層碼生成算法的時間復雜度取決于BOM展開算法的時(下轉ll5頁)響應:HB順序碼0設備標識設備狀態傳輸協議,包含報頭和數據,協議格式如下:請求:PY順序碼0設備標識設備類型策略操作策略序列號,n響應:PY順序碼數據長度設備標識策略狀態,n策略數據4.2.3流量控制當設備及策略的種類和數量不斷增長時,對于一個集中管理系統必須要考慮流量控制問題,否那么會因端口擁塞,網絡負荷太大而導致系統運行緩慢甚至崩潰.基于此,本系統從網絡拓撲結構,數據包格式及策略等級等方面進行了

24、改良.(1)在網絡拓撲結構上采用了兩級控制機制:第l級,策略管理中心(PMC)管理多臺策略效勞器(PDP)和多個策略庫(PR),成為內容分布式結構,防止所有設備直接訪問PMC,有效地減輕了PMC端口負載;第2級,每個策略效勞器(PDP)可根據網絡負載情況,適時選擇更具效率的策略庫(PR)進行策略獲取.到達負載均衡的目的.其實現機制是對當前PR進行端13流量監視,當網絡負荷超過閾值時,轉向其他相鄰的PR請求策略效勞.這樣還有效解決了單一PR結構所無法解決的因設備故障致使策略效勞中斷的問題.(2)在PDP內部設計了增量策略分發模塊(DeltaPolicyDistribute).該模塊能夠以行為單位

25、進行策略比擬,生成增量策略數據,其功能與Unix系統中的diff和patch工具所實現的功能一致,用于對來自同一臺設備的策略請求根據策略變更情況適時采取增量式策略分發,減輕網絡傳輸數據量.起到流量抑制作用.(3)根據策略平安等級采取了智能流量調控技術.由于各種平安設備在網絡中擔負的作用不同,具有不同的資產價值.其設備策略配置信息也相應具有不同的平安等級.在PDP收到來自設備的并發策略請求時,會自動根據設備策略等級,當前端口負荷情況采用智能排隊技術,按照設備優先級順序,將優先級高的策略優先分發,優先級低的策略延遲分發.最大限度確保整體系統的平安.(4)采用專用策略文件模型.從PDP到PEP的策略

26、文件【或數據流的中間格式定義的BN設計如下:PolicySet:=(PolicyEntityRNPolicyRule)PolicyEntity:=PolicyEntityType:EntityPmpertiesPolicyEntityType:=“GWlCLEntityProperties:=PropertiesPolicyRule:=Ruletitle:RulePropertiesRNRuletitle:=“RSlPLlIKElIPSECRuleProperties:=PropertiesProperties:=(Name=Value),Name=Value*RN:換行回車符采用這一類LDA

27、P格式的主要原因,一是結構緊湊,數據量小,適合網絡傳輸和高頻并發訪問;二是在設備上不需要類似XML的解析模塊,能夠加速策略解析過程,提高設備執行效率.此外,在傳輸前還對策略內容事先做以預共享密鑰為密碼的zip壓縮,可以在原來根底上減少傳輸2,3的數據量.4.3仿真實驗結果本系統經內部局域網仿真實驗證明效果良好.用多臺PC機模擬1000臺防火墻并發訪問單臺PMC連接的5臺PDP和2臺PR,每臺防火墻每隔3min向所屬管理域PDP發送一次心跳請求,傳輸策略文件平均大小為7.5KB,經zip壓縮后平均大小為2.5KB.經168h不間斷運行,測得PMC峰值端口流量為2.5MB,s,平均流量為58KB/

28、s;PDP峰值端口流量為0|24MB,s,平均流量為32KB/s;PMC最大響應時間為140ms,平均響應時間為25ms;平均無故障時間MTBF為76h,平均修復時間MTTR為0.12rain.可用性為99.8%.5結論本文介紹了一種基于策略,面向網絡平安設備的管理系統,實現了策略的集中管理和分發,建立了整體平安策略管理架構,解決了策略自動分發,流量控制等問題.基于策略的管理是當今網絡管理的開展趨勢,也是今天業界所面臨的最復雜的問題之一.本系統的平安管理有待進一步完善.把設備聯動管理,風險分析機制融合進來.借助這些構件.客戶將建造全面的集中平安管理解決方案,而這些方案將最終支持更簡單和更自動化的網絡管理.(收稿日期:2005年5月)參考文獻1.RYavatkar,DPendarakis,RGuerin.AFrameworkforPolicy-basedAdmissionCon