一种改进的BOM展开及低层码生成算法

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