（计算机软件与理论专业论文）基于bom的成本管理及其在制造业中的应用.pdf

大学硕 ：学位沧文 基于b o m 的成本管理及其在制造业中的应用 计算机软件与理论 硕士生：孙弘 指导老师：李磊教授 摘要 在企业的经营管理中，牛产成本的控制和管理是非常重要的。物料清单( b o m ) 是成本篱理的基础，研究基于b o m 的成本管理算法对于企业信息化有着重要意义。 在制造业中，分布最广泛的一类企业就是离散型制造企业，它包括机械加工、 汽车、医疗器械、家用电器等等。离散型制造业中的产品及其零部件、原材料之间 存在着清晰的层次和数量关系。另一个方面，不同产品的部分结构常常是相同的。 离散型企业的b o m 要充分体现出数据共享和集成。因为离散型制造业的重要性，本 文的研究丰要基于离散型制造业企业。 本文的r 丰要内容分为两大部分：通用算法和系统实现。 首先分析了成本b o m 的结构，介绍了成本符理的通用算法，丰要包括b o m 的 存储结构定义，成本计算和结果表示( 自定义报表) 的算法。 然后，利用这些算法，针对目前许多离散型制造企业信息化中存在的问题给出 了具体解决方案。详细描述了摹于b o m 的成本管理系统的架构、数据库设计、算法 框架。实践表明，该设计能够有效应用于企业的成本符理。 关键词：成本核算，b o m ，报表自定义 大学硕i 学位沦文 c o s tm a n a g e m e n tb a s e do nb o m 一- 。_ - _ 。_ ，_ _ _ _ _ - _ _ _ _ 。一 a n di t sa p p l i c a t i o ni ni n d u s t r y m a j o r c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：s u nh o n g s u p e r v i s o r ：p 船s s o rl il e i a b s t r a c t c o s tm a n a g e m e n ta n di t sc o n t r o li sv e r yi m p o r t a n ti nm a n a g e m e n to fm o d e m c o m p a n i e s b o m ，s h o r tf o rb i l lo f m a t e r i a l s ，i st h ef o u n d a t i o no f c o s tm a n a g e m e n t t h e r e s e a r c ho ft h ea l g o r i t h m sa b o u tc o s tm a n a g e m e n tb a s e do i lb o mi sb e n e f i c i a lt o e n t e r p r i s ei n f o r m a t i c s t h em o s tw i d e - d i s t r i b u t e dt y p eo f m a n u f a c t u r ei ni n d u s t r yi sd i s c r e t em a n u f a c t u r e ， i n c l u d i n gm a c h i n ep r o c e s s i n g ，v e h i c l e ，e l e c t r o n i ce q u i p m e n t s 1 i ld i s c r e t ee m e r p r i s e s ， t h e r ea r em a n yh i e r a r c h yr e l a t i o n sb e t w e e np r o d u c t s ，r a wm a t e r i a l sa n dp a r t s b e c a u s e t h ei m p o r t a n c eo f d i s c r e t em a n u f a c t u r e ，o u rr e s e a r c hm a i n l yb a s eo ni ti nt h i sp a p e r t h i sp a p e rc o n t a i n st w om a i np a r t s ：g e n e r a la l g o r i t h m sa b o u tc o s tm a n a g e m e n ta n d i t sr e a l i z a t i o n f i r s t , w ca n a l y z et h es t r u c t u r eo f b o m ；i n t r o d u c et h eg e n e r a la l g o r i t h m s ，i n c l u d i n g t h ea l g o r i t h m sa b o u ts t o r a g eo f b o m ，c o s tc a l c u l a t i o na n dr e s u l te x p r e s s i o n t h e n w ep r e s e n ts o l u t i o nt ot h ep r o b l e m se x i s t i n gi l lm a n yc o m p a n i e sb yu s i n g t h e s ea l g o r i t h m s w ed e s c r i b es y s t e mc o n s t r u c t i o n ，d a t a b a s ed e s i g na n da l g o r i t h mf r a m e o f c o s tm a n a g e m e n ts y s t e mb a s e do nb o m k e yw o r d s ：c o s tm a n a g e m e n t ，b o m ，s e l f - d e f i n e dr e p o r t s 1 1 引言 第1 章绪论 现代企业的经营臀弹是一个复杂的系统工程，从牛产角度来说，原材科采购、 库存箭理、产品的成本控制等方方面面的问题都需要以有效的手段进行符理。e r p 就是在这样的背景下应运面生。 e r p ( e n t e r p r i s er e s o u r c ep l a n n i n g ) ，即企业资源计划系统，是指建立在信息技术 基础上，以系统化的符理思想。为企业决策层及员工提供决策运行于段的管理平台。 e r p 系统集中信息技术与先进的销：理思想于一身，成为现代企业的运行模式，反映 时代对企业合理调配资源，最大化地创造社会财富的要求，成为企业在信息时代牛 存、发展的基石。 换言之，e r p 将企业内部所有资源整合在一起，对采购、牛产，成本、库存、分 销、运输、财务、入力资源进行规划，从而达到最佳资源组合，取得最佳效益。 e r p 的发展经过了四个辛要阶段： ( 1 ) 六十年代的时段m r p ( m a t e r i a lr e q u i r e m e n tp l a n n i n g ，物料需求计划) 。此 时m r p 的基本任务是：( a ) 从最终产品的牛产计划导出相关物料( 原材料、零部件等) 的需求量和需求时间；( b ) 根据物料的需求时问和牛产( 订货) 周期来确定其开始牛产 ( 订货) 的时间。 m r p 的基本内容是编制零件的牛产计划和采购计划。然而，要正确编制零件计 划，首先必须落实产品的出产进度计划，即丰牛产计划( m a s t e r p r o d u c t i o ns c h e d u l e ， m p s ) ，这是m r p 展开的依据。m r p 还需要知道产品的零件结构，即物芈斗清单( b i l lo f m a t e r i a l ，b o m ) ，才能把丰牛产计划展开成零件计划；同时，必须知道库存数量才 能准确计算出零件的采购数量。因此，基本m r p 的依据是：丰牛产计划( m p s ) ，物 料清单( b o m ) ，库存信息。 人乍坝i 学位硷文 ( 2 ) 七州的闭环m r p 。闭环m r p 系统除了物料需求计划外，还将牛产能力 需求计划、车间作业计划利采购作业计划也全部纳入m r p ，形成一个封闭的系统。 ( 3 ) 八十年代，人们把牛产、财务、销售、工程技术、采购等各个了系统集成 为一个一体化的系统，并称为制造资源计划( m a n u f a c t u r i n gr e s o u r c ep l a n n i n g ) 系统， 英文缩写还是m r p ，为了区别物料需求计划而记为m r p l i 。 ( 4 ) 进入九十年代，随着市场竞争的进步加剧，企业竞争空间与范围的进一 步扩大，八十年代m r p i i 丰要面向企业内部资源全面计划符殚的思想逐步发展为九 十年代怎样有效利用和管理整体资源的管理思想，e r p ( e n t e r p r i s er e s o u r c e p l a n n i n g ) - - 企业资源计划也就随之产牛。e r p 是在m r p l i 的基础上扩展了符理范 围，给出了新的结构。 1 2 物料清单( b o m ) 的介绍 在现代制造业中，很多复杂的成套设备都由数以万计的自制件、外协件、外购件 及原材料等各种各样的零部件所组成，为了形成各种型号的产品，要对这些零部件 进行合理的组合，这就是产品结构配置。摹于这种思想，人们提出了物料清单 b o m ( b i l lo f m a t e r i a l s ) 这个概念。 b o m 即物料清单，它是报表化的物料集成模型。物料一词在企业中有着广泛的 含义，它是所有产品、半成品、在制品、原材料、组装件、协作件、易耗品等与牛 产有关物料的统称【2 】。 b o m 有广义的定义和狭义的定义。狭义的b o m 也被称为产品结构表或产品结构 树。从物理装配和组成关系的空间角度分析，狭义的b o m 反映了产品与其构成的部 件、部件与其了部件之间的层次关系，是一一种代表各部件构成关系的树形结构数据 文件，还可包括有关产品及其零部件的编码、规格、材料、质量等方面的信息。这 样的b o mp - j 以直观的表示成一种有根树，即产品结构树( 如图卜1 ) 。 撇 7 零甬1 、。i 蜊l l nj 组晶、：7 蛳、零蚌t 1 组附n ：组瞎m + 、 。、| 一 j 图1 - 1产品结构树 这种产品结构树是一个包含一个元素以上的有限集合，其中： ( 1 ) 有一个特殊的元素是根元素，该元素的代表一个产品、一个组装件等： ( 2 ) 其余元素又被分成若干产品结构树，他们是其根元素的予树。 我们一般把某个部件的上级部件称为它的父部件，丽该部件就是其父部件的予 部件。同一个部件既是其父部件的了部件，又是其下级部件的父部件，每一个这样 的父了结构都称为b o m 的单层结构。 广义的b o m 是产品对象的属性集合。 我们发现，产品的成本和产品的构成一样，可以逐级分解，因此也可以采用类 似b o m 的树形表示，我们把表示产品成本构成的树形结构称为成本b o m ( 如图卜2 所示) 。 一、 产品总成本 7 材 糨 组件1 1 7 、 ，“ 、 人i 费i ：包装费j 、 ，1 童鬲： 厂螽磊i 、：厂i 蒜、 ， 图1 - 2成术b o m 示例 大学碗l 节证硷史 町以看出，成本结构树也是一个包含个元索以上的仃限集合，具中每个元素 代表。个部分的成本，如某个零件的成本，某个成品的成本。 b o m 的完整定义如下：b o m 的摹本结构是个三元组 e e + ) 。采用 m b o m 结构的成本结构表定义如下： 表2 1多层b o m 结构袁 n o键 宁段名称意义 1 土键 i d 土键，唯标示条记录 2 f a t l l e r n o 父节点的编码 3 c h i l d n o 子节点的编码 4 n o d e n u m 该节点和儿父节点之日j 的数罩关系 5 l c v e l c o d e 层次码 在多层b o m 结构表定义中，所谓了节点其实是父节点的后代，不一定是其儿了 节点。层次码表示了节点在以父节点为根的b o m 中位于第几层，如果了节点是底层 的叶予节点，则层次号用字母“l ”表示。 可见，用多层b o m 结构定义持久化一个b o m ，其每一条记录表示一个“祖先 后代”关系。 下面是一个b o m 的实例： g 大学颤l 卞【蔓沦立 图2 1b o m 示倒i 对于图2 1 所示的b o m ，若采用m b o m 结构可以用以下几条记录存储： i of f a t h e r n of c h i l d n on o d e n u m l e v e l c o d e 1 bl l 2 ac2l 3 ad3 l 4 e2 l m b o m 的缺点是零部件结构重复定义，数据兀余非常大，这无疑使得b o m 文件 难以维护。并且，m b o m 无法显示产品的层次结构信息。 单层b o m 结构( 简称s b o m ) 采用单父单了的数据结构，即给定b o m 的摹本结 构( m ，e ，t o ，s b o m 的摹本形式是 ( m i ，m 2 ) i m l 1 1 1 2 m ， e ) 。采用s b o m 结构的成本结构表定义如下： 表2 2单层b o h 结构袁 n o键宁段名称 意义 1 主键 i d 土键，唯标示条记录 2 f a t h e r n o 父节点的编码 3 c h i l d n o 子节点的编码 4 n o d e n u m 该节点和儿父节点之b j 的数晕关系 可见，用单层b o m 结构定义持久化一个b o m ，其每条记录表示一个“父亲 儿了”关系。 9 人学坝i 学位i 仑文 s b o m 对t + 每。父r 关系只定义一一次，因而可以大大行省存储宅问。f l i 使用 s b o m ，在构造整个b o m 结构时，必须实现递归算法，该算法中包含了多次数据 库的操作。对于具有复杂结构的产品来说，s b o m 带来的效率问题是不容忽视的。 虽然s b o m 结构具有潜在的效率问题，仙是其能够有效避免数据兀余以及能够 清楚地表示父了关系，有着显著的优点。我们在s b o m 的萆础上定义成本结构并对 其作适当的改进和扩展，摹本的成本结构表定义如下： 表2 3 成本结构表i n o 键字段名称 意义 1 土键 i d 土键，唯标示。1 个节点 2 n a n l e 节点名称 3 f a t h e r l d 该节点的父节点的i d 4 ，n o d e n u m 该节点和其父节点之f b j 的数晕关系 使用成本结构表l 的定义存储图2 - 1 中的b o m 。需要增加如下几条记录： i dn a m ef a t h e f l d n o d e n u m o o lan u l ll 1 0 1b0 0 l 1 1 0 2 co o l2 1 0 3d0 0 1 3 2 0 1el o i2 一般来说，成本结构表中的每一条记录要么表示某个物料，要么表示某个物料 的加工费用。该记录对应的物料或费用的信息存放在物料表或费用表中，为了体现 这种关联关系，需要在成本结构表中增加一个字段表示该记录对应的物料表或费用 表的记录i d 。物料表记录所有物料的信息，物料的属性包括重量、成本等。物料表 可以如下定义： 表2 - 4物车； 表 n o 键 宁段名称意义 1 土键t d 主键，唯标示个物料 2 n a l n e 物科名称 3 c a l u e i 受物料的成术 4 w e i g h t物科重晕 在构造b 渊的时候常常有不同成品或零件使用同一个零件的情况，例如某款男式 单乍和某款女式单车使用了同种电镀车铃。如果同一个零件的b o m 被0 i 用很多 1 0 。碗i 学位硷支 次，而每次都要重复存储的话，将带朱大量数据 c 余。为了防止数据兀余我们在 成本结构表中- 再增加一个字段s u b t r e e l d 表示该记录一j i 用了另外一个已经建征好的 b o m 树。这样，所有物料的b o m 只用存储一次就可以了。 综上所述，扩展的成本结构表的定义如下所示 表2 5成本结构表2 n o键 宁段名称 意义 1 土键 i d 主键，唯知：示一。个节点 2 n a m e 节点名称 3 f a t h c r l d 该节点的父节点的i d 4 n o d e n u m 该节点和其父节点之日】的数帚关系 5 m a t e r i a l l d 该节点对心的物科或费用的i d 6 m a t e r i a l o r n o t 布尔值，表示该节点足否为物料 7 s u b l 、d d 该节点引用的子树根节点i d 这种成本结构表定义在文献【1 9 ，2 0 】中称为高津托图( g o z i i i t og 阳p h ) 表示法。使用 这种表示法，可以清晰表示出物料之问的父予关系，避免了m b o m 表示法的父了关 系不明晰的问题，能够方便地实现物料的复用。 、 图2 2 b o m 示倒2 图2 2 中显示的b o m 是一种物料复用的情况，节点e 既是b 的儿了节点，又是d 的 儿了节点，即节点e 同时参与两个成本b o m 的构造。此时，e 应该表示一个已经构造 完成的b o m 树的根节点。像这样把已经建立好的b o m 直接作为另个b o m 中某节 点的了树，称为弓i 用。在图2 2 中，节点e 同时被b 4 1 d - j i 用。采用成本结构表2 的定 o， ， ， ， 一3 ， 大学坝i 学位论文 义，我们可以用如下一+ 组记录来表4 i 图2 2l p 的情况。 i dn a m e f a t h e r l dn o d e n u m m a t e r i a l i ds u b t r e e i d 0 0 lan u l ll i o lb 0 0 l l 1 0 2c0 0 l2 0 0 2dn u l l1 0 0 3 en u l i2 3 0 1e lo o l20 0 3 2 0 1e 2 0 0 2 30 0 3 在这里，我们把e 节点作为一个独立的b o m 树进行存储。e l 和e 2 实际上是两个 “虚节点”，它们仅仅表示了节点b 、d 和节点e 之间的父了关系，而不代表实际的物 料。e 1 和e 2 都通过s u b t r e e i d 字段引用了节点e ，这样就表示e 同时被两个b o m 树弓i 用。通过这样的存储方式，我们无需把以节点e 为根的b o m 在以a 和d 为根的b o m 中重复存储，从而实现物料复用的目的。 2 2 2b o m 的树形表示 为了把持久化的b o m 记录转换成直观的树形表示，首先需要定义b o m 树中节点 的结构。 为了直观地表示b o m 树中的父了关系，考虑把树的父亲指针存储方式和儿了链 表存储方式相结合。此外，节点中还要存储节点的名称、数量、成本等属性或信息。 一般地，b o m 树节点结构可以定义如下： t y p e d e f s t r u e t n o d e + p a r e n t ； l i s t c h i l d r c n ； s t r i n gn a m e ； f l o a tn u m b e r ； f l o a tv a l u e ； ) n o d e ； t 阪杀指针 川l 子节点指针链表 节点名称 旷符点数晕 l 缗点l 耗本 把成本结构表中的记录转换成树形表示的算法请参看第二章系统实现部分构造 成本树的算法。 2 3 成本计算 荩于已经建立好的物料的b o m ，我们就可以计算该物料的成本。成本计算应该 遵循下面瓯条规则： ( 1 ) b o m 中的叶节点成本可以直接得到，即是由用户商接录入的。例如：原材料 购价、零件购价。 ( 2 ) 非叶了节点，其成本可以由它的所有了节点的成本加和得到，公式如下： 节点成本= 子节点f 成本子节点f 数量。 图2 3b o m 示例3 在上图所示的b o m 中，节点a 的成本= 节点b 成本1 + 节点c 成本屹+ 节点d 成本 + 3 。 由于b o m 树中内部节点的成本需要由其了节点的成本累加得到，所以了节点的 成本应该先于其父节点的成本被计算。 根据有向图的深度优先搜索算法，我们可以得到成本计算的递归算法，用伪代 码表示如下，其中节点类n o d e 定义见2 2 节： v o i dd f s _ c o m p u t e ( n o d e + r o o t )f f 箅以r o o t 为根的b o m 成本 i f ( r o o t 是i + 子节点) 商接得到该节点的成本； r e l u m ； f o r ( r o o t 的每+ 个儿子节点c h i l d ) d f s _ c o m p u t e ( c h i l d ) ； 大学坝i 学位仑上 l o o t 的成术+ = c h i l d 的成本* c h i l d 的竹点数谛： * - , - j i l l 计算成本 借助堆栈，可以把上面这个算法写成非递归的形式： v o i dd f s c o m p u t e1 ( n o d e + r o o o，计算以r o o i 为根的b o m 成本 初始化节点栈n o d e s t a c k ： 把r o o t 入栈n o d e s t a c k ； 把所存节点标记为未访阳： w h i l e ( n 0 d e s t a c l 【非空) ( 取栈顶节点，记为p a r e n t n o d e ： 若p a r e n t n o d e 为叶子节点或其子节点都被访f u j 。l j p a r e m n o d e 出栈，同时标记 p a r e n t n o d e 为l 三访问： 6 】r ( p a r e n t n o d e 的每+ 个子节点c h i l d n o d e ) ( p a m t n 0 d e 成本+ - - c h i l d n o d e 成本c h i l d n o d e 数景： ) ) 根据有向图的广度优先搜索算法，还可以得到另外一个计算b o m 成本的算法。 需要注意的是，对b o m d 0 的内部节点来说，其了节点应该先于该节点入队列，这样 才能保证予节点的成本先于其父节点成本被计算。算法伪代码如下： v o i d b f sc o m p u t e ( n o d e 。r o o t )，计算以r t 为根的b o m 成本 初始化节点队列n o d e q u e u e ； 把所有节点标记为未访问： 在以r o o t 为根的b o m 树i i i 查找所柯叶子节点，把它们加入队，0 u o o e q u e u e ； w h i l e ( n o a e q u e u e 非空1 从取出。个节点，记为c h i l d n o d e ，将c h i l d n o d e 的父亲节点记为p a r e n t n o d e ： 把c h i l d n o d o 杯记为l 访问； p a r e n t n o d e 成本忙c h i l d n o d e 成本+ c h i l d n o d e 数最； 若p a r e n t n o d e 的所有子节点都l 三经被访i u j ，l j p a r e n t n o d e 节点入队列； 2 4 物料嵌套的检测 物料嵌套，就是某个物料的下级物料中包括其自身。例如：物料a 的了物料包括 物料b ，而物料b 的了物料中又包括物料a ，这样就发牛了物料嵌套。显然，物料嵌 4 大卞顺i 中位沦之 套足。忙法的。因此，在保仔b o m 和硅水b o m 的时候应该判断是古 现物科敬食的 情况。在构造之前进行判断称为预判断，在持久化后进行判断称为缸后削断。 2 4 1 物料嵌套的预判断 构造b o m 的时候，常常需要弓i 用已经建立好的另一个b o m ，此时可能发牛物料 嵌套，如下图所示： ， ， ， p s ， 7 7 p 17 7 ，7 7 7 图2 - 4物料嵌套不例i 上图就是在构造b o m 的时候发牛物料嵌套的示例，节点c 需要引用已经构造好 的以节点d 为根的b o m ， u 是d 的了节点包括c ，这样就发牛了物料嵌套。 物料嵌套的预判断就是要在引用前，判断该引用是否会带来物料嵌套问题。在 图2 - 4 中，我们称p 1 部分的c 节点为0 i 用节点，p 2 部分的d 节点为被弓i 用节点。可以 发现，假设从引用节点到其所在b o m 的根节点这条路径上面所有节点的集合记为 v i ( 即弓 用节点的所有祖先节点集合) ，以被弓 用节点为根的b o m 中所有节点组成的 集合记为v 2 ，若kn 以o ，则该弓 用会导致物料嵌套。 例如，在图2 4 所示的情况下，v i - a ，c ) ，v 2 = o ，c 。因为v l n v ! = c ，放 该j 1 l 用会导致物料嵌套。 基于这个条件，我们可以得到物料嵌套的预判断算法如下，该算法中两个入口 大学钡i7 位| 仑史 参数分别为0 | f i 】节点和被j j i 川常点，返回值为真表求出现物料嵌套： b o o lf i n d c y c l e ( n o d e u tn o d e v )u 一引f h 竹点，v - 皮i j l f lj 订点 衲始化节点集合n o d c g c t ，该集合存放引用节点的所仃丰h 先节点： w h i l e ( u ! = n u l l ) 把u ) j n 入n o d e s e h u = u 的父亲：讧点： 初始化节点队列n o d e q u e ； 把v a 队列n o d e q u e u c ： w h i l e ( n o d e q u e u e a 空 从n o d e q u e u e 取出个节点，记为p a r e n t n o d e ； f o rf p a r e n t n o d e 的每个儿子节点c h i l d n o d e ) i f ( c h i l d n o d c 在n o d e s d i l l ) r e t u r nt r u e ； c h i l d n o d e a 队n o d e q u e ； n 目u mf a l s e , ) 2 4 2 物料嵌套的事后判断 事后判断物料嵌套的算法，就是判断存储的b o m 中是否有有向回路。一般的做 法就是从b o m 的根节点开始，在b o m 上作深度优先搜索，如果发现到达前面访问 过的记录，则说明该有向图中存在回路。时间复杂度和空间复杂度均为o ( n ) ，n 为该 b o m 中的节点数目。下图是一个物料嵌套示例： 图2 5物科嵌套示例2 6 大学硕j f 戗沦支 上图是个b o m ，征该幽中我们用箭头衷小父f 关系箭头尾鄙足父节点，头 部指向儿于节点。这样，b 和c 足a 的儿了，d 足b 的儿了，吲此d 足a 的f 级物科。 u 是根据该图，a 又足d 酌儿了，这样a 就是它自己的下级物科，这显然是非法的。 以a 为根进行深度优先搜索，则依次访问a 、b 、d 节点，然后又访问a ，因为此 时a 已经被访问过，故存在一个回路。 把判断物料嵌套的算法用伪代码表示如下： b o o l f l n d c y c l e ( n o d e r o o t )判断以r o o t 为根的b o m i i 是台白回路 初始化堆栈n o d e s l a c k ： 把r o o t 压入堆栈n 0 d e s 协c k ： 把所有节点标记为来访| u j ； w h i l eo q o d e s t a c k 非空1 取栈项节点，记为p a r e n t n o d e ； 标记p a r e n t n o d e 为l 二经访问： f o r ( p a r e n t n o d c 的所自- 子节点c h i l d n o d c ) i f ( c h i l d n o d e 在n o d e s t a c k qw ) r e u i r nt r u e ； 出现物科嵌套 i f ( p a r e m n o d e 足口| 节点o rp a m a t n o d c f 听有子节点郁被访u j ) p a r e m n o d c 出栈： e l s e 取p a r e m n o d c 某个来访问的子节点c h i l d n o d e , k 栈； ) r e t u r nf a l s e ；, 由于在有向图中，一条回路上的节点必同属于同一个强连通分量，因此采用寻 找有向图中所有强连通分量的算法也可以判断有向图中是否有环。如果在有向图g 中存在强连通分量，说明g 中存在回路。 利用深度优先搜索，求有向图g 的强连通分量的算法步骤： ( 1 ) 对g 进行深度有限搜索并按递归调用完成的先后顺序对各顶点编号； ( 2 ) 改变g 的每条边的方向，构造出新的有向图g ，； ( 3 ) 按( 1 ) 中的确定的顶点编号，从编号最大的顶点开始对g ，进行深度优先搜 索。如果搜索的过程中没有访问遍g ，的所有顶点，则从未被访问过的顶点中选取编 号最大的顶点，并从此顶点开始继续做深度优先搜索； ( 4 ) 在最后得到的g ，的深度优先牛成森林中，每棵树上的顶点组成g 的一个强 1 7 大学硕l 学位论文 连通分量。 2 5 结果表示 由于b o m 的结构可以表示为一个树，所以最直观地表示成本计锋结果的方式就 是直接用树形表示法。树中每个节点都记录着其自身的属性和成本，用户根据需要 可以自由选择需要查看成本的节点，系统自动以列表方式显示该节点的成本和相关 属性。 牛产实践中，用户往往不满足于仅仅使用树形表示法查看成本计算的结果，传 统的统计报表形式由于具有能够同时显示多组数据等优点，仍然受到用户的青睐。 而且，用户希望能够自由选择报表的元组和字段，而不是由系统开发人员预先定义， 这就是自定义报表。自定义报表对系统的灵活性提出了很高的要求，在这种情况下， 有必要深入研究相关算法。 2 5 1 表格的分类 在日常牛活中出现的表格，一般可以根据其显示的元组和字段的差异分为以下 几种： ( 1 ) 一维表 表格中只有一个元组，而且显示的字段都是摹本数据项。例如： ( 2 ) 一维统计表 表格中只有一个元组，而且其字段都是满足某种统计条件的。例如： ( 3 ) 二维表 表格中有多个元组，其字段或者是基本数据项，或者是若干基本数据之和。例 如： 大学碗l 予位沦文 i5 7 0 球锁 l o o o1 0 0i o o1 20 0 i l5 7 9 l 球锁 9 o o 1 0 0 20 0 1 2 0 0 ( 4 ) 二维统计表 表格中有多个元组，其元组和字段都满足某种统计条件。例如： 职称博i ：颂i ：学i ：百分比 教授 l oil5 0 讲师 2 645 0 在离散制造业中，使用最广泛的报表形式就是二维表，所以我们丰要讨论定义 二维表的算法。 2 5 2 基本概念 二维表从其结构上看可以分为二个部分【1 2 】：( 1 ) 表说明部分；( 2 ) 横表头；( 3 ) 纵表头。如下图所示： 成品统计表 时问：2 0 0 7 ，5 ，1制作入：一t 成品材辩人工包装总成本 5 7 0 球锁 1 00 01 0 0l0 01 20 0 5 7 9 l 球锁9 0 01 0 02 0 0 1 20 0 图2 - 6维表示例 可以看到，纵表头中每一行数据可以看成具有某些属性、包含某些数据一个对 象，称为显示对象；攒表头中每一列数据是显示对象的某个属性或数据项，称为显 示内容。这样，定义报表也可以分为三个步骤：( 1 ) 定义该报表的表说明部分；( 2 ) 定义显示对象：( 3 ) 定义显示内容。 9 分广t 錾 明 头 头 锄 表 表 表 横 级 大学坝卜节位沧文 2 5 3 基本算法 根据我们前面的分析，定义报表的流程也可以分成二个卞要部分，见下图 图2 - 7 搬表定义流程 表说明部分需要记录的信息有：表名称、牛成日期、备注等。可以用如下结构 定义表说明部分。 义。 t y p e d e f s t m c t s t r i n gt a b l e n a m e ； d a t ed a t e ； s t r i n gr e m a r k ； t a b l e l n f o ； i 袭名称 = t 期 l 舔、t 显示对象需要记录的信息有：对象名称、所属表名等，可用如下结构定义。 t y p e d e f s t m c t s t r i n gt a b l e n a m e ； s t r i n go b j c c t n a m ) r o w o b j e c t ； ，表名称 显示对象名称 显示内容需要记录的信息有：内容名称、来源、所属表名等，可用如下结构定 t y p e d e f s t m c t s t r i n gt a b l e n a m e ； s t r i n gs o u r c e ； s t r i n ga t t r n a m ；c o t o b j e c t ； ，衷名称 来源 ，显示内容名称 显示内容的来源表示该显示内容从哪里取得，例如属性、成本分类等。 这二个结构之问的关系可以用u m l 类图表示如下： 人7 碘l f 位沦立 图2 4搬袁定义类图 要根据定义好的显示对象和显示内容正确牛成报表，关键的一点就是：给定一 个显示内容，如何判断某个具体的物料是否包含该内容并正确定位。即：假如显示 内容来源有n 个，对于某个显示对象来说可以构造n 个集合a i 一，a 。，分别表示属 于该显示对象的不同来源的数据集合，若定义的显示内容的集合为s ，