第8章-网络计划

（本科版）运筹学《运筹学》教材编写组编清华大学出版社第8章网络计划第1节网络计划图

第2节网络计划图的时间参数计算。

第3节时标网络计划图

第4节网络计划的优化

第5节网络计划软件

第1节

网络计划图网络计划图的基本思想是：首先应用网络计划图来表示工程项目中计划要完成的各项工作，完成各项工作必然存在先后顺序及其相互依赖的逻辑关系；这些关系用节点、箭线来构成网络图。网络图是由左向右绘制，表示工作进程。并标注工作名称、代号和工作持续时间等必要信息。通过对网络计划图进行时间参数的计算，找出计划中的关键工作和关键线路；通过不断改进网络计划，寻求最优方案，以求在计划执行过程中对计划进行有效的控制与监督，保证合理地使用人力、物力和财力，以最小的消耗取得最大的经济效果。一个项目需要有许多活动组成。把项目的活动或工序之间的逻辑顺序用一个网络图来表示，就是网络（计划）图。通过网络图可以对影响项目进行的因素进行分析，以便更好地对项目进行控制。项目控制的三大基本目标：进度、费用和质量。通过网络图分析，可以得到影响项目关键因素，以便更好地对项目进行监控。网络图分析方法主要有两种：关键路径法（CriticalPathMethod简写为CPM）和计划评审法（ProgramEvaluationandReviewTechnique简写为PERT）。前者主要对确定工序时间进行分析，后者则考虑了工序时间的不确定性（特别是随机性）。PERT主要针对完成工作的时间不能确定而是一个随机变量时的计划编制方法，活动的完成时间通常用三点估计法，注重计划的评价和审查。CPM以经验数据确定工作时间，看作是确定的数值，主要研究项目的费用与工期的相互关系。通常将这两种方法融为一体，统称为网络计划、网络计划技术(PERT/CPM)。网络计划主要应用于新产品研制与开发、大型工程项目的计划编制与计划的优化，是项目管理和项目安排领域目前比较科学的一种计划编制方法，比甘特图（Canttchart）或称横道图(barchart)计划方法有许多优点。网络计划有利于对计划进行控制、管理、调整和优化，更清晰地了解工作之间的相互联系和相互制约的逻辑关系，掌握关键工作和计划的全盘情况。PERT最早应用于美国海军北极星导弹的研制系统，由于该导弹的系统非常庞大复杂,为找到一种有效的管理技术,设计了PERT这种方法,并使北极星导弹的研制周期缩短了一年半时间。CPM是与PERT十分相似但又是独立发展的另一种技术，是1957年美国杜邦公司的沃克（M.R.walker）和兰德公司的小凯利(J.E.Kelley)共同研制的一种方法。它主要研究大型工程的费用与工期的相互关系。1.1基本术语网络计划图是在网络图上标注时标和时间参数的进度计划图，实质上是有时序的有向赋权图。表述关键路线法（CPM）和计划评审技术（PERT）的网络计划图没有本质的区别，它们的结构和术语是一样的。仅前者的时间参数是确定型的，而后者的时间参数是不确定型的。于是统一给出一套专用的术语和符号。描述工程项目网络计划图有两种表达的方式：双代号网络计划图和单代号网络计划图。双代号网络计划图在计算时间参数时，又可分为：工作计算法和节点计算法。

(3)双代号网络计划图。在双代号网络计划图中，用箭线表示工作，箭尾的节点表示工作的开始点，箭头的节点表示工作的完成点。用（i-j）两个代号及箭线表示一项工作。在箭线上标记必须的信息，如表示图11-1为：

(4)单代号网络计划图用节点表示工作，箭线表示工作之间的先完成与后完成的关系为逻辑关系。在节点中标记必须的信息，如图11-2所示：以下主要介绍双代号网络计划图

基本术语：⑴节点，（2）工作⑴节点，箭线是网络计划图的基本组成元素。箭线是一线段带箭头实射线,虚射线（用“→”,“”表示）。节点用“○”或“□”表示箭线之间的连接点。⑵工作（曾称工序、活动、作业）将整个项目按需要粗细程度分解成若干需要耗费时间或需要耗费其他资源的子项目或单元。它们是网络计划图的基本组成部分。

网络图由工序、事件及标有完成各道工序所需时间所构成的连通有向图。紧前工序紧接某项工序的先行工序紧后工序紧接某项工序的后续工序前道工序某工序之前的所有工序后续工序某工序之后的所有工序A是D、E的紧前工序，D、E是A的紧后工序，F是A的后续工序但不是A的紧后工序；A是D、E、F的前道工序但不是F的紧前工序。①②③④⑤2天3天5天4天1天2天3天6天12ABCDEFGH网络图的构成作业（工作、工序、活动），箭头表示，箭头之上表示工作名称，之下表示工作时间。可有虚工作。事项，节点表示，表示某个工作的结束和另一工作的开始。一个基建项目网络图绘制网络图的基本原则网络图应正确表示工序的执行顺序网络图应从左向右延伸，编号应从小到大，且不重复。箭头事项编号大于箭尾事项编号网络图只能一个开始节点，一个终止节点不能出现循环路线网络线长度不重要,与工序时间长度无关任何两个节点之间只能有一个工序.合理布局，尽量少交叉。绘制网络图的基本原则两事项间只能有一项作业改为ABC1.当工序A完工后B和C可以开工○○○○3.工序c在工序A完工后就可以开工，但工序D必须在A和B都完工后才能开工ACBD○○○○○○2.当工序A和B完工后C和D可以开工4.事件i、j之间有多道工序时，添加虚工序②⑥③(a)ABCD○○○○○(b)(c)(d)ABC常见工序顺序acbd○○○○○○…○acbd○○…○○(e)(f)ee图7－2网络图只有一个发点（项目的开始点）一个收点（项目的结束点）。如图（e）所示，则应合成图（f）所示的一个始点及一个终点。用弧(i，j)表示一道工序，事件i是工序的开始，事件j是工序的完成，规定i<j。见下图①②③④⑤⑥⑦ABCDGEFH4050302050252020网络图绘制方法依照工序顺序表绘制初步网络，不能确定布局节点连接用虚工序表示。在不改变逻辑顺序的前提下，去除不必要的虚工序，并调整网络图布局，使其尽可能均衡、美观。调查项目的任务分解和分析试探性绘制法：试探试探性绘制法：修改1.2双代号网络计划图

以下通过例题来说明双代号网络计划图的绘制和时间参数的计算,并按工作计算时间参数的方法介绍。例1．开发一个新产品，需要完成的工作和先后关系，各项工作需要的时间汇总在逻辑关系表中，见表11-1。要求编制这项目的网络计划图和计算有关参数。表11-1序号工作名称工作代号工作持续时间（天）紧后工作1产品设计和工艺设计A60B,C,D,E2外购配套件B45L3锻件准备C10F4工装制造1D20G,H5铸件E40H6机械加工1F18L7工装制造2G30K8机械加工2H15L9机械加工3K25L10装配与调试L35/第1步根据表11-1中数据，绘制以下网络图，见图11-3。图11-3第2节

网络计划图的时间参数计算。

网络计划的时间参数计算有几种类型：双代号网络计划有工作计算法和节点计算法；单代号网络计划有节点计算法。以下仅介绍工作计算法。其它的计算法可参考[1]。

网络图中工作的时间参数。它们是：工作持续时间(D)；

工作最早开始时间（ES）；

工作最早完成时间（EF）；工作最迟开始时间（LS）；工作最迟完成时间（LF）；工作总时差（TF）；工作自由时差（FF）。事件和工序时间事项最早时间:事项最早可能发生时间。TE(1)＝0,TE(j)=max{TE(i)+T(i,j)}事项最迟时间:事项最迟必须结束的时间。TL(n)＝0,TL(j)=min{TL(j)-T(i,j)}2.1工作持续时间(D)。工作持续时间计算是一项基础工作，关系到网络计划是否能得到正确实施。为了有效地使用网络计划技术，需要建立相应的数据库。这需要专项讨论的问题。这里简述计算工作持续时间的两类数据和两种方法：

⑴

单时估计法（定额法）每项工作只估计或规定一个确定的持续时间值的方法。一般具有工作的工作量，劳动定额资料以及投入人力的多少等，计算各工作的持续时间；

工作持续时间

Q—

工作的工作量。以时间单位表示,如小时;或以体积，重量，长度等单位表示；R—

可投入人力和设备的数量；S—

每人或每台设备每工作班能完成的工作量；n—

每天正常工作班数。或具有类似工作的持续时间的历史统计资料时，可以根据这些资料，采用分析对比的方法确定所需工作的持续时间。

⑵三时估计法。在不具备有关工作的持续时间的历史资料时，在较难估计出工作持续时间时，可对工作进行估计三个时间值，然后计算其平均值。这三个时间值是：乐观时间。在一切都顺利时，完成工作需要的最少时间，记作a。最可能时间。在正常条件下，完成工作所需要时间。记作m。悲观时间。在不顺利条件下，完成工作需要最多时间，记作b。显然上述三种时间发生都具有一定的概率，根据经验，这些时间的概率分布认为是正态分布。一般情况下，通过专家估计法，给出三时估计的数据。可以认为：工作进行时出现最顺利和最不顺利的情况比较少。较多是出现正常的情况。按平均意义可用以下公式计算工作持续时间值：事件和工序时间事项最早时间:事项最早可能发生时间。TE(1)＝0,TE(j)=max{TE(i)+T(i,j)}事项最迟时间:事项最迟必须结束的时间。TL(n)＝0,TL(j)=min{TL(j)-T(i,j)}事件和工序时间工序最早开始时间:工序最早可能开始时间。TES(i,j)=TE(i)工序最迟结束时间:工序最迟必须结束的时间。TLF(i,j)＝TL(j)工序最早结束时间:工序最早可能结束的时间。TLF(i,j)＝TES(i,j)＋T(i,j)工序最迟开始时间:工序最迟必须开始的时间。TLS(i,j)＝TLF(j)-T(i,j)工序总时差和关键工序工序总时差:TE(i,j)=TLF(i,j)-TEF(i,j)=

TLS(i,j)-TES(i,j)总时差为零的工序称为关键工序。关键工序需要特别关注，任何关键工序的延误都会造成整个项目延误。工序时差和关键工序工序名（i,j)T(i,j)TES(i,j)TLF(i,j)TLS(i,j)总时差A(1,2)6006000B(2,7)45601359030C(2,3)106011710747D(2,4)206080600E(2,5)40601208020F(3,7)187013511747G(4,6)3080110800H(5,7)1510013512020K(6,7)251101351100L(7,8)351351701350第3节

时标网络计划图

时间坐标，简称时标。在网络计划图的上方或下方，加表示工程进度时间的坐标轴。根据需要规定时间单位为：小时、天、周、月或季。标注有时间坐标的网络计划图称为：时标网络计划图。在该图中箭线的长度就表示工作持续时间的长度。并且在图中可以用实粗箭线或实红色的箭线表示关键工作和关键线路。并且可用不同的线型表示出工作的总时差和自由时差。例1的时标网络计划图如图所示。图11-8第4节

网络计划的优化

绘制网络计划图，计算时间参数和确定关键线路，仅得到一个初始计划方案。然后根据上级要求和实际资源的配置，需要对初始方案进行调整和完善。即进行网络计划优化。目标是综合考虑进度，合理利用资源，降低费用等。包括：4.1工期优化。4.2资源优化4.3时间－费用优化

4.1工期优化若网络计划图的计算工期大于上级要求的工期时。必须根据要求计划的进度，缩短工程项目的完工工期。主要从：采取技术措施，提高工效，缩短关键工作的持续时间，使关键线路的时间缩短。采取组织措施，充分利用非关键工作的总时差，合理调配人力、物力和资金等资源。增加对关键工作的投入，以便缩短关键工作的持续时间，实现工期缩短。4.2资源优化

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

下面通过例1的例子说明平衡人力资源的方法。假设在例1中，现有机械加工工人数65人，要完成工作D,F,G,H,K。各工作需要工人人数列于表11-4

表11-4

由于机械加工工人数的限制若上述工作若都按最早开始时间安排，在完成各关键工作的75天工期中，每天需要机械加工工人人数如图11-9所示。图11-9

另一种全部按照最早时间：60－70天:58人70－80天：80人80－88天：103人88－95天：81人95－110天：42人11－135天：25人有10天需要80人，另10天需要81人。超过了现有机械工人人数的约束必须进行调整。以……线表示的非关键路线上非关键工作F,H有机动时间，若将工作F延迟10天开工，就可以解决第70－80天的超负荷问题；将工作H推迟10天开工，可以解决第100－110天的超负荷问题。于是新的负荷图（见图11-10）能满足机械工人的人数65人约束条件。图11-10以上人力资源平衡是利用非关键工作的总时差，可以错开资源负荷的高峰。也可以采用将非关键工作分段作业或采用技术措施减少所需要资源。也可以根据计划规定适当延长项目的工期。

4.3时间－费用优化

编制网络计划时，要研究如何使完成项目的工期尽可能缩短，费用尽可能少；或在保证既定项目完成时间条件下，所需要的费用最少；或在费用限制的条件下，项目完工的时间最短。这就是时间－费用优化要解决的问题。完成一项目的费用可以分为两大类：1.

直接费用2.

间接费用。

1.

直接费用

直接与项目的规模有关的费用。包括材料费用，直接生产工人工资等。为了缩短工作的持续时间和工期，就需要增加投入，即增加直接费用。

2.

间接费用包括管理费等。一般按项目工期长度进行分摊。工期愈短，分摊的间接费用就愈少。一般项目的总费用与直接费用和间接费用与项目工期之间存在一定关系，可以用图11-11表示T1—

最短工期，项目总费用最高；T2—

最经济的工期；T3—

正常的工期当总费用最少工期短于要求工期时，这就是最佳工期。进行时间－费用优化时，首先要计算出不同工期下最低直接费用率，然后考虑相应的间接费用。费用优化的步骤：

⑴

计算工作费用增加率

（简称费用率）

费用增加率是指：缩短工作持续时间每一单位时间（如一天）所需要增加的费用。按工作的正常持续时间计算各关键工作的费用率通常可表示为：△Ci-j

—

工作i-j的费用率CCi-j

—

将工作i-j持续时间缩短为最短持续时间后，完成该工作所需要的直接费用.CNi-j

—

在正常条件下完成工作i-j所需要的直接费用DNi-j

—

工作i-j正常持续时间DCi-j

—

工作i-j最短持续时间⑵

在网络计划图找出费用率最低的一项关键工作或一组关键工作作为缩短持续时间的对象。其缩短后的值不能小于最短持续时间，不能成为非关键工作。⑶

同时计算相应的增加的总费用。然后考虑由于工期的缩短间接费用的变化，在这基础上计算项目的总费用。重复以上步骤，直到获得满意的方案为止。以下通过例1说明已知项目的每天间接费用为400元，利用表11-6中的已知资料，项目正常工期为170天。表11-6170天方案对应的项目直接费用为68900元，间接费用为170×400=68000元，项目总费用为136900元。这是在正常条件下进行的方案，称为170天方案。若要缩短这方案的工期，首先从缩短关键路线上直接费用率最小的工作的持续时间，在170天方案中关键工作K,G的直接费用率是最低。从表中可见这两项工作的持续时间都只能缩短10天。工期费用优化关键工序正常时间极限时间直接费用率A6060-D2010400G3020350K2515290L3535-间接费用率:400原工序时差和关键工序工序名（i,j)T(i,j)TES(i,j)TLF(i,j)TLS(i,j)总时差A(1,2)6006000B(2,7)45601359030C(2,3)106011710747D(2,4)206080600E(2,5)40601208020F(3,7)187013511747G(4,6)3080100800