关键路径法（CPM）,CPM（Critical Path Method）的基本思想：用网络图表示一个系统或一个工程的计划，分析各个工序或过程在网络中的地位，通过计算找出网络中的关键工序和关键路径。 一个网络中，完成各道工序需时最长的路线，叫做关键路径；关键路线上的工序叫关键工序。,网络图的构成,网络图由节点、弧（箭线）构成； 节点表示工序的开始或结束，起点和终点是两个特殊的节点； 弧表示工程或计划进行过程中所消耗的资源和时间； 箭尾表示工序的开始，箭头表示工序的结束；箭头所指工序是箭尾所指工序的紧后工序，箭尾所指工序是箭头所指工序紧前工序。 虚工序：有的工序之间有顺序关系，实际上并不存在而虚设的工序。虚工序不需要人力、物力等资源和时间，只是表示工序的关系。如下图：,网络图的构成,1、作业（工序）泛指一项需要消耗人力、物力、时间的具体活动。它在网络图中用箭杆“ ”表示。是网络的“边”。,2、事项（结点）是作业开始或完工的瞬间阶段点，它不耗人、物、时，在图中是前后箭杆的连接点，用“ i ”表示 并编上序号。是网络的“顶点”。,3、线路 沿箭杆方向顺序地连接起、终点事项的通路称为线路。“路长”是指一条线路上各作业的时间之和。“关键线路”(CP)是指网络图中，路长最长的线路。,绘制网络图的规则,1、网络图中不允许出现缺口（是连通图）和循环回路； 2、网络中的节点编号不能重复使用，但可以跳跃编号； 3、不允许出现编号相同的箭杆，既两个节点之间只能有一条弧； 4、网络图中只能有一个起点和一个终点； 5、网络图要简明、整齐、清晰。,网络图的绘制步骤,任务分解：把一项任务或一个工程分解成若干作业，并确定作业间的关系。列成表格形式的任务清单，标明作业的名称、代号、顺序及所需时间等。 画图：从第一道作业开始，依照任务清单确定的作业顺序一支箭杆接一支箭杆地从左至右画下去，直到最后一道作业为止，并在箭杆与箭杆的分界处画一个圆圈作为事项。 编号：从起点开始，从左至右，从小至大，到终点为止，依次编号，并且不得出现重复的编号。,网络图例1,热力管道维修任务清单,作业代号 作业名称 先行作业 作业时间（天）,A B C D E F G H,勘查设计 搭架拆旧管 制新管及零件 制新阀 安装新管 焊接新管 装新阀 保温,A A A B，C E D，E F，G,3 2 5 3 2 2 1 1,网络图例1,1,2,4,5,6,7,8,A 3,B 2,C 5,D 3,E 2,F 2,G 1,H 1,3,网络图例2,研制新产品工程的各个工序与所需时间以及它们之间的相互关系如下。网络图是一个加权有向网络。,网络图例2,关键路线,路线：在网络图中，从始点开始，按照各个工序的顺序，连续不断地到达终点的一条通路。 关键路线：完成各个工序所需时间最长的路线称为关键路线。 关键工序：组成关键路线的工序称为关键工序。,关键路线的计算,路线3为关键路线。 缩短关键工序所需的时间，就可以缩短工程的完工时间。关键路线也称主要矛盾线。,网络图的参数与计算,事项（结点）的时间参数三个 节点的最早时间 tE(j)； 节点的最迟时间 tL(i)； 节点的时差 S(i)。 作业的时间参数六个 作业的最早开始时间 tES (i, j)； 作业的最早完成时间 tEF (i, j)； 作业的最迟完成时间 tLF (i, j)； 作业的最迟开始时间 tLE (i, j)； 作业的总时差： R (i, j)； 作业的单时差： r (i, j).,节点的最早时间,节点的最早时间是指从起点到本结点 j 的最长时间之和，在此之前是不能开始的。 规定起点： tE(1)=0； 其它节点：,节点的最迟时间,节点的最迟时间是指结点 i 最迟必须完成（结束）的时间，否则将影响它的后续作业的按时开工。 规定结束点：tL(n) = 任务的总工期； 或者：tL(n) = tE(n) ； 其它节点：,节点的时差,节点的时差为结点的最迟时间减去最早时间。 对任意节点有：,作业的最早开始时间,作业的最早开始时间表示该作业最早什么时候可以开始，显然必须等到它的先行作业完工之后才能开始。 作业的最早开始时间等于起始节点的最早时间，即：,作业的最早完成时间,最早完成时间等于最早开始时间加上作业时间，即：,作业的最迟完成时间,作业最迟完成时间等于终止节点的最迟时间，否则就会耽误下面的作业。所以有：,作业的最迟开始时间,作业的最迟开始时间等于最迟结束时间减去作业时间，即：,作业的总时差,任一作业(i , j )，如果在 tES (i , j)开始，耗费 t (i , j) ，则它一定能在 tEF (i , j)时完成；但作业(i, j )又有一个 tLF(i , j)，它只要不超过 tLF(i , j)而完工，就不会拖延总工期，所以作业 (i , j)的安排具有一定的回旋余地，我们将此称为作业的总时差：R(i,j)。 由定义我们可知作业的总时差可以由下两式中的任一个计算：,总时差的示意图,总时差的含义,当 R (i , j) = 0 时，称此作业 (i , j) 为“关键作业”。 当 R (i , j) 0 时，作业 (i , j) 可作如下两种机动，即其“时差调用”有两种方式： 可以适当推迟其开工时间（只要不超过其最迟开工时间）； 可以适当放慢进度，延长其作业时间，只要延长的时间不超过R(i , j)。 可见，R (i , j) 的大小表明作业 (i , j) 具有的潜力，调用时差就是挖掘该作业具有的潜力，即人力、物力和时间的潜力。 设时差调用量为(i , j) ，则调用原则为：(i , j) R (i , j) 。,作业的单时差,在调用时差时，只要满足 (i , j) R (i , j) ，整个任务的总工期就不会拖延，但对后续作业 (j , k) 来说，会出现以下两种情况： 受到干扰，无法在 tES(j ,k) 开始下面的工序； 不受干扰，可以在tES(j ,k)开始下面的工序。 因此，可定义 r (i , j)为在不影响后续作业的最早开始时间的前提下，本作业 (i , j) 可以自由利用的机动时间范围。即：,单时差和总时差示意图,关键路线及其含义,关键结点（事项）网络图中，时差为零的结点（事项） 关键作业 网络图中，总时差为零的作业； 关键路线 网络图中，从起点到终点，由关键作业连成的通路称为关键路线。关键路线上的工序都是关键工序。 网络分析的根本任务之一就是找出关键路线(CP)，华罗庚先生称它为主要矛盾线；二是找出非关键路线各工序的时差；三是利用“向关键路线要时间，向非关键路线要资源”的指导思想，做出最优或满意的工程计划。,寻找关键路线,定理1：在CP上，全部结点的时差为零，反之不真。 这个定理给出了关键路线的必要条件，但是不充分。这个定理只是提供确定CP的必要条件，而非充分必要条件。 定理2：在CP上，全部作业的总时差均为零，反之亦真。 定理2为我们在网络图中寻找和确定CP提供一个正确的也是唯一的方法。 一张网络图中，CP 可能有多条，CP越多，表明各项作业的周期都很紧张。要缩短总工期，必须从CP上想办法，减少CP上的作业时间，因为CP上的作业时间之和决定了总工期。,完成网络图例,时间单位：天,已知某工程的工序和前后关系如下表：,完成网络图例,画出网络图，以及工序名称和所需时间。,完成网络图例,计算节点的最早时间tE； tE(1)=0； 表示在图中，写在 里。 计算节点的最迟时间tL； tL(n) = 任务的总工期，或者tL(n) = tE(n) ； 表示在图中，写在 里,完成网络图例,完成网络图例,计算 R( i , j)，写在 里； 计算r( i , j)，写在( )里.,完成网络图例,完成网络图例,将R( i , j)0的作业全部加粗或用红线串联起来形成通路，就得到CP为：,完成网络图例,网络优化的方法,时间优化 采取技术措施，缩短关键工序的作业时间； 采取组织措施，充分利用非关键工序的总时差，合理调配技术力量及人力、财力、物力等资源，缩短关键工序的作业时间； 时间资源优化 优先安排关键工序； 利用非关键工序的总时差，错开各工序的开始时间，拉平资源需要量的高峰。 综合考虑各方面的因素，确实达不到，可以适当的推迟工期。 时间费用优化,时间资源优化,某工程工序一览表如下，每天只有13人上班，计划10天内完成，试合理安排生产。,时间资源优化,画出网络图，初步分析,工程所需工作日：313+15 +28 +32 +46 +112 +55=127 10天内完成，则平均每天所需人力12.7 现有人力13 人，适当安排各工序的开工和完工，10天有可能完成工程。,时间资源优化,时间资源优化,