运筹学与系统分析：第6章 网络计划

1、第六章：网络计划网络计划方法：是一种科学管理方法。网络计划技术CPM (Critical Path Method)PERT (Program Evaluation and Review Technique)网络计划技术：广泛应用在时间进度的安排、资源分配、工程费用的优化等方面。6.1 网络图的组成及绘制6.1.1 网络图的组成一、作业（工序） 一项需要消耗人力、物质和时间的具体活动过程。 用箭杆表示，如：at1ij也表示从 i 结点到 j 结点的作业二、结点（事项） 一项作业的开始或完工的瞬间点，它不消耗人力、物质和时间。用圆圈“O”表示。如： 规定：箭尾结点的代号一定小于箭头结点的代号，逆序

2、不允许。32三、线路 沿箭头方向连接开始、结束结点的通路称为线路。路长：一条线路上各作业时间之和。关键路线：路长最长的线路。四、虚作业 用虚线画的箭杆，称为虚作业。它不占用时间，也不消耗人力与资源。如：五、其它概念先行作业：某作业前面紧接的作业；后续作业：某作业后面紧跟的作业；并行作业：与某作业同时进行的作业；中途作业：在某作业的中途进行的作业。6.1.2 绘制网络图的基本规则首先，根据工程的作业流程，列出作业时间表：根据规制画出作业时间表对应的网络图：基本规则：一、图中不允许出现循环回路；二、不允许出现编号相同的箭杆；三、一个网络图中，只能有一个起点和一个终点；四、作业顺序的表示规则表示a、

3、b都完成之后才能开始d作业。表示a、b、c都完成之后才能开始d作业。五、交叉作业表示法 例：有三件相同产品，经过a作业后才能进行b作业，有两种作业安排法（第二种称为交叉作业）六、虚作业使用规则：不得已才用虚作业，不可滥用；七、 “暗桥”、“断线”规则：尽量不用作业交叉，当作业交叉不可避免时，采用“暗桥”、“断线”）；6.1.3 网络图的绘制步骤一、任务分解：把工程分解成若干作业，确定它们之间的关系，并列成任务清单。 二、画图：从第一个作业开始，从左到右，按顺序画三、编号：将结点编号，从左至右，从小号到大号（可跳号，不必连续号），不得重复。6.1.4 作业时间的确定一、一时估计法：针对确定性问题

4、，有同类作业所需时间的资料作为参考，依据经验估计时间值 t ( i , j )。二、三时估计法：针对非确定性问题，无可靠的资料和经验来估计单一的时间，此时估计时间 tm( i , j ) = (a+4c+b)/6 a为乐观时间；b为悲观时间；c为最可能时间三、平均值法：一个任务进行过多次，它们的时间分别为a1、a2、an，则估计的时间 a = (a1+a2+an)/n6.2 网络图的参数与计算6.2.1 结点的时间参数与计算一、结点的最早开始时间 tE( j ) 等于从始点到本结点的最长线路的时间。 始点结点的最早开始时间等于零： tE( 1 ) = 0（1）若结点 j 只有一条箭线进入（如下

5、图），则： tE( j ) = tE( i )+ t (i , j)jit (i , j)（2）若结点 j 有多条箭线进入（如下图），则： tE( j ) = max tE( ik ) + t(ik , j) k = 1,2,mji1t (i1 , j)i2imt (im , j)二、结点的最迟完成时间 tL( i ) 指这个结点最迟必须结束的时间。 终点结点（n）的最迟完成时间为： tL( n ) = 总工期 通常令： tL( n )= tE( n ) （1）若结点 i 只有一条箭尾伸出（如下图），则： tL( i )= tL( j ) - t (i , j)jit (i , j)（2）若结

6、点i 有多条箭尾伸出（如下图），则：tL( i ) = min tL( jk ) t (i , jk) k = 1,mij1t (i , j1)j2jmt (i , jm)三、结点的时差 S( i ) 是指结点的最迟完成时间减去其最早开始时间。 S( i ) = tL( i ) - tE( i )itE( i )tL( i )S ( i )6.2.2 作业的时间参数与计算一、作业的最早开始时间 tES( i , j ) 一个作业必须等它前面的作业完工之后才能开始，这个时间称为作业的最早开始时间。 有两种计算方法计算tES( i , j )。 第一种计算方法：jh1t (h1 , i)ih2hm

7、t (hm , i)第二种计算方法： tES( i , j ) = tE( i )jit (i , j)二、作业的最早完成时间 tEF( i , j ) 一个作业的最早完成时间，就是它的最早开始时间加上本作业的时间。 有两种方法计算： （1） tEF( i , j ) = tES( i , j ) + t (i , j) （2） tEF( i , j ) = tE( i ) + t (i , j) jit (i , j)三、作业的最迟开始时间tLS( i , j ) 为了不影响后续作业的如期开始，每个作业应有一个最迟必须开始时间，称为作业的最迟开始时间。 有两种方法计算tLS( i , j )

8、 。第一种计算方法：jh1t (i , j)ih2hm第二种方法： tLS( i , j ) = tL( j ) t ( i , j )jit (i , j)四、作业的最迟完成时间tLF( i , j ) 一个作业的最迟完成时间等于它的最迟开始时间加上本作业的时间。 有两种计算方法： （1） tLF( i , j ) = tLS( i , j ) + t ( i , j ) （2） tLF( i , j ) = tL( j )jit (i , j)五、作业的总时差 R( i , j ) R( i , j ) = tLF( i , j ) - tEF( i , j )还有两种计算总时差的方法：

9、(1) R( i , j ) = tLS( i , j ) - tES( i , j )因tLS( i , j ) = tL( j ) -t ( i , j )，且 tES( i , j )= tE( i ),故 (2) R( i , j ) = tL( j ) - tE( i ) - t ( i , j )jit (i , j)jit (i , j)当R( i , j ) = 0 时，作业（i , j）为“关键作业”。当R( i , j ) 0 时，可进行“时差的调用”。六、作业的单时差 r( i , j ) 指在不影响后续作业（ j , h ）的最早开始时间tES( j , h )的前提下

10、，作业（ i , j ）可以自由地利用的机动时间范围。 r( i , j ) = tES( j , h ) - tEF( i , j )因tES( j , h ) = tE( j ) ,且tEF( i , j )= tE( i )+t ( i , j ) ，故 r( i , j ) = tE( j ) - tE( i ) - t ( i , j ) jih6.2.3 关键路线与时差的关系关键结点：时差为零的结点。关键路线：从始点到终点，沿箭头方向把总时差为零的作业连接起来形成的线路。 关键线路可以有多条。要想缩短整个项目工期，必须缩短关键路线上的作业时间。关键作业：总时差为零的作业。定理1 在

11、tL(n)=tE(n)的前提下，网络图上所有各项作业均有0 r( i , j ) R( i , j )，当 j 为关键结点时，r( i , j ) = R( i , j )。定理2 在关键路线上全部结点时差为零，反之不真。定理3 在关键路线上全部作业的总时差为零，反之亦真。 非关键路线上各项作业的时差不全为零，具有潜力可挖。 系统网络技术的精华在于根据网络图找出关键路线，利用非关键路线上作业的时差，调用其中的人力、物力、财力去支援和保证关键路线的执行，使关键路线能按期或提前完成。时差调用应先调用单时差，因为它是自由时差。一、图上计算法（1）计算结点的最早开始时间tE( j )：从始点开始，自左

12、向右逐点进行计算，结果填入正方形符号中。（2）计算结点的最迟完成时间tL( i )：从终点开始，自右向左逐点进行计算，结果填入三角形符号中。（3）计算作业的总时差R( i , j )： 结果填入 中。可以形象化地表示为： = j -i - t (i , j) （4）计算作业的单时差r( i , j )：结果填入（ ）中。可以形象化地表示为： （ ）= j - i - t (i , j) （5）将总时差为零的作业连接成关键路线。6.2.4 网络图参数的计算方法例：网络图如下，用图上计算法计算网络图参数。解：二、表格计算法步骤1：作表格，如下。步骤2：填表格第1、2列，如下。253223524步骤

13、3：在表上计算如下参数（1）作业最早开始时间和最早完成时间（3、4列）；（2）作业最迟开始时间和最迟完成时间（5、6列）；（3）作业的总时差和单时差（7、8列）；（4）标出关键作业（第9列）。第3列：最早开始时间（从表格上方向下求 ）第5列：最迟开始时间（从表格下方向上求）注：无后续作业时，tLS (i , j)工期t (i , j)第8列：单时差任一后续作业的第3列当前作业的第4列注：无后续作业时，r( i , j )工期当前作业的第4列其中：工期：指向终点的所有作业的最早完成时间的最大值例：网络图如下，用表格计算法计算网络图参数。解：6.3 工程按期完成的概率分析与计算6.3.1 工程完成

14、时间近似符合正态分布规律中心极限定理结点的完工时间符合正态分布根据作业预计完工时间的平均值与方差整个工程按期完成的概率估算假定一、平均值 tm( i , j ) = (a+4c+b)/6 （三时估计法）二、离差与方差 作业时间的标准离差：= (b-a)/6 方差： 2 = (b-a)/62三、工程完成时间 工程完成时间的平均值: J为工程的关键路线上关键作业数； 工程完成时间的标准离差：cpcp为关键结点的标准离差6.3.2 工程按期完成的概率计算一、计算方法 引入概率因子z，以便于查正态分布表： z = (tL tE)/cp tL为结点最迟完成时间；tE为结点最早开始时间 cp也称为关键路线

15、上方差之和的平方根： 若已规定工程计划完成时间为tS，则取 tL = tS，最后用计算出的z值查正态分布表，得到概率。二、应用举例 例： 某工程网络图如下，(1)计算工程在20天完成的可能性。(2)如完成的可能性要求94.5%，工程应规定为多少天？（作业上方为a-c-b值）解： （1） 先求tm( i , j ) ， tm( i , j ) = (a+4c+b)/6 ；计算每个作业的tm，标在作业线的下面； （2） 计算各结点最早开始时间tE和最迟完成时间tL，有tE(7)=19天； （3） 当工程规定完工时间tS=20天时，取 tL= tS = 20 而关键路线上的方差e2： (8-3)/6

16、2=25/36; (14-6)/62=64/36; (10-5)/62=25/36；概率因子z: 查表得值为0.2977，则概率P=1-0.2977=0.7023, 即20天完成的可能性为70.23%（4）如要求按时完成的可能性为94.5%，由公式：有： tL = tE + zcp = 19 + z1.8当 1-P = 1-0.945 = 0.055 时，查表有 z1.6所以，tL = 19+1.61.8 = 22 天查表6.4 网络图的调整与优化网络图调整与优化的主要内容：（1）缩短网络计划的工期；（2）工期不变，使需要的资源最少；（3）降低人力使用高峰或资源需要量高峰;（4）缩短工期，并使

17、费用增加最少。6.4.1 缩短网络计划工期缩短计划工期，通常采取以下方法：（1）在关键路线上寻找最有利的作业来缩短时间；（2）在可能条件下采取平行或交叉作业缩短工期；（3）采取新技术、新工艺、技术改造，增加人力和设备；（4）利用时差，从非关键路线上抽调适当人力、物力支援关键作业。6.4.1 缩短网络计划工期 例： 某工程网络图初始方案计划时间为19周，现上级规定完工期为16周，试对网络进行调整。 首先将终点的最迟完成时间定为16周，然后采取倒退算法，重新求出各结点的tL和作业的时差：由图可知，需要缩短日期的线路和作业有： 线路 时差（1）12 3 5 9 10 3（2）2 4 7 8 9 2（

18、3）7 9 1 考虑在线路1-2-3-5-9-10上缩短3周，根据具体情况选择作业来缩短，假定2-3、3-5、9-10作业各缩短1周，结果如下：此时，有负时差的线路为：1-2-4-7-8-9-10。 现将2-4作业缩短1周，重新调整网络图，得到： 结果全部消灭了负时差，有2条关键路线：1-2-4-7-8-9-10和1-2-3-5-9-10，工期为16周，符合上级要求。6.4.2 网络执行过程中的检查与调整 计划的网络图制定好之后，并不一定能按原计划顺利实现，因为在执行过程中可能遇到意外情况。一、对关键路线上各作业的检查与调整 关键作业的缩短或延长都会影响总工期，所以重点首先分析关键作业。二、对

19、非关键路线上各作业的检查与调整 非关键作业延长的时间如果超过了可利用的时差，可能产生新的关键路线，要对其进行适当的调整。三、检查网络编号，调整网络逻辑关系 当执行过程中需要增加作业时，需要检查网络编号，重新计算关键路线和总工期。下图中，b图在a图的基础上增加了E作业，并采用了预留的空号13。 例：某工程开工第10周检查进度，得到：2-3作业完成33%，剩余2周；2-4作业完成15%，剩余6周；2-5作业完成12.5%，剩余7周。问题出在哪里? 如何调整网络图? 将检查结果绘成网络图，增加新的结点b,c,d (当前检查点)。重新计算网络图参数如下：得到工程总工期为26周，超3周，并出现负值总时差

20、。 为消除负时差，在总时差为-3的路线上，将d-5作业由7周改为5周，6-7作业由4周改为3周。重新计算参数，达到规定的总工期23周，消除了负值总时差，出现两条关键路线。6.4.3 “时间资源”优化 “时间资源”优化：在一定资源条件下，寻求最短工期，或者在一定工期的条件下，使投入的资源量最少。 资源有两种： （1）仅限于某一项工作使用的资源，如特殊设备； （2）同时开展的多项工作所需的资源，如劳动力。第二种资源的调整原则： （1）优先保证关键作业和时差较小的作业对该资源的需要； （2）充分利用时差，错开各作业的开工时间； （3）在技术允许下适当延长作业的完工期，减少所需资源； （4）对有限资源

21、的运用，不仅需要考虑供应数量的限制，还应考虑供应的平稳。 例：某工程各项作业所需时间、人数如下，试进行人力资源优化。 该工程的网络图如下： 其横条进度计划和人数的需要量曲线如下（空白条形为时差）。由图可知，每天人数需要量很不均匀。 要合理运用时差，错开某些作业的开工时间，达到人员均衡使用。如，将a作业推迟7天开工，d、e作业各推迟2天开工，平衡的结果如下： 另一种做法，将a作业推迟7天开工，b、e作业各推迟2天开工，平衡的结果如下： 为什么原网络计划图上作业b并没有时差可利用，但第二种做法却可以将作业b推迟2天开工？6.4.4 日历计划网络图的绘制日历计划网络图：指带有时间坐标的计划网络图。例：试将下图改为日历计划网络图对应的日历计划网络图如下：日历计划网络图中： （1）垂直线不占用时间； （2）波浪线表示时差； （3）虚作业仍以虚箭杆表示； （4）作业与时差的时间长短与图