一种双代号网络图节点编号方法.pdf

《一种双代号网络图节点编号方法.pdf》由会员分享，可在线阅读，更多相关《一种双代号网络图节点编号方法.pdf（4页珍藏版）》请在三一文库上搜索。

1、2 0 0 7年 3月 第 2 3卷第 1 期 陕西理工 学 院 学报 J o u r n a l o f S h a a n x i U n i v e r s i t y o f T e c h n o l o g y Ma r 2 O 0 7 Vo 1 2 3 No 1 文章编号 1 6 7 3 2 9 4 4 ( 2 0 0 7 ) O 1 0 0 6 0 0 4 一 种双代号网络图节点编号方法 甘焕， 赵 嵩正， 高娜 (西北工业大学 管理学院 ， 陕西 西安7 1 0 0 7 2 ) 摘要】 对双代号网络 图节点进行编号是 网络 图自动生成 系统的重点与难点 ， 本文提 出了 一

2、种改进的网络图节点编号方法， 对工序排序优化 了工序集的邻接矩阵， 解决了传统方法易出 现回路的难题 ； 运用 系统工程思想 ， 紧密结合编号原则， 对工序进行 集合运算 ， 简化 了操作， 保 证了编号的唯一性与正确性。 【 关键词 双代号 网络图； 相邻矩阵； 节点编号 中图分类号 T P 3 0 2 4 【 文献标识码 】 A 双代号网络图又称箭线式网络图， 它用箭线表示工序， 用节点表示事件， 能全面而明确地反映出工 程项 目各项工作之间相互依赖、 相互制约的关 系， 是保障项 目按时完成 的有力工具 ， 但对于大、 中型 工程项 目。 工序多 、 关系复杂 ， 手工难 以实现详细、

3、准确的网络图， 计算机实现是最佳 的方法。 在双代号网络图的计算机实现中， 要求软件实现按逻辑关系进行排序、 回路检查以及双代号网络图 参数的生成， 然后根据绘图参数绘制出网络图 j 。其中， 处理好工序之间的紧前紧后关系以及对工序 节点的准确编号是实现电脑 自动绘图的关键技术。有鉴于此 本文首先优化与改进了工序集的相邻矩 阵， 并在对其进行详细分析的基础上， 结合双代号网络图的编号原则， 提出了一种改进的网络节点编号 方法。 1 双代号网络图的邻接矩阵 网络图的数学表示方法主要有两类： 数组和矩阵。本文采用矩阵表示工序之间的紧前紧后关系， 因 为工序的紧前关系可以推出工序的紧后关系， 工序的

4、紧后关系也可以推出工序的紧前关系， 二者只需知 其一就可以绘制双代号网络图， 本文的讨论基于已知紧前关系。 已知工序t t， ， tt ，： ， ， tt， ， 形成工序集 ( t t， ， tt ，： ， ， t t，： ) ， 在列出工序集的邻接矩阵前， 本文先对工 序集进行优化， 按照工序的计划开工时间将各工序排序， 开工时间早的工序居于前， 开工时间晚的工序 列于后， 若有计划开工时间相同的工序， 可以不分先后， 最终形成有序的工序序列集 W( tt， 。 ， t t，： ， ， 埘 ) 。 若用函数E a r l y ( tt ， ， ) 表示工序 的计划开工时间比工序t t， 的计

5、划开工时间早， 则对工序集W， 当 i 时， 恒有 E a r l y ( tt ， ， t t， ) 。对工序集 W及其紧前关系， 用矩阵中的每行及每列表示网络图中的每一个 工序， 以矩阵元素表示行与列对应工序的关系， 得到双代号网络图的邻接矩阵A， 如下： A= 口 I l 口 1 2 口2 1 口篮 M M 口- 1 口_ 2 口1 - 口2 - M M 口 =( P 。 ， P ： ， ， P ) =( Q。 ， Q： ， ， Q ) f o ， tt ， 是 t t， 紧前工序 【 l ， t t， 不是 t t， 紧前工序 对矩阵A进行分析发现 ， 当f 时， 口 恒等于0 ， 即

6、计划开工时间晚的工序或工序 自己不可能成为 收稿日期- 2 0 0 6 0 9一 l 1 基金项目： 航空科学基金资助项 目( 0 5 1 5 3 0 7 2 ) 。 作者简介： 甘焕( 1 9 8 2 一) ， 男， 胡南常德人， 西北工业大学在读研究生， 主要研究方向为工业工程。 维普资讯 第 1 期 甘焕， 赵嵩正， 高娜一种双代号网络图节点编号方法 计划开工时间早 的工序的紧前工序 ， 因此矩阵 A是上三角稀疏矩阵。 本文对工序的邻接矩阵进行改进后 ， 首先只需要存储上三角的非 0元素 ， 为计算机节省了大量的资 源， 其次消除了回路， 即邻接矩阵为上三角稀疏矩阵的有向图不可能存在回路

7、， 提高了工序关系表示的 准确性 。 2 网络 图邻接矩 阵的特点分析 正确的双代号网络图应该是无回路的有向图， 并且工序的方向沿着箭线的方向 】 ， 显然， 邻接矩阵 为 A的有向图不可能存在回路 ， 另外矩阵 A还有如下特点： I 第 i 行存在Y 个 1 ， 则表示工序 。 有 Y 个紧后工序， 其紧后工序集合： L = _ ， i ， 且 口 l ，：l ， 口 ， c P i ； 第 i 列存在 个 1 ， 则表示工序24) 。 有 个紧前工序， 紧前工序集合： F 。= ， 且 =l ， 口 c Q ； 工序 。 必定没有紧前工序 ， 工序 必定没有紧后工序 ； 在双代号网络图中，

8、 必定存在着至少一个开始工序和结束工序 】 ， 利用本文的邻接矩阵， 可以迅速 地判断出某工序是否存在 紧前工序或紧后工序 ， 对工序 l l ， ， 若列向量 Q 。 =0 ， 则 F i = g o， 即工序 无紧 前工序， 为开始工序， 同理， 若行向量 P = 0 ， 则 L 。 = go， 即工序 10 无紧后工序， 工序 为结束工序。 3 节点标号方法 3 1 节点编号原则 在双代号网络图中， 工序节点编号应遵循以下原则： 网络图有唯一的开始节点与结束节点； 具有相同紧前工序的开始节点具有相同的编号； 具有相同紧后工序的结束节点具有相同的编号 ； 工序开始节点的编号小于结束节点的编

9、号。 双代号网络图节点编号应该采用系统工程的思想， 从整体上考虑节点编号的合理性 】 。用( B ， ，l ) 表示工序 。 节点的编号， rn 。 表示开始节点编号， 表示结束节点编号， 则有 B ， 分别求出其紧前集合， 然后取并集， 形成新的工序 集合 o r = ： 10 i n ， 1 ， 2 ， 3 ， ， n ； S t e p 6 ： 依次取出 0 ， 的工序 ， 判断 与 是否同一工序， 如果是， 则取 0 f 的下一工序， 如果无下 一 工序可取， 则转 S t e p 7 。 6l 维普资讯 陕西理工学院学报 第2 3 卷 S t e p 7 ： 判断 W 是否编号 ，

10、如果没有编号 ， 则 W 。 的开始节点 标号为 任一 紧前工序 的结束节点编号 n ， 结束 节点 编号为 m a x ， m ax+ ； S t e p 8 ： 工序 W 的开始节点标号为 W 任一紧前工序的结束 节点标号 n ， 结束节点编号为 w 的结束节点编号 n ， 即工序 w 与工序 w 具有共同的紧后节点( 交点 ) 。 S t e p 9 ： 重复 S t e p 1 到 S t e p 8， 直到所有节点都编上号 ， 最后 将没有结束节点编号 的所有工序编号 ， 其结束节点编号为 m ax。 编号方法运用了系统工程 的思想 ， 通过对紧前工序集 ( S t e p 2 )

11、与紧后工序集( S t e p 3 ) 空集的判断 ， 确保 了双代号 网络 图有 共同的开始节点编号( 值为 1 ) 和结束节点编号( 值为 m ax 的最 大值) ， 达到了原则的要求； 同时依照紧前工序与紧后工序的 编号情况对所选节点编号( S t e p 4一S t e p 8 ) ， 确保 了网络 图节点 编号的生成满足原则和原则； 在对紧前紧后工序的判断上 实现 m ax 的自 我递增( S t e p 2 、 S t e p 7 ) ， 实现了原则。 综上所述 ， 本方法从整体上考虑 了节点编号的准确性与唯 一 性， 完全满足节点编号的原则， 是一种高可靠性、 高实用性的 方法。

12、 4 算例 图 1 双代号网络图节点嫡号算法 已知工序集 W( w - ， z ， ， ) ， 且满足当 ( ， =1 ， 2 ， ， 7 ) 时， E a r l y ( w ， ) 完全成立。其工序 关系如表 1 所示。 表 1 工序及其紧前关系 由表 1 ， 可以列出其邻接矩阵A ， 如式( 1 ) 所示： 分析矩阵A， 由于 Q 。 ： 0 ， 故 F 。 = ， 即工序 无紧前工 序 ， 因此 。 为双代号网络图的开始工序 ， 按照本文的编 号方法， 将其开始节点编号为 l ， 结束节点编号为 m a x= 2 ， 同时m ax+， 然后返回取下一个工序， 同理， 可对 A ： 编号

13、( 1 ， 3 ) ， 详细过程不在此一一赘述， 依次对各工序编 号如表2 所示。将编号填人双代号网络图， 如图2 所示。 经检验， 节点编号符合双代号网络图的编号原则， 完全正 确 ， 无需进行任何修正。 表 2 节点编号步骤 6 2 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 l 0 0 0 0 0 0 l 0 0 0 0 0 l 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 第 1 次编号 ( 1 ， 2 ) 第 2次编号 ( 1 ， 3 ) 第 3次编号 ( 2， 4 ) 第 4次编号 ( 3 。 4 ) 第 5次编号 ( 3 ， 5

14、) 第 6次编号 ( 5， ) 第 7次编号 ( 4， o) 第 8次编号 ( 5 ， 6 ) ( 4， 6 ) 维普资讯 第 1期 甘焕 赵嵩正 ， 高娜一种双代号网络图节 点编号方法 5 结论 卜 w 2 3 4 5 6 R A l a n B o w m a nD e v e l o p i n g a c t i v i ty d u r a t i o n s p e c i fi c a ti o n l i m i t s f o r e ff e c ti v e p r o j e c t c o n t r o l J E u r o p e a n J o u r n a

15、 l o f O p e r a t i o n a 1 R e s e a r c h ， 2 0 0 6 ， ( 1 7 4 ) ： l 1 9 1 一l 2 0 4 陈志华双代号网络图计算机自动绘制研究 J 武汉理工大学学报( 信息与管理工程版) ， 2 0 0 6 ， 2 8 ( 2 ) ： 2 5 之 8 魏宏博， 惠晓滨， 张凤鸣一种求双代号网络图关键路线的简便矩阵算法 J 计算机工程与设计， 2 0 0 4 ， 2 5 ( 7 ) ： l l 6 7 一 l 1 6 9 许国辉， 徐晖一种绘制双代号网络图的新方法 J 武汉大学学报( 工学版) ， 2 0 0 5 ， 3 8 (

16、3 ) ： 8 l 8 4 别冰冰 ， 刘宏国， 刘建鹏 基于 W B S的多级网络图的绘制 J 中国科技信息， 2 0 0 6 ， 1 3 ( 3 ) ： l 3 2 0 高欣群体网络计划系统模型和方法 J 系统工程理论践， 2 0 0 2 ， 3 ( 6 ) ： 5 4 5 9 T h e me t h o d o f n u mb e ri n g t h e n o d e o f d u mmy a r r o w Ga n Hu a n， Zh a o S o n g z h e n g， Ga o Na (M a n a g e m e n t S c h o o l ， N o

17、 r th w e s t e r n P o ly t e c h n i c al U n iv e r s i t y ， X i a l l 7 1 0 0 7 2 C h i n a ) Ab s t r a c t ： I t S d i f fi c u l t t o n u mb e r t h e n o d e o f d u mmy a r r o w f o r t h i s p r o b l e m， t h i s a r t i c l e g i v e s a r I i m p r o v e d s o l u t i o n ， w h i c h

18、 o p t i mi z e s t h e a d j o i n i n g m a t r i x o f w o r k p roc e d u r e s e t w i th sor t i n g w o r k p r o c e d u r e so th a t s e t t l e s the l oop p rob l e m wi th t r a d i t i o n a l me thod A c c o r d i n g t o the p ri n c i p l e o f n u mb e ri n g n ode ， the me thod a

19、d o p t s the s y s t e m e n g i n e e ri n g the o r y t o s e t u p o p e r a t i o n of w o r k p r o e d u r e ，so the o per a ti o n i s p red i g e s t e d， wh i c h e n s u res tha t th e n od e i s u n i q u e a n d v a l i d K e y w o r d s ： d u m m y a r r o w c h a r t ； a d j o i n i n

20、 g m a t r i x ； n u m b e ri n g n ode ( 上接第 5 9页) T h e a p p l i c a t i o n o f h y b rid p r o g r a mmi n g i n s o f t wa r e d e v e l o p me n t X I E F a Q i n ， T I A N S h a o L i ， Z H A N G Y o n g 3 ( 1 J i a n g X i Mode rn C o l l e g e ， N a n c h a n g 3 3 0 0 1 2 ， C h i n a 2 Z

21、h o n g S h a n B r a n c h o f Ho n g K o n g C rys t a l Grou p ， Z h o n g S h a n 5 2 8 4 5 9， Ch i n a 3 F a c u l t y of C o m p u t i n g ， N a n c h a n g I n s ti t u t e o f A e ron a u t i c a l T e c h n o l o g y， N a n c h a n g 3 3 0 0 6 3 ， C h i n a ) Ab s t r a c t ： E v e ry t ool

22、 u s e d i n sof t w a r e d e v e l o p me n t h a s b o th a d v a n t a g e s an d d i s a d v ant a g e s T h i s a r t i c l e d i s c u s s e s the me thods t o r e a l i z e h y b r i d p rog r a mmi n g o f c o mmo n d e v e l o p me n t t ool s i n c u rre n t sof t w a r e d e v e l o p me

23、 n t ， an d an aly z e s i n d e t a i l s o me t e c h n i c al p rob l e ms w h i l e u s i n g h y b rid p rog r a mmi n g Th rou g h h y b r i d p r o - g r a mmi n g i n d i ff e r e n t p rog r a mmi n g l a n g u a g e s ， t h e p rob l e m of c o d e r e u s e i s r e s o l v e d， an d f o r

24、 mi n g the r e u s e t e c h n i q u e i n t h e s o f t w a r e d e v e l o p me n t i s r e a l i z e d， the p r e d o mi n an c e of a l l k i n d s of d e v e l o p me n t t ool s i n the s o f t w are d e s i g n i s e x e rt e d， s o f t wa r e p rod u c ti v i t y i s p r o mo t e d F i n a l l y， thi s a r t i c l e g i v e s e x a mp l e s o f h y b ri d p r o - g r a mmi n g i n the s o f t w are d e v e l o p me n t Ke y wo r d s ： h y b ri d p rogra mmi n g ； s o f tware d e v e l o p me n t ； d y n a mi c l i n k l i b r a r y 6 3 维普资讯