刘电台++赵卫东

摘要：随着双代号工程网络图的影响日益广泛，手工绘制难以满足需求。该文通过分析双代号网络图的特点，提出了虚工序确定算法，并能很好的删除冗余虚工序，通过对传统经纬线布局方法的研究，提出了改进的分层分级方法，较好地解决了布局问题。通过提供工序和工序之间逻辑关系的信息，便可自动生成虚工序，自动对节点进行编号，并对节点进行布局，该方法具有效率高、产生交叉点少和结构简单等特点，能够绘制出更加简单清晰而又美观的工程网络图。

关键词：双代号工程网络图；节点；虚工序；紧前工序；紧后工序

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2016）17-0236-02

Abstract： As the impact of Activity-on-arrow Network increasingly widespread， hand-painted is difficult to meet the demand.By analyzing the characteristics of the Activity-on-arrow Network， this paperproposes a algorithm to determine the dummy activities. It can delete the redundant dummy activities very well. Through the research on the traditional method of the layout of the warp and weft lines， this paper presents an improved hierarchical classification method. It is better to solve the layout problem.By providing the information of the logical relation between the nodes and the nodes， the dummy activities can be automatically generated. It can automatically number the nodes， and places the layout of nodes. The method has the advantages of high efficiency， less intersection， simple structure and so on. It can draw a more simple， clear and beautiful Activity-on-arrow Network.

Key words： activity-on-arrow network；node；dummy activity；predecessor activities；successor activities

1背景

项目计划管理是项目管理的重要组成部分，网络计划技术则是进行项目计划管理的最具有代表性的项目管理技术。它是20世纪50年代末发展起来的，依其起源有关键路径法（CPM）与计划评审法（PERT）之分。双代号网络图是网络计划技术研究的重要工具之一，它能够非常清晰直观地表达项目工序之间的时间和逻辑关系。网络计划技术技术在产品开发、经营管理、生产组织以及日常生活的方方面面都有广泛的应用[1]。预定计划任务的进度安排，以及每个环节之间的相互协调和制约关系，都可以用网络图表示，它方便项目管理人员进行定量分析。通过网络计划的分析模型以及网络图中的工序和节点参数，计算各工序的时间参数，并在此基础上对工期、成本和资源等进行优化，而绘制网络图则是网络计划技术的第一步，也是非常关键的一步。目前国内外网络图自动绘制的软件比较多，但是大多数软件均只能绘制单代号网络图以及甘特图。长期以来国内一般都使用双代号网络图进行网络计划技术的控制实施。然而在实际应用中，直接可以得到的仅仅是工序之间的逻辑关系，只有根据工序之间的逻辑关系对现有的信息进行转换，才能得到所需的网络图草图，这是非常繁琐的过程。

工程网络图能够准确地反映出各项工序之间的相互依赖关系和相互制约关系，把项目中所有工序组成一个有机的整体。随着社会信息化的高速发展，工程项目越来越复杂，手工绘制的网络图难以满足需求，通过计算机绘制网络图也越来越受到人们的迫切关注。但是计算机绘图正处于起步阶段，难以充分满足需求，表现出各种不足之处，例如计算机自动生成的网络图虚工序冗余较多，没有进行一定的简化删除，而且最终生成的网络图节点分布不均匀、交叉点多[2]。本文主要针对计算机绘图的问题进行了相关研究，首先对网络图的结构进行分析，统筹考虑网络图的局部和全局特征，提出了双代号工程网络图虚工序确定算法，并通过相关判断规则删除部分冗余的虚工序，通过改进的分级分层方法对节点进行布局，绘制出更加清晰美观合理的网络图。

2图的存储结构

在双代号网络图中，每个工序都是由两个节点和一条箭线构成。对于每条工序来说，由于边的存在使起始节点和结束节点成为邻接节点。与节点相关联的边的条数成为节点的度。在双代号网络图中，节点的度分为入度和出度。入度是指以该节点为终点的有向边的条数，出度是指以该节点为起点的有向边的条数。由图的定义可知，双代号网络图的信息由两部分构成，它们分别是图中节点的信息和描述工序的边的信息。图的存储结构主要是边的存储，主要分为邻接矩阵和邻接表两种。本文主要使用邻接表的结构，它具有存储灵活的特点，并且非常节约空间[1]。

3虚工序确定算法

虚工序的确定是绘制网络图关键性的步骤，本文以确定虚工序以及节点间的逻辑关系为首要目标，通过输入的各工序和工序之间的逻辑关系，来确定各节点和节点之间的逻辑关系，最终实现工程网络图的生成。

双代号网络图中的虚工序并不是一项实际的工作，它不消耗任何时间和资源，而只是在双代号网络图的绘制中因工序间逻辑关系的需要而增加的[3]。虚工序是用来帮助正确表达各工序间关系，避免逻辑错误。任意2个节点之间不能有2项或2项以上的工序，故必须要引入虚工序。在双代号网络图中，虚工序的应用是至关重要的，但不可滥用，必须要合理使用，否则会增加很多工作量和分析计算的负担。

通过用户输入所有的工序信息，然后由计算机自动将工序和工序之间的逻辑关系转换成节点和节点之间的逻辑关系，这样可以大大降低用户的工作强度。转换的过程比较繁杂，涉及用来表述工序之间逻辑关系的虚工序的添加，合理添加虚工序决定了双代号网络图是否正确与简洁，虚工序的添加应该符合相应的原则。下面将对各个工序，按照先后排列次序进行信息转换，进而确定各工序的首尾节点号[4～6]。

1）首先要处理无紧前工序的工序，将所有无紧前工序的工序首节点均编号为1，尾节点依次增加进行编号，用m保存当前最大的节点编号，继续处理其他工序。

2）若当前工序只有惟一紧前工序，则当前工序的首节点号与其唯一紧前工序的尾节点编号相同，其尾节点编号为m=m+1。

3）否则，其紧前工序两两进行处理。首先判断它们的首尾节点是否相同，如果首或尾节点相同，则不需要合并，如果都不同，接着判断它们的紧后工序数是否相同，如果相同则进一步判断其紧后工序是否一致，如果一致则两者尾节点编号与较大者相同，同时记录被删掉的编号，完成合并工作。

4）若当前工序的所有紧前工序有惟一公共的尾节点，则其首尾节点号可以确定，首节点号与惟一公共的尾节点号相同，而尾节点号为m=m+1；否则需要进一步的判断。

5）查找是否存在紧后工序惟一的紧前工序，若存在，则添加虚工序。从其他紧前工序的所有尾节点都添加一个虚工序，并指向该紧前的尾节点。然后判断首尾节点编号顺序的合法性并做出相应处理，当前工序的首节点编号与该紧前工序的尾节点编号相同，尾节点编号为m=m+1。查看已存在的虚工序，判断它们是否有相同首尾节点，以免重复。添加虚工序时，其首节点编号有可能大于尾节点编号，此时要将其尾节点编号变成m+1，并且记录被删掉的尾节点编号，比较之前先保留删除节点编号作为比较值，找出所有以此比较值为尾节点编号的工序，并修改它们的尾节点编号，添加当前工序，修改其他以此比较值为尾节点编号的虚工序的尾节点编号，添加一个虚工序。

6）若不存在紧后工序惟一的紧前工序，则添加虚工序。从当前工序的所有紧前工序尾节点各引出一个虚工序，它们的尾节点编号相等均为m+1，当前工序的首节点编号与虚工序的公共尾节点编号相同，尾节点编号为m+1。

7）最后，需要归并所有的最终节点，将它们合并成一个节点。查找所有无紧后工序数组中尾节点编号最大的工序，令其尾节点为最终节点；依次遍历其他无紧后工序，判断是否需要添加虚工序，若当前工序与以前处理过的工序中的某一个具有相同的首节点，则需要添加虚工序。虚工序的首节点编号与当前工序的尾节点编号相同，尾节点编号为最终节点，否则，删除当前工序的尾节点编号，并且替换成最终节点编号，最终可以实现合并。

8）最后需要对节点的编号进行整理。首先对删除节点编号数组进行排序，然后利用排序后的删除节点编号数组依次对每组双代号数据进行整理。

4节点布局方法

确定好所有节点和节点之间的逻辑关系后，然后进行节点布局，它也是网络图自动绘制的关键性步骤。节点布局决定了网络图的交叉点的多少以及网络图是否清晰直观。当前比较流行的方法是经纬线布局方法，使用经纬坐标（X，Y）来确定节点的位置，并根据网络图的比例来确定经线X的宽度和纬线Y的高度。经线X坐标从0开始，向右横向逐渐增大；纬线Y坐标从0开始，纵向对称扩展，与坐标系的y轴相似。尽量将关键路径放在0纬线上，其他节点在0纬线两边对称分开，使网络图布点对称均衡。目前国内大多数关于经纬线坐标的实现都是通过分级分层的方法，首先将所有节点进行拓扑排序来实现分级，然后再对每级中的节点进行分层，节点层次的确定都是要以其紧前节点的层次为依据[7～8]。级数不同，层次可能相同；级数相同，层次必不同。

初始节点的级数为 1级，从初始节点到某一节点的所有路径中经过节点最多的路径，其节点数就是该节点的级数，通过拓扑排序得到所有节点的级数，节点的级数与其经线坐标X相对应[9]。但是在某些情况下，这种基于拓扑排序的分级方法可能会有一定的缺陷，如果确定经线坐标X时考虑到节点最早开始时间，那么某些节点可能会重叠在一起，对网络图的绘制造成一定的影响。因为如果考虑到节点的最早开始时间，级数不同的两个节点它们的经线坐标X可能会相同，而级数不同时，层次又可能相同，即纬线坐标Y也可能相同，所以这两个节点可能会重叠。

传统的分级方法中节点的级数和经线坐标X是一一对应的，因为确定经线坐标X时增加了节点最早开始时间因素，所以分级方法也要有对应的改变。本文针对传统分级方法存在的问题，提出了改进的节点分级方法，并且统筹考虑了节点的经线坐标X。核心思想就是经线坐标X相近的节点，尽量要使它们的级数相近或相同。节点的级数要根据其经线坐标X进行适当的调整，要保证某级所有节点的最早开始时间都要比其前一级级的任意节点的最早开始时间大。

5结束语

随着双代号工程网络图在工程项目中的广泛应用，项目越来越复杂，工序越来越多，手工绘制网络图具有一定的难度，且无法满足当前的需求。本文通过研究当前双代号工程网络图计算机自动绘制中存在的许多问题，以绘制清晰和美观的网络图为研究目标，提出了一种较好的虚工序确定算法，并可以删除冗余的虚工序，通过对传统的经纬线布局法进行相关研究，提出了改进的分级分层方法，较好地解决了节点重叠的问题。最后绘制出清晰美观的网络图，为更加简单清晰直观的展现项目进度计划的工程网络图绘制奠定了坚实的理论和技术基础。

参考文献：

[1] 李四福. 大型工程PERT智能绘图与工程优化研究[D]. 北京： 中国地质大学，2014.

[2] 崔梦天，张荣虎，程国忠. 大规模软件项目管理系统中PERT网络图的优化问题研究[J]. 西南民族大学学报：自然科学版，2012（4）：638-641.

[3] 苏志雄，魏汉英. 规范化工程网络图的理论和方法[J]. 中国管理科学，2015，S1：359-363.

[4] 邹海，邱慧丽. 双代号网络图绘制算法的研究与实现[J]. 计算机与现代化，2013，07：176-179.

[5] 何永翔. 动态环境下pert网络图的布局优化研究[D]. 北京： 中国地质大学，2010.

[6] 伍振华. 基于双代号网络图的网络计划技术研究[D]. 武汉： 华中科技大学，2008.

[7] 宋莹. 基于GA的通风网络图优化绘制算法研究[D]. 阜新： 辽宁工程技术大学，2013.

[8] 韩超. 基于不确定性的工程项目网络计划优化研究[D]. 南京： 南京林业大学，2012.

[9] 邱慧丽. 矿井建设工程网络计划技术研究[D]. 合肥： 安徽大学，2013.