文档介绍：第卷第期经济数学
年月〔尧
网络计划图的工序关系及其复杂性研究
潘开灵吕绪华
武汉科技大学,武汉,
摘要本文研究了将原始的施工工序关系表转换为规范网络计划图的活动关系的算法在理论上讨论了
网络图中活动与瞬前活动的关系以及与节点的关系,研究了网络图中添加虚活动的规律,进一步提出了生成
网络计划图的按先行工序类生成算法的补充研究
关键词网络计划图,算法,复杂性
网络计划技术是利用网络图模型研究工程活动及其排列的关系,是现代大型工程计划中
实施计划管理的有效工具应用该技术的操作过程包括将工程项目分解为子工程或活动,按
工程施工的技术逻辑关系确定各活动间的衔接根据工程项目分解表的活动及活动关系,绘制
网络图计算活动和节点的各时间参数和活动的最短路径调整活动时间和资源分配,实现资
源优化
在网络计划图的应用中,除确定工序时间和时间优化是其难点外,网络图的绘制也是一项
繁琐的工作,特别是当原始工序分解结果表与网络计划图中活动不完全一致,且需要一些虚简
明线表示工序关系时,这时大多数人则采用试探的办法或虚活动消去法等方法绘制初始网
络计划图,而所得结果不免产生一些冗余虚工序,且这些算法对于生成网络图却没有太多的帮
助本文就网络计划图中活动的逻辑关系的排
列和节点编号的产生进行讨论,并对按先行工
序类生成算法川进行完善,所设计算法将产生
规范的工序关系表生卜二④
网络计划图的构造规则和说明
图
网络计划图的基本要素是有向边和节点
在构造网络图时应遵循如下规则
规则有向边表示工程中的独立子项工
程或活动,称为活动,有向边的方向表示活动的
次序
规则节点表示完成一项或多项活动,称
为事项
规则每项活动只能联系两个事项,一个
开始事项和一个结束事项,而任意两个事项之图
间只能有一个活动
收稿日期一一
第期潘开灵吕绪华网络计划图的工序关系及其复杂性研究
规则事项表示一项或多项活动的结束和另一项或氏项活动的开始,它反映了活动间的
先后关系,具有时序的概念
规则网络图只允许存在一个源节点和个汇节点,即所有没有前活动的活动都以一个事
项为源节点,所有没有后活动的活动都以一个事项为汇节点
规则网络图不充许存在反馈环节,不允许出现回路
按照上述规则构造的网络图将是有且只有一个源节点和汇节点的无回路网络图
图表示网络图包含了、两项活动和事项,,活动联系着事项和事项,而
活动联系着事项和事项标识活动的开始,事项表示活动的结束和活动的开
始,事项表示活动的结束称为活动的开始项,为活动的结束项,称活动为活
动的紧前活动当某项活动存在多项紧前活动时,则它的所有紧前活动必须全部完工后才能开
始图中存在,,三个活动,其中,为活动的紧前活动,即,活动都完工后
活动才能开始,即的紧前工序为弋,,其关系表示为, 或,,的
紧前活动表示为
在绘制网络图时,有时需要引人虚拟活动完整表达活动之间的关系如同时存在活动的逻
辑关系有, ,代此时在何处增设虚拟活动以完整表达活动的先后逻辑关
系是构造网络图时需要解决的问题
根据上述网络图的构造规定,增加如下说明
定义两个活动的紧前活动集合相等是指它们的紧前活动集合的元素完全相同并将具
有相等的紧前活动集的活动归为同一等