网络计划技术(PERT)

运筹学之第四章网络方案技术〔ProgramEvaluationandReviewTechnique〕第四章网络方案技术〔PERT〕4.1前言4.2网络图4.3网络时间与关键路线4.4网络优化4.5网络方案的实施控制作业4.1前言用网络分析的方法编制的方案称为网络方案。它是二十世纪五十年代末开展起来的一种编制大型工程进度方案的有效方法。1956年，美国杜邦公司在制定企业不同业务部门的系统规划时，制定了第一套网络方案。这种方案借助于网络表示各项工作与所需要的时间，以及各项工作的相互关系。通过网络分析研究工程费用与工期的相互关系。并找出在编制方案时及方案执行过程中的关键路线。这种方法称为关键路线法〔CriticalPathMethod〕简称CPM。1958年，美国海军武器部，在制定研制“北极星〞导弹方案时，同样地应用了网络分析方法与网络方案。但它注重于对各项工作安排的评价和审查。这种方案称为方案评审方法〔ProgramEvaluationandReviewTechnique〕简称为PERT。鉴于这两种方法的差异，所以，CPM主要应用于以往在类似工程中已取得一定经验的承包工程；PERT更多地应用于研究与开发工程。在这两种方法得到应用推广之后，又陆续出现了类似的最低本钱和估算方案法、产品分析控制法、人员分配法、物资分配和多种工程方案制定法等等。虽然方法很多，各自側重的目标有所不同。但它们都应用的是CPM和PERT的根本原理和根本方法。二十世纪六十年代我国开始应用CPM与PERT，并根据其根本原理与方案的表达形式，称它们为网络技术或网络方法，又按照网络方案的主要特点——统筹安排，把这些方法称为统筹法。国内外应用网络方案的实践说明，它具有一系列优点，特别适用于生产技术复杂，工作工程繁多、且联系紧密的一些跨部门的工作方案。例如新产品研制开发、大型工程工程、生产技术准备、设备大修等计划。还可以应用在人力、物力、财力等资源的安排，合理组织报表、文件流程等方面。编制网络方案包括绘制网络图，计算时间参数，确定关键路线及网络优化等环节。下面分别讨论这些内容。4.2网络图【例4－1】某项研制新产品工程的各个工序与所需时间以及它们之间的相互关系如表4—1所示。要求编制该项工程的网络方案。表4—1见下页。工序工序代号所需时间(天)紧后工序产品设计与工艺设计a65b，c，d，e

外购配套件b45l

下料、锻件c10f

工装制造1d20g，h

木模、铸件e40h

机械加工1f18l

工装制造2g30k

机械加工2h15l

机械加工3k25l

装配调试l35—为了编制网络方案，首先需绘制网络图。网络图是由结点(点)、弧及权所构成的有向图。即有向的赋权图。结点表示一个事项〔或事件〕，它是一个或假设干个工序的开始或结束，是相邻工序在时间上的分界点。结点用圆圈和里面的数字表示，数字表示结点的编号，如①，②，…等。弧表示一个工序，工序是指为了完成工程工程,在工艺技术和组织管理上相对独立的工作或活动。一项工程由假设干个工序组成。工序需要一定的人力、物力等资源和时间。弧用箭线“→〞表示。权表示为完成某个工序所需要的时间或资源等数据。通常标注在箭线下面或其它适宜的位置上。根据表4—1的条件和数据，绘制的网络如图4—1所示。12467835a60b45c10d20e40f18g30h15k25l350图4—1返回表4－3在图4—1中，箭线a、b、…、l分别代表10个工序。箭线下面的数字表示为完成该个工序所需的时间〔天数〕。结点①、②、…、⑧分别表示某一或某些工序的开始和结束。例如，结点②表示a工序的结束和b、c、d、e等工序的开始,即a工序结束后,后四个工序才能开始。在绘制网络图中，用一条弧和两个结点表示一个确定的工序。例如，②→⑦表示一个确定的工序b。工序开始的结点称为箭尾结点,如b工序的②；工序结束的结点称为箭头结点,如b工序的⑦。②称为箭尾事项，⑦称为箭头事项。工序的箭尾事项与箭头事项称为该工序的相关事项。在一张网络图上只能有始点和终点两个结点，分别表示工程的开始和结束，其它结点既表示上一个〔或假设干个〕工序的结束，又表示下一个〔或假设干个〕工序的开始。为正确反映工程中各个工序的相互关系,在绘制网络图时，应遵循以下规那么：(1)方向、时序与结点编号网络图是有向图，按照工艺流程的顺序，规定工序从左向右排列。网络图中的各个结点都有一个时间(某一个或假设干个工序开始或结束的时间),一般按各个结点的时间顺序编号。为了便于修改编号及调整方案,可以在编号过程中留出一些编号。始点编号可以从1开始，也可以从0开始。(2)

紧前工序与紧后工序例如,在图4—1中,只有在a工序结束以后,b、cd、e工序才能开始。a工序是b、c、d、e等工序的紧前工序,而b、c、d、e等工序那么是工序a的紧后工序。12467835a60b45c10d20e40f18g30h15k25l350图4—1(3)虚工序为了用来表达相邻工序之间的衔接关系，而实际上并不存在而虚设的工序。虚工序不需要人力、物力等资源和时间。只表示某工序必须在另外一个工序结束后才能开始。如图4—1中，虚工序④┄→⑤只表示在d工序结束后，h工序才能开始。(4)相邻两个结点之间只能有一条弧即一个工序用确定的两个相关事项表示，某两个相邻结点只能是一个工序的相关事项。在计算机上计算各个结点和各个工序的时间参数时，相关事项的两个结点只能表示一道工序，否那么将造成逻辑上的混乱。如图4—2的画法是错误的，图4—3的画法是正确的。(5)网络图中不能有缺口和回路在网络图中，除始点和终点外，其它各个结点的前后都应有弧相连接，即图中不能有缺口，使网络图从始点经任何路线都可到达终点。否那么，将使某些工序失去与其紧后〔或紧前〕工序应有的联系。123abc图4—21243abc图4—3在本章讨论的网络图中不能有回路，即不可能有循环现象。否那么，将使组成回路的工序永远不能结束，工程永远不能完工。在如下网络图4—4中出现的情况，显然是错误的。1234abcd图4—4(6)平行作业为缩短工程的完工时间，在工艺流程和生产组织条件允许的情况下，某些工序可以同时进行，即可采用平行作业的方式。如在图4—1中，工序b、c、d、e四个工序即可平行作业。在有几个工序平行作业结束后转入下一道工序的情况下，考虑到便于计算网络时间和确定关键路线，选择在平行作业的几个工序中所需时间最长的一个工序，直接与其紧后工序衔接，而其它工序那么通过虚工序与其紧后工序衔接。如在图4—1中,工序d、e平行作业,这两个工序都结束后,它们的紧后工序h才可能开始。在工序d、e中,工序e所需的时间(40天)比工序d所需时间(20天)长，那么工序e直接与工序h连接，而工序d那么通过虚工序与工序h连接。12467835a60b45c10d20e40f18g30h15k25l350图4—1(7)交叉作业对需要较长时间才能完成的一些工序，在工艺流程与生产组织条件允许的情况下，可以不必等待工序全部结束后再转入其紧后工序，而是分期分批的转入。这种方式称为交叉作业。交叉作业可以缩短工程周期。如在图4—1中，将工装制造分为两批，将一个工序分为两个工序d、g，分别与紧后工序h、k连接。(8)始点和终点为表示工程的开始和结束，在网络图中只能有一个始点和一个终点。当工程开始时有几个工序平行作业，或在几个工序结束后完工，用一个始点、一个终点表示。假设这些工序不能用一个始点或一个终点表示时，可用虚工序把它们与始点或终点连起来。如以下图，有2个始点，3个终点，显然是错误的。123456782433121123465782403130201(9)网络图的分解与综合根据网络图的不同需要，一个工序所包括的工作内容可以多一些，即工序综合程度较高。也可以在一个工序中所包括的工作内容少一些，即工序综合程度较低。一般情况下，工程总指挥部制定的网络方案是工序综合程度较高的网络图〔母网络图〕，而下一级部门，根据综合程度高的网络图的要求，制定本部门的工序综合程度低的网络图〔子网络图〕。将母网络分解为假设干个子网络，称为网络图的分解。而将假设干个子网络综合为一个母网络，那么称为网络图的综合。假设将图4—1视为一个母网络。它可以分解为工序a，工序b、c、d、e、f、g、h、k，及工序l三个子网络。工序a和工序l都可以再分解为综合程度较低的假设干个工序。(10)网络图的布局

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

a=a1+a2a:挖沟，b:下管，c:回填土

b=b1+b2c=c1+c2a1

a2

b1

b2

c1

c2

a1

b1

c1

b2

c2

a2

【例4－2】某调研工作工序如下表：工序内容工时(天)紧前工序A初步研究1/B研究选点2AC准备调研方案4AD联系调研点2BE培训工作人员3B,CF准备表格1CG实地调研5D,E,FH写调研报告2GI开会汇总3H12325132004CFEDBAGHI1234567894.3网络时间与关键路线路线与关键路线在网络图中，从始点开始，按照各个工序的顺序，连续不断地到达终点的一条通路称为路线。如在图4—1中，共有五条路线，五条路线的组成及所需要的时间如表4—3所示。表4－3路线路线的组成各工序所需的时间之和(天)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图4－1在各条路线上，完成各个工序的时间之和是不完全相等的。其中，完成各个工序需要时间最长的路线称为关键路线，或称为主要矛盾线，在图中用粗线表示。在图4—1中，第三条路线就是条关键路线，组成关键路线的工序称为关键工序。如果能够缩短关键工序所需的时间，就可以缩短工程的完工时间。而缩短非关键路线上的各个工序所需要的时间，却不能使工程的完工时间提前。即使在一定范围内适当地拖长非关键路线上各个工序所需要的时间，也不至于影响工程的完工时间。编制网络方案的根本思想就是在一个庞大的网络图中找出关键路线。对各关键工序，优先安排资源，挖掘潜力，采取相应措施，尽量压缩需要的时间。【例4－3】关键路线356124543223312124612105613856T=12(周)而对非关键路线上的各工序，只要在不影响工程完工时间的条件下，抽出适当的人力、物力等资源，用在关键工序上，以到达缩短工程工期，合理利用资源等目的。在执行方案过程中，可以明确工作重点，对各关键工序加以有效控制和调度。关键路线是相对的，也是可以变化的。在采取一定的技术组织措施之后，关键路线有可能变为非关键路线。而非关键路线也有可能变为关键路线。(2)网络时间的计算为了编制网络方案和找出关键路线,要计算网络图中各个事项及各个工序的有关时间，称这些有关时间为网络时间。作业时间(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)为箭尾事项的最早时间；12467835a60b45c10d20e40f18g30h15k25l350图4—1例如，在网络图4—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=110TE(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

将上述计算结果计入各事项左下方的方框内，见图4-5。12467835006060808011011013513517017010012070117a(60)b(45)c(10)d(20)e(40)f(18)g(30)h(15)k(25)l(35)图4-565页37页②事项最迟时间TL(i)

即箭头事项各工序的最迟必须结束时间，或箭尾事项各工序的最迟必须开始时间。为了尽量缩短工程的完工时间,把终点事项的最早时间，即工程的最早结束时间作为终点事项的最迟时间。事项最迟时间通常按箭尾事项的最迟时间计算，从右向左反顺序进行。箭尾事项的最迟时间等于箭头事项的最迟时间减去该工序的作业时间。当箭尾事项同时引出两个以上箭线时，该箭尾事项的最迟时间必须同时满足这些工序的最迟必须开始时间。所以在这些工序的最迟必须开始时间中选一个最早〔时间值最小〕的时间，即：TL(n)=TE(n)〔n为终点事项〕TL(i)=min{TL(j)T(i,j)}(i=n1，…，2,1)式中：TL(i)为箭尾事项的最迟时间；TL(j)为箭头事项的最迟时间。例如，在网络图4—1中各事项的最迟时间为：TL(8)=TE(8)=170TL(7)=TL(8)T(7,8)=170=13512467835006060808011011013513517017010012070117a(60)b(45)c(10)d(20)e(40)f(18)g(30)h(15)k(25)l(35)图4-5TL(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)=TL(7)

T(3，7)=135

18=117

TL(2)=min{TL(7)

T(2,7)，TL(3)

T(2,3)，

TL(4)

T(2,4)，TL(5)

T(2,5)}=min{135

45，117

10，80

20，120

40}=60

TL(1)=TL(2)

T(1，2)=60

60=0将各事项的最迟时间记入该事项的右下角的三角框内，见图4—5所示。3〕工序的最早开始时间、最早结束时间、最迟结束时间与最迟开始时间①工序的最早开始时间TES(i，j)任何一个工序都必须在其紧前工序结束后才能开始。紧前工序最早结束时间即为工序最早可能开始时间，简称为工序最早开始时间，用TES(i，j)表示。它等于该工序箭尾事项的最早时间，即：TES(i，j)=TE(i)在图4-5中：TES(1，2)=0，TES(2,3)=TES(2,4)=TES(2,5)=TES(2,7)=60，TES(3，7)=70，TES(4，6)=80，TES(5，7)=100，TES(6，7)=110，TES(7，8)=135。12467835006060808011011013513517017010012070117a(60)b(45)c(10)d(20)e(40)f(18)g(30)h(15)k(25)l(35)图4-5②工序最早结束时间TEF(i，j)是工序最早可能结束时间的简称，它等于工序最早开始时间加上该工序的作业时间。即

TEF(i，j)=TES(i，j)+T(i，j)在图4-5中，TEF(1，2)=0+60=60，TEF(2，3)=60+10=70，TEF(2，4)=60+20=80，

TEF(2，5)=60+40=100，TEF(2，7)=60+45=105，TEF(3，7)=70+18=88，TEF(4，6)=80+30=110，TEF(5，7)=100+15=115，TEF(6，7)=110+25=135，

TEF(7，8)=135+35=170。③工序最迟结束时间TLF(i，j)

在不影响工程最早结束时间的条件下,工序最迟必须结束时间。简称为工序最迟结束时间,用TLF(i，j)表示。它等于工序的箭头事项的最迟时间，即:

TLF(i，j)=TL(j)

在图4-5中，TLF(7，8)=170，TLF(6,7)=TLF(5,7)=TLF(3,7)=TLF(2,7)=135，

TLF(4，6)=110，

TLF(2，5)=120，TLF(2，4)=80，TLF(2，3)=117，TLF(1，2)=60。④工序最迟开始时间TLS(i，j)

在不影响工程最早结束时间的条件下，工序最迟必须开始的时间。简称为工序最迟开始时间,用TLS(i，j)表示。它等于工序最迟结束时间减去工序的作业时间，即:TLS(i，j)=TLF(i，j)

T

(i，j)在图4-5中，TLS(1，2)=60

60=0，TLS(2，3)=117

10=107，TLS(2，4)=80

20=60，TLS(2，5)=120

40=80，TLS(2，7)=135

45=90，TLS(3，7)=135

18=117，TLS(4，6)=110

30=80TLS(5，7)=135

15=120，TLS(6，7)=135

25=110，TLS(7，8)=170

35=135。⑤工序总时差TF(i，j)在不影响工程最早结束时间的条件下，工序最早开始(或结束)时间可以推迟的时间，称为该工序的总时差。(即工序的完工期可以推迟的时间)即：工序总时差=最迟开始最早开始即:TF(i，j)=TLS(i，j)TES(i，j)或:工序总时差=最迟结束最早结束即:TF(i，j)=TLF(i，j)TEF(i，j)工序总时差越大,说明该工序在整个网络中的机动时间越大，可以在一定范围内将该工序的人力、物力资源利用到关键工序上去，以到达缩短工程结束时间的目的。⑥工序单时差FF(i，j)

在不影响紧后工序最早开始时间的条件下,工序最早结束时间可以推迟的时间,称为该工序的单时差。

FF(i，j)=TES

(j，k)

TEF

(i，j)式中，TES

(j，k)为工序i―→j的紧后工序的最早开始时间。工序总时差、单时差及其紧后工序的最早开始时间、最迟开始时间的关系如图4-6所示。工序a工序a的紧后工序b工序a的单时差工序a的总时差TESTLSTEFTLFTESTLSTEFTLF图4-6

总时差为零的工序，开始和结束的时间没有一点机动的余地。由这些工序所组成的路线就是网络中的关键路线。这些工序就是关键工序。用计算工序总时差的方法确定网络中的关键工序和关键路线是确定关键路线最常用的方法。在图4-5中，工序a、d、g、k、l的总时差为零,由这些工序组成的路线就是图4-5中的关键路线。通过上述的网络时间参数计算过程可以看出,计算过程具有一定的规律和严格的程序,可以在计算机上进行计算，也可以用表格法与矩阵法计算。小结：〔一〕事项时间参数计算(tij)(1)、事项最早时间tE(i)=tE(1)=0tE(j)=max{tE(i)+tij}i(2)、事项最迟时间tL(i)=tL(n)=tE(n)或指定tL(i)=min{tL(j)-tij}j(3)、事项时差R(i)=tL(i)-tE(i)【例4－4】计算以下网络的事项时间参数1244563523332124456352333250534790912012000729左上角数字：事项最早时间左下角数字：事项最迟时间右上角数字：事项时差【例4－5】计算以下网络的事项时间参数1259876345232312400112598763452323124001000101325505505808130131501518018左下角数字：事项最迟时间左上角数字：事项最早时间右上角数字：事项时差(二)、工序时间参数计算(1)、工序最早开工时间(2)、工序最早完工时间tES(1,j)=0tES(i,j)=max{tES(k,i)+tki}tEF(i,j)=tES(i,j)+tij(3)、工序最迟开工时间(4)、工序最迟完工时间tLF(i,n)=tEF(i,n)或指定tLS(i,j)=min{tLS(j,k)-tij}tLF(i,j)=tLS(i,j)+tij(5)、工序总时差R(i,j)=tLS(i,j)-tES(i,j)=tLF(i,j)-tEF(i,j)(6)、工序单时差r(i,j)=tES(j,k)-tEF(i,j)说明：①总时差可以串用24

总时差为178707②42350510010124456352333212445635233320000505034727292909004405270最早开工时间最迟开工时间工序总时差工序单时差1253411252248967423最早开工时间最迟开工时间工序总时差工序单时差1253411252248967423000090904150617081914040459410010013013091100628134111121T=15最早开工时间最迟开工时间工序总时差工序单时差表上计算法：工序关键工序

i

j12345678910RrtLFtijtEStEFtLS4.4网络优化绘制网络图、计算网络时间和确定关键路线,得到一个初始的方案方案。但通常还要对初始方案方案进行调整和完善。根据方案的要求，综合地考虑进度、资源利用和降低费用等目标，即进行网络优化，确定最优的方案方案。(1)

时间优化根据对方案进度的要求，缩短工程完工时间。1)采取技术措施，缩短关键工序的作业时间；2)采取组织措施,充分利用非关键工序的总时差,合理调配技术力量及人、财、物力等资源，缩短关键工序的作业时间。(2)时间——资源的优化在编制网络方案安排工程进度的同时,就要考虑尽量合理地利用现有资源,并缩短工程周期。但是，由于一项工程所包括的工作工程繁多，涉及到的资源利用情况比较复杂，往往不可能在编制网络方案时，一次性就把进度和资源利用都能够做出统筹合理的安排，常常是需要进行几次综合平衡之后，才能得到在时间进度及资源利用等方面都比较合理的方案方案。具体的要求和作法是：优先安排关键工序所需要的资源；2〕利用非关键工序的总时差，错开各工序的开始时间，拉平资源需求的顶峰；3)在确实受到资源限制，或者在考虑综合经济效益的条件下，也可以适当的推迟工程完工时间。(3)时间——费用优化在编制网络方案过程中,研究如何使得工程完工时间短、费用少；或者在保证既定的工程完工时间的条件下，所需要的费用最少；或者在限制费用的条件下，工程完工时间最短；这就是时间——费用优化所要研究和解决的问题。为完成一项工程，所需要的费用可分为两大类：直接费用包括直接生产工人的工资及附加费、设备、能源、工具及材料消耗等直接与完成工序有关的费用。为缩短工序的作业时间，需要采取一定的技术组织措施，相应地要增加一局部直接费用。在一定条件下和一定范围内，工序的作业时间越短，直接费用就越多。2)间接费用包括管理人员的工资、办公费用等。间接费用，通常按照施工时间的长短分摊，在一定生产规模内，工序的作业时间越短，分摊的间接费用就越少。在进行时间——费用优化时，需要计算在采取各种技术组织措施之后，工程工程的不同的完工时间所对应的工序总费用和工程工程所需要的总费用。使得工程费最低的工程完工时间称为最低本钱日程。编制网络方案，无论是以降低费用为主要目标，还是以尽量缩短工程完工时间为主要目标，都要计算最低本钱日程，从而提出时间——费用的优化方案。下面以一实例说明计算最低本钱日程的一种直观判断的方法。【例4－6】:图4－5中各道工序正常情况下的作业时间(已标在各条弧线的下方)和极限时间,以及对应于正常时间、极限时间各工序所需要的直接费用和每缩短一天工期需要增加的直接费用，见表4－4所示。表4－4工序正常情况下采取各种措施后缩短一天工期增加直接费用(元/天）正常时间(天)工序的直接费用(元)极限时间(天)工序的直接费用(元)a60100006010000—b454500306300120c10280054300300d2070001011000400e40100003512500500f183600105440230g3090002012500350h153750105750400k256250