运筹学第07讲 计划评审技术

运筹学 讲授 毕德春辽东学院信息技术学院信息管理系 第07讲计划评审技术 第一节计划评审技术概述第二节第三节第四节第五节 第一节计划评审技术概述 1956年 美国杜邦公司在制定企业不同业务部门的系统规划时 制定了第一套网络计划 这种计划借助于网络表示 各项工作与所需要的时间 各项工作的相互关系 分析研究工程费用与工期的相互关系 找出在编制计划时及计划执行过程中的关键路线 这种方法称为关键路线法 CriticalPathMethod 简称CPM 引言 计划评审技术概述 1958年 美国海军武器部 在制定研制 北极星 导弹计划时 同样地应用了网络分析方法与网络计划 它注重于对各项工作安排的评价和审查 这种计划称为计划评审方法 ProgramEvaluationandReviewTechnique 简称为PERT 引言 计划评审技术概述 国内外应用计划评审方法的实践表明 具有一系列优点 特别适用于生产技术复杂 工作项目繁多 且联系紧密的一些跨部门的工作计划 例如新产品研制开发 大型工程项目 生产技术准备 设备大修等计划 还可以应用在人力 物力 财力等资源的安排 合理组织报表 文件流程等方面 引言 计划评审技术概述 计划评审技术 把项目当作一个系统 采用网络图和矩阵表的形式表示各具体活动的先后顺序和相互关系 以时间为中心 以完工期限为主要约束条件 找出从开工到完工所需时间最长的关键路线 围绕关键路线 对系统进行统筹规划 合理安排 对各项活动的完成进度严密控制 达到用尽可能少的时间和资源消耗完成系统预定目标的一种进度计划与控制方法 引言 计划评审技术概述 例 某项研制新产品工程的各个工序与所需时间以及它们之间的相互关系如表所示 要求编制该项工程的网络计划 引例 计划评审技术概述 1 2 a 65 b 45 c 10 d 20 40 e 引例 计划评审技术概述 1 2 4 6 7 3 5 a 65 45 c 10 d 20 e 40 f g l 0 b 8 h 引例 计划评审技术概述 引例 计划评审技术概述 网络计划的基本概念 计划评审技术概述 工序 或叫作业 活动 任何需要一定的人力 物力等资源和时间的行动 它是指为了完成工程项目 在工艺技术和组织管理上相对独立的工作或活动 实工序 需要时间的工序 可能不需要人力 物力 虚工序 工时为0的工序 不需要人力 物力 不存在 表明工序间的逻辑关系 事项工序都有两个事项 开工事项 完工事项 工序 i j 的开工事项 工序 i j 的完工事项 网络计划的基本概念 计划评审技术概述 只有在a工序结束以后 b cd e工序才能开始 a工序是b c d e等工序的紧前工序 而b c d e等工序则是工序a的紧后工序 网络计划的基本概念 计划评审技术概述 第二节网络计划的绘制 网络图是有向图 按照工艺流程的顺序 规定工序从左向右排列网络图中的各个结点都有一个时间 某一个或若干个工序开始或结束的时间 一般按各个结点的时间顺序编号 为了便于修改编号及调整计划 可以在编号过程中留出一些编号 始点编号可以从1开始 也可以从0开始 网络计划的绘制原则 网络计划的绘制 任一工序有且仅有两个事项 直接连结两个事项的箭杆只能有一根 错误 正确 网络计划的绘制原则 网络计划的绘制 网络图中不能有缺口和回路 在网络图中 除始点和终点外 其它各个结点的前后都应有弧相连接 即图中不能有缺口 使网络图从始点经任何路线都可到达终点 否则 将使某些工序失去与其紧后 或紧前 工序应有的联系 不可能有循环现象 否则 将使组成回路的工序永远不能结束 工程永远不能完工 错误 错误 网络计划的绘制原则 网络计划的绘制 只能有一个始点和一个终点 有2个始点 3个终点 显然是错误的 1 2 3 4 6 5 7 8 2 4 3 1 3 2 1 正确 网络计划的绘制原则 网络计划的绘制 网络图的绘制示例 网络计划的绘制 A 4 B 6 C 6 D 7 E 5 G 7 F 9 H 4 I 8 例 某工程的工序一览表如下 试绘制网络图 例 某工程的工序一览表如下 试绘制网络图 网络图的绘制示例 网络计划的绘制 例 某工程的工序一览表如下 试绘制网络图 网络图的绘制示例 网络计划的绘制 网络图的绘制示例 网络计划的绘制 第三节关键路线法 路线 在网络图中 从始点开始 按照各个工序的顺序 连续不断地到达终点的一条通路称为路线 路线 关键路线法 路线 关键路线法 1 2 4 6 7 8 3 5 a 65 45 c 10 d 20 e 40 f 18 g 30 h 15 k 25 l 35 0 b 路线 关键路线法 1 2 4 6 7 8 3 5 a 65 45 c 10 d 20 e 40 f 18 g 30 h 15 k 25 l 35 0 b 路线 关键路线法 1 2 4 6 7 8 3 5 a 65 45 c 10 d 20 e 40 f 18 g 30 h 15 k 25 l 35 0 b 路线 关键路线法 1 2 4 6 7 8 3 5 a 65 45 c 10 d 20 e 40 f 18 g 30 h 15 k 25 l 35 0 b 路线 关键路线法 关键路线 在各条路线上 完成各个工序的时间之和是不完全相等的 其中 完成各个工序需要时间最长的路线称为关键路线 或称为主要矛盾线 关键路线 关键路线法 1 2 4 6 7 8 3 5 a 65 45 c 10 d 20 e 40 f 18 g 30 h 15 k 25 l 35 0 b 关键路线 关键路线法 关键路线 如果能够缩短关键工序所需的时间 就可以缩短工程的完工时间 而缩短非关键路线上的各个工序所需要的时间 却不能使工程的完工时间提前 即使在一定范围内适当地拖长非关键路线上各个工序所需要的时间 也不至于影响工程的完工时间 编制网络计划的基本思想就是在一个庞大的网络图中找出关键路线 对各关键工序 优先安排资源 挖掘潜力 采取相应措施 尽量压缩需要的时间 关键路线 关键路线法 对非关键路线上的各工序 只要在不影响工程完工时间的条件下 抽出适当的人力 物力等资源 用在关键工序上 以达到缩短工程工期 合理利用资源等目的 在执行计划过程中 可以明确工作重点 对各关键工序加以有效控制和调度 关键路线 关键路线法 关键路线是相对的 也是可以变化的 在采取一定的技术组织措施之后 关键路线有可能变为非关键路线 而非关键路线也有可能变为关键路线 关键路线 关键路线法 36 例 某项目活动清单如下 试绘制网络图 找出关键线路 并计算其工期 B C E D F G A 0 6 13 15 15 max 6 3 15 19 26 26 19 15 15 max 15 4 15 3 min 19 3 15 13 6 0 min 15 3 13 7 关键路线 关键路线法 37 例 某工程作业清单如下 试绘制网络图 找出其关键线路 并计算工期 H I G D F E C A B 0 4 5 11 14 17 15 15 22 22 17 20 17 14 18 11 0 5 关键路线 关键路线法 第四节关键路线法 例1为筹建某餐馆 需制定计划 将工程分为14道工序 各工序需时及先后关系如下表 试求该工程完工期T及关键路径 网络计划图的时间参数计算 网络图中工作的时间参数 它们是 工作持续时间 D 工作最早开始时间 ES 工作最早完成时间 EF 工作最迟开始时间 LS 工作最迟完成时间 LF 工作总时差 TF 工作自由时差 FF 工作持续时间 D 作业时间Ti j 单时估计法 定额法 每项工作只估计或规定一个确定的持续时间值的方法 一般具有工作的工作量 劳动定额资料以及投入人力的多少等 计算各工作的持续时间 工作持续时间 Q 工作的工作量 以时间单位表示 如小时 或以体积 重量 长度等单位表示 R 可投入人力和设备的数量 S 每人或每台设备每工作班能完成的工作量 n 每天正常工作班数 或具有类似工作的持续时间的历史统计资料时 可以根据这些资料 采用分析对比的方法确定所需工作的持续时间 三时估计法 在不具备有关工作的持续时间的历史资料时 在较难估计出工作持续时间时 可对工作进行估计三个时间值 然后计算其平均值 这三个时间值是 乐观时间 在一切都顺利时 完成工作需要的最少时间 记作a 最可能时间 在正常条件下 完成工作所需要时间 记作m 悲观时间 在不顺利条件下 完成工作需要最多时间 记作b 显然上述三种时间发生都具有一定的概率 根据经验 这些时间的概率分布认为是正态分布 一般情况下 通过专家估计法 给出三时估计的数据 可以认为 工作进行时出现最顺利和最不顺利的情况比较少 较多是出现正常的情况 按平均意义可用以下公式计算工作持续时间值 工作最早开始时间ES和工作最早完成时间EF工作的最早开始时间ES是紧前工序最早结束时间 ES TE i EF ES tij工作最迟开始时间LS与工作最迟完成时间LF工作的最迟完成时间LF是工作在不影响工期下最迟结束时间 LF TL j LS LF TL j 最后一项工作的最迟完成时间LF等于其最早完成时间EF 工序 i j 的时间参数 事件最早可能发生时间Te i 事件最迟必须发生时间Tl 网络时间的图示法 1 节点时间 事件时间 事件最早可能发生时间TE 顺向求和取大事件最迟必须发生时间TL 反向求差取小 TE j Max TE i tij TE 1 0 TL i Min TL j tij TL n TE n TE i 2 工序时间 工序A 3 工作时差 指工作有机动时间 工作总时差TF i j 在不影响工期的前提下 工作所具有的机动时间 工序A 总时差为零的工序即关键工序 LS ES LF EF 2 工作自由时差FF i j 在不影响其紧后工作最早开始的前提下 工序最早可能完工时间所具有机动时间 工序A 3 工作安全时差SF i j 在不影响其紧后工作的最迟开始的前提下 工作所具有机动时间 工序A 2 求完工期 用标号法 C 1 B 3 A 10 D 2 2 E 7 3 F 3 4 G 5 5 H 4 6 I 4 J 3 7 I 0 8 K 6 L 3 9 I 0 M 4 10 N 7 11 顺向求和取其大 3 求关键路 用标号法 9 Min 25 34 反向求差取其小 完工期T 38 天 关键路 D E F G H I K N 课堂习题 求下面网络计划图中的关键路径和完工期 要求使用标号法 给出节点的TE和TL 工序的ES EF LS LF以及总时差TF和自由时差FF 小结 虚工序的网络时间也应计算 以判断其是否为关键工序 虚工作为无机动时间的关键工作 否则该虚工作即为有机动时间的非关键工作 关键工序有2条 ADEGI和ADFHI完工期TE为19天 i TETL TFFF 二 工序时间不确定的工程计划网络问题 计划评审技术PERT 关键工序的平均工序时间之和 关键工序时间方差之和 例2某工程可分为11项工作 有关资料如下表 1 画出施工网络图 确定关键路线及完工期TE 2 估计工程在20周内完工的概率 期望工期TE 19 关键路 A D J K 0 6293 工程在20周内完工的概率为0 6293 课后作业 P30711 1 某项工程有关资料如下表 要求 1 画出工程网络图