运筹学基础网络计划.ppt

第七章 计划评审方法和关键线路法,网络计划技术,计划评审技术（Program Evaluation and Review Technique，PERT),是一种组织生产和进行计划管理的科学方法，也称统筹法。它是综合运用计划评审技术和关键路线法的一种较为先进和计划管理方法。,关键路线法（Critical path method,简写CPM),是对计划项目进行核算、评价，然后选定最优计划方案的一种技术。,是在计划项目的各项错综复杂的工作中，抓住其中的关键路线进行计划安排的一种方法。,第一节 PERT网络图及其绘制规则,网络图又叫箭头图或统筹图，它是计划项目的各个组成部分内在逻辑关系的综合反映，是进行计划和计算的基础，即网络计划技术的基础是网络图。,一、网络图的分类,箭线式网络图,以箭线代表作业(活动)，以结点代表作业的开始和完成。需要引进虚作业(以虚线表示)，其特点是布图明朗，应用广泛。,结点式网络图,以结点代表作业(活动)，以箭线表示各之间的待后承接关系。不需要引进虚作业，但其特点是线条纵横交错，不一目了然，应用不广泛。,箭线式网络图例,1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,A,B,D,E,F,G,H,C,I,J,K,L,M,N,O,P,Q,箭线代表作业,结点代表作业的开始和完成,结点（事件）式网络图例,始,B,A,C,D,E,F,G,H,I,J,K,M,N,O,L,P,Q,x,结点代表作业,箭线代表作业的衔接,二、箭线式网络图的构成,箭线式网络图是由作业、事件（结点）和线路三个部分组成。,1. 作业,指任何消耗人力、物力或时间等资源的相对独立的作业过程，又称作业或工序。,作业在网络图中的表示,在网络图中作业用箭线“” 表示，从箭尾到箭头表示一项作业的开始到终结的过程。,在箭线的左（上）侧写上作业的名称，右（下）侧写上该作业所占用的时间。,与某项作业前面直接相连的作业称为紧前作业，其后直接相连的后继作业为紧后作业。,虚作业：虚作业是为了表达相邻工序之间的逻辑关系而虚设的作业。不消耗时间、费用和资源，一般用虚箭线表示。,2.事件（结点）,事件（也叫结点），是相邻作业的分界点，标志着作业的开始或结束。,事件（结点）在网络图中的表示,一般用圆圈“”来表示，每个结点编上顺序号； 箭尾结点表示作业的开始， 箭头结点表示作业的完成。,结点既不消耗人力、物力，也不占用时间。,一项规划只有一个总开始结点称为最初结点，和一个总结束结点称为最终结点。,处在网络中间的结点具有两重性，对前面的作业它是终点、对后面的作业它是始点,3. 线路,线路是指从最初事件开始，顺着箭线的方向，由各项作业连贯组成的，到达最终事件的一条路。从最初事件到最终事件可以有不同的路。,路长：线路的总长度称为路程长，也是线路总作业时间,如图所示：,从起点连续到终点的各条线路是,路长最长的线路称为关键线路,关键路线,在所有的线路中，总作业时间最长的线路就是关键路线。或叫主要矛盾线。关键线路决定整个网络计划的完工时间。,关键路线，也可由所有各条线路的路长中最长的一条线路所决定。,网络分析的主要任务是找出工程中的关键路线，因为它决定着完工期。如果这条线路上工作进度有耽误，则整个工程的工期就要向后推迟；相反，如果能采取积极措施缩短这条线路的完工时间，工期就可能提前。,关键路线,三、绘制网络图的规则和注意事项,方向的规定 网络图是有方向的，工序应按工艺流程顺序或工作的逻辑关系从左向右排列。 作业表示的规定 一条箭线和它的相关结点只能代表一项作业，不能代表多项作业 两个结点之间只能有一条箭线相连,正确的画法,可引入虚作业。,不正确的画法,虚作业是为了表达相邻作业之间的逻辑关系而虚设的作业。 它不消耗时间、费用和资源，一般用虚箭线表示。,虚作业的引进原因(1),虚作业,两个事件之间的工作过程只能代表一项作业，当两个或两个以上的作业具有同一个始点和终点时，需要引入虚作业，予以区别。,虚作业的引进原因(2),是为了正确表示各个作业之间的先后承接关系，有时必须引入虚作业。如一个工程各个作业之间的先后关系如表：,各项作业之间的关系和表达方式,作业a结束后可以开始b和c,作业c在a和b均结束后才能开始,a、b两项均结束后可以开始c和d,c在a结束后即可进行、d必须在a、b两项均结束后才能开始。,不允许出现缺口与回路,编号的规定 编号应从始事件开始，按照时序依次从小到大对事件编号，直到终事件。 编号时不允许箭头编号小于箭尾编号。 事件的编号原则 箭尾事件(i)小于箭头事件(j)；一般采用非连续编号，即可空留出几个号，跳着编，将来有变化时，不致打乱全局。,网络图中只能有一个始点和一个终点，使得自网络图的始点经由任何路径都可以到达终点。,尽量避免箭线之间的交叉,为了方便计算和美观清晰，PERT网络图中通过调整布局，尽量避免箭线之间的交叉。,调整前,调整后,四、箭线式网络图的绘制,1. 任务的分解,就是把一个计划项目的总任务分解成一定数量的分任务，并确定它们之间的先后承接关系,分解任务的原则,工作的性质不同或由不同单位执行的工作应分开；,同一单位进行的工作，时间先后不衔接的要分开；,如产品设计与工装设计，铸造、锻、机械加工、装配要分开,如技术设计与工作图设计，材料采购与外协件采购要分开,占用时间不消耗资源，但影响工程完工日期的工作应作为分任务；,如油漆后的干燥，热处理后的冷却，方案的审批等,分解任务的要求,编制计划要熟悉业务，了解工程项目的各个组成部分，深入调查。,例：下表是某一工程的作业明细表,任务经过分解以后，可以列出作业明细表。,某一工程的作业时细表,2. 画网络图(以前图为例),第一步：先画出无紧前作业的A、B，给网络始点编号为,第二步：用一条斜线“”消去已画入网络图的作业A、B， 在A后面，画出紧前作业为A的作业E；在B后面，画出紧前作业为B的作业D；给新增的事件编号为、，在A与B后面，画出紧前作业为A、B的作业C；画作业C时要引进虚作业，为新增的事件编号为。,第三步：用一条斜线“”消去已画入网络图的作业C 将F画在紧前作业C之后；为新增的事件编号为。,第四步：用一条斜线“”消去已画入网络图的作业D、E、F 将G画在紧前作业E、F之后；将H画在紧前作业D、F之后，引入虚作业,第五步：再用一条斜线“”消去已画入网络图的作业G、H 以此类推，最后得出网络图,某工程的网络图,1,A,B,3,E,D,5,C,7,9,F,13,G,H,15,11,I,17,19,J,21,又例,f,a,b,c,d,e,练习：,练习1：,练习2：,答案,F,A,C,D,E,B,答案,F,A,C,D,B,E,第二节 网络时间的计算,网络时间的计算有三种计算方法：图上计算法、表格计算法和EXCEL计算法。,图上计算法要用的有关符号,作业最早开始符号。在长方形符号中标以作业最早开始时间值，该符号放在箭线的上方，靠近前事件i的右上角。,作业最迟完成符号。在三角形符号中标以作业最迟完成时间值，该符号放在箭线的好方，靠近后事件j的左好角。,一、图上计算法,（一）作业时间,作业时间就是在一定的生产技术条件下，完成一项作业或一道工序所需的时间，符号Ti,j就是表示ij这项作业的作业时间。,三种可能估计： 最乐观时间：在最理想的情况下完成工序所需时间a； 最悲观时间：在最不利的情况下完成工序所需时间b； 最可能时间：在正常情况下完成工序所需时间m。 加权平均就是工序时间t,确定作业时间的方法：,(1)单一时间估计法：就是在估计各项作业的时间时，只确定一个时间值。,(2)三种时间估计法：就是在估计各项作业的作业时间时，先估计出三个时间值，然后再求出完成该作业的作业时间。,例、求作业的期望时间和方差,各项作业的三个估计时间如下表，求各作业的期望时间和方差。,计算：,（二）作业时间参数计算,其值等于从初始点起到本作业的最长路线上各作业时间之和。 从最初作业开始，自左向右，顺着箭线方向逐个计算 。,1.作业最早可能开工时间ESi,j,截取下面部分讨论,在箭线式网络图中，要计算的作业时间有两个，即作业的最早开始时间、最迟完成时间。,作业最早开始时间计算如下：,已知：ES3,7=3， ES5,7=3， T3,7=4，T5,7=3 ，T7,9=4 。求ES7,9=？ ES9,11=？ ES11,13=？ ES11,15=？,ES7,9= maxES3,7+T3,7，ES5,7+T5,7=max3+4， 3+3 =7,ES9,11= ES7,9+T7,9=7+4=11,ES7,9=？,3,3,ES9,11=？,ES11,13=？,ES11,15=？,7,11,ES11,13= ES11,15 = ES9,11+T9,11=11+3=14,14,14,2.作业最迟必须完工时间 LFi,j,指作业最迟必须完工的时刻，否则将会影响后续作业按时开工，以至推迟整个工程的完工时间。 最终作业的最迟完成时间应等于总完工时间 从终点开始，从右向左，逆箭线方向逐个计算。,截取下面部分讨论,事件最迟完成时间计算如下：,已知：LF11,13=20， LF11,13=20，T7,9=4，T9,11=3，T11,13=6，T11,15=5 。求LF9,11=？，LF7,9=？,LF9,11=minLF11,13-T11,13，LF11,15-T11,15 =min20-6,20-5 =14,LF7,9= LF9,11-T9,11=14-3=11,LF9,11=？,LF7,9=？,20,20,LF3,7=？,LF5,7=？,14,11,LF3,7 =LF5,7 = LF7,9-T7,9=11-4=7,7,7,作业时间的完整计算,作业的最早开始时间是顺着箭线的方向，逐个计算；,作业的最迟完成时间是逆着箭线的方向，逐个计算；,0,0,2,2,3,3,3,7,10,10,10,10,17,23,完工时间28,28,23,17,17,15,15,10,10,10,7,3,3,3,3,0,关键线路,28,（三）时差与关键路线,一个工作或一个工程有多大时差，就表明了有多大的机动时间可以利用。时差越大，则时间的潜力也越大。即可以将工作的资源暂时调出去支援关键性线路。计算和利用时差是网络分析中一个重要问题，它为计划进度的安排提供了可供选择和协调的可能性，也是确定关键线路的依据。,时差,又称机动时间或宽裕时间，是指在不影响如期完成任务的条件下，各道工序可以机动使用的一段时间。,1、作业时差,作业的总时差Ri,j,作业的自由时差Fi,j,在不影响工程最早结束时间的条件下，工序最早开始时间可以推迟的时间，称为该工序的总时差。(即工序的完工期可以推迟的时间)即： 工序总时差 = 最迟完成时间作业时间最早开始时间,工序总时差越大，表明该工序在整个网络中的机动时间越大，可以在一定范围内将该工序的人力、物力资源利用到关键工序上去，以达到缩短工程结束时间的目的。,在不影响紧后作业最早开始时间的条件下, 作业最早开工时间可以推迟的时间，称为该工序的单时差。,Ri,j= LFi,jTi,jESi,j,Fi,jmin ESj,kTi,jESi,i,(1)作业的总时差Ri,j,计算公式为：,Ri,j=LFi,jTi,jESi,j,作业E（313）的总时差为：,R3,13=15528,R13,17=172105,R7,9=7430,总时差为0的作业为关键作业,作业E（1317）的总时差为：,作业E（79）的总时差为：,(2) 作业的自由时差Fi,j,计算公式为：,Fi,j= ESj,k Ti,jESi,j,作业E（313）的自由时差为：,F3,13= ES13,17T3,j3ES3,1310523,注：自由时差并不是每个作业有,作业E（515）的自由时差为：,F5,1510136,F7,97430,3、线段时差,两个关键事件之间的一个作业、或两个关键事件之间的几个作业连续相接的连线，称为线段。,R总=max(Ri,j、 Rj,k、 、 Rl,q),R1,17=max(R1,3、 R3,13、 R13,17)= max(1、 8、5)=8,R1,15=max(R1,5、 R5,15)= max(0、6)=6,4、线路时差,线路是指从始点出发，经过连续相接的作业，直到终点的一条连线。,线路1-3-13-17-19-21的线路时差为8,线路时差为0的线路，称为关键线路。是从始点出发，由各个关键作业连续相接，直到终点的线路。,注：关键线路的时差等于0，非关键线路时差通常不计算。,线路1-5-7-9-11-15-17-19-21时差为0，即为关键线路。 ,小结：各时间的计算及标注方法,tLF(i,j),t(i,j),tES(i,j),R(i,j),【例1】下表是某一工程的作业明细表,某一工程的作业时细表,解（1）画出PERT网络图,1,3,2,4,5,6,7,0,0,0,2,6,7.2,9.2,9.2,13.2,17.5,17.5,17.5,17.5,13.5,9.5,13.2,9.2,9.2,7.2,0,（2）计算作业时间和时差,7.5,7.5,7.5,4.5,2.1,0,0,0,0,Ri,j=LFi,jTi,jESi,j,Fi,j=ESj,k Ti,jESi,i,(0),(0),(7.5),(4.5),(2.1),(0),(0),(0),(0),关键路线,ES,LF,练习,1）画出PERT网络图,2）计算作业时间和时差,画出PERT网络图,1,2,4,6,7,8,3,5,a,60,b,45,c,10,d,20,e,40,f,18,g,30,h,15,k,25,l,35,0,1,2,4,6,7,8,3,5,a,60,b,45,c,10,d,20,e,40,f,18,g,30,h,15,k,25,l,35,0,0,60,60,60,60,70,80,110,80,100,135,170,170,135,135,135,135,117,120,120,110,80,60,ES,LF,Ri,j=LFi,jTi,jESi,j,0,30,47,47,0,0,0,20,20,0,Fi,j=ESj,k Ti,jESi,i,(0),(30),(0),(47),(0),(0),(0),(0),(20),(0),二、表格计算形式,三、EXCEL计算形式-同图论中最短线路问题,第三节 网络计划的优化,绘制网络图、计算网络时间和确定关键路线,得到一个初始的计划方案。但通常还要对初始计划方案进行调整和完善。根据计划的要求，综合地考虑进度、资源利用和降低费用等目标，即进行网络优化，确定最优的计划方案。,网络计划的优化包括,时间优化缩短工程时间 改进工艺和技术装备，压缩关键工序的作业时间； 合理组织平行作业、交叉作业， 平行作业指两道以上相互独立的工序同时进行， 交叉作业指将紧前工序完成的部分任务分期分批地转入下道工序。 利用时差，合理调配资源等途径实现。 时间资源优化 优先保证关键路线上关键工序对资源的需求量。 向非关键工序要资源，利用时差调整非关键工序的开工时间，以达到与其它工序在占用资源的时间上错开，拉平资源需要量的高峰。 时间成本优化 在时间进度优化中，重点在于如何缩短工期， 工期的缩短与费用是密切相关的。 网络计划的优化中，应考虑不同的完工时间所对应的工程费用， 找到工程费用最低的完工时间(最低成本日程)。,【例2】如例1中列出的各项作业必须在15小时内结束,1.9,Min2.5，3，2.1=2.1,11.1,15.4,15.4,15.4,15.4,11.1,2.1*3=6.3元,Min0.4，1，4.5=0.4,1.6,8.8,8.8,10.7,15,15.0,15.0,15.0,10.7,8.8,8.8,0.4*4=1.6元,共计7.9元,表格计算形式,练习：,各项作业必须在140小时内结束,(4-6)=Min30，10，20=10,3*10=30元,2.5*1