网络计划技术统筹法.ppt

2020 2 14 1 运筹学 网络计划技术 统筹法 2020 2 14 2 统筹方法 计划管理与统筹法1 定义1 对于任何一项生产制造 科学实验 工程实施 军事作战等活动 为了充分利用有限的时间 空间与资源 人力 物力 财力 都必须编制一个科学的工作组织计划来有效地组织 调度与控制该项活动的进程 以实现最佳的效应和效益 而这种为编制科学的组织计划的有效方法统称为统筹方法 2020 2 14 3 例1甲 乙两工程师从早上六时起床到上班前有一系列活动要做 对于同样的活动过程 有人忙乱不堪 甚至迟到 有人则又快又好 关键在于一个科学的活动实施计划 穿衣 刷牙 洗脸 做稀饭 热馒头 吃早饭 收拾房间 整理 出门上班 甲 穿衣 洗脸刷牙 收拾房间 整理 吃早饭 出门上班 做稀饭 热馒头 乙 2020 2 14 4 例2大型工程实施 三峡工程 南水北调工程 人造卫星工程 宇航工程等 有如下活动 产品设计 仿真 试制 中试原材料设备定货 采购 运输 入库厂房 设备施工建筑 安装产品计划 生产 销售 安装 调试 维护参与单位涉及国家各部门 各行业 事业单位 为高速度 低成本 高质量 并在规定期限内完成该工程项目 其关键在 抓好科学技术抓好项目管理 组织协调好各单位 各任务 各工序的完成 2020 2 14 5 例3三军联合作战演习空军夺取制空权 对敌实施地面攻击 运送空降兵海军舰艇护卫 运送陆军 海军陆战队登陆夺取滩头阵地登陆完成后的巩固阵地与纵深发展电子对抗部队实施情报收集分析与电子对抗参与兵种 海军航空兵 海军陆战队 水面舰艇部队 空军歼击机 攻击机 轰炸机 电子对抗机各团 大队 坦克 炮兵 步兵 防化兵 通讯兵 侦察兵 导弹部队等 需迅速订好科学的作战演习计划 以便对作战演习过程演习过程进行有效的管理与控制 2020 2 14 6 计划管理与统筹法 统筹法研究内容PERT ProgramEvaluationandReviewTechnique 计划评审技术CPM CriticalPathMethod 关键路线法GERT GraphicalEvaluationandReviewTechnique 随机网络技术 直译为图示的评价与评审技术 PERT CRM GERT CPM 2020 2 14 7 统筹法发展历史CPM 1956年在美杜邦公司化工厂建立过程中由美兰德公司提出 PERT 1958年美海军特种计划局在研制 北极星 导弹核潜艇过程中在哈密尔顿公司及洛克菲勒公司协助下提出了一个 北极星计划 以管理整个工程过程中的8家总承包公司 250家分承包公司 3000家三包公司 9000家厂商 由于使用PERT技术 提高了工作效率使整个工期提前两年完成 目前PERT CPM在日 英 法 德中相继推广使用并由我国在宝钢施工 与钢 84 89年 512项工程 南阳油田工程管理均获较大效益 目前国家经贸委 计委已要求重大工程必须采用此技术方法 GERT CPM在1966年由美国提出 并在阿波罗登月计划中首次使用成功 在英 阿的马岛之战中 1982年4月 英军三天完成计划网络 2003年美军攻击伊拉克 30万大军用三个月制订计划 建筑施工设备维修 钢铁 造船 汽车制造 石油 地质勘探 航空 航天 新材料 信息工程 含软件工程 2020 2 14 8 统筹法功能完成工程需做哪些工序 各工序需多长时间完成 总工期预计多长时间 完成工程的各工序采用什么样的逻辑顺序关系 关键工作是什么 如何加快工程的完成 环境发生变化时 该工程的风险分析 计划管理与统筹法 2020 2 14 9 计划网络图 工序流线图 计划网络图及其诸要素定义2 反映一个工程项目中各项作业 工序 的内在逻辑关系的一种有向图称为计划网络图 又称统筹图 工序流线图 网络图等 以符号G表示 此中 内在逻辑关系 是指由于工程本身的工艺与组织性要求 而对各工序提出的在时间上和空间上所要求的先后处理关系 定义3 如下表 2020 2 14 10 3 12 a 10 a b 2020 2 14 11 例4某公司研制新产品的部分工序明细表如下 试画出统筹图 2020 2 14 12 网络图绘制规则 每一作业用一箭线及前后两节点连接 箭线上标出作业标号 箭线下写上完成该作业的资源数 通常用时间表示 一对结点间只能有一条箭线 且不允许出现回路 若出现并行作业可引入虚工序或人为地将工序一分为二 虚作业不消耗资源 用虚线表示 并行作业 2020 2 14 13 网络图绘制规则 不允许出现交叉作业 若出现交叉作业时应引入虚工序 双向箭头可画成 2020 2 14 14 网络图绘制规则 结点编号自左向右增长 工序的终止结点编号大于起始结点编号统筹图只有一个起点与一个终点 图的封闭性 2020 2 14 15 例5 例4基础上再加三道工序f g h 某工程项目作业明细表如下 1 绘制计划网络图 2 求关键路线与路长 3 求关键工序 2020 2 14 16 解 若已知紧后工序之作业明细表 故用正象 顺向 搜索法 已知紧前工序之作业明细表 故可采用反向搜索法 fgh 1 2 5 3 4 7 6 a b e d g h f c 1 2 5 4 3 7 6 a b e d g h f c 8 60 15 13 38 8 10 16 5 2020 2 14 17 网络计划实施步骤 工程项目任务分解 确定工程全部事项 工序 的逻辑关系 确定每一工序的延续时间 制定作业明细表 绘制计划网络图 并作调整 对网络图各节点 箭线编号 计算关键路线与关键工序 形成计划初步方案 是否有潜力可挖 是否满足要求 优化计划方案 编制日程计划并执行 执行中发生偏差是否在允许范围内 结束 Y N Y N N Y 2020 2 14 18 工序延续时间估计 经验法与专家法 平均值 适用于重复性工作 不确定性因素少三点估计法 又称六分法 其中a 对工序e延续时间的最乐观时间 在顺利情况下工序e完成的最短可能时间 b 对工序e延续时间的最悲观时间 最不顺利下工序e完成的最长可能时间 M 对工序e延续时间的最可能时间 在正常情况下工序e完成耗费时间 2020 2 14 19 三点估计法这是由于通常认为工序延续时间 2020 2 14 20 三点估计法 分布随机变量 的概率密度函数见右 M a b x f x M a b x f x 2020 2 14 21 确定性网络时间参数与关键路线 时间参数的标识与关联 t t ES i j EF i j t i j R i j TE i t i j TL j LS i j LF i j t i j 0 0 工序参数 节点参数 2020 2 14 22 i j ES i j EF i j TE i TE j LS i j LF i j TL i TL j min max ES i j 工序 i j 最早开始时间EF i j 工序 i j 最早完成时间LS i j 工序 i j 最晚开始时间LF i j 工序 i j 最晚完成时间设起始节点序号为1 终点节点序号为n 1 i j nTE i 节点 事项 i最早开始时间TL i 节点 事项 i最迟完成时间R i j 工序 i j 的时差 反映该工序的机动时间 R i 节点i的时差 反映该节点的机动时间 2020 2 14 23 各时间参数的相互关系如下 2020 2 14 24 例6某公司装配一新生产线 该工程作业明细表如下 求完成该工程的关键路线和相应关键工序 2020 2 14 25 时间参数计算 顺向计算法 自左向右法 工期SD未知 2020 2 14 26 时间参数计算 逆向计算法 自右向左法 工期SD已知 2020 2 14 27 关键路线及其求解 命题1 作业路线CP为G的关键路线CP上各工序时差为0 命题2 作业路线CP为G的关键路线CP上各工序时差为0 命题3 若G为有限网络 则G至少有一条关键路线 至多有有限条关键路线 总工期不可能提前完成 因为是关键路线上的关键工序 对于非关键工序 工时不全为零 从而有潜力可挖 且关键路线是所有路线中最长的路线 故只要关键路线中各工序完成 其他非关键工序必完成 故有总工期公式 2020 2 14 28 2020 2 14 29 关键路线CL adgij总工期T Ta Td Tg Ti Tj 170天 1 2 4 6 7 8 2020 2 14 30 关键路线及其求解 绘制计划网络图自左向右 顺向 计算各节点最早开始时间TE i 及各工序最早开始时间ES i j 最早完成时间EF i j 自右向左 逆向 计算各节点最迟完成时间TL i 及各工序最晚完成时间LF i j 和最晚开始时间LS i j 计算各工序时差R i j LS i j ES i j 各节点时差R i TL i TE i 寻找时差为0的节点并联结 即可得关键路线与相应关键工序寻找时差为0的工序并联结 亦可得关键路线CP与相应关键工序计算工程总工期对非关键工序进行研究 以挖掘潜力 2020 2 14 31 2020 2 14 32 2020 2 14 33 输入节点数n 各工序长度t i j 1 i j n 工期SD TE 1 0 TL n TE n 或TL n SD i 1 ES i j TE i EF i j ES i j t i j LF i j TL j LS i j LF i j t i j R i j LS i j ES i j R j TL j TE j 寻找使R i j 0的对应关键工序 或寻找使R j 0的对应节点 输出关键路线CP与关键工序 输出工期 若未给出 END j n N Y N Y 2020 2 14 34 随机性网络时间参数与关键路线 问题与求解例7 长征研究院MBA培训网络计划制订 P248 2020 2 14 35 解计算各工序的期望与方差 见上表右 绘制计划网络图 2020 2 14 36 解计算各工序的有关时间参数ES LS EF LF R i j 2020 2 14 37 2020 2 14 38 解寻找使R i j 0的关键工序及使R i 0的对应途经节点输出关键路线与关键工序计算总工期T的期望和方差E T Ta Tb Tg Th Ti CP 2 3 4 4 2 15 天 结论 该计划网络G关键路线CP abghi或该计划网络G总工期T的期望 CP E T 15天 2020 2 14 39 命题4 设n为计划网络G的工序数 CP为大型工程计划网络G的关键路线 T为G的任务总工期 若n 1 则有 其中与分别为关键路线CP路长的期望与方差对 G在规定工期T0内完工的概率有aij 工序 i j 的最乐观时间bij 工序 i j 的最悲观时间mij 工序 i j 的最可能时间 大型工程任务总工期的概率特性 2020 2 14 40 证 大型工程的工序数n 1 且各工序对任务总工期的影响均匀地微小 且相互独立 故由中心极限定理知 有 2020 2 14 41 例8 在例7中取工期T0分别为15 17 18 20周 求该计划网络按期T0内完工的概率欲使按期完工的概率达到95 或99 试确定相应的工程任务总工期T 解 由命题4结论知对有现取T0 15 则有此中 CP 15 CP 1 025 已由例7中求得 类似地有 2020 2 14 42 解到 2020 2 14 43 系5 F x 1 0 5 CP x 2020 2 14 44 系6 2020 2 14 45 最关键路线与计划难易系数 定义4 若在G中有关键路线CPi i 1 k 此中各关键路线有对应路长的期望与方差 i 1 2 k 此中显然有 若有 则称为G的最关键路线 即方差最大的关键路线称为最关键路线 有系6知 若表执行最关键路线的对应工期 则有 j 1 k 即对任何给定工期T0 执行最关键路线时要在T0内完成的可能性最小 而考虑到只有该 最关键路线 上所有工序全部完成后工程方能完工 因此在G设计时应对上的工序予以特别关注 2020 2 14 46 2020 2 14 47 6 1 1 6 0 692 0 308 2 3 4 2020 2 14 48 2020 2 14 49 定义5 设T为G的工期 随机变量 CP为G的关键路线 CP与为CP路长的期望与方差 则称为执行给定工期T0的计划难易系数 例9对于例7的计划网络G 求解给定工期T0分别取13 15 17 18 20 周 时的计划难易系数 0 解 太保守 有潜力可挖 完成可能性很大 完成可能性很大 完成可能性较大 完成可能性小 2020 2 14 50 网络计划的优化 前述的网络计划仅给出了初等的计划模型 该模型一般是不成熟的 它可能在工期 时间 资源 或费用上存在种种的问题与矛盾或缺陷 因此需要作进一步的统筹处理 这就是网络计划优化的主要目的 也是整个统筹法研究的精华与主要内容 初步的计划网络往往存在着下述矛盾或问题 时间上 计算的总工期有可能超过用户要求期限 或部分工序的时间潜力来得到充分发挥 浪费时间 资源 有限 上 有的工序由于资源供应过多而浪费 而另一些工序则出现资源的供不应求现象 费用上 为赶工期而使用的工序增买设备 材料或增发奖金等 但事实上这样的措施却可能不是节约的 而仍然有潜力可挖 优化目的是调整与改善原始计划 以求得一个时间进度快 资源消耗少 成本低的最优计划方案 2020 2 14 51 网络优化模型的类型 单目标优化模型 通常有 时间优化资源 设备 材料 人力等 优化费用优化多目标优化模型时间 资源优化模型时间 费用优化模型时间 资源 费用优化模型 2020 2 14 52 炒菜8 切菜12 淘米5 时间优化的一般原理 向关键路线上要时间强制压缩关键工序工时 技术革新 将串联作业调整为平行作业 如例10 例11 1 2 3 4 淘米5 烧水10 洗菜5 5 6 7 8 蒸饭15 炒菜8 吃饭25 切菜12 1 2 3 4 烧水10 洗菜5 6 7 蒸饭15 吃饭25 G1 G2 T1 80分T2 55分 例10 2020 2 14 53 挖地基30 1 2 浇柏油5 3 4 铺石子12 浇柏油 铺石子 挖地基 例11 G3 G4 T3 60天T4 42天 6 6 6 4 4 4 10 10 10 2020 2 14 54 将富裕线路 非关键线路 上的资源调整到关键线路上来 以推迟非关键工序的开始时间来换取工期的节省 以推迟非关键工序的延续时间来换取工期的节省 同时推迟非关键工序的开始时间和延续时间 从计划G外增拨资源增拨运输车辆 工人由二班变为三班等方式 来缩短工期 时间优化的一般原理 2020 2 14 55 优化工序间的逻辑结构变化G中各工序的逻辑顺序关系直接建立G的优化结构模型通过线性规划等的建立与求解 时间优化的一般原理 1 2 4 3 5 6 a8 M6 c8 d6 N10 b4 1 2 4 3 5 6 a8 M6 c8 d6 N10 b4 1 2 4 3 5 6 a8 M6 c8 d6 N10 b4 1 6 M N Ta 30天 1 6 N M Tb 28天 1 6 M N并行 Tc 22天 a b c 例12 2020 2 14 56 时间 资源优化 合理利用现有资源 以最大限度的缩短工期 这就是网络计划的时间 资源优化的目的 设T G 表网络计划G对应的工期A G 表网络G所消耗的资源则时间 资源优化模型为如下双目标数学规则 2020 2 14 57 时间 资源优化 时间 资源优化准则 关键工序所需资源优先安排 削峰填谷 原则 利用非关键工序的时差推迟某些非关键工序的开始时间 以降低某些资源需求高峰时段的资源需求量 同时提高某些资源需求低谷时段的资源需求量 在不影响网络工期的前提下实现工期内各时段的资源均衡使用 特殊资源特殊利用 工序资源调配以公共资源为主 2020 2 14 58 G时间资源优化程序框图 输入工序明细表 资源需求表 计算网络时间参数 确定关键路线CP 利用横道图及逐日 或月 年 资源需求量A t 绘制t A t 曲线 并作系统分析 搜索资源需求峰值Gp及其对应时段 ta tb 设置控制水平G0 作ts tb 计算高峰期间 ta tb 内开工的非关键工序的有效机动时间Th i j 及时差Ta i j LS i j ts TL j t i j ts 按照削峰填谷原则 对高峰期 ta tb 内开工的各非关键工序 进行排队 并从中选出有效机动时间Tn i j 大且资源强度V i j 小的对应工序 i j 将上述工序 i j 的最早开工时间推迟到tb 即ES i j ts 重新累计逐日 或月 年 资源需求量A t 资源高峰是否减少 调整提前量tb 资源均衡满意 结果输出 END ts为非关键工序推迟后的最早开始时间 2020 2 14 59 时间 资源优化 例13在例6的工序明细表中增加各工序的资源需求如下表 此中工序a b c e j由于各自的特殊性 需由相关的生产设计人员 铸工 锻工 木工来完成 故在编制计划网络时只能给予充分保障 而其余的d f g h i五道工序则具有通用性 此中每一工序均可由任一机加工人来完成 现设该公司现有机加工工人65人 试求该工程的时间 资源优化方案 故可作资源调配以实现各时段的均衡使用 2020 2 14 60 2020 2 14 61 i j tatb LS EF ES LF 资源高峰 Th i j LS i j ts LS i j tb 0即LS i j tb 说明工序 i j 有后移到tb后的可能R i j LS ES i j Th i j LS tb为对后移到tb后的有效机动时间 2020 2 14 62 G图 2020 2 14 63 解根据工序明细表及资源需求表计算G的网络参数 并确定关键路线CP及关键工序集为 a d g i j 根据向非关键路线上要资源的原则 故应考虑非关键工序b c e f h的资源调整问题 但此中由于工序b c e的特殊性无法用其它资源替代故不予考虑其资源调整 此外又由于公司所拥有的共用资源 机加工工人 共给仅为65人 而关键工序d g i之一 若与其它工序并行工作时还可能会出现资源超负荷问题 综合上述考虑 以下来讨论工序 d f g h i 的资源调整与优化问题 根据工序d f g h i的最早开始时间ES和最早结束时间LS画出横道图 a 及相应的资源负荷 b 其中A t 表t日的资源需求总累计量 t日这一天的各开工工序所需总资源量 横道图中的时间起点与终点均用ES与EF 2020 2 14 64 58 G0 2020 2 14 65 64 d 58 f 22 g 42 h 39 60 70 80 90 100 110 120 130 140 60 70 80 90 100 110 120 130 140 i 26 20 18 30 15 25 20 40 60 80 t t d f gi h工序 65 58 42 65 26 横道图 a 资源负荷图 b G0 2020 2 14 66 解 对资源负荷图 b 系统分析可知 G0 65 公司供给量 ta tb 在 1 70 80 时段工程实际需求80人 65人 在 2 70 80 时段工程实际需求81人 65人 根据 削峰填谷 原则应将峰 1与 2中的非关键工序后移以填谷 注意到在二个峰期中 1中d为关键工序 f为非关键工序 2中g为关键工序 h为非关键工序 故将非关键工序f与h后移以填谷 从而可获得横道图 c 及资源负荷图 d 此中f与h的后移时段多少应视资源负荷的均衡程度为好 2020 2 14 67 工序高峰期后移计算 见程序框图 2020 2 14 68 解由资源负荷图 d 及横道图 c 获得经调整后各工序f h的最早开工时间ES i j 最早结束时间EF i j 对未调整的工序之ES i j 与EF i j 仍用原网络G图之数据 可得如下新网络图 对重新计算各网络时间参数 最终仍可得工期当G 后 由于与G有相同工期 且各时段之资源负荷均小于供应量G0且相对均衡 故END 2020 2 14 69 时间 费用优化 基本概念与符号 前述模型为后移工序的ES 以下模型为缩短工序长度t i j 直接费用 为加快工程进度需对关键工序新增人力 设备和工作班次 从而需新增一笔投入费用 作为奖金或设备购置费 此笔费用称之为直接费用 间接费用 管理人员的工资 办公费用 出差费 用车费 复印费等 统称为间接费用 通常当工序作业时间愈短 直接费用愈多 间接费用愈少 2020 2 14 70 2020 2 14 71 优化模型 目标 在给定工期T的约束下 求计划网络G各工序完成时间 以使因缩短工期而增加的直接费用达最小 2020 2 14 72 优化模型 2020 2 14 73 优化模型 说明 优化模型 仅考虑直接费用 未考虑间接费用 后述优化模型 则同时考虑直接费用与间接费用的综合效果 上述LP模型之决策变量为yij 亦即仅考虑工序 i j 的提前 而未考虑工序 i j 是否关键 因此对上述优化模型求解后有可能改变关键路线 从而使实际总工期并未缩短 此时应重新建立优化模型求解 模型中的xj为中间变量 yi决定 由LP求得yij有 工期提前量 但不一定有 详见下例14 2 2020 2 14 74 例14 对例6的计划网络补充如下有关信息 以研究工期 的提前性以及相应工序的提前量 若该工程按G需170天完成 现需要提前到150天完成 试求相应各工序的提前量 若该工程需提前到140天完工 试求相应各工序的提前量及应增加的费用投入 2020 2 14 75 2020 2 14 76 解1 由优化模型 思路有LP如下 2020 2 14 77 图G 原网络 2 4 6 7 8 60 d20 g30 i25 j35 80 110 135 170 100 115 150 20 15 图G1 经LP1优化后网络 2020 2 14 78 原计划 未调整 网络见右上图G 经上述优化后之网络见右上G1结论 即缩短工序g与i各10天 其余工序长度不变 为此需付出的最少直接费用为6400元 这样即可将工期由原170天提前20天 即T 150天可完工 G G 见上右图G1 2020 2 14 79 2 将上述优化模型的最后一个约束x8 140 其它均不变 则构成LP2 运用软件包计算可得f1 14900元 2020 2 14 80 图G 原计划网络 图G2 LP2优化后网络 2020 2 14 81 由上述求解结果知只要工序e h提前5天d g i工序提前10天 其它工序完工时间不变 则可使整个工程在T 140天完成 此时需至少增加投入经费1 49万元 此时有 对于上述LP2之结果画出网络图G2 对该G计算网络时间参数 得知工程工期恰为140天 且四条路线均为关键路线 2020 2 14 82 解 分析法 由题设要求缩短工期20天 由170天提前到150天 完成工程 根据统筹法原理 向关键工序要时间 故需从关键工序a d g i j要时间 比较这五个关键工序的直接费用变动率 见下表 可知 工序i直接费用变动率最低 其次是工序g 注意到直接费用变动率表中有约束如下 i y67 10 g y46 10 y12 0 a y78 0 j i j工序无提前余地 取上限有y67 10 y46 10 经由G1图计算知恰有TG1 150天 此时需增加支出最少的直接费用为f1 350 10 290 10 6400元 此结果与解1 1 相同 2020 2 14 83 2020 2 14 84 解 若工程期限要求在140天完成 提前工期30天 根据向关键路线CP1 a d g i j要时间的原理 可根据上述 1 同理 可设想将关键工序d g i分别缩短工期10天 注意到有 故这种设想是可以做到的 即取y24 y46 y67 10 此时若其它工序长度若仍不变 则有 然而据此对应的G3计算可知仍有TG3 150 即有 仍然未能达到缩短30天的要求 且此时关键路线亦由CP1 a d g i j转变为CP2 a e h j 祥见图G3 为此可再进一步在CP2的关键工序e与h再各提前5天 共10天 e y25 5 h y57 5 则此时可由G3转变为G2 由图G2之计算可知 此时有TG2 140天 达到要求 为缩短d g i各10天 e h各5天需多付出的最少直接费用为此结果亦与解 相同 2020 2 14 85 优化模型 设f直 为赶工而需增加支出的直接费用 显然有f间 为完工而需支出的间接费用 设其与工程完工时间成正比 则有f间 xn x1 从而可建立如下优先模型 综合考虑 f直与f间 求总费用最小目标下的网络计划赶工方案 LP3之约束是将LP1约束中去掉xn x1 T之工期的约束外 其它与LP1约束全部相同 2020 2 14 86 例15 在例14中除考虑f直外 还综合考虑f间 并使工期内的间接费用支出为 330元 试求在总费用最少的目标下 求网络计划的赶工方案 解 建立目标与约束如下 2020 2 14 87 可得最优值f 55700元 5 57万元 290 10 330 160此为有无穷最优解之案例 这可由如下G4图所证实 若将xj看作为节点j的最早开始时间 则可取x3 70 x5 100 其余同左 TG4 160天 若xj看作开工时间 则取x3 105 x5 110 其余同左 2020 2 14 88 说明 x3与x5取任何一值不影响目标函数值由约束 c 有x3 x2 10 60 10 70 由约束 f 有x3 x7 18 125 18 107 故知有70 x3 107由约束 d 有x4 x2 20 60 20 80 由约束 g 有x4 x6 30 110 30 80 故知有x4 80由约束 e 有x5 x2 40 60 40 100 由约束 h 有x5 x7 15 125 15 110 故知有100 x5 110书中P260之解x3 125不满足约束 f x4 107不满足约束 g 故有错误