运筹学第九章网络计划

网络计划,大型项目的开发涉及很复杂的项目协调和管理问题，为 使项目管理人员对项目进度有全面的了解，进行有效的 控制，必须使用科学的管理方法.,20世纪50年代以来，国外陆续出现了一些计划管理的新 方法，如关键路径法(critical path method 缩写为CPM)， 计划评审方法（program evaluation 2 计算项目的最早、最晚完成和开工时间 (网络计算) ; 3 寻找关键活动和关键路径(网络分析); 4 根据以上分析对网络进行优化。,网络计划,网络图 时间参数的计算 网络计划的优化 实施计划的管理,【例】（华罗庚：统筹方法平话及补充）某家庭有夫妇两人安排家务，要求从上午11：30开始到下午2：00结束去上班，做下例3件事：,工序 工时 代号 洗衣 3小时 A 烧饭 1小时 B 吃饭 0.5小时 C,怎样安排，使完成时间最短？,4.5,3.5,第一节 网络图,复杂工程项目可被分解为一系列小的事件或活动，各种事 件和活动之间的逻辑顺序可以表述为一个由一系列弧和节 点组成的网络图,网络图又称箭头图，由有向弧和节点组成。,有向弧,节点,工作（或工序、活动） 活动完成需要的时间写在弧上；,事件 (或事项) 表示活动的开始与结束, 每个节点有唯一节点号；,例如某工作a可表示为：,a,5,表示工作a(1,2),数字5表示为完成本工作需要的时间,事项1，2表示工作a的开始和结束,虚工作用虚箭头“”表示。它表示工时为零，不消耗任何资源的虚构工作。其作用只是为了正确表示工作的前行后续关系。,紧前工序 紧接某项工序的先行工序,紧后工序 紧接某项工序的后续工序,前道工序 某工序之前的所有工序,后续工序 某工序之后的所有工序,网络图的其他概念：,在下图中，A是D、E的紧前工序，D、E是A的紧后工序，F是A的后续工序但不是A的紧后工序；A是D、E、F的前道工序但不是 F 的紧前工序。,注意紧前工序、紧后工序、前道工序和后续工序之间的关系。,一、画网络图的规则,把表示各个工作的箭线（有向弧）按照先后顺序及逻辑关 系，由左至右排列画成图。再给节点统一编号，节点1表示 整个计划的开始（总开工项），图中最大的数码n表示计划 结束事项（总完工事项），节点由小到大编号，对任一工 作（i, j）来讲，要求j i,在绘制网络图时，还要注意以下规则：,1、网络图只能有一个总起点，一个总终点事项,图中有两个总起点事项；三个总终点事项，不符合规则。,2、网络图是有向图，不允许有回路,图中是回路，不符合规则,3、节点 i, j 之间不允许有两个或两个以上的工作。,4、必须正确表示工作之间的前行、后继关系,如4道工作a,b,c,d的关系为：c必须在a,b均完成后才能 开工，而d只要在b完工后即可开工。如画为上图是错误 的，因本来与a无关的工作d被错误地表示为必须在a完 成后才能开工,5 虚工作的运用,通过运用虚工作的方法，可用将部分不符合规则的网络图改画为正确的形式。,虚工作可以用于正确表示平行工作,虚工作可以用于正确表示交叉工作,有两个总起点事项,三个总终点事项,将网络图更改为正确的形式,节点i, j之间不允许有两个或两个以上的工作,a,b,c,d,如4道工作a,b,c,d的关系为：c必须在a,b均完成后才能开工，而d只要在b完工后即可开工。,虚工作还可以用于正确表示平行工作。一道工作分为几道工作同时进行，称为平行工作。,如下图，市场调研（2，3）需12d,如增加人力分三组同时进行,两件或两件以上的工作交叉进行，称为交叉工作。,如工作A与工作B分别为挖沟和埋管子，那么它们的关系 可以是挖一段埋一段，不必等沟全部挖好再埋。这就可 以用交叉工作来表示，如把这两件工作各分为三段， A=a1+a2+a3, B=b1+b2+b3,则可用下图表示：,小结,遵循上述画图规则是为了保证网络图的正确性，此外为了使图面布局合理、层次分明、条理清楚还要注意画图技巧。 例如：尽量避免箭杆的交叉。如下图所示 注：通常网络图的工作箭杆画成水平方式，以便于阅读和计算。,二、实例 一般绘制网络图可分为四步。我们用一个简单例子来说明。,1、列出所有活动 一个完整的项目必须被分解为一系列独立活动（称为 工序）, 分解程度取决于项目计划的需要以及相应的管 理职能。,2、确定每个活动的紧前工序 项目执行的连续性确定了项目各项活动的前后顺序, 为 了从逻辑上搞清楚活动之间的顺序关系, 需要确定每项 活动可以开始之前必须完成的活动-紧前工序。,在这两步完成后，我们可以得到一个工作项目明细表 如下图：,3 绘制网络图 按照明细表中所示的工作遵循前面的画图规则作出网络图，并在有向弧上标出工时，如下图所示,A,4,D,6,C,3,E,8,F,2,G,3,K,2,B,10,I,8,H,2,J,5,L,1,4 节点编号,编号应注意以下规则 : 每条弧上起点的编号数小于终点的编号数。,A,4,D,6,C,3,E,8,F,2,G,3,K,2,B,10,I,8,H,2,J,5,L,1,1,2,3,4,5,6,7,8,9,10,课堂练习（一）,根据某项目作业明细表的资料，绘制项目网络图,1,2,3,2,5,1,3,2,4,C,F,E,D,B,A,G,H,I,1,2,3,2,5,1,3,2,4,C,F,E,D,B,A,G,H,I,1,2,7,8,9,3,4,5,6,课堂练习（二）,根据某项目作业明细表的资料，绘制项目网络图,a,6,1,b,9,c,13,d,5,e,16,f,12,h,12,g,10,i,8,k,20,j,17,l,25,1,2,3,5,4,6,7,10,8,9,11,三、网络图分类 根据不同指标可分为： 1、确定型与概率型网络图 工作实际完成情况可按预计工时达到（即实现的概率等于或近 于1），称为确定型网络图。（由定额资料或统计资料得到） 工时用最快可能、最可能、最慢可能 完成工时来估计时，称为 概率型（非确定型）网络图。,2、总网络图与多级网络图 总网络图：以整个项目为计划对象，编制网络计划图。供决策领导层使用； 分级网络计划图：这是按不同管理层次的需要，编制的范围大小不同，详细程度不同的网络计划图；供不同管理部门使用。 除此之外，网络图还可以按其他指标进行分类。,计算时间参数的目的： 找出关键路线，为网络计划的优化、调整和执行提供 明确的时间概念。,第二节 时间参数的计算,1,2,3,4,6,7,8,5,4,3,5,2,2,4,2,4,1,3,从始点1到终点8共有4条路线，可分别计算出每条路线所需的总工时。,可以看出第四条路线所需时间最长，它表明整个任务的总完工期（为21周）。很明显，这条线上的工作，若有一个推迟，整个工期就要推迟；若某一工作能提前，整个任务就可以提前完成。,通常把网络图中需时最长的路叫做关键路，关键路上的工作称为关键工作。 要想使任务按期或提前完工，就要在关键路线的关键工作上想办法。,网络图的关键路线可以通过时间参数的计算求得,网络图的时间参数包括： 工作所需时间、事项最早、最迟时间，工作的最早、最迟时间及时差等。,进行时间参数计算不仅可以得到关键路线，确定和控制整个任务在正常进度下的最早完工期，而且在掌握非关键工作基础上可进行人、财、物等资源的合理安排，进行网络计划的优化。,一、作业时间,1、确定型,2、概率型 三点时间估计法 a-最快可能完成时间（最乐观时间） m-最可能完成时间 b-最慢可能完成时间（最悲观时间）,二、事项时间参数,1、事项最早时间,事项 j 的最早时间用 表示，它表明以它为始点的各工作最早可能开始的时间，或表示以它为终点的各工作的最早可能完成时间。,它等于从总开工事项到该事项的最长路线上所有工作的的工时总和。,设总开工事项编号为1,其中 与事项 j 相邻的各紧前事项的最早时间,设终点事项编号为n，则终点事项的最早时间就是整个工程的总最早完工期，即：,举例： 到齐上课，最后到者决定最早开课时间,2、事项最迟时间,事项 i 的最迟时间用 表示，它表明在不影响任务总工期条件下，以它为始点的工作的最迟必须开始时间，或以它为终点的各工作的最迟必须完成时间。,由于一般情况下，我们都把任务的最早完工时间作为任务的总工期，所以事项最迟时间的计算公式为：,其中 与事项 i 相邻的各紧后事项的最迟时间,举例：保证12点吃饭，路最远者决定最迟下课时间,三、工序的时间参数,1、工序(i,j)的最早开工时间（Earliest start time for an activity） 任何一件工作都必须在其所有紧前工作全部完成后才能开始，计算公式为 ：,2、工序(i,j)的最早完工时间（Earliest finish time for an activity）。计算公式为,3、 工序(i,j)的最迟必须开始时间（latest start time for an activity） 是指为了不影响整个工程如期完成的前提下，工序最迟必须开工的时间。 计算公式为 ：,4、 工序(i,j)的最迟必须结束时间(Latest finish time for an activity) 计算公式为,四、时差,工序的时差又叫工序的机动时间或富裕时间。,常用的时差有两种：工序的总时差和工序的单时差,1、工序的总时差或松弛时间(Slack for an activity) 在不影响总工期的条件下， 工序(i, j)可以延迟其开工时间的最大幅度,2、工序的单时差或自由时间(Free for an activity) 在不影响其紧后工序最早可能开工时间的前提下，本工序可以延迟其开工时间的最大幅度,单时差和总时差的联系与区别：,可以看出，总时差不仅包括本工序的单时差，而且包括后续工序的时差。占用一道工序的总时差虽然不影响整个任务的最短工期，却有可能使得后续工序丧失部分或全部的自由机动时间（余地）,4,6,1,2,3,4,5,6,7,9,10,8,3,8,2,3,2,10,0,8,2,5,1,五、时间参数的图上计算法,（1）事项时间参数的计算,0,0,4,4,10,10,18,18,20,20,23,23,31,31,25,26,32,32,23,23,4,6,1,2,3,4,5,6,7,9,8,3,8,2,3,2,10,8,2,5,1,10,0 (0),0 (0),0 (0),11 (11),0 (0),0 (0),0 (0),6 (6),0 (0),1 (0),1 (1),0 (0),（2）工序时间参数的计算,0,0,4,4,10,10,0,13,13 (13),4,15,18,18,20,20,23,29,23,24,23,23,31,31,23,23,25,26,32,32,以下图所示网络图为例。 （1）在图上计算各工序的最早开始和最迟开始时间。 （2）指出项目的关键工序和关键路线。 （3）求项目的完工时间。,a,6,1,11,b,9,c,13,d,5,e,16,f,12,h,12,g,10,i,8,k,20,j,17,l,25,【解】(1)最早开始和最迟开始时间见图,课堂练习,0,0,6,6,19,19,9,9,35,47,47,55,47,19,19,47,72,72,55,52,47,47,52,52,37,47,35,42,19,23,23,6,0,14,(3)工程的完工时间为72天,a,6,1,11,b,9,c,13,d,5,e,16,f,12,h,12,g,10,i,8,k,20,j,17,l,25,0,0,6,6,19,19,9,9,35,47,47,55,47,19,19,47,72,72,55,52,47,47,52,52,37,47,35,42,19,23,23,6,0,14,六、时间参数的表上计算法,在网络图上直接计算时间参数，方法简便直观。但是当工作数目多，图形复杂时容易遗漏和出错，故常常采用表格法,表上计算首先要列出计算用表，注意工作的排序应严格按照箭尾事项编号由小到大的顺序排列，箭尾事项相同的工作，按其箭头事项由小到大排列,4,6,1,2,3,4,5,6,7,9,8,3,8,2,3,2,10,8,2,5,1,10,仍以例1为例：,绘制网络计划图，计算时间参数和确定关键线路，仅 得到一个初始计划方案。 网络计划的核心在于从工期、成本、资源等方面对初 始方案作优化和调整。 目前一般是按照某几个指标，如工期最短，成本最低 等进行优化。,第三节 网络计划的优化,优化的几种方法。 一、把串联工作改为平行工作或平行交叉工作。 二、利用时差。 三、有限资源的合理分配。 四、最低成本日程。,一、把串联工作改为平行工作或平行交叉工作,为了缩短整个任务的完工期，达到时间优化的目标，可以研究关键路线上串联的每一个工作有无可能改为平行或交叉进行的工作，以缩短工期。,二、利用时差,由于网络中的非关键路工作都有时差，所以这些工作在开工时间上，具体工时上都具有一定的弹性。 为了缩短任务的总工期，可以考虑放慢非关键工作的进度，减少这些工作的人力、资源，转去支援关键工作，以使关键工作的工时缩短来达到目的。,三、最低成本日程（时间费用优化）,时间和费用双目标优化，一般来讲二者是矛盾的。通过计算网络计划的不同完工期相应的总费用，以求得成本最低的日程安排就是“最低成本日程”，又称“工期成本”优化。,费用：直接费用和间接费用,直接费用：建造工程本身所需材料、人工等,间接费用：工程所需管理费用、设备租金,直接费用与工作所需工时关系为： 常用成本斜率 表示,其中工作( i, j ) 的正常工时为 ,所需费用为,特急工时为 ,所需费用为,表示了工作( i, j ) 从正常工时每缩短一个单位时间所需增加的费用,下面通过例子说明最低成本日程的计算方法,例 已知网络计划各工作的正常工时、特急工时及 相应费用如表，网络图如下。 设正常工时下，任务总间接费用为18000元，工期每缩短一天，间接费用可节约330元。 求最低成本日程。,24,1,2,3,4,5,6,24,30,22,26,18,18,T(0) = 74,最低成本日常计算步骤: 1 从关键工作中选出缩短工时所需直接费用最少的方案,并确定该方案可能缩短的天数 按照工作的新工时,重新计算网络计划的关键路径 计算由于缩短工时所增加的直接费用,重复上述三个步骤,直到工期不能再缩短为止,分析过程如下所示: 第一次调整,1,2,3,4,5,6,24,30,22,26,18,18,18,24,1,2,3,4,5,6,24,22,26,18,18,18,T(1) = 64,T(1) - T(0) = 10 即关键路径只缩短了10天, 这意味着13没有必要减少12天, 工作(1, 3) 应取 30 10 = 20(天),24,1,2,3,4,5,6,24,22,26,18,18,18,有两条关键路线(如图所示), 此次调整费用为10*100 = 1000(元),T(1) = 64,20,24,第一次调整结束; 重复上述三个步骤,直到工期不能再缩短为止,第二次调整:,1,2,3,4,5,6,24,22,26,18,18,T(1) = 64,20,必须注意两条关键路线应同时缩短,有如下几个方案可选择,所需费用: 100+250=350(元),24,1,2,3,4,5,6,24,22,26,18,18,T(1) = 64,20,必须注意两条关键路线应同时缩短,有如下几个方案可选择,所需费用: 100+200=300(元),24,1,2,3,4,5,6,24,22,26,18,18,T(1) = 64,20,必须注意两条关键路线应同时缩短,有如下几个方案可选择,所需费用: 150+250=400(元),24,1,2,3,4,5,6,24,22,26,18,18,T(1) = 64,20,必须注意两条关键路线应同时缩短,有如下几个方案可选择,所需费用: 150+200=350(元),24,1,2,3,4,5,6,24,22,26,18,18,T(1) = 64,20,取最小方案. 工作(1, 3) 最多可缩短 2 天; 工作(2, 4) 最多可缩短 4 天,取其中小者,即将(1, 3) 与 (2, 4) 的工时分别改为 20 - 2 = 18(天), 22 2 = 20(天),24,1,2,3,4,5,6,24,22,26,18,18,总工期减少为62天 , 这时关键路径仍为两条, 增加直接费用 2 *300 = 600 (元),T(1) = 64,20,将(1, 3) 与 (2, 4) 的工时分别改为 20 - 2 = 18(天), 22 2 = 20(天),1,2,3,4,5,6,24,22,26,18,18,20,18,20,T(2) = 62,24,24,第二次调整结束,下面进行第三次调整,1,2,3,4,5,6,24,20,26,18,18,18,必须注意两条关键路线应同时缩短,有如下几个方案可选择,所需费用: 250+150=400(元),24,1,2,3,4,5,6,24,20,26,18,18,18,必须注意两条关键路线应同时缩短,有如下几个方案可选择,所需费用: 200+150=350(元),24,1,2,3,4,5,6,24,20,26,18,18,18,取最小方案. 工作(2, 4) 最多可缩短 2 天; 工作(3, 4) 最多可缩短 2天,取其中小者,即将(2, 4) 与 (3, 4) 的工时分别改为 20 - 2 = 18(天), 26 2 = 24(天),24,1,2,3,4,5,6,24,20,26,18,18,18,24,即将(2, 4) 与 (3, 4) 的工时分别改为 20 - 2 = 18(天), 26 2 = 24(天),1,2,3,4,5,6,24,20,26,18,18,18,24,18,24,T(3) = 60,总工期减少到60天,关键路径如图所示, 所增加的直接费用为: 2*350=700,第三次调整结束,1,3,5,6,24,18,18,18,24,24,T(3) = 60,2,4,18,该关键路径上的各工作已不能缩短, 计算结束,将全部计算过程及其相应费用-日程变化列于下表:,最低成本日程为 62 天,总成本为63440 元,四、有限资源的合理分配(时间资源优化 ),一项任务的可用资源总是有限的,因此时间计划必须考虑资源问题.,以人力资源为例.如下图所示的网络图,已计算出关键路径为,总工期为 11 天.,1,2,3,5,6,4,9,4,6,2,7,2,5,3,1,4,3,3,4,3,如画出带日程的网络图及资源动态曲线图(资源负荷图),可以看出, 若按每道工序的最早开工时间安排, 人力需求很不均匀, 即使是在人力资源充足的情况下也是很不经济的.,时间资源优化,原则：关键优先、利用时差,方法：绘制资源负荷图，排定关键工序，游移非关键工序,现假定资源有限, 每日可用人力为 10 人 ,下面进行计划调整,希望不延迟或尽量少延迟总工期,具体方法是按资源的日需求量所划分的时间段逐步从始点向终点进行调整.,本例中, 第一个时间段为 0, 2, 需求量为 18人/日, 在调整时要对本时间段内各工作按总时差递增顺序排队编号,工作(1,2) 总时差 0 , 编号为 1# 工作(1,4) 总时差 1 , 编号为 2# 工作(1,6) 总时差 7 , 编号为 3#,对编号小的优先满足资源需求量, 当累计和超过10人时, 未得到人力安排的工作应移入下一时间段考虑,本例中工作(1, 2) 与 (1, 4)人力日需求为9, 而工作(1, 6)需9人/日,所以, 应把(1, 6)移出 0, 2 时间段,接着调整 2, 3 时间段。,在编号时要注意, 如果已进行的非关键工作不允许中断, 则编号要优先考虑, 把它们按照新的总时差与最早开始时间之和的递增顺序排列, 否则同第一阶段的编号规则。,在本例中(1, 4) 为已进行中工作, 假设不允许中断。而(2, 3)为关键工作, (1, 6) 还有时差 5 天, 则编号顺序为:,工作 (1, 4), 总时差 1, 编号为1# 工作 (2, 3), 总时差 0, 编号为2# 工作 (1, 6), 总时差 5, 编号为3#,累加所需人力资源数, 工作(1, 4) 与(2, 3) 共需10人/日, 所以工作(1, 6) 要移出 2, 3 时间段。,如图所示:,以后各时间段类似处理, 经过几次调整, 可得到下图:,此时人力资源需求量已满足不超过10人的限制, 总工期未受影响, 必要时总工期可能会延迟。,注: 由于编号及调整规则只是一种原则, 所以调整结果常常是较好方案, 不一定是工期最短方案。 由于求精确解有时繁难, 网络优化中多采用这类近似算法.,