1,运 筹 学 课 件,网络计划技术,Network Program Technique,2,第十章 网络计划技术,网络计划技术 1957年，美国杜邦公司运用网络计划技术来统筹各项工作，并找出编制与执行计划的关键路线，称为关键路线法(Critical Path Method)，简称CPM。 1958年，美国海军武器局在制定研制“北极星”导弹计划时，开发出了计划评审技术(Program Evaluationand Review Technique)，简称PERT。 1962年产生了能够体现随机因素作用的图示评审技术(Graphic Evaluation and Review Technique)，简称GERT。 20世纪70年代，美国G.L.穆勒等人，在GERT基础上提出了风险评审技术(Venture Evaluation Review Technique)，简称VERT。 这些技术方法均以网络描述工序及工序之间的关系。,3,第一节 网络图及其绘制规则,工序 一项需要人力、物力或时间等资源的相对独立的活动过程， 又称作业； 在网络图中用箭线“” 表示； 与某道工序前面直接相连的工序称为紧前工序； 其后直接相连的后继工序为紧后工序。 结点(事项) 结点(事项)是相邻工序的分界点； 一般用圆圈来表示，每个结点编上顺序号： 箭尾结点表示工序的开始， 箭头结点表示工序的完成。 结点(事项)既不消耗人力、物力，也不占用时间。 网络图 由工序、事项及时间参数（工序时间）所构成的赋权有向图即为网络图。 用箭线表示工序，结点表示工序间相互关系的网络图，称箭线式网络图。,一、网络图的概念,4,第一节 网络图及其绘制规则,工序表示的规定 一条箭线和它的相关事项只能代表一道工序，不能代表多道工序， 两个结点之间只能有一条箭线相连。 不允许出现缺口与回路 网络图中只能有一个始点和一个终点，使得自网络图的始点经由任何路径都可以到达终点。 虚工序 虚工序是为了表达相邻工序之间的逻辑关系而虚设的工序。 不消耗时间、费用和资源，一般用虚箭线表示。 方向的规定 网络图是有方向的，工序应按工艺流程顺序或工作的逻辑关系从左向右排列。 编号的规定 编号应从始结点开始，按照时序依次从小到大对结点编号，直到终结点。 编号时不允许箭头编号小于箭尾编号。,二、绘制网络图的规则,5,第一节 网络图及其绘制规则,某工程的工序一览表如下，试绘制网络图。,1,2,3,4,5,6,6,第二节 关键路线法,关键路线法是在网络图的基础上，通过计算时间参数，确定关键路线，从而对工程项目进行更有效的协调与计划。 关键路线法适用于常规性生产项目的计划安排，各项工作重复性发生，有确定的操作规程和时间定额，有较完备的统计资料。 关键路线：网络中所有路线最长的路线。,7,第二节 关键路线法,结点的最早时间tE(j) 结点j的最早时间tE(j)指以该事项为始点的各道工序的最早开始时间，等于从始点开始到本结点的最长路线上各道工序时间之和。 从始点事项开始，自左向右，顺着箭线方向逐个计算 。,一、结点(事项)的时间参数计算,结点的最迟时间 tL(j) 指以该事项为结束的各道工序最迟必须完工的时刻，否则将会影响后续工序按时开工，以至推迟整个工程的完工时间。 从终点开始，从右向左，逆箭线方向逐个计算。,8,第二节 关键路线法,计算结点时间参数，确定关键路线。,1,2,3,4,5,6,0,4,6,4,6,16,16,6,6,6,6,0,9,第二节 关键路线法,工序最早可能开工时间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) 从最迟必须开工时间开工，完成本工序的时间 。 tLF(i, j)= tLS(i, j) +t(i, j) = tL( j),二 、工序的时间参数计算,10,第二节 关键路线法,时差又称机动时间或宽裕时间 在不影响如期完成任务的条件下，各道工序可以机动使用的一段时间。 工序总时差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),三 、时差与关键路线,11,第二节 关键路线法,工序单时差r(i, j) 在不影响其紧后工序最早可能开工的前提下，本工序最早可能完工时间可以推迟的时间。 r(i, j)= tE( j) -tE(i) -t(i, j) 关键路线的确定 总时差为零的工序称为关键工序， 关键工序组成的路线就是关键路线。,R(i,j),r(i,j),12,第二节 关键路线法,计算时间参数,1,2,3,4,5,6,0,4,6,4,6,16,16,6,6,6,6,0,13,第三节 计划评审技术,实际工作中，许多工程项目的工序时间是不确定的， 或者是由于随机因素的影响， 或者是属于开拓性的工作，没有经验数据或统计资料， 很难确定工序时间，这时便不宜采用关键路线法。 采用计划评审技术，对工序时间进行粗略的估计，而后绘制网络图，找出关键路线，并可对工程完工期进行概率估计。,14,第三节 计划评审技术,工序时间的三种可能估计： 最乐观时间：在最理想的情况下完成工序所需时间a； 最悲观时间：在最不利的情况下完成工序所需时间b； 最可能时间：在正常情况下完成工序所需时间m。 加权平均就是工序时间t,一、工序时间估计,二、工期估计,工程期望工期等于关键路线上各道工序的时间之和 。,设规定的工程完工时间为Tk，则完工时间的概率为,15,第三节 计划评审技术,三、应用举例 若合同规定工期为20，如期完工的概率？ 要求90%的把握如期完工，可接受的合同工期？,16,第三节 计划评审技术,绘制网络图,1,2,3,4,5,6,0,4,4,9,17,23,23,17,9,7,4,0,参数计算 工程期望工期 TE=23 ，关键工序的方差2 =49/9，则 (x)=-1.29，查表知 P(x)=9.9% P(x)=90% ，查表知 (x)=1.3，则可接受的合同工期为TE+ (x) =26,17,第四节 网络计划的优化,缩短工程时间 改进工艺和技术装备，压缩关键工序的作业时间； 合理组织平行作业、交叉作业； 平行作业指两道以上相互独立的工序同时进行。 交叉作业指将紧前工序完成的部分任务分期分批地转入下道工序。 利用时差，合理调配资源等途径实现。,18,第四节 网络计划的优化,时间费用优化 在时间进度优化中，重点在于如何缩短工期， 工期的缩短与费用是密切相关的， 网络计划的优化中，应考虑不同的完工时间所对应的工程费用， 找到工程费用最低的完工时间(最低成本日程)。,极限完 工时间,正常完 工时间,直接费用,间接费用,最优完 工时间,工程总费用,19,第四节 网络计划的优化,寻求最低成本日程的思路：从网络计划的关键工序着手，对增加直接费用做少的某些关键工序采取措施，缩短其作业时间。,极限完 工时间,正常完 工时间,20,第四节 网络计划的优化,例,21,第四节 网络计划的优化,方案I：正常完工,1,2,3,4,5,6,0,3,5,11,10,15,15,12,11,5,8,0,工程费用C(I)=正产完工直接费用+间接费用=8800+20015=11800元,22,第四节 网络计划的优化,方案II：在关键路线上赶进度 赶进度的工序：关键工序d 赶单位时间进度增加的直接费用最少，选择工序d 赶紧度； 赶进度的时间：工序d 最多只能赶3天，非关键路线时差为2和5，故工序d 只能赶2天。,1,2,3,4,5,6,0,3,5,9,10,13,13,10,9,5,6,0,工程费用C(II)=正产完工直接费用+赶进度增加的直接费用+间接费用 =8800+2100+20013=11600元,23,第四节 网络计划的优化,方案III：在关键路线上赶进度 赶进度的工序：关键工序b赶单位时间进度增加的直接费用最少，选择工序b 赶紧度； 赶进度的时间：工序b 最多只能赶2天，非关键路线时差为3，故工序b 只能赶2天。,1,2,3,4,5,6,0,3,3,7,8,11,11,8,7,3,4,0,工程费用C(III)=正产完工直接费用+赶进度增加的直接费用+间接费用 =8800+2100 +2150 +20011=11500元,24,第四节 网络计划的优化,方案IV：在关键路线上赶进度 赶进度的工序：选择工序d,e同时各 赶紧度； 赶进度的时间：工序d 最多只能赶1天，故工序d,e只能同时各赶1天。,1,2,3,4,5,6,0,3,3,6,7,10,10,7,6,3,3,0,工程费用C(IV)=正产完工直接费用+赶进度增加的直接费用+间接费用 =8800+2100 +2150 +1(100 +120 )+20010=11520元,25,第四节 网络计划的优化,时间资源优化 在一定工期下，通过平衡资源，取得工期与资源的最优配置。 平衡原则： 优先保证关键路线上关键工序对资源的需求量。 向非关键工序要资源，利用时差调整非关键工序的开工时间，达到与其它工序在占用资源的时间上错开，拉平资源需要量的高峰。 例，某工程工序一览表如下，每天只有13人上班，计划10天内完成，试合理安排生产。,26,第四节 网络计划的优化,工程所需工作日：313+15 +28 +32 +46 +112 +55=127 10天内完成，则平均每天所需人力12.7 现有人力13 人，适当安排各工序的开工和完工，10天可以完成工程。,1,2,3,4,5,0,3,5,9,10,10,9,5,3,0,27,第四节 网络计划的优化,13 13 13,5,8 8,2 2 2,6 6 6 6,12,5 5 5 5 5,28,第四节 网络计划的优化,调整非关键工序开工时间,13 13 13,5,8 8,2 2 2,6 6 6 6,12,5 5 5 5 5,29,第四节 网络计划的优化,13 13 13,5,8 8,2 2 2,6 6 6 6,12,5 5 5 5 5,