运筹说 第87期 |
您所在的位置:网站首页 › 运筹网络计划图重点难题有哪些 › 运筹说 第87期 |
一、引例 根据网络图的基本概念和原则绘制出网络图之后,我们可以计算网络图中有关的时间参数,主要目的是找出关键路线,为网络计划的优化、调整和执行提供明确的时间概念。如下图中从始点①到终点⑧共有4条路线,可以分别计算出每条路线所需的总工时。
这4条路线分别为: ①→②→③→⑤→⑧ 4+5+1+3=13(周) ①→②→④→⑥→⑦→⑧ 4+3+4+2+4=17(周) ①→②→⑥→⑦→⑧ 4+2+2+4=12(周) ①→②→③→④→⑥→⑦→⑧ 4+5+2+4+2+4=21(周) 可以看出①→②→③→④→⑥→⑦→⑧所需时间最长,它表明整个任务的总完工期为21周。这条线上的工作,若有一个延迟一周,整个工期就要推迟一周;若某一工作能提前一周,整个任务就可以提前一周完成。而不在这条路上的工作对总工期则没有这种直接影响的关系,如工作②→⑥,可以在①→②工作开始后四周就开始,也可以推迟到l0周、13周(最晚13周)后再开工,都不影响总完工期。 通常把网络图中需时最长的路叫作关键路,在图中用双线箭头⇒画出,关键路线上的工作称为关键工作。要想使任务按期或者提前完工,就要在关键路线的关键工作上想办法。网络图的关键路线可以通过时间参数的计算求得。 二、时间参数 网络图的时间参数包括工作所需时间、事项最早、最迟时间、工作的最早、最迟时间及时差等。进行时间参数计算不仅可以得到关键路线,确定和控制整个任务在正常的进度下的最早完工期,而且在掌握非关键工作的基础上可进行人、财、物等资源的合理安排,进行网络计划的优化。 1、工作时间t(i,j) 工作(i,j)的所需工时可记为t(i,j),有两种确定方法。 (1)确定型 在具备工时定额和劳动定额的任务中,工作的工时t(i,j)可以用这些定额资料确定。有些工作虽无定额可查,但有有关工作的统计资料,也可利用统计资料通过分析来确定工作的工时。 (2)概率型 对于开发性试制性的任务,往往不具备可用的定额资料,难以准确估计工作所需工时,可以采用三点时间估计法来确定工作的工时。这种方法对每道工作先要作出三种情况的时间估计:①a,最快可能完成时间(最乐观时间);②m,最可能完成时间;③b,最慢可能完成时间(最悲观时间)。 利用上述3个时间,可估计每道工作的期望工时: ,方差: 2、事项时间参数 (1)事项的最早时间 事项j的最早时间用tE(j)表示,它表明以它为始点的各工作最早可能开始的时间,也表示以它为终点的各工作的最早可能完成时间(相同),它等于从始点事项到该事项的最长路线上所有工作的工时总和。事项最早时间可用下列递推公式,按照事项编号从小到大的顺序逐个计算。 设总开工事项编号为①。 式中tE(i)表示与事项j相邻的各紧前事项的最早时间。 设终点事项编号为n,则终点事项的最早时间显然就是整个工程的总最早完工期,即:tE(n)为总最早完工期。 (2)事项的最迟时间 事项i的最迟时间用tL(i)表示,它表明在不影响任务总工期条件下,以它为始点的工作的最迟必须开始时间,或以它为终点的各工作的最迟必须完成时间。由于一般情况下,我们都把任务的最早完工时间作为任务的总工期,所以事项最迟时间的计算公式为: 其中tL(i)表示与事项i相邻的各紧后事项的最迟时间。公式(2)也是递推公式,但与(1)式相反,是从终点事项开始,按编号由大至小的顺序逐个由后向前计算。 3、工作的时间参数 (1)工作的最早可能开工时间与工作的最早可能完工时间 一个工作(i,j)的最早可能开工时间用tES(i,j)表示。任何一件工作都必须在其所有紧前工作全部完工后才能开始。工作(i,j)的最早可能完工时间用tEF(i,j)表示。它表示工作按最早开工时间开始所能达到的完工时间。它们的计算公式为: 这组公式也是递推公式。即所有从总开工事项出发的工作(1,j),其最早可能开工时间为零;任一工作(i,j)的最早开工时间要由它的所有紧前工作(k,i)的最早开工时间决定;工作(i,j)的最早完工时间显然等于其最早开工时间与工时之和。 (2)工作的最迟必须开工时间与工作的最迟必须完工时间 工作(i,j)的最迟必须开工时间用tLS(i,j)表示。它表示工作(i,j)在不影响整个任务如期完成的前提下,必须开始的最晚时间。 工作(i,j)的最迟必须完工时间用tLF(i,j)表示。它表示工作(i,j)按最迟时间开工,所能达到的完工时间。它们的计算公式为: 这组公式是按工作的最迟必须开工时间由终点向始点逐个递推的公式。凡是进入总完工事项n的工作(i,n),其最迟完工时间必须等于预定总工期或等于这个工作的最早可能完工时间。任一工作(i,j)的最迟必须开工时间由它的所有紧后工作(j,k)的最迟开工时间确定。而工作(i,j)的最迟完工时间显然等于本工作的最迟开工时间加工时。 由于任一个事项i(除去始点事项和终点事项),既表示某些工作的开始又表示某些工作的结束;所以从事项与工作的关系考虑,有关工作的时间参数也可以通过事项的时间参数来计算。 如工作(i,j)的最早可能开工时间tES(i,j)就等于事项i的最早时间tE(i)。工作(i,j)的最迟必须完工时间等于事项j的最迟时间。 4、时差 工作的时差又叫工作的机动时间或富裕时间,常用的时差有两种。 (1)工作的总时差 在不影响任务总工期的条件下,某工作(i,j)可以延迟其开工时间的最大幅度,叫做该工作的总时差,用R(i,j)表示。其计算公式为: (2)工作的单时差 工作的单时差是指在不影响紧后工作的最早开工时间条件下,此工作可以延迟其开工时间的最大幅度,用r(i,j)表示。其计算公式为: 即单时差等于其紧后工作的最早开工时间与本工作的最早完工时间之差。 (3)工作总时差和单时差的区别与联系 工作总时差和单时差的区别与联系可以通过下图来说明。在图中,工作b与工作c同为工作a的紧后工作。可以看出,工作a的单时差不影响紧后工作的最早开工时间,而其总时差却不仅包括本工作的单时差,而且包括了工作b,c的时差,使工作c失去了部分时差而工作b失去了全部自由机动时间。所以占用一道工序的总时差虽然不影响整个任务的最短工期,却有可能使其紧后工作失去自由机动的余地。 网络中最长的路线就决定了完成整个工程所需的最少时间,这条路线称为关键路线。总时差为0的工序为关键工序。三、确定型网络图时间参数计算 网络图时间参数的计算方法很多,如图上计算法、表上计算法、矩阵法以及使用计算机计算等。下面结合一道例题分别介绍图上计算法和表上计算法。 例题:根据下面的网络图找出关键路线。 1、时间参数的图上计算法 图上计算法的具体步骤如下: (1)计算事项的时间参数 ①事项最早时间计算。事项的最早时间从总开工事项①开始,利用公式(1),在图上由编号小到大逐个计算。 tE(1)=0 tE(2)=0+4=4 tE(3)=4+6=10 tE(4)=max{4+3,10+8}=18 … tE(10)=32 计算原则 所有进到该事项的箭尾最早时间加箭杆上工作时间,取最大。②事项最迟时间计算。事项的最迟时间从总完工事项⑩开始,利用公式(2),在图上由编号大到小逐个计算。当任务给定完工期限时,事项⑩的最迟时间就等于规定期限,否则就等于刚计算出的事项⑩的最早时间32。 tL(10)=32 tL(9)=32-1=31 tL(8)=31-5=26 tL(7)=min{31-8,26-2}=23 … tL(1)=4-4=0 计算原则 所有离开该事项的箭头最迟时间减箭杆上工作时间,取最小。(2)工作时间参数的计算 与计算事项的时间参数类似,先用式(3)从始点开始,逐个计算工作的最早可能开工时间,标入箭杆上方的菱形方框的上半部。然后从终点由后向前按式(4)逐个计算工作最迟必须开工时间,填入菱形方框的下半部。 工作的最早可能开工时间和工作的最迟必须开工时间,这两个一旦算出,那么工作的最早可能完工时间和工作的最迟必须完工时间将很容易算得,下面仅举例算出工作的最早可能开工时间和工作的最迟必须开工时间,如下图所示: 计算原则所有紧前工作的最早开始时间加该工作时间,取最大。所有紧后工作的最晚开始时间减该工作时间,取最小。(3)计算总时差和单时差 工作的总时差就是下图中的下三角减去上三角,标记在图中【】处,单时差利用式(6)计算,标记在图中()处。 由关键路线的意义可知,这条线在时间上没有回旋余地,即每个关键工作应满足“最早开工时间等于最迟必须开工时间”的条件,而非关键工作则有富裕时间。所以总时差为零的工作链就是关键路线。 以总时差为零为依据检查各工作的总时差,得出关键路线如下图所示。 2、时间参数的表上计算法 在网络图上直接计算时间参数,方法简便直观。但是当工作数目多,图形复杂时容易遗漏和出错,故常常采用表格法。表上计算法的具体步骤如下: (1)表上计算首先要列出计算用表,如下表的表头,注意工作的排列应严格按照箭尾事项编号由小到大的顺序排列,箭尾事项相同的工作,按其箭头事项由小到大排列。将已知各工作的工时(第3列)填入表中: (2)计算工作的最早开工时间和最早完工时间,利用公式(3)首先计算出最早开工时间,再用最早开工时间加上工作时间求得最早完工时间,按照由上至下的顺序逐个计算填入表格中的第4列、第5列。 (3)计算并填写工作的最迟开工和最迟完工时间,即表中第6列、第7列,计算和填写顺序是由下至上,利用公式(4)首先计算出最迟完工时间,然后用最迟完工时间减去工作时间得到最迟开工时间。 (4)计算总时差和单时差。第8列总时差可由各工作第6列与第4列上的数相减求得即用公式(5),也可以由第7列与第5列相减求得。第9列单时差是用公式(6)由紧后工作的第4列与该项工作第5列相应数字相减得到。按总时差为0选出关键工作写入第10列,得到关键路线,最终结果如下图。 四、概率型网络图时间参数计算 对于概率型网络图,当求出每道工作的平均期望工时t和方差σ2后,就可以同确定型网络图一样,计算有关时间参数及总完工期TZ。由于它们的工作工时本身包含着随机因素,所以整个任务的总完工期也是个期望工期。它是关键路线上各道工作的平均工时之和TZ =Σt,所以总完工期的方差就是关键路上所有工序的方差之和Σσ2。若工作足够多,每一工作的工时对整个任务的完工期影响不大时,由中心极限定理可知,总完工期服从以TZ为均值,以Σσ2为方差的正态分布。 为达到严格控制工期,确保任务在计划期内完成的目的,我们可以计算在某一给定期限Ts前完工的概率。可以指定多个完工期Ts,直到求得有足够可靠性保证的计划完工期Ts*,将其作为总工期。完工概率求解公式如下: 其中,NTZ,∑σ2 是以TZ为均值,以∑σ2 为均方差的正态分布。 概率型网络图时间参数的计算过程可以总结为以下几个步骤: 1、利用a,m,b求出各项工作的平均工时t和σ; 2、利用确定型网络图的方法,按照t值计算出各工作的最早开工时间、最迟开工时间和时差,确定关键路线和总完工期(期望工期); 3、求出完工概率 与确定型工作时间不同的是,概率型计算出每一事项按期完工概率后,具有较小概率的事项应特别注意,凡是以它为完工时间工作均应加快工作进度。另外,还应注意那些从始点到终点完工日期与总工期相近的次关键路线,计算它们按总工期完工的概率,实施计划时要对其中完工概率较小的一些路线从严控制进度。 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |