管理运筹学：第八章 网络计划

1、管理运筹学-管理科学方法第八章 网络计划2第八章 动态规划网络图的绘制关键路线法计划评审技术网络计划优化本章主要内容：3第八章 网络计划网络计划技术 用网络分析的方法编制的计划称为网络计划。它是二十世纪五十年代末发展起来的一种编制大型工程进度计划的有效方法。1956年，美国杜邦公司在制定企业不同业务部门的系统规划时，制定了第一套网络计划。这种计划借助于网络表示各项工作与所需要的时间，以及各项工作的相互关系。通过网络分析研究工程费用与工期的相互关系。并找出在编制计划时及计划执行过程中的关键路线。这种方法称为关键路线法（Critical Path Method）简称CPM。4第八章 网络计划195

2、8年，美国海军武器部，在制定研制“北极星”导弹计划时，同样地应用了网络分析方法与网络计划。但它注重于对各项工作安排的评价和审查。这种计划称为计划评审方法（Program Evaluation and Review Technique）简称为PERT。鉴于这两种方法的差别，所以，CPM主要应用于以往在类似工程中已取得一定经验的承包工程；PERT更多地应用于研究与开发项目。在这两种方法得到应用推广之后，又陆续出现了类似的最低成本和估算计划法、产品分析控制法、人员分配法、物资分配和多种项目计划制定法等等。5第八章 网络计划 网络计划技术的特性 网络计划技术只不过是反映和表达项目计划安排的一种方法，是

3、被项目施工技术所决定的，它只能适应项目施工方法的要求。是把工程进度安排通过网络的形式直观地反映出来。 6第一节 网络图的绘制一、网络计划的图示形式 工序(作业)：一项需要人财物或时间等资源的相对独立的活动过程，又称作业在网络图中用箭线“” 表示，前面直接相连工序称紧前工序，直接相连的后继工序为紧后工序。 7第一节 网络图的绘制一、网络计划的图示形式 结点(事项)：相邻工序的分界点一般用圆圈来表示，每个结点编上顺序号箭尾结点表示工序的开始，箭头结点表示工序的完成。结点既不消耗人力、物力，也不占用时间。网络图由工序、事项及时间参数所构成的有向图即为网络图。 箭线表示工序,结点为工序间相互关系的网络

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

5、源，一般用虚箭线表示。10第一节 网络图的绘制123abc图11243abc图21234abcd图311第一节 网络图的绘制二、箭线式网络图的规则 方向的规定网络图是有方向的，工序应按工艺流程顺序或工作逻辑关系从左向右排列。编号的规定编号应从始结点开始，按照时序依次从小到大对结点编号，直到终结点。 编号时不允许箭头编号小于箭尾编号。 网络中只能有一个始点和终点 （如图4）12第一节 网络图的绘制二、箭线式网络图的规则 123456782433121图4 出现多个结点13第一节 网络图的绘制二、箭线式网络图的规则 平行作业为缩短工程的完工时间，在工艺流程和生产组织条件允许的情况下，某些工序可以同

6、时进行，即可采用平行作业的方式。交叉作业对需要较长时间才能完成的一些工序，在工艺流程与生产组织条件允许的情况下，可以不必等待工序全部结束后再转入其紧后工序，而是分期分批的转入。这种方式称为交叉作业。交叉作业可以缩短工程周期。14第一节 网络图的绘制二、箭线式网络图的规则 a1 a2 b1 b2 c1 c2 15第一节 网络图的绘制三、箭线式网络图举例 1、先绘制网络草图 绘制网络草图的方法是顺推法，即以始结点开始，首先确定由始结点引出的作业，然后根据作业间的逻辑关系，确定每项作业的紧后作业。 2、整理网络图布局审查作业的逻辑关系和虚作业的必要性，去掉多余的虚作业。然后对网络图布局进行合理安排和

7、整理，突出整齐性和美观性。 3、检查结点的编号 参照作业明细表中的逻辑关系，按照基本原则，检查网络图有无错误;若无错误，对结点进行顺序编号。 16第一节 网络图的绘制工序（作业、活动）名称工序代号紧前工序工序时间（天）拆卸清洗A-2电器检修BA3机件检修CA1零件加工DC8零件修理EC5组装FD、B、E3试机GF1紧前工序是指紧接在某工序前的工序，只有该工序完工后后续工序才能开工；某机器修理工序关系分析表三、箭线式网络图举例 17第一节 网络图的绘制1234562天C机件检查D零件加工B(电器检修)F组装G试机1天8天 3天1天某机器修理的简单网络图3天A(拆卸清洗)E零件修理5天18第一节

8、网络图的绘制三、箭线式网络图举例 某工程的工程一览表 工序abcdefg紧前工序-aa,cbb,d,e工序时间63445108124536badcegf36445810第一节 网络图的绘制工 序 工序代号 所需时间(天) 紧后工序 产品设计与工艺设计 a60b，c，d，e 外购配套件 b45l 下料、锻件 c10f 工装制造1 d20g，h 木模、铸件 e40h 机械加工1 f18l 工装制造2 g30k 机械加工2 h15l 机械加工3 k25l 装配调试 l35第一节 网络图的绘制12467835a60b45 c10d20e40f18g30h15k25l350ab，c，d，e bl cf

9、dg，h eh fl gk hl kl l21第二节 关键路线法在网络图中，从始点开始，按照各个工序的顺序，连续不断地到达终点的一条通路称为路线。如在图5中，共有五条路线，五条路线的组成及所需要的时间如下页所示22第二节 关键路线法12467835a60b45 c10d20e40f18g30h15k25l350图 523第二节 关键路线法路线 路 线 的 组 成 各工序所需的时间之和(天) 1 60+45+35=140 2 60+10+18+35=123 3 60+20+30+25+35=170 4 60+20+15+35=130 5 60+40+15+35=150 24第二节 关键路线法在各

10、条路线上，完成各个工序的时间之和是不完全相等的。其中，完成各个工序需要时间最长的路线称为关键路线，或称为主要矛盾线，在图中用粗线表示。在上图中，第三条路线就是条关键路线，组成关键路线的工序称为关键工序。如果能够缩短关键工序所需的时间，就可以缩短工程的完工时间。而缩短非关键路线上的各个工序所需要的时间，却不能使工程的完工时间提前。即使在一定范围内适当地拖长非关键路线上各个工序所需要的时间，也不至于影响工程的完工时间。编制网络计划的基本思想就是在一个庞大的网络图中找出关键路线。对各关键工序，优先安排资源，挖掘潜力，采取相应措施，尽量压缩需要的时间。25第二节 关键路线法求下图的关键路线356124

11、543223312124612105613856T=12 (周)26第二节 关键路线法关键路线法是在网络图的基础上，通过计算时间参数，确定关键路线，从而对工程项目进行更有效的协调与计划。而对非关键路线上的各工序，只要在不影响工程完工时间的条件下，抽出适当的人力、物力等资源，用在关键工序上，以达到缩短工程工期，合理利用资源等目的。在执行计划过程中，可以明确工作重点，对各关键工序加以有效控制和调度。27第二节 关键路线法关键路线是相对的，也是可以变化的。在采取一定的技术组织措施之后，关键路线有可能变为非关键路线。而非关键路线也有可能变为关键路线。适用于常规性生产项目的计划安排，各项工作重复性发生，

12、有确定的操作规程和时间定额，有较完备的统计资料。关键路线法相当于我们经常说到的“确定型模型”。 28第二节 关键路线法为了编制网络计划和找出关键路线,要计算网络图中各个事项及各个工序的有关时间，称这些有关时间为网络时间。作业时间(tij )：为完成某一工序所需要的时间称为该工序的作业时间，用tij表示。i表示箭尾，j表是箭头29第二节 关键路线法一、结点的时间参数 结点的最早时间tE(j)tE(j)等于从始点开始到本结点的最长路线上各道工序时间之和。从始点事项开始，自左向右，顺着箭线方向逐个计算 。假定始点事项的最早时间等于零，即TE (1) = 0。箭头事项的最早时间等于箭尾事项最早时间加上

13、作业时间。当同时有两个或若干个箭线指向箭头事项时，选择各工序的箭尾事项最早时间与各自工序作业时间之和的最大值。第二节 关键路线法TE (1) = 0TE (2) = TE (1)+T(1，2) = 0+60 = 60TE (3) = TE (2)+T(2，3) = 60+10 = 70TE (4) = TE (2)+T(2，4) = 60+20 = 80TE (5) = max TE (2)+T(2，5) ，TE (4)+T(4，5) = max 60+40 ， 80+0 = 100TE (6) = TE (4)+T(4，6) = 80+30 = 110TE (7) = max TE (2)

14、+ T(2,7) ，TE (3) + T(3,7) ， TE (6) + T(6,7) ，TE (5) + T(5,7) = max 60 + 45 ,70 + 18 ,110 + 25 ,100 + 15 = 135TE (8) = TE (7) + T(7，8) = 135 + 35 = 170 将上述计算结果计入各事项左下方的方框内，31第二节 关键路线法060801101351701007012467835a(60)b(45)c(10)d(20)e(40)f(18)g(30)h(15)k(25)l(35)TE (7) = max TE (2) + T(2,7) ，TE (3) + T(

15、3,7) ， TE (6) + T(6,7) ，TE (5) + T(5,7) =max 60 + 45 ,70 + 18 ,110 + 25 ,100 + 15 = 13532第二节 关键路线法一、结点的时间参数 结点的最迟时间 tL(j)指以该结点为结束的各道工序最迟必须完工的时刻，否则将会影响后续工序按时开工，以至推迟整个工程的完工时间。从为了尽量缩短工程的完工时间,把终点事项的最早时间，即工程的最早结束时间作为终点事项的最迟时间。事项最迟时间通常按箭尾事项的最迟时间计算，从右向左反顺序进行。箭尾事项的最迟时间等于箭头事项的最迟时间减去该工序的作业时间。当箭尾事项同时引出两个以上箭线时，

16、该箭尾事项的最迟时间必须同时满足这些工序的最迟必须开始时间。所以在这些工序的最迟必须开始时间中选一个最早（时间值最小）的时间第二节 关键路线法例如，在网络图中各事项的最迟时间为： TL (8) = TE (8) = 170 TL (7) = TL (8) T(7,8) = 170 = 135第二节 关键路线法TL (6) = TL (7) T(6,7) = 135 25 = 110TL (5) = TL (7) T(5,7) = 135 20 = 115TL (4) = min TL (6) T(4,6) ， TL (5) T(4,5) = min 110 30 ，120 0 = 80TL (

17、3) = TL (7) T(3，7) = 135 18 = 117 TL (2) = min TL (7) T(2,7) ，TL (3) T(2,3) ， TL (4) T(2,4) ，TL (5) T(2,5) = min 135 45 ，117 10 ，80 20 ， 120 40 = 60TL (1) = TL (2) T(1，2) = 60 60 = 0第二节 关键路线法124678350608011013517010070a(60)b(45)c(10)d(20)e(40)f(18)g(30)h(15)k(25)l(35)06080110135170120117第二节 关键路线法某工程

18、的工程一览表 工序abcdefg紧前工序-aa,cbb,d,e工序时间63445108124536badcegf36445810第二节 关键路线法124536badcegf548364100366111996611190计算结点时间参数38第二节 关键路线法二、作业的时间参数 最早可能开工时间tES(i, j)一个作业必须在其各紧前作业都完工后才能开工，紧前工序最早结束时间即为工序最早可能开始时间，简称为工序最早开始时间，用tES(i, j)表示。作业最早可能开工时间等于其箭尾事项的最早时间。 tES(i, j)= tE(i)39第二节 关键路线法12467835060801101351701

19、0070a(60)b(45)c(10)d(20)e(40)f(18)g(30)h(15)k(25)l(35)0608011013517012011740第二节 关键路线法二、作业的时间参数 最早可能完工时间 tEF(i, j)从最早可能开工时间开工，完成本作业的时间 。它等于工序最早开始时间加上该工序的作业时间。 tEF(i, j)= tES(i, j) +t(i, j)在图5中， TEF (1，2) = 0 + 60 = 60 ， TEF (2，3) = 60 + 10 = 70 ， TEF (2，4) = 60 + 20 = 80 ，41第二节 关键路线法二、作业的时间参数 最迟必须开工时

20、间 tLS(i, j)在不影响工程如期完工的前提下，作业最迟必须开工的时刻。等于它的箭头事项的最迟时间减去本作业的作业时间 ，即：tLS(i, j)= tL( j) - t(i, j)在图5中，TLS (1，2) = 60 60 = 0 ， TLS (2，3) = 117 10 = 107 ，TLS (2，4) = 80 20 = 60 ，TLS (2，5) = 120 40 = 80 ，42第二节 关键路线法二、作业的时间参数 最迟必须完工时间 tLF(i, j)在不影响工程如期完工的前提下，作业最迟必须完工的时刻 。它等于工序的箭头事项的最迟时间。 tLF(i, j)= tLS(i, j)

21、 +t(i, j) = tL( j) 在图5中， TLF (7，8) = 170 ，TLF (6, 7) = TLF (5, 7) = TLF (3, 7) = TLF (2, 7) = 135 ，TLF (4，6) = 110 ， TLF (2，5) = 120 ，43第二节 关键路线法三、时差与关键路线 时差又称宽裕时间：不影响如期完成任务的条件下，各道工序可以机动使用的一段时间。总时差R(i, j)：不影响其紧后工序最迟必须开工的前提下，本工序最早可能完工时间可以推迟的时间。 工序总时差 = 最迟开始 最早开始 即: R(i, j)= tLS(i, j) -tES(i, j) =tL(

22、j) -tE(i) -t(i, j) 工序总时差 = 最迟结束 最早结束 即:R(i, j)= tLF(i, j) -tEF(i, j) = tL( j) -tE(i) -t(i, j) 工序总时差越大,表明该工序在整个网络中的机动时间越大，可以在一定范围内将该工序的人力、物力资源利用到关键工序上去，以达到缩短工程结束时间的目的。44第二节 关键路线法三、时差与关键路线 单时差r(i, j)：不影响其紧后工序最早可能开工的前提下，本工序最早可能完工时间可以推迟的时间。r(i, j)= tES(j, k) -tEF(i, j) =tE( j) -tE(i) -t(i, j) 式中， tES(j,

23、 k)为工序 ij 的紧后工序的最早开始时间。总时差为零的工序称为关键工序；关键工序组成关键路线。工序总时差、单时差及其紧后工序的最早开始时间、最迟开始时间的关系如图6所示。第二节 关键路线法三、时差与关键路线 工序 a工序a 的紧后工序b工序a 的单时差工序a 的总时差 TES TLS TEF TLF TES TLS TEF TLF图6第二节 关键路线法 总时差为零的工序，开始和结束的时间没有一点机动的余地。由这些工序所组成的路线就是网络中的关键路线。这些工序就是关键工序。用计算工序总时差的方法确定网络中的关键工序和关键路线是确定关键路线最常用的方法。在图5中，工序a、d、g、k、l 的总时

24、差为零,由这些工序组成的路线就是图5中的关键路线。见下页 通过上述的网络时间参数计算过程可以看出, 计算过程具有一定的规律和严格的程序,可以在计算机上进行计算，也可以用表格法与矩阵法计算。第二节 关键路线法124678350608011013517010070a(60)b(45)c(10)d(20)e(40)f(18)g(30)h(15)k(25)l(35)图506080110135170120117关键路线第二节 关键路线法某工程的工程一览表 工序abcdefg紧前工序-aa,cbb,d,e工序时间63445108124536badcegf3644581049第二节 关键路线法三、时差与关键

25、路线 路线 路线的组成 路线长度13+10=13 23+0+8=11 36+4+8=1846+0+5+8=1954+5+8=17 1 2 4 5 3 6badcegf54836410036611199661119050第二节 关键路线法四、时间参数算例 计算作业最早开始时间、最迟开始时间、最早结束时间、最迟结束时间以及时差，从表中寻找总时差与单时差都为零的作业，即为关键作业，将其连接起来就是关键路线。作业关键作业a6b3c4d4e5f10g800066311a-e-g06210606961111191906276911634101113190021000第三节 计划评审技术一、作业时间估计 工

26、序时间的三种可能估计：最乐观时间：在最理想的情况下完成工序所需时间a；最悲观时间：在最不利的情况下完成工序所需时间b；最可能时间：在正常情况下完成工序所需时间m。加权平均就是工序时间t 第三节 计划评审技术在（a,m）上的平均值在（m,b）上的平均值工时的分布可以用 与 各以1/2可能性出现的分布来代表所以平均（期望）工时而方差由实际工作情况表明，工作进行时出现最顺利和最不利情况都比较少，更多的是在最可能完成进间内完成，工时的分布近似服从于正态分布，即应用加权平均法第三节 计划评审技术工程期望工期等于关键路线上各道工序的时间之和 。则完工时间的概率为二、计算期望工期 为达到严格控制工期,确保任

27、务在计划期内完成的目的，我们可以计算在某一给定期限Tk前完工的概率。54第三节 计划评审技术三、PERT应用举例 某项目的作业流程及其时间估计 若合同规定工期为20，求如期完工的概率；若要求有90%的把握如期完工，求可接受的合同工期的为多少。 作业紧前作业作业时间估计作业时间乐观时间悲观时间可能时间期望方差a-35441/9b-24331/9ca,b13221/9da3114516/9ec,d2109816/9fa71310101ge,f2106616/955第三节 计划评审技术三、PERT应用举例 1234a3b2c45d8e10f566g0449172323179740参数计算工程期望工期

28、 TE=23 ，关键工序的方差2 =49/9，则 (x)=-1.29，查表知 P(x)=9.9%P(x)=90% ，查表知 (x)=1.3，则可接受的合同工期为TE+ (x) =2656第四节 网络计划优化一、缩短工程工期改进工艺和技术装备，压缩关键工序的作业时间合理组织平行作业、交叉作业平行作业指两道以上相互独立的工序同时进行交叉作业指将紧前工序完成的部分任务分期分批地转入下道工序利用时差，合理调配资源等途径实现57第四节 网络计划优化二、工期-费用优化1、工期与成本之间关系工期的缩短与费用是密切相关的工程费用最低的完工时间(最低成本日程)时间费用极限完工时间正常完工时间直接费用间接费用最优

29、完工时间工程总费用58第四节 网络计划优化二、工期-费用优化寻求最低成本日程的思路：从网络计划的关键工序着手，对增加直接费用做少的某些关键工序采取措施，缩短其作业时间。时间直接费用极限完工时间正常完工时间59第四节 网络计划优化2、工期-费用优化案例某工程作业流程及其费用统计资料 作业紧前作业作业时间（天）作业直接费用（万元）费率正常完工极限完工正常完工极限完工A-3388-B-5316191.5C-5420233DB6320231EB5258.61.2FC、E331010-GD439112HA5220282合计88间接费用2万元/天60第四节 网络计划优化方案I：各道作业正常完工工程费用=正

30、常完工直接费用+间接费用=88+215=118万元。 23a5b6d 45h4g5e 563f 0 3 5 11 10 15 05 31011121515c61第四节 网络计划优化2、工期-费用优化案例某工程作业流程及其费用统计资料 作业紧前作业作业时间（天）作业直接费用（万元）费率正常完工极限完工正常完工极限完工A-3388-B-5316191.5C-5420233DB6320231EB5258.61.2FC、E331010-GD439112HA5220282合计88间接费用2万元/天62第四节 网络计划优化方案2：关键路线d上赶进度 工程费用=正常完工直接费用+赶进度增加的直接费用+间接费

31、用 =88+21+213=116万元。23a5b4d 45h4g5e 563f 0 3 5 9 10 13 0 5 38 9 10 13 15c63第四节 网络计划优化方案3：关键路线b上赶进度 工程费用=正常完工直接费用+赶进度增加的直接费用+间接费用 =88+21+21.5+211=115万元。23a3b4d 45h4g5e 563f 0 3 3 7 8 11 0 3 3 6 7 8 11 15c64第四节 网络计划优化方案4：关键路线d、e上赶进度 工程费用=正常完工直接费用+赶进度增加的直接费用+间接费用 =88+21+21.5+1(1+1.2)+211=115.2万元。23a3b3d 45h4g4e 5 63f 0 33 6 7 10 0 3 3 8 6 7 10 15c65第四节 网络计划优化三、工期-资源优化资源平衡准则：在压缩工程时间及费用的同时，要分别考量每道作业所需资源的用量与供应能力及时间限制，以便确定每道作业可压缩时间的限度及其进度安排。优先保证关键路线上关键作业对资源的需求量。对非关键作业要资源，利用时差调整非关键作业的开工时间和完工时间，以达到与关键作业在占用资源的时间上错开，拉平资源需要量的高峰。当资源绝对受限制时，在保证不推迟或尽量少推迟工程完工时间的前提下，全面统筹安排，最大限度地利用资源。第四节 网络计划优化每天只有13台设备可用