第7章-网络计划-谢家平课件

运筹学运筹学 O OPERATIONS RESEARCHPERATIONS RESEARCH精品PPT 第第7 7章章网络计划网络计划第第1 1节节 网络计划概述网络计划概述第第2 2节节 网络图的绘制网络图的绘制第第3 3节节 关键路线法关键路线法第第4 4节节 计划评审技术计划评审技术第第5 5节节 网络计划优化网络计划优化第第6 6节节 缓冲时间设置缓冲时间设置 精品PPT第第1 1节节 网络计划概述网络计划概述l网络计划法网络计划法(networkprogram,NP)也称网也称网络计划技划技术,是利用网是利用网络图及其及其时间参数参数计算算进行生行生产组织与管理的一种方法。与管理的一种方法。网络计划技术的特性网络计划技术的特性 反映和表达项目计划安排的一种方法，是被项目施工技术反映和表达项目计划安排的一种方法，是被项目施工技术所决定的，它只能适应项目施工方法的要求。所决定的，它只能适应项目施工方法的要求。是把工程进度安排通过网络的形式直观地反映出来。是把工程进度安排通过网络的形式直观地反映出来。精品PPT 网络计划的发展历程网络计划的发展历程 v关关键路路线法法(Critical Path Method，CPM)关关键路径是指路径是指设计中从中从输入到入到输出出经过的延的延时最最长的的逻辑路径。路径。优化关化关键路径是一种提高路径是一种提高设计工作速度的有效方法。工作速度的有效方法。v计划划评审技技术(Program Evaluation and Review Technique，PERT)利用网利用网络分析制定分析制定计划以及划以及对计划予以划予以评价的技价的技术。它能它能协调整个整个计划的各道工序，合理安排人力、物力、划的各道工序，合理安排人力、物力、时间、资金，金，加速加速计划的完成。划的完成。PERT被广泛地使用，是被广泛地使用，是现代代项目管理的重要手段和方法。目管理的重要手段和方法。精品PPT5v图图示示评审评审技技术术(Graphic Evaluation and Review Technique，GERT)在在PERT的的基基础础上，增加决策上，增加决策节节点，不点，不仅仅将活将活动动的各参数如的各参数如时间时间和和费费用用设为设为随机性分布，而且其各个活随机性分布，而且其各个活动动及相互之及相互之间间的影响关系也的影响关系也具有具有随机性。随机性。该该方法通方法通过过解析方法及蒙特卡解析方法及蒙特卡罗罗模模拟拟方法，最方法，最终终求出求出项项目成本和目成本和工期的概率分布曲工期的概率分布曲线线。图图形形评审评审技技术术是是项项目目时间时间管理的管理的术语术语。v风险评审风险评审技技术术(Venture Evaluation Review Technique，VERT)是一种以管理系是一种以管理系统为对统为对象，以随机网象，以随机网络络仿真仿真为为手段的手段的风险风险定量分定量分析技析技术术。精品PPT我国，是从我国，是从2020世纪世纪6060年代开始运用网络计划的，著名年代开始运用网络计划的，著名数学家数学家华罗庚华罗庚教授结合我国实际，在吸收国外网络计教授结合我国实际，在吸收国外网络计划技术理论的基础上，将划技术理论的基础上，将CPMCPM、PERTPERT、GERTGERT、VERTVERT等方等方法统一定名为法统一定名为统筹法统筹法。统筹方法包括绘制计划网络图、进度安排、网络优化统筹方法包括绘制计划网络图、进度安排、网络优化等环节。等环节。精品PPT第第2 2节节 网络图的绘制网络图的绘制工工序序(作作业业)：一一项项需需要要人人财财物物或或时时间间等等资资源源的的相相对对独独立立的的活活动过程动过程在网络图中用箭线在网络图中用箭线“”表示，表示，前面直接相连工序称前面直接相连工序称紧前工序紧前工序，直接相连的后继工序为直接相连的后继工序为紧后工序紧后工序。结点结点(事项事项)：相邻工序的分界点相邻工序的分界点一般用圆圈来表示，每个结点编上顺序号，一般用圆圈来表示，每个结点编上顺序号，结点既不消耗人力、物力，也不占用时间。结点既不消耗人力、物力，也不占用时间。精品PPT网络图网络图由工序、结点及时间参数所构成的有向图即为网络图。由工序、结点及时间参数所构成的有向图即为网络图。箭线表示工序箭线表示工序,结点为工序间相互关系的网络图，称结点为工序间相互关系的网络图，称箭箭线式网络线式网络结点表示工序结点表示工序,箭线为工序间相互关系的网络图，称箭线为工序间相互关系的网络图，称结结点式网络点式网络精品PPT1.1.箭线式网络图箭线式网络图 21A25B343C55D5Et作作业时间iN作作业名称名称j2.2.结点式网络图结点式网络图 t作作业时间N N作作业名称名称iNti i作作业序号序号122543355560精品PPT工序表示的规定工序表示的规定一条箭线和它的相关结点只能代表一道工序，不能代表多一条箭线和它的相关结点只能代表一道工序，不能代表多道工序，道工序，两个结点之间只能有一条箭线相连两个结点之间只能有一条箭线相连。不允许出现缺口与回路不允许出现缺口与回路网络图中网络图中只能有一个始点和一个终点只能有一个始点和一个终点，使得自网络图的始，使得自网络图的始点经由任何路径都可以到达终点。点经由任何路径都可以到达终点。虚工序虚工序虚工序是为了表达相邻工序之间的逻辑关系而虚工序是为了表达相邻工序之间的逻辑关系而虚设的工序虚设的工序。不消耗时间、费用和资源，一般用虚箭线表示。不消耗时间、费用和资源，一般用虚箭线表示。ij精品PPT方向的规定方向的规定网络图是有方向的，工序应按工艺流程顺序或工作逻辑网络图是有方向的，工序应按工艺流程顺序或工作逻辑关系关系从左向右排列从左向右排列。编号的规定编号的规定编号应从始结点开始，按照时序依次从小到大对结点编编号应从始结点开始，按照时序依次从小到大对结点编号，直到终结点。号，直到终结点。编号时编号时不允许箭头编号小于箭尾编号不允许箭头编号小于箭尾编号。节点标号：节点标号：j iij精品PPT某工程的工序一览表某工程的工序一览表 工序工序abcdefg紧前工序紧前工序-a,bac,dae,f工序时间工序时间4235556例例7-1精品PPT 例例7.17.1某公司研制新产品的部分工序与所需时间以及它某公司研制新产品的部分工序与所需时间以及它们之间的相互关系都显示在其工序进度表如表所示，请们之间的相互关系都显示在其工序进度表如表所示，请画出其网络计划图。画出其网络计划图。工序代号工序代号所需时间所需时间（天）（天）紧前工序紧前工序abcdefgh60151338810165aacb，dde，精品PPT161257834a6015bec13d388h510f6g精品PPT第第3 3节节 关键路线法关键路线法关关键键路路线线法是在网法是在网络图络图的基的基础础上，通上，通过计过计算算时间时间参数，确参数，确定关定关键键路路线线，从而，从而对对工程工程项项目目进进行更有效的行更有效的协调协调与与计计划。划。关关键键路路线线法适用于常法适用于常规规性生性生产项产项目的目的计计划安排，各划安排，各项项工作工作重复性重复性发发生，有确定的操作生，有确定的操作规规程和程和时间时间定定额额，有，有较较完完备备的的统计资统计资料。料。关关键键路路线线法相当于法相当于经经常常说说到的到的“确定型模型确定型模型”。精品PPT一、结点的时间参数一、结点的时间参数 结点的最早时间结点的最早时间tE(j)指以指以该结点点为始点的各道工序最早可能的开工始点的各道工序最早可能的开工时刻，刻，等于从始点开等于从始点开始到本结点的最长路线上各道工序时间之和。始到本结点的最长路线上各道工序时间之和。从始点事项开始，自左向右，顺着箭线方向逐个计算从始点事项开始，自左向右，顺着箭线方向逐个计算。结点的最迟时间结点的最迟时间 tL(j)指以指以该结点点为结束的各道工序最束的各道工序最迟必必须完工的完工的时刻，否刻，否则将会影响将会影响后后续工序按工序按时开工，以至推开工，以至推迟整个工程的完工整个工程的完工时间。从从终点开始，从右向左，逆箭点开始，从右向左，逆箭线方向逐个方向逐个计算。算。精品PPT精品PPT二、工序的时间参数二、工序的时间参数 最早开工时间最早开工时间tES(i,j)一个作业必须在其各紧前作业都完工后才能开工，作业最一个作业必须在其各紧前作业都完工后才能开工，作业最早可能开工时间等于其箭尾事项的最早时间。早可能开工时间等于其箭尾事项的最早时间。tES(i,j)=tE(i)最早完工时间最早完工时间 tEF(i,j)从最早可能开工时间开工，完成本作业的时间从最早可能开工时间开工，完成本作业的时间。tEF(i,j)=tES(i,j)+t(i,j)工序工序a的最早的最早开始开始时间工序工序a的最早的最早完成完成时间ija0，6060精品PPT最迟完工时间最迟完工时间 tLF(i,j)在不影响工程如期完工的前提下，作业最迟必须完工在不影响工程如期完工的前提下，作业最迟必须完工的时刻的时刻。tLF(i,j）=tL(j)最迟开工时间最迟开工时间 tLS(i,j)在不影响工程如期完工的前提下，作业最迟必须开工在不影响工程如期完工的前提下，作业最迟必须开工的时刻。的时刻。等于它的箭头事项的最迟时间减去本作业的作业时间等于它的箭头事项的最迟时间减去本作业的作业时间 tLS(i,j)=tL(j)-t(i,j)工序工序a的最晚的最晚开始开始时间工序工序a的最晚的最晚完成完成时间ij0，60a精品PPT精品PPT三、时差与关键路线三、时差与关键路线 总总时时差差R(i,j)：不不影影响响其其紧紧后后工工序序最最迟迟开开工工的的前前提提下下，本本工工序最早可能完工时间可以推迟的时间。序最早可能完工时间可以推迟的时间。R(i,j)=tLS(i,j)-tES(i,j)=tLF(i,j)-tEF(i,j)单单时时差差r(i,j)：不不影影响响其其紧紧后后工工序序最最早早开开工工的的前前提提下下，本本工工序最早可能完工时间可以推迟的时间。序最早可能完工时间可以推迟的时间。r(i,j)=tES(j,k)-tEF(i,j)总时差为零的工序称为总时差为零的工序称为关键工序关键工序；关键工序组成；关键工序组成关键路线关键路线。精品PPT精品PPT四、时间参数计算四、时间参数计算 作业作业t(i,j)tES(i,j)tEF(i,j)tLS(i,j)tLF(i,j)R(i,j)r(i,j)关键作业关键作业abcdefg精品PPT第第4 4节节 计划评审技术计划评审技术实际实际工作中，工作中，许许多工程多工程项项目的目的工序工序时间时间是不确定的是不确定的或者是由于随机因素的影响或者是由于随机因素的影响或者是属于开拓性的工作，没有或者是属于开拓性的工作，没有经验经验数据或数据或统计资统计资料料很很难难确定工序确定工序时间时间，这时这时便不宜采用关便不宜采用关键键路路线线法法采用采用计计划划评审评审技技术术，对对工序工序时间进时间进行粗略的估行粗略的估计计，而，而后后绘绘制网制网络图络图，找出关，找出关键键路路线线，并可，并可对对工程工期工程工期进进行行概率估概率估计计精品PPT一、作业时间估计一、作业时间估计 工序时间（工序时间（分布分布）的三种可能估计：）的三种可能估计：最乐观时间最乐观时间：在最理想的情况下完成工序所需时间：在最理想的情况下完成工序所需时间 a；最悲观时间最悲观时间：在最不利的情况下完成工序所需时间：在最不利的情况下完成工序所需时间 b；最可能时间最可能时间：在正常情况下完成工序所需时间：在正常情况下完成工序所需时间 m。加权平均就是工序时间加权平均就是工序时间 t 精品PPT期望工期等于关期望工期等于关键路路线上各道工序的上各道工序的时间之和之和。设规定的工程完工定的工程完工时间为Tk，则完工完工时间的概率的概率为二、计算期望工期二、计算期望工期 精品PPT例例7-2 某某项项目的作目的作业业及相关及相关时间时间如表。求如表。求项项目的最短期望目的最短期望工期；若合同工期；若合同规规定工期定工期为为17，求如期完成的概率；若要求，求如期完成的概率；若要求有有90%的把握如期完成，求可接受的合同工期。的把握如期完成，求可接受的合同工期。作业作业紧前作业紧前作业乐观时间乐观时间悲观时间悲观时间可能时间可能时间期望期望方差方差abcdefg-a,bac,dae,f312233453410119124234.544.55精品PPT精品PPT第第5 5节节 网络计划优化网络计划优化一一、缩短工程工期、缩短工程工期改进工艺和技术装备，压缩关键工序的作业时间改进工艺和技术装备，压缩关键工序的作业时间合理组织平行作业、交叉作业合理组织平行作业、交叉作业平行作业平行作业指两道以上相互独立的工序同指两道以上相互独立的工序同时进行行交交叉叉作作业业指指将将紧前前工工序序完完成成的的部部分分任任务分分期期分分批批地地转入下道工序入下道工序利用时差，合理调配资源等途径实现利用时差，合理调配资源等途径实现总时差不影响最短工期，但影响后差不影响最短工期，但影响后续工序的自由工序的自由时间。单时差不影响后差不影响后续工序。工序。精品PPT把串联工作改为平行工作或平行交叉工作把串联工作改为平行工作或平行交叉工作精品PPT二、工期二、工期-费用优化费用优化工期与成本之间关系工期与成本之间关系工期的缩短与费用是密切相关的工期的缩短与费用是密切相关的工程费用最低的完工时间工程费用最低的完工时间(最低成本日程最低成本日程)时间费用用极限完极限完工工时间正常完正常完工工时间直接直接费用用间接接费用用最最优完完工工时间工程工程总费用用精品PPT直接费用直接费用：为了加快工程进度，需要增加人力、设备和工作：为了加快工程进度，需要增加人力、设备和工作班次，这需要增加一笔费用，成为直接费用。班次，这需要增加一笔费用，成为直接费用。间接费用间接费用：由于工程早日完工，减少了管理人员的工资办公：由于工程早日完工，减少了管理人员的工资办公费等费用称为间接费用。费等费用称为间接费用。一般说工序越短，直接费用越多，间接费用越少。一般说工序越短，直接费用越多，间接费用越少。精品PPT寻求最低成本日程的思路：从网络计划的关键工序着手，寻求最低成本日程的思路：从网络计划的关键工序着手，对增加直接费用做少的某些关键工序采取措施，缩短其作对增加直接费用做少的某些关键工序采取措施，缩短其作业时间。业时间。时间直接直接费用用极限完极限完工工时间正常完正常完工工时间精品PPT完成工序完成工序j的正常所需的正常所需时间为时间为Tj;直接直接费费用用为为cj;完成工序完成工序j的最快完成的最快完成时间为时间为Tj,直接直接费费用用为为cj。缩缩短工序短工序j的一天工期所增加的直接的一天工期所增加的直接费费用，用用，用kj表示，称表示，称为为直直接接费费用用变动变动率（成本斜率）率（成本斜率）。有。有精品PPT某工程作业流程及其费用统计资料某工程作业流程及其费用统计资料 作业作业紧前作业紧前作业作业时间（天）作业时间（天）作业直接费用（万元）作业直接费用（万元）费率费率正常完工正常完工极限完工极限完工正常完工正常完工极限完工极限完工a-438124b-2116171ca,b322021.21.2da5210131ec,d5315192fa5310121ge,f649174合计合计88间接费用间接费用2万元万元/天天例例7-3精品PPT方案方案I I：各道作各道作业业正常完工正常完工工程费用工程费用=正常完工直接费用正常完工直接费用+间接费用间接费用 =88+220=128万元。万元。0,40,40,24,74,99,1414,204,914,209,149,144,96,94,6精品PPT方案方案2 2：关关键路路线aad degeg上赶上赶进度度 考考虑关关键工序可工序可压时间、费用用变动率率 非关非关键路路线总时差差为4、2、5，故赶，故赶2天。天。工程费用工程费用=正常完工直接费用正常完工直接费用+赶进度增加的直接费用赶进度增加的直接费用+间接费用间接费用 =88+21+218=126万元。万元。0,40,40,24,74,99,1414,204,914,209,149,144,96,94,6精品PPT方案方案3 3：关关键路路线adade egg，acace egg上赶上赶进度度 考考虑关关键工序可工序可压时间、费用用变动率率 非关非关键路路线总时差差为2 2、3 3，故赶，故赶2 2天。天。工程费用工程费用=正常完工直接费用正常完工直接费用+赶进度增加的直接费用赶进度增加的直接费用+间接费用间接费用 =88+21+22+216=126万元。万元。0,40,40,24,74,77,1212,184,912,187,127,124,74,72,4精品PPT方案方案4 4：关关键路路线aad de egg，aac ce egg上上赶赶进度各赶度各赶1天天工程费用工程费用=正常完工直接费用正常完工直接费用+赶进度增加的直接费用赶进度增加的直接费用+间接费用间接费用 =88+21+21.5+1(1+1.2)+215=126.2万元。万元。0,40,40,24,74,77,1010,164,910,165,107,104,74,72,4精品PPT线性规划法线性规划法S.t.xj-xi Tij-yij,对对一切弧（一切弧（i,j)yij Tij-Tij,对对一切弧（一切弧（i,j)xn-x1 T,xi 0，yij 0。提前完工提前完工时间为时间为yijTij,Tij分分别别表示正常完工表示正常完工时间时间与最快完工的与最快完工的时间时间实际实际完工完工时间为时间为：Tij-yij 精品PPT三、工期三、工期-资源优化资源优化资源平衡准则：资源平衡准则：u考量每道作业所需资源的用量与供应能力，安排进度。考量每道作业所需资源的用量与供应能力，安排进度。u通过平衡资源，取得工期与资源的最优配置通过平衡资源，取得工期与资源的最优配置优先保证关键路线优先保证关键路线上关键作业对资源的需求量。上关键作业对资源的需求量。对非关键作业要资源对非关键作业要资源，利用时差调整非关键作业的开，利用时差调整非关键作业的开工工/完工时间，拉平资源需要量的高峰。完工时间，拉平资源需要量的高峰。u当资源绝对受限制时，在保证不推迟或尽量少推迟工期当资源绝对受限制时，在保证不推迟或尽量少推迟工期的前提下，全面统筹安排，最大限度地利用资源。的前提下，全面统筹安排，最大限度地利用资源。精品PPT每天只有每天只有1313台设备可用，工期台设备可用，工期2020天，试合理安排进度天，试合理安排进度工序工序abcdefg紧前工序紧前工序-a,bac,dae,f作业时间作业时间4235556每天所需设备数每天所需设备数137856712例例7-40,40,40,24,74,99,1414,204,914,209,149,144,96,94,6精品PPT(1)(1)制定初始方案制定初始方案以最早开工以最早开工时间，安排初始，安排初始进度如表度如表 精品PPT(2)(2)调整开工时间调整开工时间精品PPT第六节第六节 缓冲时间设置缓冲时间设置“学生学生综综合症合症”是人的一种普遍行是人的一种普遍行为为“还还早呢，急什么？早呢，急什么？”考考试试，“临阵临阵磨磨枪枪”写作，不到写作，不到时时候不候不动动笔笔 任任务务，不急不，不急不办办对对管理的启示管理的启示“留有余地留有余地”是否是安排工作的有效方式？是否是安排工作的有效方式？留有多少余地最好？留有多少余地最好？在什么地方留有余地最好？在什么地方留有余地最好？精品PPT高德拉特考高德拉特考虑人的行人的行为，突破，突破“关关键路路线”的金科玉律，的金科玉律，1997年提出关年提出关键链方法方法以色列以色列飞机工机工业有限公司运用关有限公司运用关键链方法，将方法，将飞机机维修施工期由修施工期由3个月个月缩减到减到2星期。星期。美国美国宾州建一芯片厂，州建一芯片厂，预计28-36个月才能建成，运个月才能建成，运用关用关键链方法，方法，计划划18个月，个月，实际13个月。个月。精品PPT具体的思路是：具体的思路是：削减每道作业的预估时间，不为单道作业削减每道作业的预估时间，不为单道作业设置安全缓冲时间，而将节省的时间建立一个任务缓冲（某设置安全缓冲时间，而将节省的时间建立一个任务缓冲（某项任务的总体安全时间）项任务的总体安全时间）高德拉特（高德拉特（EliyahuEliyahu GoldrattGoldratt）的）的关键链方法关键链方法精品PPT任务1任务2任务3任务4 1 2 3 4项目缓冲将每项任务的预估将每项任务的预估时间减去一半，然时间减去一半，然后将减去时间的和后将减去时间的和的一半作为项目缓的一半作为项目缓冲，共用，所需时冲，共用，所需时间为原来的间为原来的3/4 4 6 3 5 18 2 3 1.5 2.5 4.5 13.5精品PPT考虑资源冲突，使制约因素（瓶颈资源）不受非制约因素考虑资源冲突，使制约因素（瓶颈资源）不受非制约因素的影响，在每条衔接路径与关键路线汇合的地方插入衔接时的影响，在每条衔接路径与关键路线汇合的地方插入衔接时间缓冲，例如零件的供货缓冲时间间缓冲，例如零件的供货缓冲时间 项目缓冲衔接缓冲衔接缓冲A1 A2 B1 B2 C1 C2 C3 C4精品PPT作作 业业3 34 45 5精品PPT