数学模型3-3关键路径分析.pdf

3 3 关键路径分析 CPA 和计划3 3 关键路径分析 CPA 和计划 评审技术 PERT 评审技术 关键路径分析算法关键路径分析算法 赶工优化问题 引言引言 中学课本华罗庚先生的篇文章统筹方 中学课本华罗庚先生的一篇文章 统筹方 法 如何有效地安排各项活动的顺序 历史 CPM 1956年 美国杜邦公司 CPM1956年 美国杜邦公司 PERT 1958年 美国海军特种计划局 PDM Precedence Diagramming Method PDM Precedence Diagramming Method 1964年 美国IBM公司 现代应用项目管理TCP IP网络分析 现代应用 项目管理 TCP IP网络分析 项目管理项目管理 数采集 数据采集 项目活动组成 项目活动组成 每项活动和其他活动之间的依存关系 每项活动需要延续的时间 每项活动需要延续的时间 目标 如何安排项目活动最节约时间 最 经济经济 个例子一个例子 编号活动前期活动延续时间 1地基无4 01地基无4 0 2挖沟无1 7 3管线22 0 4砌砖1 2 315 04砌砖1 2 315 0 5喷绘44 8 6木工48 46木工48 4 7屋顶610 0 图形表示图形表示 Activity on arc AOA Activity on node AON AOA 表示AOA 表示 每的边表 每项活动以图形的边表示 活动的延续时间作为边的权活动的延续时间作为边的权 节点代表两个活动间的连接点 人为加入 开始 和 结束 节点 需要加入空边以表示活动的依存关系 AOA 表示 例子AOA 表示 例子 s 地基4 喷绘4 8 s t 挖沟1 7 砌砖15 木工8 4 挖沟1 7 管线 2屋顶10 这里粉红色的线不代表任何活动 只是为了 表示活动的依存关系表示活动的依存关系 AON 表示AON 表示 每个点代表 每个节点代表一项活动 有向弧表示活动之间的依存关系 表示一有向弧表示活动之间的依存关系 表示 项活动是另一项活动的前提条件 顶点的值表示活动延续时间 顶点的值表示活动延续时间 人为引进 开始 和 结束 节点 人为引进开始和结束节点 AON 表示例子AON 表示 例子 4 0 4 8 地基 喷绘 15 4 8 开始 砌砖 结束 挖沟 管线 木工 屋顶 管线 1 7 2 0 8 4 10 2 0 总工期问题总工期问题 从开工到结束至少需要多长时间 从开工到结束至少需要多长时间 说明 乍一看似乎是一个最 短 路径问 题 但由于PERT图的特殊性 只有当前的题 但由于PERT图的特殊性 只有当前的 活动结束后后面的活动才能 实际上是一 个求最长轨道的问题个求最长轨道的问题 关键路径算法求解 关键路径算法 CPM 求解 关键路径算法 CPM 关键路径算法 CPM 初始 初始化 递归 终止 如果v t 停止 实例演示 初始化实例演示 初始化 地基4喷绘4 8 s t 地基4喷绘4 8 0 挖沟1 7 管线 2 砌砖15 木工8 4 屋顶10管线 2屋顶10 实例演示 递归 1 实例演示 递归 1 地基4喷绘4 8 4 s t 地基4喷绘4 8 0 挖沟1 7 管线 2 砌砖15 木工8 4 屋顶10管线 2屋顶10 1 71 7 实例演示 递归 2 实例演示 递归 2 4 地基4喷绘4 8 4 s t 地基4喷绘4 8 木工8 4 0 4 屋顶10 挖沟1 7 管线 2 砌砖15 木工8 4 屋顶10管线 2 1 7 实例演示 递归 3 实例演示 递归 3 4 s t 地基4喷绘4 8 0 4 s t 挖沟1 7 砌砖15 木工8 4 0 19 屋顶10 挖沟1 7 管线 2 1 71 7 实例演示 递归 4 实例演示 递归 4 4 23 8 s 地基4喷绘4 8 0 4 s t 挖沟1 7 砌砖15 木工8 4 0 19 屋顶10 挖沟1 7 管线 2 1 7 27 4 1 7 27 4 实例演示 递归 5 实例演示 递归 5 4 23 8 s t 地基4喷绘4 8 0 4 s t 挖沟1 7 砌砖15 木工8 4 0 19 37 4 屋顶10 挖沟1 7 管线 2 1 7 27 4 1 7 27 4 实例演示 路径回溯实例演示 路径回溯 4 地基4喷绘4 8 4 23 8 s t 地基4喷绘4 8 木工8 4 0 4 屋顶10 挖沟1 7 管线 2 砌砖15 木工8 4 19 37 4 屋顶10管线 2 1 7 27 4 关键路径算法说明关键路径算法说明 关键路径算法给出的时间是任活动的最 关键路径算法给出的时间是任一活动的最 早开工时间 若e uv 则最早开工时间 E e u 关键路径上活动的拖延将会引起整个工期关键路径上活动的拖延将会引起整个工期 延长 相反非关键路径上的活动的是容许一定 相反 非关键路径上的活动的是容许定 时间的延迟的 故可考虑如下的问题 活 动的最晚开工时间是多少 动的最晚开工时间是多少 最晚开工时间计算L e 最晚开工时间计算L e 若活动由边e表示 e uv 则 w 初始化 u v 初始化 实例演示 最晚开工时间实例演示 最晚开工时间 地基4 喷绘4 8 4 23 8 37 4 4 s t 地基4 喷绘4 8 0 4 37 4 32 6 4 0 屋顶10 s t 挖沟1 7 管线 2 砌砖15 木工8 4 0 19 37 4 19 0 3 屋顶10挖沟1 7 管线 2 1 7 27 427 4 21 72 23 8 地基4 喷绘4 8 4 23 8 37 4 32 6 4 0 s t 砌砖15 木工8 4 0 4 37 4 32 6 4 0 3 0 屋顶10挖沟1 7 管线 2 砌砖15 19 27 4 37 4 27 4 19 0 3 关键路径上的活动 地基砌砖木工屋顶最早开工 1 7 27 427 4 2 关键路径上的活动 地基 砌砖 木工 屋顶最早开工 最晚开工时间相等 不在关键路径上的活动挖沟 0 0 3 管线 1 7 2 0 不在关键路径上的活动 挖沟 0 0 3 管线 1 7 2 0 喷绘 19 32 6 最早开工 最晚开工时间有一个时间 差 浮动时间 记为R e R e L e E e 差浮动时间 记为R e R e L e E e 赶工优化问题赶工优化问题 关键路径上的活动的任何延误将会延长总 工期 相反如果要缩短工期 在不计较代期相反如果要缩短期在不计较代 价的情况下 自然的做法是把关键路径上 的活动耗时量缩小 的活动耗时量缩小 如果计较代价 如何缩短总工期而且使得 赶成本最少这个问题就是所谓的赶赶工成本最少 这个问题就是所谓的赶工 优化问题 赶工优化问题 数学描述赶工优化问题 数学描述 中的最耗时为常情 设项目中活动e的最少耗时为b e 正常情况 下耗时l e 赶工成本为每天c e 现在要赶耗 本每 工 T天 应该在那些活动上赶工多少天 才能使赶工总成本最小 才能使赶工总成本最小 基本考虑基本考虑 待赶工活动对象 浮动时间小于要缩短的 工期 R e T 不妨称之为 准关键路径 期 妨关路径 如果只在关键路径上赶工准关键路径可 如果只在关键路径上赶工 准关键路径可 能变成关键路径 而且并没有达到预期的 赶工目的 例子 1 例子 1 6172517 6 adt 118 6 6 6 4 21 11 0 bcs 10505 01015161 例子 2 例子 2 在加时产生的关 如果在ad上加班两天 这时产生了新的关 键路径 但最后的完工时间并没有达到赶键路径但最后的完时间并没有达到赶 工两天的效果 6162417 adt 98 6162417 6 6 6 4 21 11 0 bcs 105105 01015161 赶工策略 如果只想在关键路径上赶工 那么能够赶 工的天数应该受那些准关键路径的限制 天数关路径限制 考虑全部关键路径活动组成的网络 关键 网络网络 所有求解的关键在于 既要保证赶工活动 费用的最小性 又要保证赶工的天数不至 于使得原赶工前功尽弃 于使得原赶工前功尽弃 费用网络费用网络 费用网络 全部关键路径组成一个网络 关键网络 网络权取为赶工费用 注关键网络网络权取为赶费用注 意 如果b e l e 表示该活动不能加快 故取赶工费用为故取赶工费用为 给定关键网络下 赶工费用对应于费用网 络的切割容量否则并不能实现期的压络的切割容量 否则并不能实现工期的压 缩 下面的图例对此加以说明 例子 1 例子 1 6172517 6 adt 118 6 6 7 4 21 10 0 bcs 10505 01015160 例子 2 例子 2 在给定的关键网络中 如果不在某个切割 上赶工 最后的总工期没有改变 比如只赶最后的总期没有改变如只 在ad上加班2天 总工期没有减小 6172517 adt 98 6172517 6 6 7 4 21 10 0 bcs 105105 01015160 例子 3 例子 3 在给定关键网络中 只有在关键网络的切 割上赶工 才能引起总工期的改变 比如割赶才能引起总期的改变如 只在在ad和bd上均加班2天 总工期减小2 6152315 adt 98 6152315 6 6 5 4 19 10 0 bcs 105105 01015140 求解思路求解思路 给定关键网络下 最小赶工费用可以通过 最大流算法求得 最小切割最大流定理 最大算得最割最大定 给定关键网络中的最小切割后 如何决定 赶工天数是关键赶工天数是关键 引进 跃变度 的概念 跃变度跃变度 在给定关键网络中的最小切割求出后 令 切割上的权为0 其它边上活动时间不变 割权其活动 此时对应的总工期和原工期的差值定义为 跃变度 跃变度 跃变度刻画的是非关键路径对关键路径工 期缩短量的限制让切割上的权为是为期缩短量的限制 让切割上的权为0 是为 了强调纯粹来自于非关键路径的影响 切割上的可缩短工期数切割上的可缩短工期数 制 限制 未完成的赶工天数 未完成的赶工天数 每个活动的极限工期 跃变度 跃变度 切割上可缩短工期 上述三个因素的最小 值 赶工优化问题解法赶工优化问题解法 计算总工期T和各活动的浮动时间 求关键网络 由关键网络定义费用网络 求费用网络的最大流所对应的切割 P Q 令切割 P Q 上活动工期为0 其它活动不变 求总工期T 计算跃变度 J T T J T T 计算切割上的可缩短工期 将切割 P Q 上的活动工序减 重复上面的步骤直到完成全部赶工 将切割 P Q 上的活动工序减 重复上面的步骤 直到完成全部赶工 天数为止 实例演示I 问题实例演示I 问题 adt 11 9 40 8 7 160 adt 6 4 306 5 100 4 4 100 bcs bcs 10 8 905 2 200 边上的数字对应于 l b 要把工期边上的数字对应于 l e b e c e 要把工期 提前三天 如何赶工 使得总赶工费用最小 实例演示I 浮动时间实例演示I 浮动时间 6172517 6 adt 118 6 6 6 4 21 11 0 bcs 10505 01015161 实例演示I 费用网络最大流实例演示I 费用网络最大流 adt 160 30 40 30 30 30 bcsbcs 切割为 s a d t 切割为 s a d t 在sa上缩短工期 实例演示I 跃变度实例演示I 跃变度 0162416 5 adt 118 5 0 6 4 20 10 0 bcs 105 01015150 工期为24工期为 跃变度 25 24 1 上的缩短期量sa上的缩短工期量 Min 3 6 4 1 1 实例演示 II 问题实例演示 II 问题 在sa上压缩天工期费用为30 新的工在sa上压缩一天工期 费用为30 新的工 期如下 还需要赶工2天 11 9 40 8 7 160 adt 5 4 306 5 100 bcs 10 8 905 2 200 实例演示II 浮动时间实例演示II 浮动时间 6162416 6 adt 118 6 5 6 4 20 10 0 bcs 10505 01015150 实例演示II 费用网络最大流实例演示II 费用网络最大流 adt 160 120 40 30 30 30 100 90 bcs bcs 切割为 s a b d t 90 90 切割为 s a b d t 在sa sb上缩短工期 实例演示II 跃变度实例演示II 跃变度 0111911 5 adt 118 5 0 6 4 20 5 0 bcs 05 0015150 工期为19工期为 9 跃变度 24 19 5 上的缩短期量sa sb上的缩短工期量 Min 2 5 4 10 8 5 1 实例演示 III 问题实例演示 III 问题 在sa sb上各压缩天工期费用为120在sa sb上各压缩一天工期 费用为120 新的工期如下 还需要赶工1天 11 9 40 8 7 160 adt 4 4 306 5 100 bcs 9 8 905 2 200 实例演示II 浮动时间实例演示II 浮动时间 4152315 4 adt 118 4 4 6 4 20 9 0 bcs 9595 0915150 实例演示III 费用网络最大流实例演示III 费用网络最大流 adt 160 130 40 40 1 40 100 90 bcs bcs 切割为 s a b d t 90 90 切割为 s a b d t 在sb ad上缩短工期 实例演示III 跃变度实例演示III 跃变度 4111911 5 adt 08 5 4 6 4 20 5 0 bcs 05 0015150 工期为19 跃变度 23 19 4