运筹学第八章项目管理.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,浙江大学管理学院,杜红 博士 副教授,应用运筹学,第八章 项目管理网络计划技术）,项目管理的背景,项目网络的绘制,网络时间的计算,关键线路的确定,网络计划的调整,项目管理背景,工程：一系列特定的能自行控制的工作，有,明确的起始与结束时间。,项目管理：方案、组织和控制资源人员、,设备和物料），使其满足项目的,技术、成本和时间等要求。,项目控制,报告机制：项目进展的信息收集处理系统。,甘特图、成本分解图、时间进度表,组织机制：项目的组织形式。,组织结构职能、矩阵）、项目经理、,项目管理背景,网络计划：通过绘制项目网络图与网络计算,统筹安排工程项目和专项任务。,关键路线技术：运用关键路线制定网络计划.,CPM(Critical Path Method)关键路线法,PERT(Program Evaluation and Review,Technique)计划评审技术,适用性：生产技术复杂、工作项目繁多且联系紧,密的一些跨部门的工作计划。如：新产,品研制、大型工程项目、生产技术的准,备，设备大修计划等流程性工程,项目管理背景,网络计划制定的条件,组成项目的各项活动都可以作为实体加以识别,（有清晰的开始和结束时间，相互独立）,项目活动序列的关系可以被确定和网络化,存在资源调整的可能性,网络计划的编制,工程任务分析工序划分、关系及时间估计）,绘制网络图形实、虚箭线、结点、线路）,计算时间参数最早、最晚开始与结束时间）,确定关键线路总时差为零的工序为最长线路）,网络优化调整工期、时间费用、资源分析）,网络图的绘制,网络图的构成,实箭线：表示一道具体的工序。箭头方向表示工序进行方向，箭尾位置表示工序开始，箭头位置表示工序结束。,虚箭线：表示一道虚工序，虚工序仅仅表示工序与工序之间的关联关系，不需要消耗时间和资源。,工序名称或代码,工序时间,工序名称或代码,网络图的绘制,网络图的构成,结点：又称事项、事件等。表示一个工序的开始或结束。用圆圈表示，在圈内注上该结点的序号。整个网络图的开始事项称起始结点，最后工序结束事项为结束结点。只有当某一结点的所有紧前工序都完成后，它的紧后工序才能开始,（A是B的紧前工序，B是A的紧后工序）,线路：从起始结点沿箭头方向连续不断地到达终点的通路。线路有多条，线路的长度为各工序的时间和，最长的为关键线路。,1,2,3,A,B,网络图的绘制,绘制网络图的准备工作,确定目标：以时间要求还是资源费用要求为主,工程分解：列出全部分解后的工序及代号清单,工序关系：确定每一道工序的紧前工序是哪些,工序时间：确定每一道工序的完成所需的时间,一时估计法：仅估计一个完成工序的最大时间D,三时估计法：乐观时间 a、悲观时间b、最可能时间m,网络图的绘制,网络图绘制规则,方向、时序与结点编号,网络图是有向图，按流程的顺序，规定工序从左向右排列。网络图中的各个结点都有一个时间某一个或若干个工序开始或结束时间），一般按结点的时间顺序编号从左到右，从上到下），箭尾结点编号应小于箭头结点编号。始结点编号为1。,网络图中不能出现缺口和回路,二个结点之间只能有一个直接的工序,两条箭线不能有同样的始末结点，若二个事项之间有几个平行进行的工序，不许直接连接，而需要引入虚工序。,网络图的绘制,网络图绘制规则,平行作业,有几个工序平行作业结束后转入下一个工序的情况下，考虑到计算网络时间的方便，选择在平行作业的几个工序中所需时间最长的一个工序，直接与其紧后工序衔接，而其它工序则通过虚工序与其紧后工序衔接。,交叉作业,对需要较长时间才能完成的一些工序，在工艺流程与生产组织条件允许的情况下，可以不必等待工序全部结束后再转入其紧后工序，而是分期分批的转入。分批转入时需增加虚工序。,网络图的绘制,网络图绘制规则,始点和终点,为表示工程的开始和结束，在网络图中只能有一个始点和一个终点。当工程开始时有几个平行工序或结束时有几个平行工序，而又不能用一个始结点或一个终结点表示时，需用虚工序把它们与始结点或终结点连接。,网络图布局,尽可能将关键线路布置在中心位置，尽量将联系紧密的工作布置在相近的位置；尽量用水平线或具有一段水平线的折线。,网络图的绘制,虚工序应用,1,2,A,B,3,2,1,A,B,工序,紧前,A,B,C,D,-,-,A,A,B,D,C,B,A,4,2,1,3,5,4,5,6,网络图的绘制,虚工序应用,1,2,A,B,3,2,1,A,B,工序,紧前,A,B,C,D,-,-,A,A,B,D,C,B,A,4,2,1,3,5,4,5,6,D,C,B,A,2,1,4,3,网络图的绘制,虚工序应用平行与交叉）,1,3,2,12,A,1,2,4,3,5,A3,A2,A1,4,4,4,B,B,A:修路基,B:铺轨道,A=A1+A2+A3,B=B1+B2+B3,1,3,5,7,8,6,4,2,A1,B2,B1,A3,A2,B3,12,12,网络图的绘制,例81：某化工厂管道安装的工程进度表:,工程项目,分解,工序,代号,紧前,工序,工序,时间,器材调查,停用管道,搭脚手架,拆除旧管道阀门,装备阀门,装备管道,组装管道,安装管道,A,B,C,D,E,F,G,H,-,A,A,B,C,A,A,F,D,E,G,8,8,12,35,225,200,40,32,工程项目,分解,工序,代号,紧前,工序,工序,时间,安装阀门,焊接管道,装配管道 和阀门,包扎阀门,拆脚手架,压力试验,整理现场,I,J,K,L,M,N,P,D,E,H,I,J,J,K,L,K,M,N,8,8,8,24,4,6,4,网络图的绘制,例81：某化工厂管道安装的网络图,先画出没有紧前工序的工作A,在A后画出紧前工序为A 的各工作,即B,C,E,F。,A,B,C,E,F,网络图的绘制,例81：网络图的绘制,在表中查出B,C为D的紧前工序，F为G的紧前工序，则在F工序后画出G，在B,C工序后面画出D。,G,D,A,B,C,E,F,网络图的绘制,例81：网络图的绘制,画出H,I,J的工序如下：,A,B,C,E,F,G,D,H,I,J,H紧前：D、E、G,I紧前：D、E,J紧前：H、I,H 除 J,外已没有,紧后工序,网络图的绘制,例81：网络图的绘制,画出K,L工序，K,L的紧前工序均为J。,A,B,C,E,F,G,D,H,I,J,L,K,网络图的绘制,例81：网络图的绘制,在K,L后画出M,N,P：,1,2,5,4,3,A,B,C,E,F,7,6,G,D,H,I,8,9,J,10,11,L,K,N,M,P,M紧前：K、L,N紧前：K,P紧前：M、N,12,13,网络图的绘制,练习：画出以下网络图,工序,工序代号,所需时间,紧后工序,产品设计,A,60,B,C,D,E,外购配套件,B,45,L,下料、锻件,C,10,F,工装制造1,D,20,G,H,木模、铸件,E,40,H,机械加工1,F,18,L,工装制造2,G,30,K,机械加工2,H,15,L,机械加工3,K,25,L,装配调试,L,35,-,网络图的绘制,练习答案：,1,5,3,8,7,6,4,2,A,H,E,L,K,G,D,F,C,B,60,45,18,10,20,40,15,30,25,35,时间参数的计算,符号约定,i,E(i),L(i),S(i),j,E(j),L(j),S(j),K,D(i,j),LFij,EFij,LSij,ESij,E(1)=0,L(j),E(j),L(n)=E(n),保证质量和不增加人力物力的前提下尽量缩短工期。,在原关键线路上各工序的总时差均为3，因此,优先安排关键工序所需要的资源；,L(n)=E(n),费用直接费用间接费用,例84：教材P315，实例10.,组成项目的各项活动都可以作为实体加以识别,技术、成本和时间等要求。,例84：教材P315，实例10.,整个项目的周期服从正态分布,最早结束时间：EFij=ESij+D(i,j),关键路径为 E-F-G-J,周期为24周，正常总成本为正常成本的加总，总计为221000，超过要求时间6周，罚金成本为21000，总成本为242000。,=13,结点最迟时间L(i)的计算,必须满足以上条件才有可能缩短3天,表上作业法：计算工序时间，总时差为0的工序组成关键线路。,时间参数的计算,结点事项时间,结点本身不占用时间，它只表示某项工作应在某一时刻开始或结束，因此，结点参数主要只有两个：最早实现时间最早时间和最迟实现时间最迟时间）。,最早时间：以该结点结束的工作最早可能结束的时间，或以该结点开始的工作最早可能开始的时间。E(1)=0,E(n)为工程时间，从左往右计算。,最迟时间：允许所有后续工序都能及时开始的最晚时间。L(n)=E(n),L(0)=0，从右往左计算。,时间参数的计算,结点事项时间计算,结点最早时间E(j)的计算,E(1)=0,E(j)=maxE(i)+D(i,j),i=2,3,4,9,8,7,6,7,E(7)=5,E(8)=6,E(9)=MAXE(7)+6,E(8)+7),=13,时间参数的计算,结点事项时间计算,结点最迟时间L(i)的计算,L(n)=E(n),L(i)=MINL(j)-D(i,j),j=n-1,n-2,9,11,10,20,12,L(10)=70,L(11)=89,L(9)=MIML(10)-20,L(11)-12),=50,时间参数的计算,工序时间参数计算,一个工序可以从箭尾结点的最早时间开始作业，也可以适当推迟开始，但须在箭头结点的最迟时间内完工才不至于延误后续工序，因此工序时间就包括最早开始时间和最迟开始时间，加上或减去该工序的作业时间，相应地还有最早结束时间和最迟结束时间。,最早开始时间:ESij=E(i),最早结束时间：EFij=ESij+D(i,j),最迟结束时间：LFij=L(j),最迟开始时间：LSij=LFij-D(i,j),时间参数的计算,时差及计算,结点时差：最迟与最早时间差 S(i)=L(i)E(i),工序总时差：不影响工期(最早结束时间的该工序可松动的时间可以推迟开始的时间）.,Sij=LSij ESij,=LFij EFij,=L(j)E(i)D(i,j)（总浮动）,工序单时差：不影响紧后工序最早可能开始条件下，工序最早可能完工时间可以推迟的时间.,Rij=E(j)EFij （自由浮动）,时间参数的计算,工序及时差关系,工序,A,ES,工序A,的紧后工序,ES,EF,LF,LF,EF,LS,LS,总时差SA,单时差RA,(自由浮动),D,关键线路的确定,关键线路,关键线路的长度决定了工程周期，关键线路可以有多条，计划安排得越紧凑，关键线路越多。,关键线路的确定,破圈法：在圈中去掉最短的一个工序。,图上作业法：标注结点时间，结点时差为0的结点组成关键线路。,表上作业法：计算工序时间，总时差为0的工序组成关键线路。,例8-2：关键线路的确定,破圈法：,1,5,3,8,7,6,4,2,A,H,E,L,K,G,D,F,C,B,60,45,18,10,20,40,15,30,25,35,关键线路 A-D-G-K-L(1-2-4-6-7-8),长度为 170,关键线路的确定,图上标注法,1,5,3,8,7,6,4,2,A,H,E,L,K,G,D,F,C,B,60,45,18,10,20,40,15,30,25,35,0,60,70,80,100,110,170,170,110,120,80,117,60,0,关键线路的确定,表上作业法,工序,D,ES,LS,EF,LF,S,关键否,A,60,0,0,60,60,0,是,B,45,60,90,105,135,30,C,10,60,107,70,117,47,D,20,60,60,80,80,0,是,E,40,60,80,100,120,20,F,18,70,117,88,135,47,G,30,80,80,110,110,0,是,H,15,100,120,115,135,20,K,25,110,110,135,135,0,是,L,35,135,135,170,170,0,是,分布式活动周期时间参数计算,项目评审技术,六分之一原则,整个项目的周期服从正态分布,均值为关键线路上所有活动的期望周期和,方差为关键线路上所有活动周期方差和,例8-3 ：实例10.7，教材P307,实例10.8，教材P308,网络图的调整及优化,缩短工程计划工期问题,保证质量和不增加人力物力的前提下尽量缩短工期。注意关键线路的变化。,压缩关键工序的工序时间,在关键工序上采取改进技术、工艺和设备等措施，优先保证关键工序所需，矛盾时非关键线路应尽可能让路。,在非关键工序上尽量挖掘潜力,利用非关键线路上的时差进行合理调度，抽调资源支援关键线路。,采用平行或交叉作业,例83：缩短计划工期,某工程有关的工序关系及时间如下：,工序代号,所需时间,紧后工序,A,2,B,C,D,B,3,E,C,5,F,H,D,4,G,E,6,H,F,2,L,J,G,1,L,H,4,M,J,4,M,L,5,M,M,3,-,例83：缩短计划工期,画出网络图：,1,5,3,10,9,7,4,2,A,L,D,M,J,F,C,H,B,2,6,4,3,5,4,5,2,4,3,8,6,G,E,1,例83：缩短计划工期,计算时间参数，确定关键线路：,1,5,3,10,9,7,4,2,A,L,D,M,J,F,C,H,B,2,6,4,3,5,4,5,2,4,3,8,6,G,E,1,0,18,2,5,7,6,11,9,9,15,18,15,10,10,11,9,8,5,2,0,关键线路 A-B-E-H-M(1-2-3-6-9-10),长度为 18,例83：缩短计划工期,现要求将整个计划工期缩短3天。,首先从关键线路上想办法，能否缩短3天？,也要考虑其它非关键线路上工时缩短的情况。,具体做法如下：,将图中的最后一个节点的最迟时间设定为15,倒退计算法求出各工作的时差,找出所有时差为负值的工序,对其中的关键工序进行协调，缩短工作时间，使总时间为15天,重新计算时间，如仍有负时差工序，再考虑缩短该工序的时间，直到没有负时差为止。,例83：缩短计划工期,将第10节点的最迟时间设定为15，计算各工序时差,1,5,3,10,9,7,4,2,A,L,D,M,J,F,C,H,B,2,6,4,3,5,4,5,2,4,3,8,6,G,E,1,0,15,2,5,7,6,11,9,9,15,18,12,7,7,8,6,5,2,1,3,-3,-2,-1,-3,0,-2,-3,0,-2,-3,-3,18,12,15,15,15,例83：缩短计划工期,从图中可以看出：,在原关键线路上各工序的总时差均为3，因此,需要在原来的关键线路上缩短3天。,除了原先关键线路上是负时差外，在其它非关键线路上也出现负时差，在这些线路上也要进行日期的缩短。,共有以下几条需要缩短：,第一条：1236910 缩短3天,第二条：24789 缩短2天,第三条：79 缩短1天,必须满足以上条件才有可能缩短3天,先考虑关键线路缩短3天，经协调使B、M、E各减1天：,B和M工序各缩短为2天，E工序缩短为5天,重新计算时间,例83：缩短计划工期,关键路线工序时间缩短后，重新计算时间：,1,5,3,10,9,7,4,2,A,L,D,M,J,F,C,H,B,2,6,4,2,5,4,5,2,4,3,8,6,G,E,1,0,15,2,4,7,6,9,9,9,16,13,8,8,9,7,6,4,1,1,-1,-1,0,0,1,-1,0,1,-1,0,-1,14,3,5,2,负时差线路：1-2-4-7-8-9-10,每个工序总时差为1,例83：缩短计划工期,负时差工序C时间缩短1天后，重新计算时间：,1,5,3,10,9,7,4,2,A,L,D,M,J,F,C,H,B,2,4,2,5,4,5,2,4,8,6,G,E,1,0,15,2,4,6,6,9,8,8,15,13,8,8,9,7,6,4,2,0,0,0,1,0,1,0,0,1,0,0,0,13,5,2,关键线路有两条：1-2-4-7-8-9-10、1-2-3-6-9-10,4,网络图的调整及优化,缩短工程计划工期问题,保证质量和不增加人力物力的前提下尽量缩短工期。注意关键线路的变化。,压缩关键工序的工序时间,在关键工序上采取改进技术、工艺和设备等措施，优先保证关键工序所需，矛盾时非关键线路应尽可能让路。,在非关键工序上尽量挖掘潜力,利用非关键线路上的时差进行合理调度，抽调资源支援关键线路。,采用平行或交叉作业,线路有多条，线路的长度为各工序的时间和，最长的为关键线路。,分布式活动周期时间参数计算,A-B-C-D与H-J的总浮动分别为2和4，在它们成为新的关键线路之前，关键线路 E-F-G-J上能压缩的最大时间是2周，找出其中的 g 值最小的工序是 E，E最多能缩短3周，因此对 E 减少2周是可行的。,例84：教材P315，实例10.,E(1)=0,重新计算时间，如果还有负时差，再缩短，再计算时间，直到没有负时差为止。,三时估计法：乐观时间 a、悲观时间b、最可能时间m,优先安排关键工序所需要的资源；,工序关系：确定每一道工序的紧前工序是哪些,网络图是有向图，按流程的顺序，规定工序从左向右排列。,费用与完工时间的关系,方差为关键线路上所有活动周期方差和,整个项目的周期服从正态分布,最早结束时间：EFij=ESij+D(i,j),倒退计算法求出各工作的时差,将第10节点的最迟时间设定为15，计算各工序时差,工序单时差：不影响紧后工序最早可能开始条件下，工序最早可能完工时间可以推迟的时间.,技术、成本和时间等要求。,例83：缩短计划工期,将第10节点的最迟时间设定为15，计算各工序时差,1,5,3,10,9,7,4,2,A,L,D,M,J,F,C,H,B,2,6,4,3,5,4,5,2,4,3,8,6,G,E,1,0,15,2,5,7,6,11,9,9,15,18,12,7,7,8,6,5,2,1,3,-3,-2,-1,-3,0,-2,-3,0,-2,-3,-3,18,12,15,15,15,例83：缩短计划工期,从图中可以看出：,在原关键线路上各工序的总时差均为3，因此,需要在原来的关键线路上缩短3天。,除了原先关键线路上是负时差外，在其它非关键线路上也出现负时差，在这些线路上也要进行日期的缩短。,共有以下几条需要缩短：,第一条：1236910 缩短3天,第二条：24789 缩短2天,第三条：79 缩短1天,必须满足以上条件才有可能缩短3天,先考虑关键线路缩短3天，经协调使B、M、E各减1天：,B和M工序各缩短为2天，E工序缩短为5天,重新计算时间，如果还有负时差，再缩短，再计算时间，直到没有负时差为止。,网络图的调整及优化,工程的时间-费用优化,费用分析：,费用直接费用间接费用,直接费用：直接生产工人工资、资源直接消,耗等直接与完成工序有关的费用,一般情况下，作业时间越短，直接费用越多,间接费用：管理人员的工资、办公费等，需,按施工时间长短分摊,一般情况下，作业时间越短，分摊间接费用越少,网络图的调整及优化,费用与完工时间的关系,工,程,费,用,极限时间,间接费用,直接费用,总费用,正常时间,T,网络图的调整及优化,时间-费用优化分析方法：,最低成本日程：费用最低的工程完工时间T,直接费用变动率g：缩短单位时间增加的直接费用,T计算程序教材P315),按正常时间画出网络图，找到关键线路计算成本时间,在关键线路上找出g最小的工序，压缩活动时间,重复上一步，直到总费用上升为止,例84：教材P315，实例10.12,画出网络图，计算网络时间：,4,2,9,8,6,3,1,I,H,J,G,F,E,C,A,7,5,3,8,12,6,6,8,2,5,B,24,0,3,8,12,10,14,22,24,22,14,12,16,8,5,0,7,D,5,15,17,例84：教材P315，实例10.12,关键路径为 E-F-G-J,周期为24周，正常总成本为正常成本的加总，总计为221000，超过要求时间6周，罚金成本为21000，总成本为242000。,计算压缩每项工序后的单位加急成本g(单位：千英镑/周）:,A B C D E F G H I J,2 1 3 6 2 5 2.5 0.8 1.7 7,A-B-C-D与H-J的总浮动分别为2和4，在它们成为新的关键线路之前，关键线路 E-F-G-J上能压缩的最大时间是2周，找出其中的 g 值最小的工序是 E，E最多能缩短3周，因此对 E 减少2周是可行的。,例84：教材P315，实例10.12,此时，时间计算结果如下：,4,2,9,8,6,3,1,I,H,J,G,F,E,C,A,7,5,3,6,12,6,6,8,2,5,B,22,0,3,6,12,10,12,20,22,20,12,10,14,6,3,0,7,D,5,15,15,8,例84：教材P315，实例10.12,计算E压缩2周后成本的变化：,加急成本增加：2g=220004000,处罚成本减少：235007000,还可以继续压缩。,关键线路有两条：E-F-G-J和A-B-C-D-J,找出各自最小g的工序为E和B,E最多只能压缩1周，B虽能压缩3周，但如压缩时间超过1周后，它就不再是关键线路，因此先考虑B也压缩1周的情况，此时总时间为21周。加急成本增加为200010003000，处罚成本节省3500。因此，还可以继续压缩。,例84：教材P315，实例10.12,此时，时间计算结果如下：,4,2,9,8,6,3,1,I,H,J,G,F,E,C,A,6,5,3,5,12,6,6,8,2,5,B,21,0,3,5,12,9,11,19,21,19,11,9,13,5,3,0,7,D,5,14,14,留意：此时H-I的总时差为1,6,7,例84：教材P315，实例10.12,关键线路有两条：E-F-G-J和A-B-C-D-J,找出各自最小g的工序为G和B,G最多只能压缩2周，B还能压缩2周，但如压缩时间超过2周后，H-I-J的时间要大于它们，就不再是关键线路，因此考虑B和G各压缩1周的情况，此时总时间为20周。加急成本增加为100025003500，处罚成本节省3500。因此，已不能再压缩，找到的最低成本时间为20周。,成本节省,总正常成本22100，,加急成本增加：40003000350010500；,延误2周的处罚成本：235007000；,总成本238500；,总成本节省：2420002385003500。,例84：教材P315，实例10.12,此时，时间计算结果如下：,4,2,9,8,6,3,1,I,H,J,G,F,E,C,A,6,5,3,5,12,6,6,8,2,5,B,20,0,3,5,12,8,11,18,20,18,11,8,12,5,3,0,7,D,5,13,13,此时三条线路均为关键线路,5,7,作业：画网络图并计算时间,网络图的调整及优化,时间资源优化,尽量合理地利用现有资源，并缩短周期,时间资源优化方法,优先安排关键工序所需要的资源；,利用非关键工序的总时差，错开工序开工时间，拉平资源需要量的高峰；,在确实受到资源限制，或者在综合考虑经济效益的条件下，也可适当地推迟完工时间,例82：关键线路的确定,1,5,3,8,7,6,4,2,A,H,E,L,K,G,D,F,C,B,60,45,18,10,20,40,15,30,25,35,0,60,70,80,100,110,170,170,110,120,80,117,60,0,网络图的调整及优化,例84：在例8-2的基础上考虑以下资源：,工序,作业时间,需要人数,总时差,D,F,G,H,k,20,18,30,15,25,58,22,42,39,26,0,47,0,20,0,每个工序都从最早时间开始：,5,3,7,6,4,2,H,K,G,D,F,18,20,15,30,25,工,人,数,65,60,100,88,110,80,70,58人,C,10,5822,80人,2242,64人,100,42人,4239,81人,2639,65,115,26人,时间,70,80,110,60,58,42,39,22,26,开始时间适当调整后的结果：,5,3,7,6,4,2,H 39,K 26,G 42,D 58,F 22,18,20,15,30,25,工,人,数,65,60,98,110,80,70,58人,D,2242,64人,F G,42人,G,2639,65人,K H,125,26人,K,时间,F推迟10,H推迟10,47,20,100,谢谢观看,