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

2020/6/8,1,运筹学,网络计划技术（统筹法）,2020/6/8,2,统筹方法,计划管理与统筹法1.定义1：对于任何一项生产制造、科学实验、工程实施、军事作战等活动，为了充分利用有限的时间、空间与资源（人力、物力、财力），都必须编制一个科学的工作组织计划来有效地组织、调度与控制该项活动的进程，以实现最佳的效应和效益。而这种为编制科学的组织计划的有效方法统称为统筹方法。,2020/6/8,3,例1甲、乙两工程师从早上六时起床到上班前有一系列活动要做。对于同样的活动过程，有人忙乱不堪，甚至迟到，有人则又快又好，关键在于一个科学的活动实施计划。,穿衣,刷牙,洗脸,做稀饭,热馒头,吃早饭,收拾房间,整理,出门上班,甲,穿衣,洗脸刷牙,收拾房间,整理,吃早饭,出门上班,做稀饭,热馒头,乙,2020/6/8,4,例2大型工程实施（三峡工程、南水北调工程、人造卫星工程、宇航工程等）有如下活动：产品设计、仿真、试制、中试原材料设备定货、采购、运输、入库厂房、设备施工建筑、安装产品计划、生产、销售、安装、调试、维护参与单位涉及国家各部门、各行业、事业单位，为高速度、低成本、高质量，并在规定期限内完成该工程项目，其关键在：抓好科学技术抓好项目管理，组织协调好各单位、各任务、各工序的完成。,2020/6/8,5,例3三军联合作战演习空军夺取制空权，对敌实施地面攻击，运送空降兵海军舰艇护卫，运送陆军、海军陆战队登陆夺取滩头阵地登陆完成后的巩固阵地与纵深发展电子对抗部队实施情报收集分析与电子对抗参与兵种：海军航空兵、海军陆战队、水面舰艇部队、空军歼击机、攻击机、轰炸机、电子对抗机各团、大队，坦克、炮兵、步兵、防化兵、通讯兵、侦察兵、导弹部队等。需迅速订好科学的作战演习计划，以便对作战演习过程演习过程进行有效的管理与控制。,2020/6/8,6,计划管理与统筹法,统筹法研究内容PERT(ProgramEvaluationandReviewTechnique)计划评审技术CPM(CriticalPathMethod)关键路线法GERT(GraphicalEvaluationandReviewTechnique)随机网络技术（直译为图示的评价与评审技术）PERT/CRM，GERT/CPM,2020/6/8,7,统筹法发展历史CPM：1956年在美杜邦公司化工厂建立过程中由美兰德公司提出。PERT：1958年美海军特种计划局在研制“北极星”导弹核潜艇过程中在哈密尔顿公司及洛克菲勒公司协助下提出了一个“北极星计划”以管理整个工程过程中的8家总承包公司，250家分承包公司，3000家三包公司，9000家厂商，由于使用PERT技术，提高了工作效率使整个工期提前两年完成。目前PERT/CPM在日、英、法、德中相继推广使用并由我国在宝钢施工，与钢（8489年）512项工程，南阳油田工程管理均获较大效益。目前国家经贸委、计委已要求重大工程必须采用此技术方法。GERT/CPM在1966年由美国提出，并在阿波罗登月计划中首次使用成功，在英、阿的马岛之战中，1982年4月，英军三天完成计划网络，2003年美军攻击伊拉克（30万大军用三个月制订计划）,建筑施工设备维修,钢铁、造船、汽车制造、石油、地质勘探,航空、航天、新材料、信息工程（含软件工程）,2020/6/8,8,统筹法功能完成工程需做哪些工序，各工序需多长时间完成？总工期预计多长时间？完成工程的各工序采用什么样的逻辑顺序关系？关键工作是什么？如何加快工程的完成。环境发生变化时，该工程的风险分析。,计划管理与统筹法,2020/6/8,9,计划网络图（工序流线图）,计划网络图及其诸要素定义2：反映一个工程项目中各项作业（工序）的内在逻辑关系的一种有向图称为计划网络图，又称统筹图，工序流线图，网络图等，以符号G表示。此中“内在逻辑关系”是指由于工程本身的工艺与组织性要求，而对各工序提出的在时间上和空间上所要求的先后处理关系。定义3：如下表,2020/6/8,10,3,12,a,10,a,b,2020/6/8,11,例4某公司研制新产品的部分工序明细表如下，试画出统筹图。,2020/6/8,12,网络图绘制规则,每一作业用一箭线及前后两节点连接，箭线上标出作业标号，箭线下写上完成该作业的资源数（通常用时间表示）一对结点间只能有一条箭线，且不允许出现回路；若出现并行作业可引入虚工序或人为地将工序一分为二。（虚作业不消耗资源，用虚线表示）,并行作业,2020/6/8,13,网络图绘制规则,不允许出现交叉作业，若出现交叉作业时应引入虚工序,双向箭头可画成,2020/6/8,14,网络图绘制规则,结点编号自左向右增长，工序的终止结点编号大于起始结点编号统筹图只有一个起点与一个终点（图的封闭性）,2020/6/8,15,例5(例4基础上再加三道工序f、g、h)某工程项目作业明细表如下，（1）绘制计划网络图；（2）求关键路线与路长；（3）求关键工序,2020/6/8,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/6/8,17,网络计划实施步骤,工程项目任务分解,确定工程全部事项（工序）的逻辑关系,确定每一工序的延续时间，制定作业明细表,绘制计划网络图，并作调整,对网络图各节点，箭线编号,计算关键路线与关键工序，形成计划初步方案,是否有潜力可挖,是否满足要求,优化计划方案,编制日程计划并执行,执行中发生偏差是否在允许范围内,结束,Y,N,Y,N,N,Y,2020/6/8,18,工序延续时间估计,经验法与专家法（平均值）：适用于重复性工作，不确定性因素少三点估计法（又称六分法）其中a对工序e延续时间的最乐观时间（在顺利情况下工序e完成的最短可能时间）b对工序e延续时间的最悲观时间（最不顺利下工序e完成的最长可能时间）M对工序e延续时间的最可能时间（在正常情况下工序e完成耗费时间）,2020/6/8,19,三点估计法这是由于通常认为工序延续时间,2020/6/8,20,三点估计法分布随机变量的概率密度函数见右,M,a,b,x,f(x),M,a,b,x,f(x),2020/6/8,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/6/8,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，1i1，则有：，其中与分别为关键路线CP路长的期望与方差对，G在规定工期T0内完工的概率有aij工序（i,j）的最乐观时间bij工序（i,j）的最悲观时间mij工序（i,j）的最可能时间,大型工程任务总工期的概率特性,2020/6/8,40,证：大型工程的工序数n1，且各工序对任务总工期的影响均匀地微小，且相互独立，故由中心极限定理知：有,2020/6/8,41,例8：在例7中取工期T0分别为15，17，18，20周，求该计划网络按期T0内完工的概率欲使按期完工的概率达到95%或99%，试确定相应的工程任务总工期T。解：由命题4结论知对有现取T0=15，则有此中CP=15，CP=1.025，已由例7中求得。类似地有,2020/6/8,42,解到,2020/6/8,43,系5：,F(x),1,0.5,CP,x,2020/6/8,44,系6,2020/6/8,45,最关键路线与计划难易系数,定义4：若在G中有关键路线CPi，i=1k，此中各关键路线有对应路长的期望与方差，i=1,2k，（此中显然有），若有，则称为G的最关键路线（即方差最大的关键路线称为最关键路线）有系6知，若表执行最关键路线的对应工期，则有，j=1k，即对任何给定工期T0，执行最关键路线时要在T0内完成的可能性最小，而考虑到只有该（最关键路线）上所有工序全部完成后工程方能完工，因此在G设计时应对上的工序予以特别关注。,2020/6/8,46,2020/6/8,47,-6,-1,1,6,0.692,0.308,2,3,4,2020/6/8,48,2020/6/8,49,定义5：设T为G的工期（随机变量），CP为G的关键路线，CP与为CP路长的期望与方差，则称为执行给定工期T0的计划难易系数。例9对于例7的计划网络G，求解给定工期T0分别取13,15,17,18,20（周）时的计划难易系数0。解：,太保守，有潜力可挖,完成可能性很大,完成可能性很大,完成可能性较大,完成可能性小,2020/6/8,50,网络计划的优化,前述的网络计划仅给出了初等的计划模型，该模型一般是不成熟的，它可能在工期（时间）、资源、或费用上存在种种的问题与矛盾或缺陷，因此需要作进一步的统筹处理，这就是网络计划优化的主要目的，也是整个统筹法研究的精华与主要内容。初步的计划网络往往存在着下述矛盾或问题：时间上计算的总工期有可能超过用户要求期限；或部分工序的时间潜力来得到充分发挥。（浪费时间）资源（有限）上有的工序由于资源供应过多而浪费，而另一些工序则出现资源的供不应求现象。费用上为赶工期而使用的工序增买设备、材料或增发奖金等，但事实上这样的措施却可能不是节约的，而仍然有潜力可挖。优化目的是调整与改善原始计划，以求得一个时间进度快，资源消耗少，成本低的最优计划方案。,2020/6/8,51,网络优化模型的类型,单目标优化模型，通常有：时间优化资源（设备、材料、人力等）优化费用优化多目标优化模型时间资源优化模型时间费用优化模型时间资源费用优化模型,2020/6/8,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/6/8,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/6/8,54,将富裕线路（非关键线路）上的资源调整到关键线路上来。以推迟非关键工序的开始时间来换取工期的节省。以推迟非关键工序的延续时间来换取工期的节省。同时推迟非关键工序的开始时间和延续时间。从计划G外增拨资源增拨运输车辆，工人由二班变为三班等方式。来缩短工期。,时间优化的一般原理,2020/6/8,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/6/8,56,时间资源优化,合理利用现有资源，以最大限度的缩短工期，这就是网络计划的时间资源优化的目的。设T(G)表网络计划G对应的工期A(G)表网络G所消耗的资源则时间资源优化模型为如下双目标数学规则,2020/6/8,57,时间资源优化,时间资源优化准则：关键工序所需资源优先安排“削峰填谷”原则：利用非关键工序的时差推迟某些非关键工序的开始时间，以降低某些资源需求高峰时段的资源需求量，同时提高某些资源需求低谷时段的资源需求量，在不影响网络工期的前提下实现工期内各时段的资源均衡使用。特殊资源特殊利用，工序资源调配以公共资源为主。,2020/6/8,58,G时间资源优化程序框图,输入工序明细表，资源需求表,计算网络时间参数，确定关键路线CP,利用横道图及逐日（或月、年）资源需求量A(t)，绘制tA(t)曲线，并作系统分析,搜索资源需求峰值Gp及其对应时段（ta,tb），设置控制水平G0，作tstb，说明工序(i,j)有后移到tb后的可能R(i,j)=LSES(i,j)Th(i,j)=LStb为对后移到tb后的有效机动时间,2020/6/8,62,G图,2020/6/8,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/6/8,64,58,G0,2020/6/8,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/6/8,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/6/8,67,工序高峰期后移计算（见程序框图）,2020/6/8,68,解由资源负荷图(d)及横道图(c)获得经调整后各工序f,h的最早开工时间ES(i,j)，最早结束时间EF(i,j)对未调整的工序之ES(i,j)与EF(i,j)仍用原网络G图之数据，可得如下新网络图。对重新计算各网络时间参数。最终仍可得工期当G后，由于与G有相同工期，且各时段之资源负荷均小于供应量G0且相对均衡，故END。,2020/6/8,69,时间费用优化,基本概念与符号（前述模型为后移工序的ES，以下模型为缩短工序长度t(i,j)）直接费用为加快工程进度需对关键工序新增人力，设备和工作班次，从而需新增一笔投入费用（作为奖金或设备购置费），此笔费用称之为直接费用。间接费用管理人员的工资，办公费用（出差费、用车费、复印费等）统称为间接费用。通常当工序作业时间愈短，直接费用愈多，间接费用愈少。,2020/6/8,70,2020/6/8,71,优化模型,目标：在给定工期T的约束下，求计划网络G各工序完成时间，以使因缩短工期而增加的直接费用达最小。,2020/6/8,72,优化模型,2020/6/8,73,优化模型,说明：优化模型仅考虑直接费用，未考虑间接费用，后述优化模型，则同时考虑直接费用与间接费用的综合效果。上述LP模型之决策变量为yij，亦即仅考虑工序(i,j)的提前，而未考虑工序(i,j)是否关键，因此对上述优化模型求解后有可能改变关键路线，从而使实际总工期并未缩短，此时应重新建立优化模型求解。模型中的xj为中间变量（yi决定）由LP求得yij有（工期提前量），但不一定有（详见下例14(2)）,2020/6/8,74,例14：对例6的计划网络补充如下有关信息，以研究工期的提前性以及相应工序的提前量。若该工程按G需170天完成，现需要提前到150天完成，试求相应各工序的提前量。若该工程需提前到140天完工，试求相应各工序的提前量及应增加的费用投入。,2020/6/8,75,2020/6/8,76,解1：由优化模型思路有LP如下：,2020/6/8,77,图G（原网络）,2,4,6,7,8,60,d20,g30,i25,j35,80,110,135,170,100,115,150,20,15,图G1（经LP1优化后网络）,2020/6/8,78,原计划（未调整）网络见右上图G，经上述优化后之网络见右上G1结论：即缩短工序g与i各10天，其余工序长度不变，为此需付出的最少直接费用为6400元，这样即可将工期由原170天提前20天，即T=150天可完工。GG（见上右图G1）,2020/6/8,79,(2)将上述优化模型的最后一个约束x8140，其它均不变，则构成LP2，运用软件包计算可得f1=14900元,2020/6/8,80,图G（原计划网络）,图G2（LP2优化后网络）,2020/6/8,81,由上述求解结果知只要工序e，h提前5天d，g，i工序提前10天，其它工序完工时间不变，则可使整个工程在T=140天完成，此时需至少增加投入经费1.49万元。此时有，对于上述LP2之结果画出网络图G2，对该G计算网络时间参数，得知工程工期恰为140天，且四条路线均为关键路线。,2020/6/8,82,解：（分析法）由题设要求缩短工期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）相同。,2020/6/8,83,2020/6/8,84,解：若工程期限要求在140天完成（提前工期30天），根据向关键路线CP1：adgij要时间的原理，可根据上述(1)同理，可设想将关键工序d，g，i分别缩短工期10天，注意到有，故这种设想是可以做到的，即取y24=y46=y