运筹学教学-关键路线法.ppt

第八章计划评审方法和关键路线方法 网络计划方法的产生 起源 网络计划方法是项目计划管理的重要方法 它起源于美国 当时 有两种网络计划方法 关键路线法和计划评审技术 1957年 美国杜邦化学公司用关键路线法 CriticalPathMethod 当年就节约100万美元 为该公司用于该项目研究费用的5倍以上 1958年 美国海军当局在研制北极星导弹潜艇时 第一次采用了BuzzAllen提出的计划评审技术 ProgramEvaluationandReviewTechnique 主要承包商200多家 转包商10000家 23个系统网络 每两周检查一次 原定6年 提前两年完成 节约经费10 15 60年代耗时11年阿波罗登月计划3000亿 42万人 2万家公司 120所大学 600台计算机 700万零件 终于在1969年7月 阿波罗11号船长阿姆斯特朗登上月球 60 70年代我国开始应用和推广 钱学森 华罗庚等都曾为此做了大量工作 华罗庚的例子 有客来访 要请他饮茶 于是要做几件事 洗茶杯 洗杯盖 烧开水 泡茶到端茶 客来沏茶 本问题的几道 工序 有次序 时间 2 5 1 0 2 0 5 第一节PERT网络图 网络图由三大要素构成 节点 事件 箭线 作业 和路线 1 3 2 一 网络图构成 箭线 1 代表计划中的一项作业或工序 包括人力 财力 物力的付出 2 作业的内容可大可小 可多可少 3 箭尾表示作业开始 箭头表示作业结束4 通常把作业的代号和作业所耗时间标在箭线的上下 5 虚箭线 不占用时间和空间 不消耗任何资源 只是为了明确活动的相互之间的逻辑关系 3 4 A10 A i j A 作业活动代号 结点 表示事件 网络图中两条或两条以上的箭线的交接点就是结点 结点代表的作业开始和结束 用圆圈加上数字表示 路线 从网络图的始点事件开始到终点事件为止 由一系列首尾相连的箭线和结点所代表的作业和事件所组成的通道 网络图一般有多条路线 其中最长的我们称之为关键路线 关键路线上的工序为关键工序 错误 正确 PERT图的开始节点与结束节点均应是唯一的 二 绘制PERT图的原则 如果在实际工作中发生不吻合时 应将没有紧前作业的结点用虚箭头线同网络始点事项连接起来 将没有后续事项的结点用虚箭头同终点事项边接起来 在相邻的两个节点之间 最多只能有一条箭线相连 进入某一个结点的箭线可以有多条 但其它任何结点直接连接该结点的箭线只能有一条 两个相邻结点间只允许有一条箭线直接相连 若有平行活动 可引入虚线以保证这一规则不被破坏 网络图中不能出现循环回路 节点编号时 按照矢线箭头的指向 升序排号 保证节点序号先后关系保持一致 应将各作业的工时数据标注在表示该作业的矢线的下面 正确使用虚工序 不消耗资源 一般表示平行工作关系 三 PERT图的绘制步骤 先画草图 再修改后变成规范图 步骤如下 根据活动清单中规定的关系 将活动代号栏所有的活动逐次地画在网络图上 从左到右 理顺活动的紧前 紧后关系 没有紧后活动的活动所对应的箭线汇集在终止结点上 草图绘制完成后 将序号标在结点上 将活动代号和时间标在箭线上 检查无误后 将草图绘制成规范图 例 某项工程任务经分解后 确定由9项作业构成 各项作业的代号 紧前作业及作业时间如表所示 画出网络图 14 例 建筑一幢房屋 施工顺序如上表所示 要求计算工程周期及关键路线 某机械厂管理信息系统开发活动清单 例 四 PERT图的分类 1 按工时估计的性质 A 确定型网络 每个工作的预计工时只估一个值 即 这些工作的实际完成情况一般地可按预计工时达到 也即实现的概率等于或近似等于1 B 概率型网络 每个工作按三种情况下给定工时 最快可能完成工时 最可能完成工时 最慢可能完成工时 五 PERT图的计算 1 工作时间tij的确定 确定型 利用已知的工时定额资料给出 概率型 对于开发性任务 或对工作所需的工时难以准确估计时 可采用三点时间法来确定工作的工时 则实际计算中 完成一项作业的期望工时t i j 按如下公式计算 设 a是最乐观的时间估计值 m是最可能的估计值 b是最悲观的时间估计值 方差为 2 结点 事项 的时间参数确定 1 节点的最早时间 它表明以它为始点的各工作最早可能开始的时间 也表明以它为终点的各工作的最早可能完成时间 等于从始点结点到该结点的最长路线上所有工作的工时总和 递推公式 整个工程的总最早完工期 2 节点的最迟时间 它表明在不影响任务总工期的条件下 以它为始点的各工作最迟必须开始的时间 也表明以它为终点的各工作的最迟必须完成时间 由于 一般都把任务的最早完工时间作为任务的总工期 所以结点的最迟时间递推公式为 3 工作的时间参数确定 1 作业的最早可能开始时间 ES 是指作业最早可能开始的时间 是它的各项紧前作业最早结束的时间中最大的一个 2 作业的最早可能结束时间 EF 是指作业按最早开工时间开始所能达到的完工时间 3 作业的最迟必须开工时间 LS 是指作业 i j 在不影响整个任务如期完工的前提下 必须开始的最晚时间 4 作业的最迟必须结束时间 LF 是指作业 i j 按最迟时间开工 所能达到的完工时间 4 时差 按性质可以分为作业的总时差R i j 和作业的自由时差F i j 总时差 在不影响任务总工期的条件下 某工作 i j 可以延迟其开工时间的最大幅度 这是网络上多于一项作业共同拥有的机动时间 并非为某项作业单独拥有 工作 i j 的总时差等于它的最迟完工时间与最早完工时间的差 也等于它的最迟开工时间与最早开工时间的差 自由时差 不影响它的各项紧后作业最早开工时间条件下 该项作业可以推迟的开工时间的最大限度 它是一项作业独自拥有的机动时间 即自由时差等于其紧后作业的最早开工时间与本工作的最早完工时间的差 下图是一个工程施工图 请依次求出各时间参数 时间参数计算举例 1 结点时间参数 方括号 最早时间 三角 最晚时间 2 作业时间参数 方括号 最早开工时间 三角 最晚开工时间 3 总时差 自由时差 中括号 总时差 园括号 自由时差 说明 1 由关键路线的意义知 这条线在时间上没有回旋余地 即每个关键工作应满足 最早开工时间 最迟必须开工时间 而非关键路线则有富裕时间 所以 总时差为0的工作链就是关键路线 此处为 2 比较总时差和自由时差的关系 工作 1 7 有自由时差13 若把它拖至13周开工 对它后面的工作的最早开工时间及时差等都没有影响 对整个工期也没有影响 而只有总时差没有自由时差的工作则不然 若工作 7 8 总时差为1 自由时差为0 如果让它推迟1周开工 虽然总工期不受影响 但其后面的工作最早时间及时差都要受影响 所以使用时差来调整工作时 应尽量先用自由时差 PERT例题 客来沏茶 PERT解法 最早完成时间 最晚开始时间 洗杯盖2端茶0 5烧水5泡茶2洗杯1虚0 0 1 5 7 7 5 7 5 7 5 5 0 5 5 最佳次序 先烧开水 等待水开之时洗杯 盖 水烧开后泡茶 端茶 例 某人于早晨7 00起床 按其生活习惯 在其出门工作前 必须完成下列活动 5分钟时间穿衣服 洗脸4分钟 10分钟烧开一壶开水 5分钟取牛奶 5分钟热牛奶 5分钟吃饭 试问此人最早何时可以出门上班 假定只有一个炉灶 1 利用正推计算确定活动的最早完工时间 2 利用逆推计算确定活动的最迟开工时间 3 确定关键工作与关键线路 网络图图解法计算 1 2 4 3 5 6 穿衣5 烧开水10 热奶5 吃饭5 洗脸 4 取奶 5 0 9 15 5 20 25 0 5 15 20 25 10 例题 0 0 3 3 7 12 9 9 14 14 17 20 20 20 23 23 28 28 31 31 的先驱元素是 的先驱元素是 的先驱元素是 的后继元素是 的后继元素是 发点 收点 表示所有点 i j 表示一项作业 n表示最大结点编号即终点 TES 1 0 TES i j max TES i t i TEF i j TES i j tijTLF n max TEF n TLF i j min TLF j tj TLS i j TLF i j tij 1 2 3 4 A2 B7 C20 D12 0 2 2 9 2 22 9 21 0 2 3 10 10 22 2 22 黑色表示作业长度tij 红色表示ES和EF 蓝色表示LS和LF 例题 第二节关键路线与网络计划的优化 路线时间最长的网络路线为关键路线 关键路线上的工序称为关键工序 不在关键路线上的工序为非关键工序 网络图的优化与调整 通过绘制网络图 计算时间参数 确定关键路线 得到的仅是一个初步计划方案 为了得到从各方面都较好的方案 一般一项工程或任务的网络计划 往往要根据项目的要求综合考虑时间 资源和费用等目标 对初始方案进一步改善和调整 进行网络优化 确定最优的方案 求得最佳效果 4 工期不变的条件下 如何使所用资源最少 资源优化 1 缩短网络计划工期 时间优化 2 降低人力使用高峰 使其符合人力供应能力 并使各工种人员中的使用连续均衡 且工期最短 时间 资源优化 3 缩短工期并使费用增加最少 时间费用优化 在网络系统中 关键线路决定总工期 当规定的工期大于关键线路上工序时间总和时 关键线路上各工序的总时差就会出现正值 说明完成该项任务的时间较宽余 必要时可适当延长某些工序的时间 以便减少资源或节省费用 反之 任务比较急时 规定的工期会小于总工期 则需对网络进行调整 对超过规定工期的各条线路上的某些工序 通常在组织上和技术上可采用的方法有如下几种 1 时间优化 缩短网络计划工期 a 在关键线路上寻找最有利的工序来缩短其作业时间 b 可能条件下采取平行交叉工序缩短工期 c 搞技术改造 或增加人力 物质设备等多种措施 缩短某些工序的延续时间 d 利用时差 从非关键线路上抽调适当的人力 物力集中于关键路线 以缩短关键路线的持续时间 以上几种缩短工期方法在使用过程中 会随时引起网络计划的改变 每次改变后都要重新计算网络时间和确定关键路线 直到求得最短周期为止 例图1是某工程的网络图 初始方案计划时间为19周完成 现因特殊情况 上级要求提前3周完工 即总工期压缩为16周 试对网络进行调整 解 1 计算工序的时间参数 找出关键线路 如图1 双箭线的工序组成的线路为关键线路 注 方括号内 作业最早开始时间 三角内 最迟开始时间 2 缩短工期的计算 首先将终点事项 的最迟结束时间定为16周 从右向左逐个求出各工序的最迟开始时间tLS 标在图2相应箭线下方的 内 同时求出各工序总时差 用 括起来放于相应工序下方 图中方括号内的数字为总工期16周时 各工序的总时差 从计划的结果可看出 在原先的关键路线上各工序的总时差为 3 这意味着原来的关键路线上应缩短3周 而其他非关键线路上也出现负时差 即在这些线路上也要进行日期的缩短 需要缩短日期的线路和工序有 线路时差 1 3 2 2 3 1 首先考虑关键线路即线路 上缩短3周 不妨在 上各缩1周 缩短后 通过网络时间参数的计算 其结果如图所示 由上图可知 绝对值最大的负时差线路为 现在其中任一工序上压缩1周 比如 改为5周 再计算时间参数 可知负时差已全部消灭 如图所示 6压缩为5 这时总时差为0的线路有三条 和 它们均是关键线路 总工期为16周 符合规定的要求 网络计划的时间 资源优化 是指对时间和其他资源进行统筹安排 达到特定的工程要求 往往要求在有限的资源条件下合理分配资源 既满足各项活动对计划的需求 又确保整个工程项目在尽可能短的时间内完成 包括以下几个方面 2 时间 资源优化 1 先安排关键工程所需资源 2 错开非关键工序的开始时间 使工程各时段对资源的需求趋于平衡 3 为达到总体效益最佳 必要时可适当延长总工期 例某市防疫站从下属单位抽调部分人员 进行一项疫情调查 整个工作可分许多阶段 工序 各阶段所需的时间和人员数量不等 具体见表1 问各阶段工作应如何合理安排 才可以使人力的使用最合理 表1各工序所需的时间和人员数量 此时 关键路线为 a e f h i 时间为14天 如果不做任何调整 按照正常的时间安排工作 则1 2天做a b c d 需要26人 3 4天做d e g 需要27人 第5天做f g 需要12人 6 7天做f 需要3人 8 11天做h 需要2人 12 14天做i需要12人 结果见下图 考虑时差 可调整d的工作 让它延迟到第8天开工 人数安排变为 继续调整g的工作 让它延迟到第5天开工 人数安排变为 继续调整b的工作 让它延迟到第3天开工 人数安排变为 结论 最少安排12人 工程所需时间与工程所需费用是一对矛盾 一般情况下 缩短一道工序时间 就要采取一些措施 如加班 增加设备等 需要增加一定费用 同时也会得到一些收益 如节约了管理费用等 要想缩短整个工程的工期 必须从两方面考虑 1 要分析缩短工期所需代价 2 要分析缩短工期带来得收益 在一定条件下 达到工程时间与工程费用的最佳结合是网络计划时间 费用优化工作的关键 3 时间 费用优化 1 费用与时间的关系工程所需费用 基本上分为两大部分 直接费用 完成工序直接有关的费用 如人力 机械 原材料等费用 间接费用 管理费 设备租金等 是根据各道工序时间按比例分摊的 工序时间越少 间接费用就越少 反之 工序时间越多 间接费用就越多 工程总费用W就是直接费用U与间接费用V的总和 即 W U V 工程费用与完工期之间的关系可用下图表示 从图中可看出 在正常工期和最短工期 缩短工期的最低限度 也简称赶工时间 之间 存在着一个最优工期 此时总费用最少 这个时间称为最少工程费日程 从关键路线入手 找出最少工程费日程的方法 就是关键路线法 CPM 假设工序的直接费用与工序时间是线性关系 设工序k每赶一天进度所需要增加的费用为q k 则 式中q k 为费用斜率 c为赶工所需费用 n为正常完工所需费用 nt为正常完工所需时间 ct为赶工时间 2 时间 费用优化的计算 显然 费用斜率越大的工序 每缩短一天 花的费用就越多 在考虑缩短工程工期时 当然是要缩短各关键工序中的某一道或某几道工序的工期 而选择缩短哪道工序要以总费用最省为根据 时间 费用优化的计算 首先应确定工期与直接费用的关系 即先对全部工序按正常时间计算参数 求出网络图的关键路线 工程周期和相应的直接费用 工程项目的总费用 正常完工的直接费用 赶工增加的费用 间接费用 其次逐次压缩费用增长率q最小的关键工序延续时间 使直接费用的增加最小 压缩网络时 按下面原则进行 a 压缩关键线路上费用增长率最小的工序时间 以增加最少的费用来缩短工期 b 在选择压缩某项工序的延续时间时 既要满足工序费用一时间变化关系的限制 又要考虑网络中和该作业并列的各工序时差数的限制 应取这两个限制的最小值 c 当网络图不断压缩出现数条关键路线时 继续压缩工期 需要同时缩短这数条路线 仅缩短一条线路不会达到缩短工期的目的 下面以例子说明通过缩短关键路线上工序时间来寻求最少工程费日程的方法 例某项工程根据有关资料 计算出了费用斜率如表2 试制定该工程的最少工程费计划方案 表2工程的有关资料及费用斜率 图1 a 解根据表2 可绘出统筹图1 a 按正常时间完工需25天 所需总费用为 14900 500 25 27400元 图1 b 若使工程工期最短 即将所有工序时间都压缩到其可能的最短时间 看其费用情况如何 这时 统筹图如图1 b 所示 工程完工期为17天 其赶工增加费用 c n 为 3 400 1 200 1 200 1 300 2 300 3 500 3 100 1 400 4700元 总费用 14900 4700 500 17 28100元 显然费用太大 不是最优 分析按正常时间完工的计划方案 找出最少工程费方案 由图2 a 可以看出 在按正常时间完工的统筹图中 有两条关键路线 图2 a 要缩短工期 就要缩短关键工序的时间 首先考虑压缩关键线路上费用增长率最小的工序时间 以增加最少的费用来缩短工期 在上述两条关键路线的情况下 缩短哪道关键工序 分析如下 图1 a 两条关键路线在结点3和结点6之间有并联部分 关键工序为a d e f g和h 其中工序a h为两条关键路线所共有 要缩短工期 在费用最小的情况下 首先考虑缩短共有的关键工序 其次考虑结点3和结点6之间的各关键工序d e f和g 因为它们之间是并联的 所以要想缩短工程的工期 必须在d f中和e g中 各压缩一道工序的时间 这样 它们就有4种可能的组合 综合以上组合及费用情况可通过下表考虑选择 从上表比较可知 费用增长率最小的工序或工序组合为a h d和g 这三者中首先考虑缩短两条关键路线所共有的关键工序a h 不妨先缩短关键工序h 每缩短1天 需增加费用400元 但节省间接费500元 净省费用100元 因此 把工序h压缩到最低限度4天 同时 总费用减为27300元 表3几种可能缩短的工序或工序组合 然后再考虑压缩工序a 与压缩工序h一样 每压缩1天 总费用净省100元 但此处需注意 工序a不能压缩到其最低时间限度7天 因为当工序压缩2天时 工序时间为8天 这时工序b和工序c就都变成了关键工序 这样 在结点1和结点3之间 也出现了并联的关键路线部分 继续单独压缩工序a 已不能缩短整个工程的工期 因此 只能把工序a压缩为8天 总费用减为27100元 最后 将工序d和工序g各压缩1天 总费用减为27000元 由于工序d的限制 不能进一步压缩了 综合起来 最少工程费计划方案 按下列要求去做 将工序a压缩为8天 将工序d压缩为3天 将工序g压缩为4天 将工序h压缩为4天 其它工序b c e和f仍按正常时间进行 这样得到的最少工程费日程为21天 总费用为27000元 其统筹图如图1 c 所示 图1 c 第三节完成作业的期望时间 在规定时间内实现事件的概率 在实际计算中 完成一项作业的期望时间Et i j 按如下公式计算 其中 a是最乐观的时间估计值 m是最可能的估计值 b是最悲观的时间估计值 例 一项工程项目由9个作业组成 各作业间的逻辑关系以及工期信息见表 1 绘制相应的网络 2 用表格计算法找出关键线路 并预测该项目的总工期 解 1 绘制相应的网络图见图 1 2 3 4 5 6 7 A4 B6 C3 D5 H6 E6 F2 G6 I5 4 5 4 6 6 2 4 4 6 6 5 6 4 7 6 4 6 4 8 6 计算出工期的均值 如下表中的工期ET 计算时间 得下图 找出关键线路 预测该项目的总工期为24周 也可以用后面的表表示 如果该项目的计划工期为26周 则按期完工的可能性有多大 为计算方便 我们假定每个事件的最早实现时间服从正态分布 此假定对最终事件的完成时间是基本正确的 即事件3的正态分布的中心为 方差 假定事件k的最早实现时间的期望和方差已知 则事件k的实现时间Tk小于规定期限Tdk的概率为 1 下表给出一个汽车库及引道的施工计划 请解答 1 该工程从施工开始道工程结束的最短周期 2 如果引道混凝土施工工期拖延10天 对整个工程进度有何影响 3 若装天花板的施工时间从12天缩短为8天 对整个工程进度有何影响 4 为保证工期不拖延 装门这项作业最晚应从哪一天开工 5 如果要求该工程必须在75天内完工 是否应采取措施 应采取什么措施 决策分析 1 某钟表公司计划通过它的销售网销售一种低价钟