运筹学chap7网络计划1.ppt

PERT网络图 网络图时间参数的计算 关键路线和网络计划的优化,网络计划 (Program Evaluation and Review Technique),网络计划技术被广泛应用于建筑施工和新产品的研制计划、计算机系统的安装调试及各种大型复杂工程的控制管理。 基本原理：首先是把所要做的工作，哪项工作先做，哪项工作后做，各占用多少时间，以及各项工作之间的相互关系等运用网络图的形式表达出来；其次是通过简单的计算，找出哪些工作是关键的，哪些工作不是关键的，并在原来计划方案的基础上，进行计划的优化。,第1节 网络计划图,网络计划图的基本思想是，首先应用网络计划图来表示工程项目中计划要完成的各项工作，完成各项工作必然存在先后顺序及其相互依赖的逻辑关系；这些关系用节点和箭线来构成网络图。,第1节 网络计划图,1.1 基本术语,网络图又称箭线图，是由箭线和节点组成的，用来表示工作流程的有向、有序的网状图形。,网络计划图是在网络图上标注时标和时间参数的进度计划图，实质上是有时序的有向赋权图。表述关键路线法(CPM)和计划评审技术(PERT)的网络计划图并无本质的区别。下面介绍PRET网络图。,1.1 基本术语,1、绘图符号和术语,(1) 工作（活动、工序、作业） 任何一项计划，都包含许多项待完成的工作。在网络图中，工作用箭线(弧)表示。箭尾表示工作的开始，箭头表示工作的完成。箭头的方向表示工作的前进方向（从左向右）。工作的名称或内容写在箭线的上面，持续时间写在箭线的下面：,双代号网络计划图,1.1 基本术语,（2）节点 节点表示工作之间的联结。在时间上它表示指向某节点的工作全部完成后，该节点后面的工作才能开始。 节点用圆圈表示，圆圈中编上整数号码。 对于某项工作来说，紧接在其箭尾节点前面的工作，是其紧前工作，紧接在其箭头节点后面的工作是其紧后工作；和它同时进行的工作称为平行工作。,1.1 基本术语,（3）虚工作 虚工作仅仅表示工作之间的先后顺序，用虚线箭线表示，它的持续时间0。,1.1 基本术语,2、各项工作之间的关系以及各项工作在网络图上 的表达方式,（1）工作a 结束后才可以开始b 和c。,1.1 基本术语,（2）工作c 在a 和b 均结束后才能开始。,1.1 基本术语,（3）a和b 两作工序均结束后才可以开始c 和d。,1.1 基本术语,（4）工作c 在a 结束后即可进行，但工作d 必须 同时在a 和b结束后才能开始。, 虚工序,第1节 网络计划图,1.2 双代号网络计划图,、绘图规则,（1）起点和终点 为了表示工程的开始和结束，网络图只能有一个起点和一个终点。 （2）方向与节点 网络图是有向图，按照工艺流程的顺序，规定工作从左向右排列。,1.2 双代号网络计划图,（3）虚工作 用虚线箭线表示。它表示工时为零，不消耗任何资源的虚构工作。其作用只是为了正确表示工作间的先后次序关系。 （4）两个节点之间不能有两道或两道以上的工作。即两个节点只能表示一道工序，否则将造成逻辑上的混乱。,1.2 双代号网络计划图,（5）网络图中不能有缺口和回路。有缺口，将使某些工作失去与其紧前或紧后工作应有的联系；有回路，将使组成回路的工作永远不能结束，工程永远不能完工。,1.2 双代号网络计划图,(6) 平行作业 为缩短工程的完工时间，在条件允许的情况下，某些工作可以同时进行，即可采用平行作业的方式。如下图中的工作b，c，d。,1.2 双代号网络计划图,（7）交叉作业 对需要较长时间才能完成的一些工作，在工艺流程与生产组织条件允许的情况下，可以不必等待该工作全部结束后再转入其紧后工序，而是分期分批的转入。这种方式称为交叉作业。交叉作业可以缩短工程的完工时间。如工作A与工作B分别为挖沟和埋水管，可以挖一段埋一段，不必等沟全部挖好后再埋。这种关系可以用交叉作业来表示，如果把这两项工作各分为三段，则A=a1+a2+a3，B=b1+b2+b3，如下图所示。,1.2 双代号网络计划图,交叉作业,1.2 双代号网络计划图,（8）网络图布局 网络图中尽可能将关键路线布置在中心位置，将联系紧密的工作布置在相近的位置。为了使网络图清楚和便于在图上填写有关数据，箭线尽量用水平线或具有一段水平线的折线(什么是关键路线？后面介绍)。,1.2 双代号网络计划图,2、绘图步骤,（1）将一个任务分解成若干个工作（工序）； （2）分析这些工作之间的关系； （3）在前两步的基础上，遵循前边的绘图规则作出网络图。,1.2 双代号网络计划图,3、实例,例1 某项建筑工程的部分工作与所需时间以及它们之间的关系如下表所示。,1.2 双代号网络计划图,步骤1、2可用上表表示。,根据表所示的工作及它们之间的关系可作出网络图。,1.2 双代号网络计划图,例2 某项研制新产品工程的各个工作与所需时间及它们之间的相互关系见下表。作出该项工程的网络计划图。,1.2 双代号网络计划图,网络图中的虚工作 表示在D工作结束后H工作才能开始。,第2节 网络计划图的时间参数计算,定义：在网络图中，从始点开始，按照各个工序的顺序，连续不断地到达终点的一条路称为路线。而这样的路线往往有多条，称其中时间最长的路线为关键路线（CP），关键路线上的工作称为关键工作。,*整个工程所需的最短时间就等于关键路线所需的时间，因此关键工序完工时间的提前或拖延就直接影响了整个工程的完工时间。,2.1 工作持续时间D,计算工作持续时间通常有两种方法，所用到的数据也有所不同。,1、单时估计法（定额法）,根据工作的工作量、劳动定额资料以及投入的人力多少等，计算各工作的持续时间。,其中， Q-工作的工作量； R-可投入的人力和设备的数量； S-每人或每台设备每工作班能完成的工作量； n-每天正常工作班数。,使用条件：具有类似工作的持续时间的历史统计资料。,2、三时估计法,不具有类似工作的持续时间的历史统计资料时，对工作进行估计三种时间值，然后计算其平均值。,其中， 乐观时间a-在一切都顺利时，完成工作所需的最小时间； 最可能时间 m-在正常条件下，完成工作所需的最小时间； 悲观时间b-在一切都顺利时，完成工作所需的最小时间。,方差,根据大量统计，它服从 分布，其,三个节点时间参数 节点最早时间TE 节点的最迟时间TL 节点时差R（i）,2.2 节点时间参数计算关系式,节点的时间参数计算： 节点最早时间TE：节点i的最早时间TEi是以i节点开始的各项工序最早可以开工时间。它等于从始点开始到该节点的最长路线的时间。计算公式： TE1=0 TEj= maxTEi+Di-j 节点的最迟时间TL：节点i的最迟时间TLj是以j节点结束的各项工序最迟必须结束的，否则就会延误整个工期。它等于总周期减去该节点到终点的最长路线的时间。计算公式： TLn= TEn TLi= minTLj-Di-j 节点时差Ri：该节点最迟时间和最早时间之差。计算公式： Ri= TLi- TEi,B(3),D(8),G(4),2,9,1,5,A(3),8,4,C(3),E(5),F(4),3,6,7,10,H(2),I(2),B(3),D(8),G(4),2,9,1,5,A(3),8,4,C(3),E(5),F(4),3,6,7,10,H(2),I(2),0,3,6,6,6,11,14,11,18,20,0,3,9,9,6,14,14,16,18,20,工作的六个时间参数 ES i-j(Earliest Starting Time) EF i-j(Earliest Finishing Time) LS i-j(Latest Starting Time) LF i-j(Latest Finishing Time) TF i-j(Total Float Time) FF i-j(Free Float Time),2.3 工作时间参数计算关系式,最早时间参数ES i-j 和EF i-j 最早开始时间等于其所有的紧前工作最早结束时间中的最大值： ES i-j =max EF h-i=max ES h-i +D h-i 最早结束时间是它的最早开始时间加上该工作的持续时间之和：EF i-j= ES i-j +D i-j,最迟时间参数LS i-j和LF i-j 最迟结束时间等于其所有紧后工作的最迟开始时间中的最小值： LF i-j =min LS j-k=min LF j-k D j-k 最迟开始时间是它的最迟结束时间减去该工作的持续时间之差：LS i-j = LF i-j D i-j,总时差TF i-j 在不影响工期的前提下，工作所具有的机动时间：,若干项工作共同拥有的机动时间。,自由时差FF i-j 在不影响其紧后工作最早开始的前提下，工作所具有的机动时间：,某项工作单独拥有的机动时间，其大小不受其它工作机动时间的影响,关键路线是由总时差为0的工序所组成的路线。关键路线上的各工序开始时间和结束时间没有一点机动的余地。网络图制成以后，把时差为0的工序连接起来得到的一条路线就是关键路线。 关键路线的特点： (1) 关键路线上的工序，时差等于0。 (2) 关键路线是从网络计划开始点到结束点之间持续时间最长的路线。 (3) 关键路线在网络计划中不一定只有一条，有时存在两条以上。,第3节 网络计划的优化,绘制网络图、计算时间参数和确定关键路线得到的只是一个初始的计划方案。为了得到一个较(最)好的方案通常还需要从工期、费用、资源利用等方面对初始计划方案进行调整和改善，这一过程就是网络计划的优化。,3.1 工期优化,若网络计划图的计算工期大于要求的工期，必须根据要求计划的进度，缩短工程项目的完工工期。主要采用以下措施，增加对关键工作的投入，以便缩短关键工作的持续时间，实现工期的缩短。 在确定需缩短持续时间的关键工序时，应注意以下几个方面： 1. 缩短持续时间对质量和安全影响不大的工序； 2. 有充足备用资源的工序； 3. 缩短持续时间所需增加的工人或材料最少的工序； 4. 缩短持续时间所需增加的费用最少的工序。,网络计划的工期优化步骤 1.计算并找出网络计划的计算工期、关键线路及关键工序。 2.按计划工期，计算出工期应缩短的时间目标T： TTcTr 式中Tc是计算工期，Tr是计划工期。 3.确定各关键工序能缩短的时间。 4.选择关键工作压缩作业时间，并重新计算工期Tc。 5.若计算工期仍超过要求工期，则重复以上步骤，直到满足工期要求或工期已不能再缩短为止。,例题：,已知网络计划如下图，要求工期为11天，试用非时标网络计划对其进行优化。,1,2,3,4,5,6,4,7,8,2,1,6,3,2(1),6(5),3(2),3(2),6(3),4(2),3(2),优选系数,正常持续时间,最短持续时间,1,2,3,4,5,6,4,7,8,2,1,6,3,2(1),6(5),3(2),3(2),6(3),4(2),3(2),（1）计算并找出初始网络计划的关键线路、关键工作；,（2）求出应压缩的时间,（3）确定各关键工作能压缩的时间；,0,0,2,6,6,6,9,11,15,15,12,12,1,2,3,4,5,6,4,7,8,2,1,6,3,2(1),6(5),3(2),3(2),6(3),4(2),3(2),0,0,2,6,6,6,9,11,15,15,12,12,（4）选择关键工作压缩作业时间，并重新计算工期Tc,第一次：选择工作-，压缩2天，成为4天；,1,2,3,4,5,6,4,7,8,2,1,6,3,2(1),6(5),3(2),3(2),4(3),4(2),3(2),0,0,2,6,6,6,9,9,13,13,10,10,（4）选择关键工作压缩作业时间，并重新计算工期Tc,第一次：选择工作-，压缩2天，成为4天；,工期变为13天，和也变为关键工作。,1,2,3,4,5,6,4,7,8,2,1,6,3,2(1),6(5),3(2),3(2),4(3),4(2),3(2),0,0,2,6,6,6,9,9,13,13,10,10,（4）选择关键工作压缩作业时间，并重新计算工期Tc,第二次：选择工作和-，同时压缩1天，成为2天，-成为3天 ；,1,2,3,4,5,6,4,7,8,2,1,6,3,2(1),6(5),3(2),2(2),3(3),4(2),3(2),0,0,2,5,6,6,8,8,12,12,9,9,（4）选择关键工作压缩作业时间，并重新计算工期Tc,第二次：选择工作和-，同时压缩1天，成为2天，-成为3天 ；,工期变为12天，关键工作没有变化。,1,2,3,4,5,6,4,7,8,2,1,6,3,2(1),6(5),3(2),2(2),3(3),4(2),3(2),0,0,2,5,6,6,8,8,12,12,9,9,（4）选择关键工作压缩作业时间，并重新计算工期Tc,第三次：选择工作，压缩1天，成为5天 ；,1,2,3,4,5,6,4,7,8,2,1,6,3,2(1),5(5),3(2),2(2),3(3),4(2),3(2),0,0,2,4,5,5,7,7,11,11,8,8,（4）选择关键工作压缩作业时间，并重新计算工期Tc,第三次：选择工作，压缩1天，成为5天 ；,工期变为11天，关键工作没有变化。,3.2 资源优化,由于实际工程项目包括了众多工作，涉及到的资源种类很多，不少工作是否能够按时完成，受到资源的约束。如何均衡地利用资源是在编制好初始网络计划图后所要考虑的事。 均衡资源可以减少工作现场各种临时设施(包括临时生产设施和生活福利设施)的规模，从而节省工程费用。,资源优化的步骤 （1）将网络计划绘成时间坐标网络。 （2）画出网络计划的每日资源需要量曲线，并标出资源供应量限值。 （3）找出最先超过日资源供应限额的时段，将该时段内的各工序按顺序编号。 （4）按顺序依次给本时段的工序分配资源。 （5）绘出工序推移后时标网络，并绘出资源需要量曲线。 （6）后面优化重复以上步骤。,例1：现有机械加工工人65人，要完成工作D、F、G、H、K。各工作所需人数如下：,由于机械加工工人人数的限制，若上述工作都按最早开始时间安排，在完成各关键工作的75天工期中，每天需要的加工工人人数如图8-9所示。有10天需要80人，另外10天需要81人。超过现有人数的约束，必须进行调整。,如何调整？ 以虚线表示的非关键线路上非关键工作F、G有机动时间。若将工作F延迟10天开工可以解决第7080天的超负荷问题；将工作H延迟10天开工可以解决第100110天的超负荷问题。从而得到的新负荷图能满足约束条件