运筹学第十一章网络计划

1第十一章网络计划(ProjectScheduling)1网络计划图2时间参数计算3网络计划的优化2网络计划技术的发展•1956年杜邦公司CPM：关键路线法•1958年美国海军部建“北极星”导弹PERT：计划评审法•1964年华罗庚《统筹方法平话》•1961-1972年美国“阿波罗”登月计划3什么是网络计划技术洗水壶1A12灌水B13烧水C154洗茶杯D15拿茶叶E16泡茶F17T=20洗水壶1A12灌水B13烧水C155泡茶F164洗茶杯D1E拿茶叶1T’=18洗水壶A1灌水B1烧水C15洗茶杯D1拿茶叶E1泡茶F142、节点——表示一个事件，是一个或若干个工序的开始或结束3、关键路线——从起点到终点的最长路线4、关键工序——关键路线上的每道工序第一节网络计划图一、基本术语1、工序——将整个项目按需要粗细程度分解成若干子项目或单元。它们是网络计划图的基本组成部分。5二、网络图的绘制1、原则：1）两个节点之间只能表示一道工序3A、BC5－B10－A时间紧前(后)工序工序名称工序明细表1A2C3B10531A2C33510B362）只有一个起点、一个终点工序名称紧前(后)工序A－B－CA、BDA、B3A1245BCD31254ACDB73）不能出现缺口与回路4）绘图原则：①只有一个起点和一个终点；②按项目工作流程自左至右地绘制；③箭头节点的标号要大于箭尾节点的标号；④箭线应是水平线或具有一段水平线的折线；⑤尽可能将关键路径布置在中心位置8工序工序代号所需时间（天）紧后工序产品设计与工艺设计a60b,c,d,e外购配套件b45l下料、锻件c10f工装制造1d20g,h木模、铸件e40h机械加工1f18l工装制造2g30k机械加工2h15l机械加工3k25l装配调试l35/例1某项研制新产品工程的各个工序与所需时间以及它们之间的相互关系如表所示，编制该工程的网络计划2、绘制方法：91a60362d205k254g307l358c10f18h15e40b45为编制网络计划，首先绘制网络图。网络图是由结点、弧及权所构成的有向图。•节点表示一个事件，用圆圈和里面的数字表示•权表示为完成某个工序所需的时间或资源等数据，通常标注在箭线下或其它合适的位置•弧表示一个工序，用表示10例2某工厂进行技术改造，需要拆掉旧厂房、建造新厂房和安排设备。这项改建工程可以分解为7道工序，其相关资料如下表：工序代号工序名称紧前工序工序时间（周）A拆迁/2B工程设计/3C土建工程设计B2.5D采购设备B6E厂房土建C、A20F设备安装D、E4G设备调试F21112345A（2）B(3)C(2.5)D(6)E(20)F(4)6G(2)工序代号工序名称紧前工序工序时间（周）A拆迁/2B工程设计/3C土建工程设计B2.5D采购设备B6E厂房土建C、A20F设备安装D、E4G设备调试F2解：12工序代号紧前工序工序时间（周）A/2B/3C/2DA3EA4工序代号紧前工序工序时间（周）FB7GB6HD、E4IB、C10JG、I3例3绘制工程网络图续左表解：1A(2)D(3)C(2)2E(4)3F(7)B'(0)G(6)45E'(0)6I(10)7J(3)H(4)8B(3)13②四个工序A、B、X、Y有如下关系：A是X的紧前工序，A和B同时又是Y的紧前工序123456ABXYA'虚工序5）两种情况需要引入虚工序12AB12A3B虚工序①两个工序A、B有相同的始点和终点B'141、关键路线路线路线的组成各工序所需时间之各(天)1a→b→l60＋45＋35＝1402a→c→f→l60＋10＋18＋35＝1233a→d→g→k→l60＋20＋30＋25＋35＝1704a→d→→h→l60＋20＋15＋35＝1305a→e→h→l60＋40＋15＋35＝150完成各个工序需要的时间最长的路线称为关键路线图中第三条路线为关键路线第二节网络计划图的时间参数计算152、工序时间的计算方法作业时间(Tij)在确定作业时间时，只给出一个时间值1）一点估计法2）三点估计法在未知和难以估计因素较多的条件下，对完成工序可估计三种时间，计算平均时间，作为该工序作业时间为完成某一工序所需的时间称为该工序i→j的作业时间。确定作业时间的方法有：16乐观时间：在顺利情况下，完成工序所需的最少时间，常用ai表示最可能时间：在正常情况下，完成工序所需要的时间，常用mi表示悲观时间：在不顺利情况下，完成工序所需的最多时间，常用bi表示估计的三种时间是：17对于每道工序i，作业时间的64ibmaTiii)6(22abiiσiabET完成工序所需要的上述三种时间都有一定的概率。根据经验可以认为近似于正态分布方差为均值为18工程完工时间等于各关键工序的平均时间之和。假设所有工序的作业时间相互独立，且具有相同分布，若在关键路线上有s道工序，则工程完工时间可以认为是一个以siiiibmaT1E64为方差的正态分布。根据TE与E2即可计算出工程的不同完工时间的概率siEabii122)6(为均值，以19例1已知某项工程，各关键工序的平均作业时间与方差如表所示:由表可以算出，该工程是工序T2c10.501.36d10.160.25f20.334.00g5.160.25h12.8314.6798.58),(CPvviEjiTT为期望值，以53.20),(22CPvviEji为方差的正态分布。以20式中，Tk为预定的工程完工时间或目标时间；u为的系数。上例中，Tk＝60，则TK=TE+Eu，或EEKTTu在TE和E2已知条件下，即可估算出工程完工时间的概率，也可以估算出具有一定概率的工程完工时间。22.053.2098.5860u根据正态分布表22.02/21dxex的值为0.587,即60天完成的概率为0.587213、节点的最早、迟时间节点最早时间（TE（j））：以j为起始节点的工序的最早可能开始时间。节点最迟时间(TL(i))：以i节点为终点的工序在不影响总工期的前提下的最迟完工时间TE（1）＝0TE（j）＝max{TE（i）+T（i,j）}(j=2,,n)TL（n）＝TE（n）(n为终点事件)TL（i）＝min{TL（j）-T（i,j）}(i=n-1,n-2,,1)将节点的最早时间记入中将节点的最迟时间记入中TE(j)为箭头节点的最早时间TE(i)为箭尾节点的最早时间TL(i)为箭尾节点的最迟时间TL(j)为箭头节点的最迟时间22用标号法求关键路线（1）标出各事项的最早时间（2）终点即为工期n的标号T1A(2)D(3)C(2)2E(4)3F(7)B'(0)G(6)45E'(0)6I(10)7J(3)H(4)8B(3)0233tE(j)Ⅱ、给任意事项j标，tE(j)=max{以”}为箭头的各箭之“箭尾j+箭长t(i,j)661316Ⅰ、给始点①标0231A(2)D(3)C(2)2E(4)3F(7)B'(0)G(6)45E'(0)6I(10)7J(3)H(4)8B(3)0233661316（3）标出各事项的最晚时间TⅠ、给终点n标161281333012tL(i)=min{以”}为箭尾的各箭之“箭头－箭长Ⅱ、给任意事项i标，itL(i)t(i,j)241A(2)D(3)C(2)2E(4)3F(7)B'(0)G(6)45E'(0)6I(10)7J(3)H(4)8B(3)0233661316T161212813330注：关键工序头尾皆有=（反之未必成立）R(i,j)=j的－i的－（4）计算各工序ij的时差R(i,j)：则关键工序为R(i,j)=0的工序。t(i,j)2512346109857A3B4C6D8E8F5H6G3J5L3K8I3例2003371299141417202020232328283131009914142020232328283131264、工序最早、最迟，开工、完工时间计算方法最早开工时间TES(i,j)=TE(i)最早完工时间TEF(i,j)=TES(i,j)＋T(i,j)最迟开工时间TLS(i,j)=TLF(i,j)-T(i,j)最迟完工时间TLF(i,j)=TL(j)工序总时差(i,j)=TLS(i,j)-TES(i,j)27PERT与CPM的主要区别：CPM工序时间是确定的；TTE第三节计划评审技术（PERT）PERT工序时间tij是随机变量，而完工期T也是随机的，由概率知识：T服从正态分布2~(,)ETNT28确定平均工序时间的三点估计法：64ijijijijbmat226ijijijab其中：IjiijEtT),(（I为关键路线）Ijiij),(22)1,0(~NTTETTE标准化总工期2~(,)ETNT291.给定时间T*，求工期T≤T*内完工的概率PERT的内容方法：首先计算ETT**，*2d21*}{*}{2tePTTPt*：阴影面积*)()(1)()(然后查表求。*)(Δ30912.837.838.17410.3312.1711ABCDEFGH2135764例1已知某工程网络图，以及各工序的时间参数。工序ambA101315B5810C7810D7911E246F81014G101215H91113TE=42.330.44/1.00//0.25/0.692ij1112.1710.33498.177.8312.83tij求工程在40天内完工的概率。关键路线I为:A→C→F→H；Ijiij),(2238.2ETT**51.154.133.4240解：}40{TP066.0)51.1(312.给定概率p，求完工可能性为p的工期方法：首先查表求*，使p*)(；再由ETT***T解出例、上例中，求完工可能性达95%的工期。95.0*)(解：由，查表；6.1*再由54.133.42***TTTE45*T解出321、工期优化根据对计划进度的要求，缩短工程完工时间(1)采取技术措施，缩短关键工序的作业时间(2)采取组织措施，充分利用非关键工序的总时差，合理调配技术力量及人财物力等资源，缩短关键工序的作业时间第四节网络计划的优化绘制网络图、计算网络时间和确定关键路线,得到一个初始的计划方案。但通常还要对初始计划方案进行调整和完善。根据计划的要求，综合地考虑进度、资源利用和降低费用等目标，即进行网络优化，确定最优的计划方案。332、资源优化（1）优先安排关键工序所需要的资源（2）利用非关键工序的总时差，错开各工序的开始时间拉平资源需要量的高峰（3）在确实受到资源限制，或者在考虑综合经济效益的条件下，也可以适当地推迟工程完工时间尽量合理地利用现有资源，缩短工程周期34例1在下例中，若完成工序d、f、g、h、k的机械加工工人数有限制时，并已知现有机械加工工人数为65人，并假定这些工人可以完成五个工序中的任何一个工序。各工序所需要的工人数及工序的总时差如表所示。工序作业时间(天)需要的机械加工人数总时差d20580f182247g30420h153920k25260356k(26)254g(42)307352d(58)20f(22)18h(39)15时间81人58人80人64人42人65人26人65人工人数607080901001101201305h(39)1542人3f(22)1864人58人363、时间－费用优化尽量使工程完工时间短，费用少；或者在保证既定的工程完工时间的条件下，所需费用最少；或者在限制费用的条件下，工程完工时间最短工程的时间费用分析求最低成本工期T*求规定工期下的最小成本方案37（1）费用构成：直接费用：原材料、工时费等间接费用：管理费、办公费应急时间正常时间正常费用应急费用；ABCDAB完工时间间接费用间接费用率一般固定，与工序无关。ABCD完工时间直接费用T*:最低成