关键路径与最短路径-C_第1页
关键路径与最短路径-C_第2页
关键路径与最短路径-C_第3页
关键路径与最短路径-C_第4页
关键路径与最短路径-C_第5页
已阅读5页，还剩9页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

关键路径

对整个工程和系统，人们关心的是两个方面的问题：

1）工程能否顺利进行对AOV网进行拓扑排序

2）估算整个工程完成所必须的最短时间对AOE网求关键路径AOE-网AOE－网(ActivityOnEdgeNetwork)：即边表示活动的网。AOE网是一个带权的有向无环图。其中：顶点表示事件（Event）弧表示活动（Activity）权值表示活动持续的时间通常可用AOE网来估算工程的完成时间。上图AOE-网中：共有11项活动：a1,a2,a3,…a11；共有9个事件：v1,v2,v3,…v9，每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。v9表示整个工程的结束v5表示a4和a5已经完成，a7和a8可以开始与每个活动相联系的数是执行该活动所需的时间v1表示整个工程的开始

由于整个工程只有一个开始点和一个完成点，在正常的情况（无环）下，网中只有一个入度为零的点（称作源点）和一个出度为零的点（称作汇点）汇点源点依据AOE-网可以研究什么问题？（1）完成整项工程至少需要多少时间？（2）哪些活动是影响工程进度的关键？

完成工程的最短时间是从源点到汇点的最长路径的长度。路径长度最长的路径叫做关键路径。从v1到v9的最长路径是（v1,v2,v5,v8,v9），路径长度是18。

假设开始点是v1，从v1到vi的最长路径长度叫做事件vi的最早发生时间。这个时间决定了所有以vi为尾的弧所表示的活动的最早开始时间。用e(i)表示活动ai的最早开始时间。V9的最早发生时间是18事件vi的最早发生时间l(i)－e(i)两者之差意味着完成活动ai的时间余量。我们把l(i)＝e(i)的活动叫做关键活动。显然，关键路径上的所有活动都是关键活动，因此提前完成非关键活动并不能加快工程的进度。a6的最早开始时间是5，最迟开始时间是8。如a6推迟3天开始或延迟3天完成，都不会影响整个工程的完成。

人人文库> 全部分类> 专业文献 > 医学资料

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论