运筹学网络计划

1、第九章网络计划,目录前言第1节网络计划图第2节网络计划图的时间参数计算第3节网络计划的优化,前言,用网络分析的方法编制的计划称为网络计划。它是二十世纪五十年代末发展起来的一种编制大型工程进度计划的有效方法。1956年，美国杜邦公司在制定企业不同业务部门的系统规划时，制定了第一套网络计划。这种计划借助于网络表示各项工作与所需要的时间，以及各项工作的相互关系。,网络计划方法的基本原理,将工程项目分解为相对独立的活动，根据各活动先后顺序、相互关系以及完成所需时间做出反映项目全貌的网络图；从项目完成全过程着眼，找出影响项目进度的关键活动和关键路线，通过对资源的优化调度，实现对项目实施的有效控制和管理。

2、,网络计划方法的主要功能,1用网络图描述一个实际项目的管理问题(画网络图);2计算项目的最早、最晚完成和开工时间(网络计算);3寻找关键活动和关键路径(网络分析);4根据以上分析对网络进行优化。,第1节网络计划图,网络计划图的基本思想是：首先应用网络计划图来表示工程项目中计划要完成的各项工作，完成各项工作必然存在先后顺序及其相互依赖的逻辑关系；这些关系用节点、箭线来构成网络图。网络图是由左向右绘制，表示工作进程。并标注工作名称、代号和工作持续时间等必要信息。通过对网络计划图进行时间参数的计算，找出计划中的关键工作和关键线路；通过不断改进网络计划，寻求最优方案，以求在计划执行过程中对计划进行有效

3、的控制与监督，保证合理地使用人力物力和财力，以最小的消耗取得最大的经济效果。,1.1基本术语,网络计划图是在网络图上标注时标和时间参数的进度计划图，实质上是有时序的有向赋权图。表述关键路线法（CPM）和计划评审技术（PERT）的网络计划图没有本质的区别，它们的结构和术语是一样的。仅前者的时间参数是确定型的，而后者的时间参数是不确定型的。于是统一给出一套专用的术语和符号。描述工程项目网络计划图有两种表达的方式：双代号网络计划图和单代号网络计划图。双代号网络计划图在计算时间参数时，又可分为：工作计算法和节点计算法。,基本术语：节点,（2）工作,节点，箭线是网络计划图的基本组成元素。箭线是一线段带箭

4、头实射线,虚射线（用“”,“”表示）。节点用“”或“”表示箭线之间的连接点。工作（曾称工序、活动、作业）将整个项目按需要粗细程度分解成若干需要耗费时间或需要耗费其他资源的子项目或单元。它们是网络计划图的基本组成部分。,(3)双代号网络计划图,在双代号网络计划图中，用箭线表示工作，箭尾的节点表示工作的开始点，箭头的节点表示工作的完成点。用（i-j）两个代号及箭线表示一项工作。在箭线上标记必须的信息，如表示图9-1为：,(4)单代号网络计划图,用节点表示工作，箭线表示工作之间的先完成与后完成的关系为逻辑关系。在节点中标记必须的信息，如图9-2所示：以下主要介绍双代号网络计划图,1.2双代号网络计划

5、图,以下通过例题来说明双代号网络计划图的绘制和按工作计算时间参数的方法。例1开发一个新产品，需要完成的工作和先后关系，各项工作需要的时间汇总在逻辑关系表中，见表9-1。要求编制这项目的网络计划图和计算有关参数。,表9-1,第1步,根据表9-1中数据，绘制以下网络图，见图9-3。,图9-3,为了正确表述工程项目中各个工作的相互连接关系和正确绘制网络计划图，应遵循以下规则和了解有关术语:,1.网络计划图的方向、时序和节点编号网络计划图是有向、有序的赋权图，按项目的工作流程自左向右地绘制。在时序上反映完成各项工作的先后顺序。节点编号必须按箭尾节点的编号小于箭头节点的编号来标记。在网络图中只能有一个起

6、始节点，表示工程项目的开始。一个终点节点，表示工程项目的完成。从起始节点开始沿箭线方向顺序自左往右，通过一系列箭线和节点，最后到达终点节点的通路，称为线路。,2.紧前工作和紧后工作,紧前工作是指紧排在本工作之前的工作；完成后，才能开始本工作。紧后工作是指紧排在本工作之后的工作；本工作结束后，才能开始的工作。如图9-3中，只有工作A完成后工作B,C,D,E才能开始，工作A是B,C,D,E的紧前工作；而工作B,C,D,E则是工作A的紧后工作。,在复杂的工程项目中，它们之间的有三种关系：结束后，才开始（FS）；开始后，才开始(SS)；结束后，才结束(FF)。本例只涉及结束后，才开始(FS)的关系。从

7、起始节点至本工作之前在同一线路的所有工作，称为先行工作；自本工作到终点节点在同一线路的所有工作，称为后继工作。工作G的先行工作有工作A,D;工作K,L是工作G的后继工作。,3.虚工作,在双代号网络计划图中，虚工作只表示相邻工作之间的逻辑关系，不占用时间和不消耗人力，资金等的虚设的工作。虚工作用虚箭线表示。如图9-3中的只表示工作D完成后，工作H才能开始的逻辑关系。,4.相邻两节点之间只能有一条箭线连接。否则将造成逻辑上的混乱。,如图9-4是错误画法，为了使两节点之间只有一条箭线，可增加一个节点，并增加一项虚工作。图9-5是正确的画法,图9-4,图9-5,应改正为,5.网络计划图中不能有缺口和回

8、路。,在网络计划图中严禁出现从一个节点出发，顺箭线方向又回到原出发节点，形成回路。回路将表示这工作永远不能完成。网络计划图中出现缺口，表示这些工作永远达不到终点。项目无法完成。,6.平行作业和交叉作业。,（1）平行作业为缩短工程的完工时间，在工艺流程和生产组织条件允许的情况下，某些工序可以同时进行，即可采用平行作业的方式。如在图91中，工序B、C、D、E四个工序即可平行作业。在有几个工序平行作业结束后转入下一道工序的情况下，考虑到便于计算网络时间和确定关键路线，选择在平行作业的几个工序中所需时间最长的一个工序，直接与其紧后工序衔接，而其它工序则通过虚工序与其紧后工序衔接。,虚工作可以用于正确地

9、表示平行工作。如图中市场调查（2，3）中需12天，如增加人力分为三组同时进行，可画为（b）。,图（a）,图（b）,(2)交叉作业对需要较长时间才能完成的一些工序，在工艺流程与生产组织条件允许的情况下，可以不必等待工序全部结束后再转入其紧后工序，而是分期分批的转入。这种方式称为交叉作业。交叉作业可以缩短工程周期。如在图91中，将工装制造分为两批，将一个工序分为两个工序D、G，分别与紧后工序H、K连接。,如工作A与工作B分别为挖沟和埋管子，那么它们的关系可以是挖一段埋一段，不必等沟全部挖好再埋，这就可以用交叉作业来表示。,如把这工作各分为三段，A=a1+a2+a3,B=b1+b2+b3，可用下图表

10、示：,为了尽量避免弧的交叉，下图（a）整体改为（b）就比较清晰了。,图（a）,图（b）,7.起始节点与终点节点。,在网络计划图中只能有一个起始节点和一个终点节点。当工程开始或完成时存在几个平行工作时，可以用虚工作将它们与起始节点或终点节点连接起来。,1,2,s,下图，有2个始点，3个终点，显然是错误的。,图9-3,8.线路：,网络图中从起点节点沿箭线方向顺序通过一系列箭线与节点，最后到达终点节点的通路。本例中有五条线路。并可以计算出各线路的持续时间，见表9-2。,关键路线,从网络图中可以计算出各线路的持续时间。其中有一条线路的持续时间最长线路是关键路线。或称为主要矛盾线。关键路线上的各工作为关

11、键工作。因为它的持续时间就决定了整个项目的工期。如果能够缩短关键工序所需的时间，就可以缩短工程的完工时间。而缩短非关键路线上的各个工序所需要的时间，却不能使工程的完工时间提前。即使在一定范围内适当地拖长非关键路线上各个工序所需要的时间，也不至于影响工程的完工时间。,关键路线,而对非关键路线上的各工序，只要在不影响工程完工时间的条件下，抽出适当的人力、物力等资源，用在关键工序上，以达到缩短工程工期，合理利用资源等目的。在执行计划过程中，可以明确工作重点，对各关键工序加以有效控制和调度。关键路线是相对的，也是可以变化的。在采取一定的技术组织措施之后，关键路线有可能变为非关键路线。而非关键路线也有可

12、能变为关键路线。,9.网络计划图的布局。,尽可能将关键路线布置在网络计划图的中心位置，按工作的先后顺序将联系紧密的工作布置在邻近的位置。为了便于在网络计划图上标注时间等数据，箭线应是水平线或具有一段水平线的折线。在网络计划图上附有时间坐标或日历进程。,10.网络计划图的类型。,总网络计划图，以整个项目为计划对象，编制网络计划图。供决策领导层使用；分级网络计划图，这是按不同管理层次的需要，编制的范围大小不同，详细程度不同的网络计划图；供不同管理部门使用；局部网络计划图，将整个项目某部分为对象，编制的更详细的网络计划图。供专业部门使用。,当用计算机网络计划软件编制网络计划时，在计算机上可进行网络计

13、划图分解与合并。网络计划图详细程度，可以根据需要，将工作分解为更细的子工作；也可以将几项工作合并为综合的工作。以便显示不同粗细程度的网络计划。当前的软件都实现这些操作。,例2某调研工作工序如下表：,第2节网络计划图的时间参数计算,网络计划的时间参数计算有几种类型：双代号网络计划有工作计算法和节点计算法；单代号网络计划有节点计算法。以下仅介绍工作计算法。网络图中工作的时间参数。它们是：工作持续时间(D)；工作最早开始时间（ES）；工作最早完成时间（EF）；EF=ES+D工作最迟开始时间（LS）；LS=LF-D工作最迟完成时间（LF）；工作总时差（TF）；TF=LS-ES=lf-d-es=LF-E

14、F工作自由时差（FF）。,图9-7,20,工作自由时差FF是指：在不影响其紧后工作最早开始的前提下，工作所具有机动时间:FFi-j=ESj-kESi-jDi-j;或FFi-j=ESj-kEFi-j计算结果见表9-4列和图9-7,20,工作自由时差是某项工作单独拥有的机动时间，其大小不受其它工作机动时间的影响。关键路线的特征：在线路上从起点到终点都由关键工作组成。在确定型网络计划中是指线路中工作总持续时间最长的线路。在关键线路上无机动时间，工作总时差为零。在非确定型网络计划中是指估计工期完成可能性最小的线路,4,网络计划的时间参数计算一、控制性参数最早时间：结点的最早可能实现时间（ET）工作的最

15、早可能开始时间（ES）工作的最早可能结束时间（EF）,网络计划的时间参数计算一、控制性参数最迟时间：结点的最迟必须实现时间（LT）工作的最迟必须开始时间（LS）工作的最迟必须结束时间（LF）,网络计划的时间参数计算二、协调性参数工作的总机动时间（TF）工作的局部机动时间（FF）第一类局部机动时间（FF）第二类局部机动时间（FF）,网络计划的时间参数计算公式最早时间：ETS=0ETj=max（ETi+tij）ESij=ETiEFij=ETi+tij,网络计划的时间参数计算公式最迟时间：LTT=D（指令工期，通常D=T）LTi=min（LTj+tij）LFij=LTiLSij=LTj-tij,网络

16、计划的时间参数计算公式协调性参数：TFij=LTj-ETi-tijFFij=ETj-ETi-tijFFij=LTj-LTi-tijTFFF,凡是TF=0的工作便是关键工作，组成的线路便是关键线路。关键线路上的关键结点必有ET=LT，但不充分。唯一的判断是TF=0。,图算法一种简单有效的方法步骤：1计算结点最早实现时间（顺向计算）2计算结点最迟实现时间（逆向计算）3确定关键线路（ET=LT）4计算工作的总机动时间（非关键线路）,1,2,3,4,5,6,10,5,4,5,10,10,10,顺向计算最早时间ET,0,1,2,3,4,5,6,10,5,4,5,10,10,10,顺向计算最早时间ET,0

17、,5,10,1,2,3,4,5,6,10,5,4,5,10,10,10,顺向计算最早时间ET,0,5,10,20,1,2,3,4,5,6,10,5,4,5,10,10,10,顺向计算最早时间ET,0,5,10,20,30,1,2,3,4,5,6,10,5,4,5,10,10,10,0,5,10,20,30,40,计算工期T=40,顺向计算最早时间ET,1,2,3,4,5,6,10,5,4,5,10,10,10,逆向计算最迟时间LT,0,5,10,20,30,40,令D=T=40,1,2,3,4,5,6,10,5,4,5,10,10,10,0,5,10,20,30,40,令D=T=40,40,逆

18、向计算最迟时间LT,1,2,3,4,5,6,10,5,4,5,10,10,10,0,5,10,20,30,40,令D=T=40,40,30,逆向计算最迟时间LT,1,2,3,4,5,6,10,5,4,5,10,10,10,0,5,10,20,30,40,令D=T=40,20,30,40,逆向计算最迟时间LT,1,2,3,4,5,6,10,5,4,5,10,10,10,0,5,10,20,30,40,令D=T=40,20,30,40,10,逆向计算最迟时间LT,1,2,3,4,5,6,10,5,4,5,10,10,10,0,5,10,20,30,40,令D=T=40,20,30,40,10,26

19、,逆向计算最迟时间LT,1,2,3,4,5,6,10,5,4,5,10,10,10,0,5,10,20,30,40,令D=T=40,20,30,40,10,26,0,逆向计算最迟时间LT,1,2,3,4,5,6,10,5,4,5,10,10,10,计算总机动时间TF=LTj-Eti-tij,0,5,10,20,30,40,20,30,40,10,26,0,TF35=30-5-4=21,1,2,3,4,5,6,10,5,4,5,10,10,10,计算总机动时间TF=LTj-Eti-tij,0,5,10,20,30,40,20,30,40,10,26,0,TF35=30-5-4=21,21,1,2

20、,3,4,5,6,10,5,4,5,10,10,10,0,5,10,20,30,40,20,30,40,10,26,0,TF25=30-10-5=15,21,15,计算总机动时间TF=LTj-Eti-tij,1,2,3,4,5,6,10,5,4,5,10,10,10,0,5,10,20,30,40,20,30,40,10,26,0,TF13=26-0-5=21,21,15,21,计算总机动时间TF=LTj-Eti-tij,1,2,3,4,5,6,10,5,4,5,10,10,10,0,5,10,20,30,40,20,30,40,10,26,0,21,15,21,计算总机动时间TF=LTj-E

21、ti-tij,第3节网络计划的优化,绘制网络计划图，计算时间参数和确定关键线路，仅得到一个初始计划方案。然后根据上级要求和实际资源的配置，需要对初始方案进行调整和完善。即进行网络计划优化。目标是综合考虑进度，合理利用资源，降低费用等。包括：4.1工期优化。4.2资源优化4.3时间费用优化,4.1工期优化（时间技术、组织优化）,若网络计划图的计算工期大于上级要求的工期,就必须根据要求计划的进度，缩短工程项目的完工工期。主要采取以下措施，增加对关键工作的投入，以便缩短关键工作的持续时间，实现工期缩短。采取技术措施，提高工效，缩短关键工作的持续时间，使关键线路的时间缩短。采取组织措施，充分利用非关键

22、工作的总时差，合理调配人力、物力和资金等资源。增加对关键工作的投入，以便缩短关键工作的持续时间，实现工期缩短。,4.2资源优化,在编制初始网络计划图后，需要进一步考虑尽量利用现有资源的问题。即在项目的工期不变的条件下，均衡地利用资源。实际工程项目包括工作繁多，需要投入资源种类很多，均衡地利用资源是很麻烦的事，要用计算机来完成。为了简化计算，具体操作可以：优先安排关键工作所需要的资源。利用非关键工作的总时差，错开各工作的开始时间，避开在同一时区内集中使用同一资源，以免出现高峰。在确实受到资源制约，或在考虑综合经济效益的条件下，在许可时，也可以适当地推迟工程的工期。实现错开高峰的目的。,20,下面

23、通过例1的例子说明平衡人力资源的方法。假设在例1中，现有机械加工工人数65人，要完成工作D,F,G,H,K。各工作需要工人人数列于表9-4,表9-4,708088100110115135,由于机械加工工人数的限制,若上述工作若都按最早开始时间安排，在完成各关键工作的75天工期中，每天需要机械加工工人人数如图9-9所示。,图9-9,有10天需要80人，另10天需要81人。超过了现有机械工人人数的约束,必须进行调整。以线表示的非关键路线上非关键工作F,H有机动时间，若将工作F延迟10天开工，就可以解决第7080天的超负荷问题；将工作H推迟10天开工，可以解决第100110天的超负荷问题。于是新的负

24、荷图（见图9-10）能满足机械工人的人数65人约束条件。,608098110125135,图9-10,以上人力资源平衡是利用非关键工作的总时差，可以错开资源负荷的高峰。也可以采用将非关键工作分段作业或采用技术措施减少所需要资源。也可以根据计划规定适当延长项目的工期。,4.3时间费用优化,完成一项目的费用可以分为两大类：1.直接费用2.间接费用。1.直接费用与时间成反比直接与项目的规模有关的费用。包括材料费用，直接生产工人工资等。为了缩短工作的持续时间和工期，就需要增加投入，即增加直接费用。2.间接费用与时间成正比包括管理费等。一般按项目工期长度进行分摊。工期愈短，分摊的间接费用就愈少。,编制网

25、络计划时，要研究1、如何使完成项目的工期尽可能缩短，费用尽可能少；2、或在保证既定项目完成时间条件下，所需要的费用最少；3、或在费用限制的条件下，项目完工的时间最短。这就是时间费用优化要解决的问题。,一般项目的总费用与直接费用和间接费用与项目工期之间存在一定关系，可以用图9-11表示,T1最短工期，项目总费用最高；T2最经济的工期（总费用最少）；T3正常的工期当总费用最少工期短于要求工期时，这就是最佳工期。,费用优化的步骤：计算工作费用增加率（简称费用率）费用增加率是指：缩短工作持续时间每一单位时间（如一天）所需要增加的费用。在网络计划图找出费用率最低的一项关键工作或一组关键工作作为缩短持续时间的对象。其缩短后的值不能小于最短持续时间，不能成为非关键工作。同时计算相应的增加的直接费用。然后考虑由于工期的缩短间接费用的变化，在这基础上计算项目的总费用。重复以上步骤，直到获得满意的方案为止。,以下通过例1说明,已