管理运筹学讲义：网络计划.ppt

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=12710天内完成，则平均每天所需人力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,