网络图绘制与关键路径.ppt

1 甘特图例子 2 甘特图优缺点 优点 每项活动时间定位非常准确 图形简单 清晰 缺点 活动之间关系不够清晰 活动的重要度不够明确 对大型复杂项目 甘特图显得不太适用 3 单代号网络图法 单代号网络图法 PDM PrecedenceDiagrammingMethod 节点法 顺序图法 大多数项目管理软件所采用 软件项目中PDM更通用 4 活动之间的逻辑关系 A结束后B才开始 FS 一种活动结束后 另一种活动才能开始这是应用最普遍的一种关系例如 软件的分析 设计 编码活动 B开始前A必须开始 SS 后续活动不需要等待前导活动结束后才开始这经常表示某种并行 但具有一定依赖关系的活动例如 软件的测试活动 往往依赖开发活动的结果 但又独立于开发活动 5 活动之间的逻辑关系 A结束前B必须结束 FF 例如 热水器安装 B 厨房粉刷 A A开始后B才结束 SF 这是一种最特殊的活动逻辑先后关系 即后续活动的结束依赖于前导活动的开始日常的生活中 例如 找到新的工作后 才可能放弃原来的工作 许多人再找到新爱后才会放弃旧爱 6 7 单代号网络图法特点 1 单代号搭接网络图必须正确表述已定的逻辑关系 2 单代号搭接网络图中 严禁出现循环回路 3 单代号搭接网络图中 严禁出现双向箭头或无箭头的连线 4 单代号搭接网络图中 严禁出现没有箭尾节点的箭线和没有箭头节点的箭线 5 绘制网络图时 箭线不宜交叉 6 单代号搭接网络图只应有一个起点节点和一个终点节点 当网络图中有多项起点节点或多项终点节点时 应在网络图的两端分别设置一项虚工作 作为该网络图的起点节点 St 和终点节点 Fin 8 单代号网络图法特点 1 工作之间的逻辑关系容易表达 绘图较简单 2 网络图便于检查和修改 3 由于工作持续时间表示在节点之中 没有长度 故不够形象直观 4 表示工作之间逻辑关系的箭线可能产生较多的纵横交叉现象 9 10 双代号网络图法 箭线式网络图 ArrowDiagrammingMethod 以箭线表示活动 每个活动都由两个数字来定义 节点代表关系虚活动我国应用比较多 国内采用该方法的软件较多 11 双代号网络图图例 12 如何编制进度计划 0建立企业和项目资源库1设置项目日历 资源日历2设置项目的主要里程碑点3在WBS下列出工作清单 Task Activity 4估计每个Task的工期5计算每个Task之间的逻辑关系6加载完成每个Task所需要的资源和资源数量7进度计算后 看开工 完工里程碑是否符合合同或业主要求 看资源负荷是否过大 8需要调整吗 9调整的方法 压缩关键路径上Task的工期 多投入资源以缩短工期 分解工期较长的作业10合适了吗 合适了 则把第一份计划保存为目标计划 Baseline 11公布第一版计划 通知项目干系人 13 关键路线 CPM从项目开始到结束占用时间最长的路线工作总时差为零的工作 也就是其开始时间或结束时间没有任何机动余地的工作 项目的总工期是由关键路线的工作总时间决定的CPM上任一节点若不按期完成 则整个计划的完工若要缩短项目的计划完工期限 应当设法缩短某个或某些关键工作的作业时间某个项目关键路线可能不止一条 14 正推法 Forwardpass 按照时间顺序计算最早开始时间和最早完成时间的方法 称为正推法 首先建立项目的开始时间项目的开始时间是网络图中第一个活动的最早开始时间从左到右 从上到下进行任务编排当一个任务有多个前置时 选择其中最大的最早完成日期作为其后置任务的最早开始日期公式 ES Duration EF 15 正推法实例 Start LF LS EF ES Duration 7TaskA 1 8 LF LS EF ES Duration 3TaskB 1 4 LF LS EF ES Duration 6TaskC 8 14 LF LS EF ES Duration 3TaskD 4 7 LF LS EF ES Duration 3TaskG 14 17 LF LS EF ES Duration 3TaskE 7 10 LF LS EF ES Duration 2TaskH 17 19 LF LS EF ES Duration 2TaskF 4 6 Finish 当一个任务有多个前置时 选择其中最大的最早完成日期作为其后置任务的最早开始日期 16 逆推法 Backwardpass 按照逆时间顺序计算最晚开始时间和最晚结束时间的方法 称为逆推法 首先建立项目的结束时间项目的结束时间是网络图中最后一个活动的最晚结束时间从右到左 从上到下进行计算当一个前置任务有多个后置任务时 选择其中最小最晚开始日期作为其前置任务的最晚完成日期公式 LF Duration LS 17 逆推图示 Start LF LS EF ES Duration 7TaskA 1 8 1 8 LF LS EF ES Duration 3TaskB 1 4 8 11 LF LS EF ES Duration 6TaskC 8 14 8 14 LF LS EF ES Duration 3TaskD 4 7 11 14 LF LS EF ES Duration 3TaskG 14 17 14 17 LF LS EF ES Duration 3TaskE 7 10 14 17 LF LS EF ES Duration 2TaskH 17 19 17 19 LF LS EF ES Duration 2TaskF 4 6 12 14 Finish 当一个前置任务有多个后置任务时 选择其中最小最晚开始日期作为其前置任务的最晚完成日期 CP A C G H CpPath 18 18 课堂练习 作为项目经理 你需要给一个软件项目做计划安排 经过任务分解后得到任务A B C D E F G 假设各个任务之间没有滞后和超前 下图是这个项目的PDM网络图 通过历时估计已经估算出每个任务的工期 现已标识在PDM网络图上 假设项目的最早开工日期是第 天 请计算每个任务的最早开始时间 最晚开始时间 最早完成时间 最晚完成时间 同时确定关键路径 并计算关键路径的长度 19 课堂练习 确定 以及 的长度 20 课堂练习 答案 4 4 10 4 12 12 19 19 24 12 20 24 27 27 24 24 24 16 19 19 12 12 6 12 4 4 0 CP A E C D G CPPath 27 21 1 边表示活动的网 ActivityOnEdgeNetwork 简称为AOE网 为带权有向无环图 其中 顶点表示事件 边表示活动 边的权值表示活动持续的时间 其中 AOE网中顶点表示的事件实际上体现了一种状态 即该顶点的所有入边表示的活动均已完成 出边表示的活动可以开始 关键路径程序实现 一 基本概念 22 2 源点 汇点 表示实际工程的AOE网应该只有一个入度为0的顶点和一个出度为0的顶点 前者称作为源点 后者称作为汇点 研究的问题 对于表示工程计划的AOE网 需要研究的问题是 完成整个工程至少需要多少时间 哪些活动是影响工程进度的关键 23 3 关键路径 由于AOE网中的若干活动是可以并行进行的 所以完成工程的最短时间是从源点到汇点的最长路径的长度 即最长路径上各边权值之和 从源点到汇点的最长路径称为关键路径 24 事件vj可能的最早发生时间ve j 应为从源点到顶点vj的最长路径长度弧表示的活动ai的最早开始时间e i 等于ve j 在不推迟整个工程完成的前提下 事件vk允许的最迟发生时间vl k 应等于汇点vn的最迟发生时间vl n 减去vk到vn的最长路径长度 弧表示的活动ai的最迟开始时间l i 等于vl k 减去弧的权值 4 ve j e i vl k l i 25 ve 5 11 vl 2 11 8 3e 1 0l 1 vl 2 3 0 26 5 关键活动 对活动ai而言 l i e i 为其在不延误整个工程工期情况下 可以延迟的时间 若e i l i 则称活动ai为关键活动 关键路径上的所有活动都是关键活动 缩短或延误关键活动的持续时间将提前或推迟整个工程的完工时间 27 二 如何求AOE网的关键活动 1 分析 由关键活动的定义可知 只要求出了某个活动的e i 和l i 便可判断该活动是否为关键活动 而为了求AOE网中活动的e i 和l i 首先需求网中所有事件的ve j 和vl j e i ve j l i vl k dut 因为 若活动ai由表示 其权值记为dut 则有如下关系 28 求ve j 和vl j 需分两步进行 1 从ve 1 0开始向前递推ve j max ve i dut 属于以vj为头的弧的集合 2 j n ve 1 0ve 2 3ve 3 max ve 1 2 ve 2 2 5ve 4 max ve 1 1 ve 3 3 8ve 5 max ve 2 8 ve 4 3 11 29 2 从vl n ve n 开始向后递推vl i min vl j dut 属于以vi为尾的弧的集合 1 i n 1 vl 5 11vl 4 vl 5 3 8vl 3 vl 4 3 5vl 2 min vl 3 2 vl 5 8 3vl 1 min vl 2 3 vl 3 2 vl 4 1 0 30 e i ve j l i vl k dut 31 2 求关键活动的算法 1 对AOE网进行拓扑排序 并按排序的次序求各顶点事件的ve值 若网有回路 则算法终止 否则执行步骤 2 2 按拓扑排序的逆序求各顶点事件的vl值 3 根据各顶点事件的ve值和vl值 求各活动ai的e i 和l i 若e i l i 则ai为关键活动 32 3 算法描述 StackTopologicalOrder ALGraphG StackT inti j k count StackS ArcNode p FindInDegree G indegree InitStack 33 intCriticalPath ALGraphG StackT inti j k dut ee el ArcNode p intvl n T TopologicalOrder G T for i 0 inextrc k p adjvex dut p info if vl k dutnextrc k p adjvex dut p info ee ve j el vl k dut tag ee el printf 34 双代号时标网络计划 双代号时标网络计划的概念双代号时标网络计划的时间参数计算 35 双代号时标网络计划的概念 1 基本符号 实箭线 水平投影长度表示工作的持续时间虚箭线 虚工作波形线 工作自由时差 36 双代号时标网络计划的概念 2 绘制规则按最早时间绘制 各工作的时间参数由其在时标表上的水平位置表示 各工作持续时间由其水平投影长度表示 自由时差由波形线表示 37 时标网络计划的时间参数计算 1 关键路线 没有波形线的路线2 时间参数的确定计算工期工作最早时间工作最迟时间工作总时差工作自由时差 38 1 请绘制网络图 确定关键路线 绘制各工序在最早时间开始时标网络图 综合作业