应用运筹学-8- 网络计划- 2015

第五章网络计划 网络图 时间参数的计算 网络计划的优化关键路线法，CPM(criticalpathmethod)计划评审法，PERT(programevaluation&reviewtechnique)统筹法的基本原理从需要管理的任务的总进度着眼，以任务中各工作所需的工时为时间因素，按工作的先后顺序和相互关系作出网络图，以反映任务全貌，实现管理过程的模型化。进行时间参数计算，找出计划中的关键工作和关键路线，对任务的各项工作所需的人、财、物通过改善网络计划作出合理安排，得到最优方案并付诸实施。对各种评价指标进行定量分析，在计划实施过程中，进行有效的监督与控制，以保证任务优质优量地完成。简介项目：一系列特定的能自行控制的工作，有明确的起始与结束时间。项目管理：计划、组织和控制资源（人员、设备和物料），使其满足项目的技术、成本和时间等要求。项目控制报告机制：项目进展的信息收集处理系统。甘特图、成本分解图、时间进度表…组织机制：项目的组织形式。组织结构（职能、矩阵）、项目经理、…项目管理背景网络计划制定的条件组成项目的各项活动都可以作为实体加以识别（有清晰的开始和结束时间，相互独立）项目活动序列的关系可以被确定和网络化存在资源调整的可能性网络计划的编制工程任务分析（工序划分、关系及时间估计）绘制网络图形（实、虚箭线、节点、线路）计算时间参数（最早、最晚开始与结束时间）确定关键路线（总时差为零的工序为最长路线）网络优化调整（工期、时间－费用、资源分析）项目网络计划网络图的构成实箭线：表示一道具体的工序。箭头方向表示工序进行方向，箭尾位置表示工序开始，箭头位置表示工序结束。虚箭线：表示一道虚工序，虚工序仅仅表示工序与工序之间的关联关系，不需要消耗时间和资源。工序名称或代码工序时间工序名称或代码网络图绘制1网络图的构成节点：又称事项、事件等。表示一个工序的开始或结束。用圆圈表示，在圈内注上该节点的序号。整个网络图的开始事项称起始节点，最后工序结束事项为结束节点。只有当某一节点的所有紧前工序都完成后，它的紧后工序才能开始.（A是B的紧前工序，B是A的紧后工序）路线：从起始节点沿箭头方向连续不断地到达终点的通路。路线有多条，路线的长度为各工序的时间和，最长的为关键路线。23AB网络图绘制绘制网络图的准备工作确定目标：以时间要求还是资源费用要求为主工程分解：列出全部分解后的工序及代号清单工序关系：确定每一道工序的紧前工序是哪些工序时间：确定每一道工序的完成所需的时间一时估计法：仅估计一个完成工序的最大时间D三时估计法：乐观时间a、悲观时间b、最可能时间m网络图绘制网络图绘制规则方向、时序与节点编号

网络图是有向图，按流程的顺序，规定工序从左向右排列。网络图中的各个节点都有一个时间（某一个或若干个工序开始或结束时间），一般按节点的时间顺序编号（从左到右，从上到下），箭尾节点编号应小于箭头节点编号。始节点编号为1。网络图中不能出现缺口和回路二个节点之间只能有一个直接的工序

两条箭线不能有同样的始末节点，若二个事项之间有几个平行进行的工序，不许直接连接，而需要引入虚工序。

网络图绘制网络图绘制规则平行作业

有几个工序平行作业结束后转入下一个工序的情况下，考虑到计算网络时间的方便，选择在平行作业的几个工序中所需时间最长的一个工序，直接与其紧后工序衔接，而其它工序则通过虚工序与其紧后工序衔接。交叉作业

对需要较长时间才能完成的一些工序，在工艺流程与生产组织条件允许的情况下，可以不必等待工序全部结束后再转入其紧后工序，而是分期分批的转入。分批转入时需增加虚工序。网络图绘制网络图绘制规则始点和终点

为表示工程的开始和结束，在网络图中只能有一个始点和一个终点。当工程开始时有几个平行工序或结束时有几个平行工序，而又不能用一个始节点或一个终节点表示时，需用虚工序把它们与始节点或终节点连接。网络图布局

尽可能将关键线路布置在中心位置，尽量将联系紧密的工作布置在相近的位置；尽量用水平线或具有一段水平线的折线。网络图绘制6554虚工序应用12AB321ABDCB4A213网络图绘制虚工序应用12AB321ABDCBA5213546DCBA2143网络图绘制13212A12435A3A2A1444BBA:修路基B:铺轨道A=A1+A2+A3B=B1+B2+B31212178642A1B2B1A3A2B35364312A1B2B1A3A2B35网络图绘制例5.1某化工厂管道安装的工程进度表:网络图绘制例5.1某化工厂管道安装的网络图先画出没有紧前工序的工作A,在A后画出紧前工序为A的各工作,即B,C,E,F。ABCEF网络图绘制例5.1网络图的绘制在表中查出B,C为D的紧前工序，F为G的紧前工序，则在F工序后画出G，在B,C工序后面画出D。GDABCEF网络图绘制例5.1网络图的绘制画出H,I,J的工序如下：ABCEFGDHIJH紧前：D、E、GI紧前：D、EJ紧前：H、IH除J外已没有紧后工序网络图绘制例5.1网络图的绘制画出K,L工序，K,L的紧前工序均为J。ABCEFGDHIJLK网络图绘制例5.1网络图的绘制在K,L后画出M,N,P：ABCEFGDHIJLKNMPM紧前：K、LN紧前：KP紧前：M、N网络图绘制练习：画出以下网络图网络图绘制练习答案：15387642AHELKGDFCB60451810204015302535网络图绘制符号约定

iE(i)L(i)S(i)jE(j)L(j)S(j)KD(i,j)LFijEFijLSijESijE(1)=0L(j)E(j)L(n)=E(n)SijRij时间参数计算节点（事项）时间

节点本身不占用时间，它只表示某项工作应在某一时刻开始或结束，因此，节点参数主要只有两个：最早实现时间（最早时间）和最迟实现时间（最迟时间）。最早时间：以该节点结束的工作最早可能结束的时间，或以该节点开始的工作最早可能开始的时间。E(1)=0,E(n)为工程时间，从左往右计算。最迟时间：允许所有后续工序都能及时开始的最晚时间。L(n)=E(n),L(1)=0，从右往左计算。时间参数计算节点（事项）时间计算节点最早时间E(j)的计算E(1)=0E(j)=max[E(i)+D(i,j)],i=2,3,4,……98767E(7)=5E(8)=6E(9)=MAX[E(7)+6,E(8)+7)]=13时间参数计算节点（事项）时间计算节点最迟时间L(i)的计算L(n)=E(n)L(i)=MIN[L(j)-D(i,j)],j=n-1,n-2,……911102012L(10)=70L(11)=89L(9)=MIM[L(10)-20,L(11)-12)]=50时间参数计算543561267243EDCBAF1点的开始时刻为0；2点的最早时间为2；3点的最早时间为5；4点的最早时间为6；5点的最早时间为12；6点的最早时间为19；6点的最迟时间为19；5点的最迟时间为12；3点的最迟时间为7；4点的最迟时间为6；2点的最迟时间为2；1点的最迟时间为0。

00

22

1212

5

7

191966例5.2节点时间计算工序时间参数计算

一个工序可以从箭尾节点的最早时间开始作业，也可以适当推迟开始，但须在箭头节点的最迟时间内完工才不至于延误后续工序，因此工序时间就包括最早开始时间和最迟开始时间，加上或减去该工序的作业时间，相应地还有最早结束时间和最迟结束时间。最早开始时间:ESij=E(i)最早结束时间：EFij=ESij+D(i,j)最迟结束时间：LFij=L(j)最迟开始时间：LSij=LFij-D(i,j)时间参数计算时差及计算节点时差：最迟与最早时间差

S(i)=L(i)－E(i)工序总时差：不影响工期(最早结束时间）的该工序可松动的时间（可以推迟开始的时间）.Sij=LSij－ESij=LFij－EFij

=L(j)－E(i)－D(i,j)（总浮动）工序单时差：不影响紧后工序最早可能开始条件下，工序最早可能完工时间可以推迟的时间.Rij=E(j)－EFij（自由浮动）时间参数计算工序及时差关系工序AES工序A的紧后工序ESEFLFLFEFLSLS总时差SA单时差RA(自由浮动)D时间参数计算关键线路关键线路的长度决定了工程周期，关键线路可以有多条，计划安排得越紧凑，关键线路越多。关键线路的确定破“圈”法：在“圈”中去掉最短的一个工序。图上作业法：标注节点时间，通常情况下，节点时差为0的节点组成关键线路。表上作业法：计算工序时间，总时差为0的工序组成关键线路。线性规划法：最大允许时间法和影子价格法关键线路的确定破圈法：15387642AHELKGDFCB60451810204015302535关键线路A-D-G-K-L(1-2-4-6-7-8),长度为170例5.4关键线路的确定图上标注法15387642AHELKGDFCB60451810204015302535060708010011013517017013511012080117600关键线路的确定表上作业法关键线路的确定参照最短路径的方法，假设网络图中的总流量为1，将每个工序的作业时间作为单位流量费用，求这一个流量通过网络的最大费用，所经过的弧即为关键工序，按顺序连在一起即为关键路径，求得的最大费用（最长距离）即为项目的最早完工时间。根据各个节点的净流量条件，目标为总经过的时间最长。线性规划法求关键线路(1)15387642AHELKGDFCB60451810204015302535例5.4线性规划法确定关键线路例5.4：设fij表示通过节点(i,j)的流量，根据题意求关键线路的线性规划模型(1)画出网络图例5.4决策变量：各节点的发生时间（项目起始时刻为0，节点的最早时间）；目标函数：最后一个节点的发生（完成）时间最早；约束条件：各个活动的实际持续时间应不小于完成活动所需时间；某活动实际持续时间＝某活动结束时间－开始时间线性规划法求关键线路(2)例5.4：设xi表示通过节点i的最早时间，根据题意求关键线路的线性规划模型(2)建立活动--节点矩阵，对任一节点，箭头进入为+1，箭头流出为-1。利用该矩阵元素与相应变量之间的乘积和计算各工序的时间。关键线路判断：作业时间影子价格为1的工序（为什么？）或实际持续时间与完成活动所需时间相等的工序为关键线路上的工序。线性规划法求关键线路(2)线性规划方法求关键线路举例网络图的调整及优化缩短工程计划工期问题

保证质量和不增加人力物力的前提下尽量缩短工期。注意关键线路的变化。压缩关键工序的工序时间

在关键工序上采取改进技术、工艺和设备等措施，优先保证关键工序所需，矛盾时非关键线路应尽可能让路。在非关键工序上尽量挖掘潜力

利用非关键线路上的时差进行合理调度，抽调资源支援关键线路。采用平行或交叉作业例5.5缩短计划工期某工程有关的工序关系及时间如下：例5.5缩短计划工期画出网络图：153109742ALDMJFCHB264354524386GE1例5.5缩短计划工期计算时间参数，确定关键线路：153109742ALDMJFCHB264354524386GE10182576119915181510101198520关键线路A-B-E-H-M(1-2-3-6-9-10),长度为18例5.5缩短计划工期现要求将整个计划工期缩短3天。首先从关键线路上想办法，能否缩短3天？也要考虑其它非关键线路上工时缩短的情况。具体做法如下：将图中的最后一个节点的最迟时间设定为15倒退计算法求出各工作的时差找出所有时差为负值的工序对其中的关键工序进行协调，缩短工作时间，使总时间为15天重新计算时间，如仍有负时差工序，再考虑缩短该工序的时间，直到没有负时差为止。例5.5缩短计划工期将第10节点的最迟时间设定为15，计算各工序时差153109742ALDMJFCHB264354524386GE101525761199151812778652－1－3-3-2-1-30-2-30-2-3-31515例5.5缩短计划工期从图中可以看出：在原关键线路上各工序的总时差均为－3，因此需要在原来的关键线路上缩短3天。除了原先关键线路上是负时差外，在其它非关键线路上也出现负时差，在这些线路上也要进行日期的缩短。共有以下几条需要缩短：第一条：1－2－3－6－9－10缩短3天第二条：2－4－7－8－9缩短2天第三条：7－9缩短1天必须满足以上条件才有可能缩短3天例5.5缩短计划工期先考虑关键线路缩短3天，经协调使B、M、E各减1天；B和M工序各缩短为2天；E工序缩短为5天重新计算时间例5.5缩短计划工期关键路线工序时间缩短后，重新计算时间：153109742ALDMJFCHB26425452438