网络计划技术（统筹法）.ppt

运筹学 网络计划技术（统筹法） Date 1 统筹方法 l计划管理与统筹法 1. 定义1：对于任何一项生产制造、科学实 验、工程实施、军事作战等活动，为了充分利 用有限的时间、空间与资源（人力、物力、财 力），都必须编制一个科学的工作组织计划来 有效地组织、调度与控制该项活动的进程，以 实现最佳的效应和效益。而这种为编制科学的 组织计划的有效方法统称为统筹方法。 2019/1/26 2 l例1 甲、乙两工程师从早上六时起床 到上班前有一系列活动要做。对于同 样的活动过程，有人忙乱不堪，甚至 迟到，有人则又快又好，关键在于一 个科学的活动实施计划。 穿衣刷牙洗脸做稀饭热馒头 吃早饭收拾房间整理出门上班 甲 穿衣 洗脸刷牙收拾房间整理 吃早饭 出门上班 做稀饭热馒头 乙 Date 3 l例2 大型工程实施（三峡工程、南水北调工 程、人造卫星工程、宇航工程等）有如下活动 ： u产品设计、仿真、试制、中试 u原材料设备定货、采购、运输、入库 u厂房、设备施工建筑、安装 u产品计划、生产、销售、安装、调试、维护 参与单位涉及国家各部门、各行业、事业单 位，为高速度、低成本、高质量，并在规定 期限内完成该工程项目，其关键在： u 抓好科学技术 u 抓好项目管理，组织协调好各单位、各任务 、各工序的完成。 Date 4 l例3 三军联合作战演习 u空军夺取制空权，对敌实施地面攻击，运送空降 兵 u海军舰艇护卫，运送陆军、海军陆战队登陆夺取 滩头阵地 u登陆完成后的巩固阵地与纵深发展 u电子对抗部队实施情报收集分析与电子对抗 l参与兵种：海军航空兵、海军陆战队、水面舰 艇部队、空军歼击机、攻击机、轰炸机、电子 对抗机各团、大队，坦克、炮兵、步兵、防化 兵、通讯兵、侦察兵、导弹部队等。 l需迅速订好科学的作战演习计划，以便对作战 演习过程演习过程进行有效的管理与控制。 Date 5 计划管理与统筹法 l统筹法研究内容 uPERT (Program Evaluation and Review Technique) 计划评审技术 uCPM (Critical Path Method) 关键路线法 uGERT (Graphical Evaluation and Review Technique) 随机网络技术（直译为图示 的评价与评审技术） uPERT/CRM，GERT/CPM Date 6 l统筹法发展历史 uCPM：1956年在美杜邦公司化工厂建立过程中由美兰德公 司提出。 uPERT：1958年美海军特种计划局在研制“北极星”导弹核潜 艇过程中在哈密尔顿公司及洛克菲勒公司协助下提出了一 个“北极星计划”以管理整个工程过程中的8家总承包公司， 250家分承包公司，3000家三包公司，9000家厂商，由于使 用PERT技术，提高了工作效率使整个工期提前两年完成。 目前PERT/CPM在日、英、法、德中相继推广使用并由 我国在宝钢施工，与钢（8489年）512项工程，南阳油田 工程管理均获较大效益。目前国家经贸委、计委已要求重 大工程必须采用此技术方法。 uGERT/CPM 在1966年由美国提出，并在阿波罗登月计划 中首次使用成功，在英、阿的马岛之战中，1982年4月，英 军三天完成计划网络，2003年美军攻击伊拉克（30万大军 用三个月制订计划） 建筑施工 设备维修 钢铁、造船、 汽车制造、石 油、地质勘探 航空、航天、新 材料、信息工程 （含软件工程） Date 7 l统筹法功能 u完成工程需做哪些工序，各工序需多长 时间完成？总工期预计多长时间？ u完成工程的各工序采用什么样的逻辑顺 序关系？关键工作是什么？如何加快工程 的完成。 u环境发生变化时，该工程的风险分析。 计划管理与统筹法 Date 8 计划网络图（工序流线图） l计划网络图及其诸要素 u定义2：反映一个工程项目中各项作业（ 工序）的内在逻辑关系的一种有向图称为 计划网络图，又称统筹图，工序流线图， 网络图等，以符号G表示。此中“内在逻 辑关系”是指由于工程本身的工艺与组织 性要求，而对各工序提出的在时间上和空 间上所要求的先后处理关系。 u定义3：如下表 Date 9 要素定义符号及含义 事件（事 项） 一个或多个作业发生变化（开始或结 束）的瞬间状态 圆圈内为事项名（编号）， 圆圈上方数字为瞬间状态发 生时刻 工序（活 动、作业 ） 一个工程通常可划分为若干阶段来完 成，使在每一阶段中来完成全部工程 的部分内容，这一阶段完成的部分工 程内容称为工序或作业、活动。 有向线段上方标号为工序名 ， 其下方数字表为完成工序a所 需的资源（时间、人力、物 力）数或工序长度 路长每一网络只有一个起点和一个终点， 从起点开始经过一系列工序直到终点 为止的一条通路称为路线。路线中所 经由的各工序长度之和称为路长。 t (i, j) 紧前工序与紧后工序：b的紧前工序 为a， 工序a结束后方能完成 工序b, a的紧后工序为b 关键路线 ，关键工 序 在G的所有路线中，路长最大对应的 路线称为关键路线；在关键路线上的 各工序称为关键工序、 序号工序 代号 工序 名称 工序 长度 紧前 工序 1a15- 2b2a 作业明细 表 反映G中各工序间的前后逻辑关系的 表格称为作业明细表（详见右表） 3c10b 3 12 a 10 ab Date 10 l例4 某公司研制新产品的部分工序明细 表如下，试画出统筹图。 工序代号 工序名称（或内容）工序长度紧前工序 a产品设计与工艺设 计 60- b外购配套零件15a c外购生产原料13a d自制主件38c e主配件可靠性试验8b, d 1 24 5 3 ab c e d 60 15 13 38 8 Date 11 网络图绘制规则 l每一作业用一箭线及前后两节点连接，箭线上 标出作业标号，箭线下写上完成该作业的资源 数（通常用时间表示） l一对结点间只能有一条箭线，且不允许出现回 路；若出现并行作业可引入虚工序或人为地将 工序一分为二。（虚作业不消耗资源，用虚线 表示） 并行作业 1 2 a b 4 6 a 1 2 b 4 6 回路 1 3 2 a c 40 b 6 1 3 2 a/2 22 b 6 a/2 Date 12 网络图绘制规则 l不允许出现交叉作业，若出现交叉作 业时应引入虚工序 12345 1 A1 A2A3 B1B2 B3 2 3 4 5 A1 A2A3 B1B2B3 12 3 4 5 A1 A2 A3 B1 B2B3 双向箭头 可画成 Date 13 网络图绘制规则 l结点编号自左向右增长，工序的终止 结点编号大于起始结点编号 l统筹图只有一个起点与一个终点（图 的封闭性） Date 14 l例5 (例4基础上再加三道工序f、g、h) 某工程项目作业明细表如下 ，（1）绘制计 划网络图 ；（2）求关键路线与路长；（3 ）求关键工序 序号 工序 代号 所需 时间 紧前工 序 路线路长 1a60-a, b, e, h88 2b15aa, c, d, e, h 124 3c13aa, c, d, f, h 126 4d38ca, c, d, g, h 关键路线 132 5e8b、d 可从最终 工序开始逆 向完成网 络图 6f10d 紧后工序列中 没有标明的工 序即为最终的 工序 7g16d 8h5e、f、g Date 15 l解：若已知紧后工序之作业明细表， 故用正象（顺向）搜索法，已知紧前 工序之作业明细表，故可采用反向搜 索法。 （f g h） 125 3 4 76 a be dg h f c 12 5 4 37 6 a b e dg h f c 8 60 15 13 38 8 10 16 5 Date 16 网 络 计 划 实 施 步 骤 工程项目任务分解 确定工程全部事项（工序）的逻辑关系 确定每一工序的延续时间，制定作业明细表 绘制计划网络图，并作调整 对网络图各节点，箭线编号 计算关键路线与关键工序，形成计划初步方案 是否有潜力可挖 是否满足要求 优化计划方案 编制日程计划并执行 执行中发生偏差 是否在允许范围内 结束 Y N Y N N Y Date 17 工序延续时间估计 l经验法与专家法（平均值）：适用于重复性工作，不确定性因素少 l三点估计法（又称六分法） 其中a对工序e延续时间的最乐观时间（在顺利情况下工序e完成的最短可能时间） b对工序e延续时间的最悲观时间（最不顺利下工序e完成的最长可能时间） M对工序e延续时间的最可能时间（在正常情况下工序e完成耗费时间） Date 18 l三点估计法 这是由于通常认为工序延续时间 Date 19 l三点估计法 分布随机变量的概率密度函数见右 M a b x f(x) M a b x f(x) Date 20 确定性网络时间参数与关键路线 l时间参数的标识与关联 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 工 序 参 数 节 点 参 数 Date 21 ij 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，1i1，则有： ， 其中 与 分别为关键路线CP 路长的期望与方差 对 ，G在规定工期T0内完工的概率有 aij工序（i, j ）的最乐观时间 bij工序（i, j ）的最悲观时间 mij工序（i, j ）的最可能时间 大型工程任务总工期的概率特性 Date 39 l证： 大型工程的工序数n1，且各工序对任 务总工期的影响均匀地微小，且相互独立 ，故由中心极限定理知： 有 Date 40 l例8：在例7中取工期T0分别为15，17，18， 20周，求 l该计划网络按期T0内完工的概率 l欲使按期完工的概率达到95%或99%，试确 定相应的工程任务总工期T。 l解： l由命题4结论知对 有 现 取 T0=15，则有 此中 CP=15，CP=1.025，已由例7中求得。类似 地有 Date 41 T015171820 P(TT0)0.50.9740.9982 1 l解 2. 到 Date 42 l系5： F(x) 1 0.5 CP x Date 43 l系6 Date 44 最关键路线与计划难易系数 l定义4：若在G中有关键路线CPi，i=1k，此中各 关键路线有对应路长的期望与方差 ， ， i=1,2k，（此中显然有 ）， 若有 ，则称 为G的最关键路线 （即方差最大的关键路线称为最关键路线） l有系6知，若 表执行最关键路线 的对应 工期，则有 ， j=1k， 即对任何给定工期T0，执行最关键路线时要在T0 内完成的可能性最小，而考虑到只有该 （最 关键路线）上所有工序全部完成后工程方能完工 ，因此在G设计时应对 上的工序予以特别关 注。 Date 45 Date 46 -6 -1 16 0.692 0.308 234 Date 47 Date 48 l定义5：设T为G的工期（随机变量），CP为 G的关键路线，CP与 为CP路长的期望与 方差，则称 为执行给定 工 l期T0的计划难易系数。 l例9 对于例7的计划网络G，求解给定工期 T0分别取13,15,17,18,20（周）时的计划难易 系数0。 l解： T01315171820 0-3.90 03.905.859.75 太保守，有潜力可挖 完成可能性很大 完成可能性很大 完成可能性较大 完成可能性小 Date 49 网络计划的优化 l前述的网络计划仅给出了初等的计划模型，该模 型一般是不成熟的，它可能在工期（时间）、资 源、或费用上存在种种的问题与矛盾或缺陷，因 此需要作进一步的统筹处理，这就是网络计划优 化的主要目的，也是整个统筹法研究的精华与主 要内容。 l初步的计划网络往往存在着下述矛盾或问题： u时间上计算的总工期有可能超过用户要求期限；或 部分工序的时间潜力来得到充分发挥。（浪费时间） u资源（有限）上有的工序由于资源供应过多而浪费 ，而另一些工序则出现资源的供不应求现象。 u费用上为赶工期而使用的工序增买设备、材料或增 发奖金等，但事实上这样的措施却可能不是节约的， 而仍然有潜力可挖。 l优化目的是调整与改善原始计划，以求得一个时 间进度快，资源消耗少，成本低的最优计划方案 。 Date 50 网络优化模型的类型 l单目标优化模型，通常有 ： u时间优化 u资源（设备、材料、人力等）优化 u费用优化 l多目标优化模型 u时间资源优化模型 u时间费用优化模型 u时间资源费用优化模型 Date 51 炒菜 8 切菜 12 淘米 5 时间优化的一般原理 l向关键路线上要时间 u强制压缩关键工序工时（技术革新） u将串联作业调整为平行作业，如例10，例11 。 1234 淘米 5 烧水 10 洗菜 5 5678 蒸饭 15 炒菜 8 吃饭 25 切菜 12 1 2 3 4 烧水 10 洗菜 5 67 蒸饭 15 吃饭 25 G1： G2： T1=80分 T2=55分 例10 Date 52 挖地基 30 12 浇柏油 5 3 4 铺石子 12 浇柏油 铺石子 挖地基 例11 G3 G4 T3=60天 T4=42天 66 6 444 101010 Date 53 l将富裕线路（非关键线路）上的资源 调整到关键线路上来。 u以推迟非关键工序的开始时间来换取工 期的节省。 u以推迟非关键工序的延续时间来换取工 期的节省。 u同时推迟非关键工序的开始时间和延续 时间。 l从计划G外增拨资源 u增拨运输车辆，工人由二班变为三班等 方式。来缩短工期。 时间优化的一般原理 Date 54 l优化工序间的逻辑结构 u变化G中各工序的逻辑顺序关系 l直接建立G的优化结构模型 u通过线性规划等的建立与求解 时间优化的一般原理 1 2 4 3 5 6 a 8 M 6 c 8 d 6 N 10 b 4 1 2 4 3 5 6 a 8 M 6 c 8 d 6 N 10 b 4 1 2 4 3 5 6 a 8 M 6 c 8 d 6 N 10 b 4 1 6 MN Ta=30天 1 6 NM Tb=28天 1 6M,N 并行 Tc=22天 (a) (b) (c) 例12 Date 55 时间资源优化 l合理利用现有资源，以最大限度的缩 短工期，这就是网络计划的时间资 源优化的目的。 l设T(G)表网络计划G对应的工期 A(G)表网络G所消耗的资源 l则时间资源优化模型为如下双目标 数学规则 Date 56 时间资源优化 l时间资源优化准则： u关键工序所需资源优先安排 u“削峰填谷”原则：利用非关键工序的时 差推迟某些非关键工序的开始时间，以降 低某些资源需求高峰时段的资源需求量， 同时提高某些资源需求低谷时段的资源需 求量，在不影响网络工期的前提下实现工 期内各时段的资源均衡使用。 u特殊资源特殊利用，工序资源调配以公 共资源为主。 Date 57 G 时 间 资 源 优 化 程 序 框 图 输入工序明细表，资源需求表 计算网络时间参数，确定关键路线CP 利用横道图及逐日（或月、年）资源需求 量A(t)，绘制tA(t)曲线，并作系统分析 搜索资源需求峰值Gp及其对应时段（ ta,tb），设置控制水平G0，作ts0 即LS(i,j)tb，说明工序(i,j)有后移到tb后的可 能 R(i,j)=LS ES(i,j) Th(i,j)=LS tb 为对后移到tb后的有效机动时间 Date 61 e 60,100 4080,120 g(42人)80,110 30 80，110 i(26人)110,135 25110,135 c60,70 10 a0,60 60 0，60 f(22人)70,88 18117,135 j135,170 35 135,170 d(58人)60,80 20 60,80 1 8 5 764 3 b 60,105 45 90,135 h(39人)100,115 15 120,135 0 60 70 80 100 110 135 170 2 G图 Date 62 l解 根据工序明细表及资源需求表计算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） Date 63 d(58) f(22) g(42) h(39) 60708090100110120130140 60708090100110120130140 i(26) 20 18 30 15 25 20 40 60 80 关键工序 非关键工序 非关键工序 资源需求 工序长度 t t d f g i h 工序 65 80 81 64 42 65 26 横道图（a） 资源负荷图（b） 58 G0 Date 64 64 d(58) f(22) g(42) h(39) 60708090100110120130140 60708090100110120130140 i(26) 20 18 30 15 25 20 40 60 80 t t d f g i h 工序 65 58 42 65 26 横道图（a） 资源负荷图（b） G0 Date 65 l解： 对资源负荷图(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的后移时 段多少应视资源负荷的均衡程度为好。 Date 66 工序高峰期后移计算（见程序框图） 工序 高峰期（ ta,tb） A(t)G0tsLSTh(*) =LS- ts 资资源 V(i,j) ES(*) 后移 f(70,80)8065801173722ES(f) =80 h(100,110 ) 81651101201039ES(f) =110 Date 67 l解 由资源负荷图(d)及横道图(c)获得经调整后各工序f,h 的最早开工时间ES(i,j)，最早结束时间EF(i,j)对未调 整的工序之ES(i,j)与EF(i,j)仍用原网络G 图之数据， 可得如下新网络图 。对 重新计算各网络时间参 数。最终仍可得工期 当G 后，由于 与G有相同工期，且各时段之 资源负荷均小于供应量G0且相对均衡，故END。 e 60,100 40 g(42人)80,110 30 i(26人)110,135 25 c60,70 10 a0,60 60 f(22人)80,98 18 j135,170 35 135,170 d(58人)60,80 20 1 8 5 764 3 b 60,105 45 h(39人)110,125 15 0 60 80 80 110 110 135 170 2 Date 68 时间费用优化 l基本概念与符号（前述模型为后移工序的 ES，以下模型为缩短工序长度t(i,j)） u直接费用为加快工程进度需对关键工序新 增人力，设备和工作班次，从而需新增一笔 投入费用（作为奖金或设备购置费），此笔 费用称之为直接费用。 u间接费用管理人员的工资，办公费用（出 差费、用车费、复印费等）统称为间接费用 。通常当工序作业时间愈短，直接费用愈多 ，间接费用愈少。 Date 69 Date 70 优化模型 l目标：在给定工期T的约束下，求计划 网络G各工序完成时间，以使因缩短工 期而增加的直接费用达最小。 Date 71 优化模型 正常（ 最慢） 实际最快（ 最大） 工序完 成时间 TijTij yij 工序提 前量 0yij Date 72 优化模型 l说明： 优化模型仅考虑直接费用，未考虑间接费用 ，后述优化模型，则同时考虑直接费用与间 接费用的综合效果。 上述LP模型之决策变量为yij，亦即仅考虑工序 (i,j)的提前，而未考虑工序(i,j)是否关键，因此 对上述优化模型求解后有可能改变关键路线， 从而使实际总工期并未缩短，此时应重新建立 优化模型求解。模型中的xj为中间变量（yi决 定） 由LP求得yij有 （工期提前量），但 不一定有 （详见下例14(2)） Date 73 l例14：对例6的计划网络补充如下有关 信息，以研究工期的提前性以及相 应工序的提前量。 若该工程按G 需170天完成，现需要提前 到150天完成，试求相应各工序的提前量 。 若该工程需提前到140天完工，试求相应 各工序的提前量及应增加的费用投入。 Date 74 工序正常情况下（天）采取措施后（天） （元 /天 ） （天） 提前量 yij 提前量 的上限 正常完工 时间时间 Tij(t(i,j) 正常下直 接费费用Cij 最快完 工时间时间 相应应直接费费 用 a(1,2)60100006010000-y120 b(2,7)454500306300120y2715 c(2,3)10280054300300y235 d(2,4)2070001011000400y2410 e(2,5)40100003512500500y255 f(3,7)183600105440230y378 g(4,6)3090002012500350y4610 h(5,7)153750105750400y575 i(6,7)256250159150290y6710 j(7,8)35120003512000-y780 Date 75 l解1：由优化模型思路有LP如下 ： Date 76 f70,88 18 j135,170 35 i110,135 25 g80,110 30 d60,80 20 1 28 5 764 3 a0,60 60 b0,60 45 c60,70 10 e 60,100 40 h100,115 15 0 60 70 80 100 110 135 170 图G（原网络） 24678 60 d 20 g 30 i 25 j 35 80110135170 100115150 2015 图G1（经LP1优化后网络） Date 77 原计划（未调整）网络见右上图 G，经上述优化后之网络 见右上G1 结论：即缩短工序g与i各10天，其余工序长度不变，为此需付 出的最少直接费用为6400元，这样即可将工期由原170天提前 20天，即T=150天可完工。 GG（见上右图G1） Date 78 l(2) 将上述优化模型的最后一个约束x8140 ，其它均不变，则构成LP2，运用软件包计 算可得f1=14900元 Date 79 f 18 j 35 i 25 g 30 d 20 1 28 5 764 3 a 60 b 45 c 10 e 40 h 15 0 60 70 80 100 110 135 170 图G（原计划网络） f 18 j 35 i 15 g 20 d 10 1 28 5 764 3 a 60 b 45 c 10 e 35 h 10 0 60 87 70 95 90 105 140 图G2（LP2优化后网络） Date 80 l由上述求解结果知只要工序e，h提前5天d ，g，i工序提前10天，其它工序完工时间 不变，则可使整个工程在T=140天完成， 此时需至少增加投入经费1.49万元。此时 有 ，对于上述LP2之结 果 画出网络图G2，对该G计算网络时间参数 ，得知工程工期恰为140天，且四条路线 均为关键路线。 Date 81 l解：（分析法） u由题设要求缩短工期20天（由170天提前到150 天）完成工程。 根据统筹法原理：向关键工序要时间，故需从 关键工序a，d，g，i，j要时间，比较这五个关 键工序的直接费用变动率（见下表）可知：工 序i直接费用变动率最低，其次是工序 g，注意 到直接费用变动率表中有约束如下：iy6710 ，gy4610，y120 (a)， y780 (j)（i，j工序无 提前余地）。取上限有y67=10，y46=10，经由G1 图计算知恰有TG1=150天，此时需增加支出最少 的直接费用为f1=35010+29010=6400元，此结 果与解1（1）相同。 Date 82 CP1关键 工序 KijCP2关键 工序 Kij a-0a-0 d40010e5005 g35010h4005 i29010j-0 j-0 Date 83 l解： u若工程期限要求在140天完成（提前工期30天），根据 向关键路线CP1：adgij要时间的原理，可根据 上述(1)同理，可设想将关键工序d，g，i分别缩短工期 10天，注意到有 ，故这种设 想