厦门大学运筹学7

第八

章网络计划技术（PERT）

用网络分析的方法编制的计划称为网络计划。它是二十世纪五十年代末发展起来的一种编制大型工程进度计划的有效方法。1956年，美国杜邦公私在制定企业不同业务部门的系统规划时，制定了第一套网络计划。这种计划借助于网络表示各项工作与所需要的时间，以及各项工作的相互关系。通过网络分析研究工程费用与工期的相互关系。并找出在编制计划时及计划执行过程中的关键路线。这种方法称为关键路线法（CriticalPathMethod）简称CPM。1958年，美国海军武器部，在制定研制“北极星”导弹计划时，同样地应用了网络分析方法与网络计划。但它注重于对各项工作安排的评价和审查。这种计划称为计划评审方法(ProgramEvaluationandReviewTechnique）简称为PERT。鉴于这两种方法的差别，所以，CPM主要应用于以往在类似工程中已取得一定经验的承包工程；PERT更多地应用于研究与开发项目。在这两种方法得到应用推广之后，又陆续出现了类似的最低成本和估算计划法、产品分析控制法、人员分配法、物资分配和多种项目计划制定法等等。虽然方法很多，各自側重的目标有所不同。但它们都应用的是CPM和PERT的基本原理和基本方法。二十世纪六十年代我国开始应用CPM与PERT，并根据其基本原理与计划的表达形式，称它们为网络技术或网络方法，又按照网络计划的主要特点——统筹安排，把这些方法称为统筹法。

国内外应用网络计划的实践表明，它具有一系列优点，特别适用于生产技术复杂，工作项目繁多、且联系紧密的一些跨部门的工作计划。例如新产品研制开发、大型工程项目、生产技术准备、设备大修等计划。还可以应用在人力、物力、财力等资源的安排，合理组织报表、文件流程等方面。

编制网络计划包括绘制网络图，计算时间参数，确定关键路线及网络优化等环节。下面分别讨论这些内容。

第一节网络图例1某项研制新产品工程的各个工序与所需时间以及它们之间的相互关系如表7—1所示。要求编制该项工程的网络计划。表7—1工序工序代号所需时间(天)紧后工序产品设计与工艺设计a65b，c，d，e

外购配套件b45l

下料、锻件c10f

工装制造1

d20g，h

木模、铸件e40h

机械加工1

f18l

工装制造2

g30k

机械加工2

h15l

机械加工3

k25l

装配调试l35—为了编制网络计划，首先需绘制网络图。网络图是由结点(点)、弧及权所构成的有向图。即有向的赋权图。

结点表示一个事项（或事件），它是一个或若干个工序的开始或结束，是相邻工序在时间上的分界点。结点用圆圈和里面的数字表示，数字表示结点的编号，如①，②，…等。弧表示一个工序，工序是指为了完成工程项目,在工艺技术和组织管理上相对独立的工作或活动。一项工程由若干个工序组成。工序需要一定的人力、物力等资源和时间。弧用箭线“→”表示。

权表示为完成某个工序所需要的时间或资源等数据。通常标注在箭线下面或其它合适的位置上。

根据表7—1的已知条件和数据，绘制的网络如图7—1所示。

在图7—1中，箭线a、b、…、

l分别代表10个工序。箭线下面的数字表示为完成该个工序所需的时间（天数）。结点①、②、…、⑧分别表示某一或某些工序的开始和结束。例如，结点②表示a工序的结束和b、c、d、e等工序的开始,即a工序结束后,后四个工序才能开始。12467835a60b45c10d20e40f18g30h15k25l350图7—1

在绘制网络图中，用一条弧和两个结点表示一个确定的工序。例如，②→⑦表示一个确定的工序b。工序开始的结点称为箭尾结点,如b工序的②；工序结束的结点称为箭头结点,如b工序的⑦。②称为箭尾事项，⑦称为箭头事项。工序的箭尾事项与箭头事项称为该工序的相关事项。在一张网络图上只能有始点和终点两个结点，分别表示工程的开始和结束，其它结点既表示上一个（或若干个）工序的结束，又表示下一个（或若干个）工序的开始。

为正确反映工程中各个工序的相互关系,在绘制网络图时，应遵循以下规则：(1)方向、时序与结点编号

网络图是有向图，按照工艺流程的顺序，规定工序从左向右排列。网络图中的各个结点都有一个时间(某一个或若干个工序开始或结束的时间),一般按各个结点的时间顺序编号。为了便于修改编号及调整计划,可以在编号过程中留出一些编号。始点编号可以从1开始，也可以从0开始。(2)

紧前工序与紧后工序例如,在图7—1中,只有在a

工序结束以后,b、c、d、e工序才能开始。a工序是b、c、d、e

等工序的紧前工序,而b、c、d、e等工序则是工序a

的紧后工序。(3)虚工序

为了用来表达相邻工序之间的衔接关系，而实际上并不存在而虚设的工序。虚工序不需要人力、物力等资源和时间。只表示某工序必须在另外一个工序结束后才能开始。如图7—1中，虚工序④┄→⑤只表示在d

工序结束后，h

工序才能开始。(4)相邻两个结点之间只能有一条弧

即一个工序用确定的两个相关事项表示，某两个

相邻结点只能是一个工序的相关事项。在计算机上计算各个结点和各个工序的时间参数时，相关事项的两个结点只能表示一道工序，否则将造成逻辑上的混乱。如图7—2的画法是错误的，图7—3的画法是正确的。1231243abcabc图7—2图7—3(5)网络图中不能有缺口和回路在网络图中，除始点和终点外，其它各个结点的

前后都应有弧相连接，即图中不能有缺口，使网络图从始点经任何路线都可到达终点。否则，将使某些工序失去与其紧后（或紧前）工序应有的联系。

在本章讨论的网络图中不能有回路，即不可能有循环现象。否则，将使组成回路的工序永远不能结束，工程永远不能完工。在如下网络图7—4中出现的情况，显然是错误的。1234abcd图7—4(6)平行作业

为缩短工程的完工时间，在工艺流程和生产组织条件允许的情况下，某些工序可以同时进行，即可采用平行作业的方式。如在图7—1中，工序b、c、d、e四个工序即可平行作业。

在有几个工序平行作业结束后转入下一道工序的情况下，考虑到便于计算网络时间和确定关键路线，选择在平行作业的几个工序中所需时间最长的一个工序，直接与其紧后工序衔接，而其它工序则通过虚工序与其紧后工序衔接。如在图7—1中,工序d、e

平行作业,这两个工序都结束后,它们的紧后工序h

才可能开始。在工序d、e

中,工序e所需的时间(40天)比工序d所需时间(20天)长，则工序e

直接与工序h

连接，而工序d则通过虚工序与工序

h连接。(7)交叉作业

对需要较长时间才能完成的一些工序，在工艺流程与生产组织条件允许的情况下，可以不必等待工序全部结束后再转入其紧后工序，而是分期分批的转入。这种方式称为交叉作业。交叉作业可以缩短工程周期。如在图7—1中，将工装制造分为两批，将一个工序分为两个工序d、g，分别与紧后工序h、k连接。(8)始点和终点

为表示工程的开始和结束，在网络图中只能有一个始点和一个终点。当工程开始时有几个工序平行作业，或在几个工序结束后完工，用一个始点、一个终点表示。若这些工序不能用一个始点或一个终点表示时，可用虚工序把它们与始点或终点连起来。(9)网络图的分解与综合根据网络图的不同需要，一个工序所包括的工作内容可以多一些，即工序综合程度较高。也可以在一个工序中所包括的工作内容少一些，即工序综合程度较低。一般情况下，工程总指挥部制定的网络计划是工序综合程度较高的网络图（母网络图）而下一级部门，根据综合程度高的网络图的要求，制定本部门的工序综合程度低的网络图（子网络图）。将母网络分解为若干个子网络，称为网络图的分解。而将若干个子网络综合为一个母网络，则称为网络图的综合。若将图7—1视为一个母网络。它可以分解为工序a，工序b、c、d、e、f、g、h、k，及工序l

三个子网络。工序a

和工序

l都可以再分解为综合程度较低的若干个工序。(10)网络图的步局

在网络图中，尽可能将关键路线布置在中心位置，并尽量将联系紧密的工作布置在相近的位置。为使网络图清楚和便于在图上填写有关的时间数据与其它数据，弧线尽量用水平线或具有一段水平线的折线。网络图也可以附有时间进度；必要时也可以按完成各工序的工作单位布置网络图。

第二节网络时间与关键路线(1)

路线与关键路线在网络图中，从始点开始，按照各个工序的顺序，连续不断地到达终点的一条通路称为路线。如在图7—1中，共有五条路线，五条路线的组成及所需要的时间如表7—2所示。表7—2路线路线的组成各工序所需的时间之和(天)1①→②→⑦→⑧60+45+35=1402①→②→③→⑦→⑧60+10+18+35=1233①→②→④→⑥→⑦→⑧60+20+30+25+35=1704①→②→④→⑤→⑦→⑧60+20+15+35=1305①→②→⑤→⑦→⑧60+40+15+35=150

在各条路线上，完成各个工序的时间之和是不完全相等的。其中，完成各个工序需要时间最长的路线称为关键路线，或称为主要矛盾线，在图中用粗线表示。在图7—1中，第三条路线就是条关键路线，组成关键路线的工序称为关键工序。如果能够缩短关键工序所需的时间，就可以缩短工程的完工时间。而缩短非关键路线上的各个工序所需要的时间，却不能使工程的完工时间提前。即使在一定范围内适当地拖长非关键路线上各个工序所需要的时间，也不至于影响工程的完工时间。编制网络计划的基本思想就是在一个庞大的网络图中找出关键路线。对各关键工序，优先安排资源，挖掘潜力，采取相应措施，尽量压缩需要的时间。而对非关键路线上的各工序，只要在不影响工程完工时间的条件下，抽出适当的人力、物力等资源，用在关键工序上，以达到缩短工程工期，合理利用资源等目的。在执行计划过程中，可以明确工作重点，对各关键工序加以有效控制和调度。关键路线是相对的，也是可以变化的。在采取一定的技术组织措施之后，关键路线有可能变为非关键路线。而非关键路线也有可能变为关键路线。(2)网络时间的计算为了编制网络计划和找出关键路线,要计算网络图中各个事项及各个工序的有关时间，称这些有关时间为网络时间。

1)作业时间(Tij)：为完成某一工序所需要的时间称为该工序的作业时间，用Tij表示。

2)事项时间：①事项最早时间TE(j)——若事项为某一工序的箭尾事项时，事项最早时间为各工序的最早可能开始时间。若事项为某一或若干工序的箭头事项时，事项最早时间为各工序的最早可能结束时间。通常是按箭头事项计算事项最早时间,用TE(j)表示,它等于从始点事项起到本事项最长路线的时间长度。计算事项最早时间是从始点事项开始，自左向右逐个事件向前计算。假定始点事项的最早时间等于零，即TE(1)=0。箭头事项的最早时间等于箭尾事项最早时间加上作业时间。当同时有两个或若干个箭线指向箭头事项时，选择各工序的箭尾事项最早时间与各自工序作业时间之和的最大值。即：

TE(1)=0TE(j)=max{TE(i)+T(i，j)}(j=2，…，n)

式中：TE(j)为箭头事项的最早时间；TE(i)为箭尾事项的最早时间；

例如，在网络图7—1中各事项的最早时间为：TE(1)=0TE(2)=TE(1)+T(1，2)=0+60=60TE(3)=TE(2)+T(2，3)=60+10=70TE(4)=TE(2)+T(2，4)=60+20=80TE(5)=max{TE(2)+T(2，5)，TE(4)+T(4，5)}=max{60+40，80+0}=100TE(6)=TE(4)+T(4，6)=80+30=110

TE(7)=max{TE(2)+T(2,7)，TE(3)+T(3,7)，TE(6)+T(6,7)，TE(5)+T(5,7)}=max{60+45,70+18,110+25,100+15}=135TE(8)=TE(7)+T(7，8)=135+35=170

将上述计算结果计入各事项左下方的方框内，见图7—5。②事项最迟时间TL(i)

即箭头事项各工序的最迟必须结束时间，或箭尾事项各工序的最迟必须开始时间。

为了尽量缩短工程的完工时间,把终点事项的最早时间，即工程的最早结束时间作为终点事项的最迟时间。事项最迟时间通常按箭尾事项的最迟时间计算，从右向左反顺序进行。箭尾事项的最迟时间等于箭头事项的最迟时间减去该工序的作业时间。当箭尾事项同时引出两个以上箭线时，该箭尾事项的最迟时间必须同时满足这些工序的最迟必须开始时间。所以在这些工序的最迟必须开始时间中选一个最早（时间值最小）的时间，即：TL(n)=TE(n)（n

为终点事项）TL(i)=min{TL(j)

T(i,j)}(i=n

1，…，2,1)

式中：

TL(i)为箭尾事项的最迟时间；

TL(j)为箭头事项的最迟时间。例如，在网络图7—1中各事项的最迟时间为：

TL(8)=TE(8)=170

TL(7)=TL(8)

T(7,8)=170=135

TL(6)=TL(7)

T(6,7)=135

25=110

TL(5)=TL(7)

T(5,7)=135

20=115

TL(4)=min{TL(6)

T(4,6)，TL(5)

T(4,5)}=min{110

30，120

0}=80

TL(3)=