试谈PERT网络图的计算

1、运筹学刘东南第二节第二节 PERT网络图的计算网络图的计算v 例例1：某：某PERT网络图如下：网络图如下：v 四条路线四条路线v 1-2-3-5-8：13v 1-2-4-6-7-8：17v 1-2-6-7-8：12v 1-2-3-4-6-7-8：21关键线路决定工期，各项工作有轻重缓急之分。关键线路决定工期，各项工作有轻重缓急之分。158236474523421342运筹学刘东南一、作业时间一、作业时间t(i,j)的确定的确定 完成某一工序所需要的时间完成某一工序所需要的时间（1）确定型）确定型 资源确定，时间可确定计算资源确定，时间可确定计算（2）概率型（三点时间估计）概率型（三点时间估计

2、）乐观时间：在顺利情况下，完成工序所乐观时间：在顺利情况下，完成工序所需要的最少时间，常用符号需要的最少时间，常用符号a表示；表示；最可能时间：在正常情况下，完成工序最可能时间：在正常情况下，完成工序所需要的时间，常用符号所需要的时间，常用符号m表示；表示；悲观时间：在不顺利情况下，完成工序悲观时间：在不顺利情况下，完成工序所需要的最多时间，常用符合所需要的最多时间，常用符合b表示。表示。运筹学刘东南二、事项时间参数二、事项时间参数(1)事项最早时间事项最早时间(后面工作的最早可能开工后面工作的最早可能开工时间时间)tE(i)：与事项：与事项j相邻的各紧前事项的最早时相邻的各紧前事项的最早时间

3、。间。tE(n)=总最早完工期。总最早完工期。从前向后计算，取大值从前向后计算，取大值(1)0Et( ) ( )( , )maxEEitjtit i j运筹学刘东南（2）事项最迟时间）事项最迟时间(后面工作的最迟必须开后面工作的最迟必须开工时间工时间) tL(j)：与事项：与事项i相邻的各紧后事项的最迟时间。相邻的各紧后事项的最迟时间。确定工期，从右向左计算取小值。确定工期，从右向左计算取小值。 ( )( )LEtntn 总工期或( ) ( )( , )minLLjtitjt i j运筹学刘东南三、工作的时间参数三、工作的时间参数1.最早可能开工时间与最早可能完工时间。最早可能开工时间与最早可

4、能完工时间。 tES(i,j)（i事项最早时间）事项最早时间）， tEF(i,j)(1, )0( , )max( , )( , )( , )( , )( , )ESESESEFEStjti jtk it k iti jti jt i j1.所有从总开工事项出发的工作所有从总开工事项出发的工作(1,j),其最早可能开工时间其最早可能开工时间=0；2.任一工作任一工作(i,j)其最早可能开工时间其最早可能开工时间,要与它的所有的紧前工要与它的所有的紧前工作（作（k,i）的最早开工时间决定；）的最早开工时间决定；3.工作工作(i,j)其最早完工时间等于其最早开工时间与工时之和。其最早完工时间等于其最

5、早开工时间与工时之和。运筹学刘东南2.最迟必须开工时间与最迟必须完工时间。最迟必须开工时间与最迟必须完工时间。 tLS(i,j)， tLF(i,j)(j事项最迟时间事项最迟时间)( , )( , )( , )min( , )( , )( , )( , )( , )LFEFLSLSLFLSti nti nti jtj kt i jti jti jt i j或总完工期1. 总完工事项的工作总完工事项的工作(i,n),其最迟完工时间其最迟完工时间=预定总工期或者预定总工期或者等于这个工作的最早可能完工时间；等于这个工作的最早可能完工时间；2.任一工作任一工作(i,j)其最迟必须开工时间其最迟必须开工

6、时间,要与它的所有的紧后工要与它的所有的紧后工作（作（j,k）的最迟开工时间决定；）的最迟开工时间决定；3.工作工作(i,j)其最迟完工时间等于其最迟开工时间与工时之和。其最迟完工时间等于其最迟开工时间与工时之和。运筹学刘东南四、时差：工作的机动时间或富裕时间四、时差：工作的机动时间或富裕时间（1）工作总时差）工作总时差 不影响总工期的最多机动时间。某工作可以不影响总工期的最多机动时间。某工作可以延迟其开工时间的最大幅度。延迟其开工时间的最大幅度。（2）工作单时差）工作单时差 不影响紧后工作的最早开工时间。不影响紧后工作的最早开工时间。( , )( , )( , )( , )( , )LFEF

7、LSESR i jti jti jti jti j( , )( , )( , )( )( , )( , )( , )( , )( , )ESEFEESESESr i jtj kti jtjt i jti jtj kti jt i j运筹学刘东南 工作及时差关系工作及时差关系工作工作AES工作工作A的紧后工作的紧后工作ESEFLFLFEFLSLS总时差总时差单时差单时差(自由浮动自由浮动)运筹学刘东南v五、时间参数的图上计算法五、时间参数的图上计算法运筹学刘东南v 例例2189723106544683223825100410182023232531323231262323201810400441

8、01820232323232531010041513182029232324263110tEStLSRr001100000013611001100006130100( , )( , )( , )( )( , )( , )( , )( , )( , )ESEFEESESESr i jtj kti jtjt i jti jtj kti jt i j运筹学刘东南六、表上计算法六、表上计算法见下表见下表 原则：原则：工作的排列应严格按照箭尾事项工作的排列应严格按照箭尾事项编号由小到大的顺序排列，箭尾事项相编号由小到大的顺序排列，箭尾事项相同的工作，按其箭头事项有小到大排列。同的工作，按其箭头事项有小到

9、大排列。运筹学刘东南工作工作工作工时工作工时t(i,j)最早开工最早开工tES(i,j)最早完工最早完工tEF(i,j)最迟开工最迟开工tLS(i,j)最迟完工最迟完工tLF(i,j)总时差总时差R(i,j)单时差单时差r(i,j)关键工作关键工作箭尾箭尾i箭头箭头j1234567891041063823022851040104104 71018 18 20 2023 23 23 23 25 23 25 23 3125 3031323231312631232624312923232320201818101815104231340013011000061010013011000060010*运筹学刘东南关键线路的确定关键线路的确定 图上标注法图上标注法15387642AHELKGDFCB60451810204015302535060708010