《毕业论文关键路径的应用分析与实现》由会员分享，可在线阅读，更多相关《毕业论文关键路径的应用分析与实现（11页珍藏版）》请在金锄头文库上搜索。
1、关键路径的应用分析与实现作者姓名：吴黄海 指导老师：张玉洲摘要：关键路径法，又称关键线路法。一种计划管理方法。本文介绍了关键路径在科学和现实的应用。并详细介绍关键路径的概念及特点。以及AOE网的表示方法及性质。重点介绍关键路径的算法。包括（数据结构，算法实现，文字描述，代码书写）。最后对运行结果进行分析。关键词：关键路径法（CPM），网络图，AOE-网，关键活动，直接费用，间接费用1引言关键路径法(Critical Path Method，CPM)最早出现于20世纪50年代，由雷明顿-兰德公司(Remington- Rand)的JE克里(JE Kelly)和杜邦公司的MR沃尔克(MR Walk
2、er)在1957年提出的，用于对化工工厂的维护项目进行日程安排。这种方法产生的背景是，在当时出现了许多庞大而复杂的科研和工程项目，这些项目常常需要运用大量的人力、物力和财力，因此如何合理而有效地对这些项目进行组织，在有限资源下以最短的时间和最低的成本费用下完成整个项目就成为一个突出的问题，这样CPM就应运而生了。关键路径法，又称关键线路法。一种计划管理方法。它是通过分析项目过程中哪个活动序列进度安排的总时差最少来预测项目工期的网络分析。它用网络图表示各项工作之间的相互关系，找出控制工期的关键路线，在一定工期、成本、资源条件下获得最佳的计划安排，以达到缩短工期、提高工效、降低成本的目的。CPM中
3、工序时间是确定的，这种方法多用于建筑施工和大修工程的计划安排。它适用于有很多作业而且必须按时完成的项目。关键路线法是一个动态系统，它会随着项目的进展不断更新，该方法采用单一时间估计法，其中时间被视为一定的或确定的。关键路径法是项目管理中最基本也是非常关键的一个概念，它上连着WBS（工作分解结构），下连着执行进度控制与监督。关键路径是项目计划中最长的路线。它决定了项目的总实耗时间。项目经理必须把注意力集中于那些优先等级最高的任务，确保它们准时完成，关键路径上的任何活动的推迟将使整个项目推迟。向关键路径要时间，向非关键路径要资源。所以在进行项目操作的时候确定关键路径并进行有效的管理是至关重要的。2
4、. 关键路径法 - 特点（1）关键路径上的活动持续时间决定了项目的工期，关键路径上所有活动的持续时间总和就是项目的工期。 （2）关键路径上的任何一个活动都是关键活动，其中任何一个活动的延迟都会导致整个项目完工时间的延迟。 （3）关键路径上的耗时是可以完工的最短时间量，若缩短关键路径的总耗时，会缩短项目工期；反之，则会延长整个项目的总工期。但是如果缩短非关键路径上的各个活动所需要的时间，也不至于影响工程的完工时间。 （4）关键路径上活动是总时差最小的活动，改变其中某个活动的耗时，可能使关键路径发生变化。 （5）可以存在多条关键路径，它们各自的时间总量肯定相等，即可完工的总工期。3. 关键路径法的
5、网络图设定步骤（1）画出网络图，以节点标明事件，由箭头代表作业。这样可以对整个项目有一个整体概观。习惯上项目开始于左方终止于右方。 （2）在箭头上标出每项作业的持续时间（T） （3）从左面开始，计算每项作业的最早结束时间（EF）。该时间等于最早可能的开始时间（ES）加上该作业的持续时间。 （4）当所有的计算都完成时，最后算出的时间就是完成整个项目所需要的时间。 （5）从右边开始，根据整个项目的持续时间决定每项作业的最迟结束时间（LF）。 （6）最迟结束时间减去作业的持续时间得到最迟开始时间（LS）。 （7）每项作业的最迟结束时间与最早结束时间，或者最迟开始时间与最早开始时间的差额就是该作业的时
6、差。 8）如果某作业的时差为零，那么该作业就在关键路线上。 （9）项目的关联路线就是所有作业的时差为零的路线。 4.关键路径的算法AOE-网是一个带权的有向无环图，其中，顶点表示事件(Event)，弧表示活动，权表示活动持续的时间。通常，AOE-网可用来估算工程的完成时间。例如，下图是一个假想的有11项活动的AOE-网。其中有9个事件v1，v2，v3，v9，每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。如v1表示整个工程开始，v9表示整个工程结束，v5表示a4和a5已经完成，a7和a8可以开始。与每个活动相联系的数是执行该活动所需的时间。比如，活动a1需要6天， a2需要4天等。
7、对AOE-网有待研究的问题是： (1)完成整项工程至少需要多少时间? (2)哪些活动是影响工程进度的关键? 由于在AOE-网中有些活动可以并行地进行，所以完成工程的最短时间是从开始点到完成点的最长路径的长度(这里所说的路径长度是指路径上各活动持续时间之和，不是路径上弧的数目)。路径长度最长的路径叫做关键路径(Critical Path)。假设开始点是v1，从v1到vi的最长路径长度叫做事件vi的最早发生时间。这个时间决定了所有以vi为尾的弧所表示的活动的最早开始时间。我们用e(i)表示活动ai的最早开始时间。还可以定义一个活动的最迟开始时间l(i)，这是在不推迟整个工程完成的前提下，活动ai最
8、迟必须开始进行的时间。两者之差l(i)-e(i)意味着完成活动ai的时间余量。我们把l(i)=e(i)的活动叫做关键活动。显然，关键路径上的所有活动都是关键活动，因此提前完成非关键活动并不能加快工程的进度。因此，分析关键路径的目的是辨别哪些是关键活动，以便争取提高关键活动的工效，缩短整个工期。由上分析可知，辨别关键活动就是要找e(i)=l(i)的活动。为了求得AOE-网中活动的e(i)和l(i)， 首先求事件的最早发生时间ve(j)和最迟发生时间vl(j)。如果活动ai由弧表示，其持续时间记为dut(),则有如下关系： e(i ) = ve(j) (7-1) l (i) = vl(k)-dut
9、() 求ve(j)和vl(j)需分两步进行： （1）从ve(0)开始向前递推 ve(j) = Maxve(i)+dut()i T, j=1,2,3,n-1 （7-2） 其中，T是所有以第j个顶点为尾的弧的结合。（2）从vl(n-1)=ve(n-1)起向后递推 vl(i) = Min vl (j) dut() j S , i=n-2,0 （7-3）其中，S是所有以第i个顶点为头的弧的集合。 这两个递推公式的计算必须分别在拓扑有序和逆拓扑有序的前提下进行。也就是说ve(j-1)必须在vj的所有前驱的最早发生时间求得之后才能确定，而vl(j-1)则必须在vj的所有后继的最迟发生时间求得之后才能确定。
10、因此，可以在拓扑排序的基础上计算ve(j-1)和vl(j-1)。由此得到求关键路径的算法：(1)输入e条弧，建立AOE-网的存储结构； (2)从源点v0出发，令ve0=0，按拓扑有序求其余各顶点的最早发生时间vei (1in-1)。如果得到的拓扑有序序列中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径，算法终止；否则执行步骤(3)。 (3)从汇点vn出发，令vln-1=ven-1，按逆拓扑有序求其余各顶点的最迟发生时间vli(n2i2)； (4)根据各顶点的ve和vl值，求每条弧s的最早开始时间e(s)和最迟开始时间 l(s)。若某条弧满足条件e(s)=l(s)，则为关键活动。5.
11、程序代码根据上述例题，编写出程序如下：#include #include #define MAXVEX 100#define TRUE 1#define FALSE 0typedef char VertexTypeMAXVEX; /*存放顶点信息的字符串*/typedef float AdjType;typedef struct ArcNode int adjvex; /* 相邻顶点字段 */ AdjType weight; struct ArcNode *nextarc; /* 链字段 */ArcNode; /* 边表中的结点 */typedef struct VNode VertexTyp
12、e data; /* 顶点信息 */ ArcNode *firstarc;/* 边表头指针 */VNode,AdjListMAXVEX;/* 顶点表中的结点 */typedef struct AdjList vertices; int vexnum,arcnum;/* 图的顶点个数 */ALGraph;/* 求出图中所有顶点的入度，方法是搜索整个邻接表 */void FindInDegree(ALGraph G,int inDegree) int i; ArcNode *p; for(i=0;iG.vexnum;i+) inDegreei=0; /*顶点入度数组赋初值*/ for(i=0;ia
13、djvex+; p=p-nextarc; void makeNewAOV(ArcNode *p,int *indegree, int &top) int k; while(p) /* 删除以该顶点为起点的边 */ k=p-adjvex; indegreek-; if(indegreek=0) /* 将新的入度为零的边入栈 */ indegreek=top; top=k; p=p-nextarc; int topoSort(ALGraph G,int *topo) /*拓扑排序算法*/ ArcNode *p; int i,j,count=0,top=-1; int indegreeMAXVEX; FindInDegree(G,indegree); /* 求出图中所有顶点的入度 */ for(i=0;iG.vexnum;i+) if(indegreei=0) /* 将入度为零的顶点入栈*/ indegreei=top; top=i; while(top!=-1) /* 栈不为空 */ j=top; top=indegreetop; /* 取出当前栈顶元素 */ topocount+=j; /*ptopo数组存放拓扑序列*/ p=G.verticesj.firstarc;/取该元素边表中的第一个边结点，删除该结
