运筹学课件--第8章网络计划

1、运筹学课件-第8章网络计划2Sub titleOR:SM第8 章 网络计划内容提要第一节 网络图的绘制第二节 关键路线法 结点的时间参数 作业的时间参数 时差与关键路线第三节 计划评审技术第四节 网络计划优化 缩短工程工期 工期-费用优化 工期-资源优化第五节 缓冲时间设置3OR:SMOR:SM第8 章 网络计划教学目标：通过本章的学习，掌握网络图的绘制方法，掌握时间参数的计算方法，并能够找出关键路线；能够对实际的项目进行时间与资源的优化与调整。教学要求：知识要点绘制网络图能力要求（1）了解网络图的基本概念：工序、事件、路线（2） 绘制网络图的规则（3）计算网络图的时间参数（4）找出关键路线（

2、1） 时间优化相关知识4网络计划优化 （2） 费用优化（3） 资源综合优化费用的构成OR:SMOR:SM第8 章 网络计划 网络计划的发展历程关键路线法(Critical Path Method，CPM )计划评审技术(Program Evaluation and Review Technique，PERT )图示评审技术(Graphic Evaluation and Review Technique，GERT )风险评审技术(Venture Evaluation Review Technique，VERT ) 网络计划技术的特性明确表达各项工作的逻辑关系通过时间参数计算，确定关键工作和关键线

3、路掌握机动时间，进行资源合理分配运用计算机辅助手段，调整与控制5OR:SMOR:SM第一节网络图的绘制一、网络计划的图示形式 工序(作业)：一项需要人财物或时间等资源的相对独立的活动过程 在网络图中用箭线“” 表示， 前面直接相连工序称紧前工序， 直接相连的后继工序为紧后工序。 结点(事项)：相邻工序的分界点（每一箭头始端和末端各有一个结点，表示前一个作业的结束和后一个作业的结束，即两个事件。） 一般用圆圈来表示，每个结点编上顺序号， 结点既不消耗人力、物力，也不占用时间。 网络图 由工序、事项及时间参数所构成的有向图即为网络图。 箭线表示工序,结点为工序间相互关系的网络图，称箭线式网络 结点

4、表示工序,箭线为工序间相互关系的网络图，称结点式网络6OR:SMOR:SM第一节网络图的绘制一、网络计划的图示形式1、箭线式网络图N作业名称it作业时间2、结点式网络图j1A22B5C334D5E55iNti作业序号N作业名称t作业时间1225356074355OR:SMOR:SM第一节网络图的绘制二、箭线式网络图的规则 工序表示的规定 一条箭线和它的相关事项只能代表一道工序，不能代表多道工序，两个结点之间只能有一条箭线相连。不允许出现缺口与回路 网络图中只能有一个始点和一个终点，使得自网络图的始点经由任何路径都可以到达终点。虚工序 虚工序是为了表达相邻工序之间的逻辑关系而虚设的工序。 不消耗

5、时间、费用和资源，一般用虚箭线表示。 方向的规定 网络图是有方向的，工序应按工艺流程顺序或工作逻辑关系从左向右排列。 编号的规定 编号应从始结点开始，按照时序依次从小到大对结点编号，直到终结点。 编号时不允许箭头编号小于箭尾编号。8OR:SMOR:SM二、箭线式网络图的规则 箭线不允许出现循环。 图中234就是一个循环。24513 两相邻结点之间只允许有一条箭线相连。作业A和B是两个并行的作业，在计算机系统中，作业A和B均用（1，2）表示，无法区别这两个作业。此时，可借助于虚作业来表示。A1A31B3B2C9OR:SMOR:SM二、箭线式网络图的规则（续）箭头结点的编号（j）要大于箭尾结点的编

6、号（i）。编号可以不连续编。例如：34一个完整的网络图只能有一个起点和一个终点。错误正确 箭线首尾都应有一结点，不能从一箭线中间引出另一箭线。51034OR:SMOR:SM 双代号最早开始时间最早结束时间11i事件序号活动描述工作持续时间双代号网络图的表示方法j事件序号OR:SMOR:SM一、双代号网络图的表示方法双代号网络图的三要素指箭线、节点和线路。A、箭线（指工作、工序、作业、活动）资源、时间和空间资源、时间和空间紧前工作、紧后工作紧前工作、紧后工作和平行工作12OR:SMOR:SM一、双代号网络图的表示方法虚工作表示工作之间的先后逻辑关系，不耗用资源，也不占用时间。符号表示:B、节点：

7、表示工作之间的联系（起始节点，终止节点，中间节点）开始完成i“时点时点”C、线路：线路的长度，即线路所需要的时间。（关键路线总持续时间最长的线路；非关键线路除了关键线路之外的线路。）13OR:SMOR:SM绘制网络图的步骤（双代号） 第一步：找出所有从节点1开始的活动。画出它们结束的节点，并在节点1与他们的每一个结束节点之间画一条箭线。将活动字母代号或名称写在相应的箭线上方，历时估算写在箭线的下方。 第二步：继续从左至右绘制网络图，寻找分叉点与交会点。 第三步：继续绘制网络图，直到图中包括了所有的活动。 双代号网络图中所有的箭头应该指向右方，不应当有箭线交叉。14OR:SMOR:SM第一节网络

8、图的绘制三、箭线式网络图举例某工程的工程一览表工序紧前工序工序时间a-6b-3c-4da4ea,c5fb10gb,d,e84b310f1a62d45g864ce5315OR:SM LOR:SM第二节关键路线法一、结点的时间参数 结点的最早时间tE(j) tE(j)等于从始点开始到本结点的最长路线上各道工序时间之和。等于从始点开始到本结点的最长路线上各道工序时间之和。 从始点事项开始，自左向右，顺着箭线方向逐个计算 。 t E (1) 0 t E ( j ) max t E ( i ) t ( i , j )i 结点的最迟时间 tL(j) 指以该结点为结束的各道工序最迟必须完工的时刻，否则将会影

9、响后续工序按时开工，以至推迟整个工程的完工时间。 从终点开始，从右向左，逆箭线方向逐个计算。 t L ( n ) t E ( n ) t ( i ) min t L ( j ) t ( i , j )j16OR:SMOR:SM第二节一、结点的时间参数关键路线法计算结点时间参数349b310f001a6626d4511g8619194c3e5111766OR:SMOR:SM补充双代号绘图题工作ABCDEF紧前工作-AABCB,C时间432157工作GHIJKL紧前工作DD,FE,FG,HH,IJ,K时间638964要求：画出网络图并计算各节点最早时间和最迟时间18OR:SMOR:SM第二节关键路

10、线法二、作业的时间参数 最早可能开工时间tES(i, j) 一个作业必须在其各紧前作业都完工后才能开工， 作业最早可能开工时间等于其箭尾事项的最早时间。 tES(i, j)= tE(i) 最早可能完工时间 tEF(i, j) 从最早可能开工时间开工，完成本作业的时间 。 tEF(i, j)= tES(i, j) +t(i, j) 最迟必须开工时间 tLS(i, j) 在不影响工程如期完工的前提下，作业最迟必须开工的时刻。 等于它的箭头事项的最迟时间减去本作业的作业时间tLS(i, j)= tL( j) - t(i, j) 最迟必须完工时间 tLF(i, j) 在不影响工程如期完工的前提下，作业

11、最迟必须完工的时刻 。 tLF(i, j)= tLS(i, j) +t(i, j) = tL( j)19OR:SMOR:SM第二节关键路线法三、时差与关键路线 时差又称宽裕时间：不影响如期完成任务的条件下，各道工序可以机动使用的一段时间。总时差R(i, j)：不影响其紧后工序最迟必须开工的前提下，本工序最早可能完工时间可以推迟的时间。 R(i, j)= tLS(i, j) -tES(i, j) = tLF(i, j) -tEF(i, j) = tL( j) -tE(i) -t(i, j)单时差r(i, j)：不影响其紧后工序最早可能开工的前提下，本工序最早可能完工时间可以推迟的时间。 r(i,

12、 j)= tE( j) -tE(i) -t(i, j) 总时差为零的工序称为关键工序；关键工序组成关键路线。tEStLStEFtLF20r(i,j)tESR(i,j)tLStEFtLFOR:SM13OR:SM第二节三、时差与关键路线关键路线法路线路线的组成路线长度3+10=1323+0+8=116+4+8=18349456+0+5+8=194+5+8=17b310f001a6626d4511g8619194c3e5112166OR:SMOR:SM第二节关键路线法四、时间参数算例计算作业最早开始时间、最迟开始时间、最早结束时间、最迟结束时间以及时差，从表中寻找总时差与单时差都为零的作业，即为关键

13、作业，将其连接起来就是关键路线。作业t (i, j)tES (i, j) tEF (i, j)tLS (i, j) tLF (i, j)R(i, j)r (i, j)关键作业abcdefg634451080006631163410111319062769116961111191906210600021000a-e-g22OR:SMOR:SM例例 一个项目由九个作业所组成，每个作业的作业时间如表所示。作业时间A10B15C12D20E18F8G16H10I20（天）作业的先后顺序为：A、B、C三个作业同时开始；A作业结束后，D和E作业开始；D作业结束后，H作业开始； B作业结束后，E作业开始；C

14、作业结束后，G作业开始； E和F作业均结束后，I作业开始；H、I和G作业结束后，项目结束。解：第一步：先做网络图1A10B1523D20E18F856H10I20723C124G16OR:SMOR:SM网络时间参数计算实例 第二步：计算正向线路所需时间，即每项作业的最早开始时间ES和最早结束时间EF。（从起点向后推算） 1、最早开始时间：起点ES=0 其他任意一项作业的ES = max（其任何一项紧前作业的ES+该紧前作业的作业时间）21010D205300A1018EH1010B15315F8628I2070C2412412G16OR:SM10OR:SM网络时间参数计算实例 2、最早结束时间

15、：任意一项作业的EF = 该作业的ES+该作业的作业时间）102D 3010 205300A1018E28H1040100B 1515315F 238628I 4820 287C121212G164正向线路图25OR:SMIOR:SM网络时间参数计算实例 第三步：计算反向线路所需时间，即每项作业的最迟开始时间LS和最迟结束时间LF。（从终点向前推算） 1、最迟结束时间：终点LF = max（终点所有紧前作业的EF） 其他任意一项作业的LF = min（其任何一项紧后作业的LF-该紧后作业的作业时间）2D20 385A101018EH1001B15 20328F8 2864820 4872612

16、C324G1648OR:SMOR:SM网络时间参数计算实例 2、最迟开始时间：任意一项作业的LS = 该作业的LF-该作业的作业时间）2D18 20 385A10101018E38H10105B15 2032028F8 286I28 20484872012CG481632432反向线路图27OR:SMOR:SM网络时间参数计算实例ESEF作业的时间参数的图表示法LSLF101830383040001010A102D20E1851038H481B153F86I207C1523122028G16012122820324324828OR:SMOR:SM网络时间参数计算实例 第四步：计算各作业的松弛时

17、间。 1、作业松弛时间：TF = 该作业的LF-该作业的ES-该作业的作业时间 2、作业的自由松弛时间：TL = 后续作业的ES-该作业的EF作业名时间参数（天）称ABCDEFGHIt10151220188161020ES000101015123028EF101512302823284048LS0520181020323828LF102032382828484848TF0520805208029OR:SMijOR:SM网络时间参数计算实例第五步：求关键路线。1、关键路线是从开始到结束最长的路线。2、关键路线上所有作业的松弛时间为0。AEI3、复杂项目建立线性规划模型求解Maxf ( x ) i

18、 jt ij X约束条件： X 1 j 1 X in 1 X kj X ik 0 , k 1, k nXij=1或0Xij=1的作业构成的路线为关键路线30Xij 0OR:SM)ai 4mi bi b ai 266Tk TEOR:SM第三节计划评审技术一、作业时间估计 工序时间的三种可能估计： 最乐观时间：在最理想的情况下完成工序所需时间a； 最悲观时间：在最不利的情况下完成工序所需时间b； 最可能时间：在正常情况下完成工序所需时间m。 加权平均就是工序时间t工序时间t 二、计算期望工期a 4m b6，方差 2 （b a 26 工程期望工期等于关键路线上各道工序的时间之和 。工期TE ( )，

19、方差 2 ( i )i i 设规定的工程完工时间为Tk，则完工时间的概率为 ( x) 31OR:SMOR:SM第三节计划评审技术三、PERT应用举例某项目的作业流程及其时间估计作业紧前作业乐观时间作业时间估计悲观时间可能时间作业时间期望 方差abcdefg-a,bac,dae,f32132725431110131043249106432581061/91/91/916/916/9116/9若合同规定工期为20，求如期完工的概率；若要求有90%的把握如期完工，求可接受的合同工期的为多少。32OR:SMOR:SM第三节三、PERT应用举例计划评审技术44001a42d5f10e17175g6232

20、36b8 参数计算3437c2499 工程期望工期 TE=23 ，关键工序的方差2 =49/9，则，则 (x)=-1.29，查表知，查表知 P(x)=9.9% P(x)=90% ，查表知 (x)=1.3，则可接受的合同工期为，则可接受的合同工期为TE+ (x) =2633OR:SMOR:SM网络计划方法可以告诉我们什么？项目的预期完工时间按规定时间完工的概率及其影响因素关键作业有哪些？它们在项目执行中是不能耽误的。非关键作业有哪些？它们活动的余地多大？各作业要求的开始和结束时间。了解影响项目进度的因素，在此基础上进行资源的安排34OR:SMOR:SM第四节网络计划优化一、缩短工程工期 改进工艺

21、和技术装备，压缩关键工序的作业时间 合理组织平行作业、交叉作业 平行作业指两道以上相互独立的工序同时进行 交叉作业指将紧前工序完成的部分任务分期分批地转入下道工序 利用时差，合理调配资源等途径实现35OR:SMOR:SM第四节网络计划优化二、工期-费用优化1、工期与成本之间关系 工期的缩短与费用是密切相关的 工程费用最低的完工时间(最低成本日程)费用直接费用工程总费用间接费用36极限完工时间最优完工时间正常完工时间时间OR:SMOR:SM第四节网络计划优化二、工期-费用优化 寻求最低成本日程的思路：从网络计划的关键工序着手，对增加直接费用最少的某些关键工序采取措施，缩短其作业时间。直接费用极限

22、完工时间正常完工时间时间37赶单位时间增加的直接费用(费率) 赶进度极限完工费用 - 正常完工费用正常完工作业时间 - 极限完工作业时间OR:SMOR:SM第四节网络计划优化2、工期-费用优化案例某工程作业流程及其费用统计资料作业紧前作业作业时间（天）正常完工 极限完工作业直接费用（万元）正常完工 极限完工费率ABCDEFGH-BBEDA3556534533432332816202051092081923238.6101128-1.5311.2-2238合计间接费用882万元万元/天天OR:SMOR:SM第四节网络计划优化方案I：各道作业正常完工a33210h5001b5535d6e11411

23、g4615155c510512f3工程费用=正常完工直接费用+间接费用=88+215=118万元。39OR:SMOR:SM第四节网络计划优化方案2：关键路线d上赶进度a3328h5001b5535d4e949g4613135c510510f3工程费用=正常完工直接费用+赶进度增加的直接费用+间接费用=88+21+213=116万元。万元。40OR:SMOR:SM第四节网络计划优化方案3：关键路线b上赶进度36a32h5001b3333d4e747g4611115c5858f3工程费用=正常完工直接费用+赶进度增加的直接费用+间接费用=88+21+21.5+211=115万元。万元。41OR:S

24、MOR:SM第四节网络计划优化方案4：关键路线b、e上赶进度a3328h5001b3333d3e646g4610104c5757f3工程费用=正常完工直接费用+赶进度增加的直接费用+间接费用=88+21+21.5+1(1+1.2)+211=115.2万元。万元。42OR:SM2G20OR:SM时间成本优化的基本原理应用的补充例1：步骤：1、E减1天2、I减2天3、B、E各减1天4、K减2天1A12C104E65F56H87J108K698B3D8I关键路线：A,C,E,F,I,K(48天）要求：42天内完成，若完成可获1000元奖励作业成本斜率可能缩短天数A0B501C751D1502E253

25、F0G0H1501I506J1502K150243OR:SMOR:SM缩减结果:有多条关键路线缩减时间的作业EIBEK合计缩减天数121126成本斜率（元/天）25505025150赶工代价251005025300500奖励10001000G21A12C104E35F56H87J108K49447B3D8I18OR:SMOR:SM例2：要求将工期缩短到17天解：1、求关键路线2、改进：活动 正常时间赶工时间成本斜率（元/天）（1）c少1天，关键路线长变为19天abcdef6105492684171500300700600800（2）e少1天，关键路线长为18天（为什么不少2天？）（3）现有两条

26、关键路线：a、b、f 和 c、d、e、f。（4）缩短f 1天（b少1天500元+e少1天600还已知：间接成本为每天1000元元1100元）3、结果：项目周期17天。a2b1C610e5f2653d44945OR:SMOR:SM第四节网络计划优化三、工期-资源优化资源平衡准则：在压缩工程时间及费用的同时，要分别考量每道作业所需资源的用量与供应能力及时间限制，以便确定每道作业可压缩时间的限度及其进度安排。优先保证关键路线上关键作业对资源的需求量。对非关键作业要资源，利用时差调整非关键作业的开工时间和完工时间，以达到与关键作业在占用资源的时间上错开，拉平资源需要量的高峰。当资源绝对受限制时，在保证

27、不推迟或尽量少推迟工程完工时间的前提下，全面统筹安排，最大限度地利用资源。46OR:SM3 3g0510f1e0OR:SM第四节网络计划优化每天只有13台设备可用，计划10天完成，试合理安排生产进度工序紧前工序作业时间每天所需设备数a-313b-15ca28da32eb,c46fe,d112ga552a3 10c 2 d 5103b13 445 5 9 9所需工作日：313+15 +28 +32 +46 +112 +55=1274710天完成，则平均每天所需机器天完成，则平均每天所需机器12.7台，现有机器台，现有机器13台，适当安排可以完工台，适当安排可以完工OR:SM12OR:SM第四节网

28、络计划优化三、工期-资源优化3、制定初始方案 以最早开工时间，安排初始进度如表工序相关结点作业 最早时间 开工时间总时差1234工程进度5 678910abc312003040135131388d333222e4506666f19012g5325555548每天所需人数合计18 13 13 15 15 13 11 11 6OR:SMOR:SM第四节网络计划优化三、工期-资源优化4、调整开工时间第一次调整工序相关结点作业 最早时间 开工时间总时差1234工程进度5 678910abc312003040131313588d333222e4506666f19012g53255555每天所需人数合计1

29、3 13 13 13 15 13 13 11 11 12非关键作业b延至第4天开工，非关键作业d和g延至第5天开工。49OR:SMOR:SM第四节网络计划优化三、工期-资源优化4、调整开工时间第二次调整工序相关结点作业 最早时间 开工时间总时差1234工程进度5 678910abc312003040131313588d333222e4506666f19012g53255555每天所需人数合计13 13 13 13 13 13 13 13 11 12将非关键作业d延至第6天开工50OR:SMOR:SM第五节缓冲时间设置具体的思路是：削减每道作业的预估时间，不为单道作业设置安全缓冲时间，而将节省的时间建立一个任务缓冲（某项任务的总体安全时间）51OR:SMOR:SM第五节缓冲