第十二章:统筹方法.ppt
- 文档编号:18729708
- 上传时间:2023-10-21
- 格式:PPT
- 页数:39
- 大小:1.21MB
第十二章:统筹方法.ppt
《第十二章:统筹方法.ppt》由会员分享,可在线阅读,更多相关《第十二章:统筹方法.ppt(39页珍藏版)》请在冰点文库上搜索。
Chapter12统筹方法(SchedulingMethods),计划网络图网络时间与关键路线完成工序的网络时间与关键路线网络优化,本章主要内容:
2,1956年,美国杜邦公司运用网络计划技术来统筹各项工作,并找出编制与执行计划的关键路线,称为关键路线法(CriticalPathMethod),简称CPM。
1958年,美国海军武器局在制定研制“北极星”导弹计划时,开发出了计划评审技术(ProgramEvaluationandReviewTechnique),简称PERT。
1962年产生了能够体现随机因素作用的图示评审技术(GraphicEvaluationandReviewTechnique),简称GERT。
20世纪70年代,美国G.L.穆勒等人,在GERT基础上提出了风险评审技术(VentureEvaluationReviewTechnique),简称VERT。
这些技术方法均以网络描述工序及工序之间的关系。
统筹方法,3,统筹方法包括绘制计划网络图、进度安排、网络优化等环节,下面进行分别讨论:
一、计划网络图统筹方法的第一步工作就是绘制计划网络图,也就是将工序(或称为活动)进度表转换为统筹方法的网络图。
工序一项需要人力、物力或时间等资源的相对独立的活动过程,又称作业,在网络图中用箭线“”表示,与某道工序前面直接相连的工序称为紧前工序,其后直接相连的后继工序为紧后工序。
计划网络图,4,结点(事件)结点(事件)是相邻工序的分界点,一般用圆圈来表示,每个结点编上顺序号:
箭尾结点表示工序的开始,箭头结点表示工序的完成。
结点(事件)既不消耗人力、物力,也不占用时间。
网络图由工序、事件及时间参数所构成的有向图即为网络图。
用箭线表示工序,结点表示工序间相互关系的网络图,称箭线式网络。
计划网络图,5,例1、某公司研制新产品的部分工序与所需时间以及它们之间的相互关系都显示在其工序进度表如表12-1所示,请画出其统筹方法网络图。
表12-1,计划网络图,6,解:
用网络图表示上述的工序进度表网络图中的点表示一个事件,是一个或若干个工序的开始或结束,是相邻工序在时间上的分界点,点用圆圈表示,圆圈里的数字表示点的编号。
弧表示一个工序(或活动),弧的方向是从工序开始指向工序的结束,弧上是各工序的代号,下面标以完成此工序所需的时间(或资源)等数据,即为对此弧所赋的权数,图12-1,计划网络图,7,例2、把例1的工序进度表做一些扩充,如表12-2,请画出其统筹方法的网络图。
表12-2,计划网络图,8,解:
我们把工序扩充到图12-1发生了问题,由于是的紧前工序,故的结束应该是的开始,所以代表的弧的起点应该是,由于工序的结束也是,所以工序也成了工序的紧前工序,与题意不符。
为此我们设立虚工序。
虚工序是实际上并不存在而虚设的工序,用来表示相邻工序的衔接关系,不需要人力、物力等资源与时间。
a,b,图12-2,计划网络图,a,b,9,在网络图上添加、工序得网络图12-3。
在统筹方法的网络图中不允许两个点之间多于一条弧,因此增加了一个点和虚工序如图12-4。
图12-3,计划网络图,10,在绘制统筹方法的网络图时,要注意图中不能有缺口和回路。
图12-4,计划网络图,11,工序表示的规定:
一条箭线和它的相关事项只能代表一道工序,不能代表多道工序,两个结点之间只能有一条箭线相连。
不允许出现缺口与回路:
网络图中只能有一个始点和一个终点,使得自网络图的始点经由任何路径都可以到达终点。
虚工序:
虚工序是为了表达相邻工序之间的逻辑关系而虚设的工序。
不消耗时间、费用和资源,一般用虚箭线表示。
方向的规定:
网络图是有方向的,工序应按工艺流程顺序或工作的逻辑关系从左向右排列。
编号的规定:
编号应从始结点开始,按照时序依次从小到大对结点编号,直到终结点。
编号时不允许箭头编号小于箭尾编号。
绘制网络图的规则,12,二、网络时间与关键路线(P266)在绘制出网络图之后,我们可以由网络图求出:
1、完成此工程项目所需的最少时间。
2、每个工序的开始时间与结束时间。
3、关键路线及其应用的关键工序。
4、非关键工序在不影响工程的完成时间的前提下,其开始时间与结束时间可以推迟多久。
网络时间与关键路线,13,例5、某公司装配一条新的生产线,具体过程如表12-3,求:
完成此工程的最少时间,关键路线及相应的关键工序,各工序的最早开始时间和非关键工序在不影响工程完成时间的前提下,其开始时间与结束时间可以推迟多久。
(P267)表12-3,14,40,15,解:
据表12-3,绘制网络图如图12-5。
图12-5,如图12-5,-就是一条关键路线,我们要干完所有的工序就必须走完所有这样的路线,由于很多工序可以同时进行,所以网络中最长的路线就决定了完成整个工程所需的最少时间,这条路线称为关键路线。
网络时间与关键路线,15,40,15,下面我们给出找关键路线的办法首先,从网络的发点开始,按顺序计算出每个工序的最早开始时间(ES)和最早结束时间(EF),设一个工序所需的时间为t,这对于同一个工序来说,有EF=ES+t。
网络时间与关键路线,16,其次,从网络的收点开始计算出在不影响整个工程最早结束时间的情况下各个工序的最晚开始时间(缩写为LS)和最晚结束时间(缩写为LF),显然对同一工序有LS=LF-t,图12-7,网络时间与关键路线,17,运用此法则,可以从首点开始计算出每个工序的LF与LS,如图12-8所示。
接着,可以计算出每一个工序的时差,把在不影响工程最早结束时间的条件下,工序最早开始(或结束)的时间可以推迟的时间,成为该工序的时差,对每个工序来说其时差记为Ts有Ts=LS-ES=LF-EF,网络时间与关键路线,18,最后将各工序的时差,以及其他信息构成工序时间表如表12-5所示。
这样就找到了一条由关键工序a,d,g,i和j依次连接成的从发点到收点的关键路线。
网络时间与关键路线,19,三、完成工序所需时间与关键路线当完成工序所需时间不确定的情况下如何求网络时间和关键路线?
例6.长征研究院培训中心负责明年春天的各干部的工商管理培训,培训中心列出有关培训组织的各项活动的信息如表12-6所示,要求绘制出统筹方法的网络图,设法求出网络时间和关键路线,并确定开始这个组织工作的时间以保证培训工作如期举行。
解:
由表12-6,绘出统筹方法的网络图如图12-9所示。
图12-12,完成工序所需时间与关键路线,20,完成工序所需时间与关键路线,21,由于是第一次搞培训,缺乏统计来确定完成每个活动所需时间,但对所需时间做了三种估计:
1.乐观时间。
指所需最少时间,用a表示。
2.最可能时间。
指正常时间,用m表示。
3.悲观时间。
指不顺利情况下,最多时间,用b表示。
如表12-7所示:
表12-7单位:
周,完成工序所需时间与关键路线,22,显然这三种完成活动所需时间都具有一定概率,由经验,我们可以可以假定这些时间的概率分布近似服从分布。
我们可以用如下公式计算出完成活动所需的平均时间:
以及方差:
例如:
完成工作g所需平均时间:
同时求出方差为:
完成工序所需时间与关键路线,23,同样可以求出每个活动的完成所需平均时间及方差,如表12-8:
表12-8,完成工序所需时间与关键路线,24,下面就用平均时间代替完成活动所需时间,并在网络图上标上每个活动最早开始时间和最早结束时间,如图12-10所示。
1,2,3,4,5,8,7,6,同样也可以标上最晚开始时间和最晚完成时间等。
a0,2,g5,9,b2,5,e5,6,d2,4,f6,8,c0,2,i13,15,h9,13,3,2,2,2,1,4,2,4,2,1,2,3,4,5,8,7,6,a0,2,g5,9,b2,5,e5,6,d2,4,f6,8,c0,2,i13,15,h9,13,21,3,110,11,45,9,49,13,23,5,20,2,32,5,213,15,211,13,图12-10,图12-11,完成工序所需时间与关键路线,25,从表12-8上我们找到了一条从发点到收点由关键工序a,b,g,h,i组成的关键路线,用双线标出来。
则完成培训工作所需的平均时间为各关键路线的时间之和:
=2+3+4+4+2=15(周)同时完成时间近似服从一定的概率分布正态分布,则均值为关键路线上各关键活动之均值之和15,方差也为关键路线上各关键活动方差之和1.05。
由此我们可以计算出此项培训组织工作不同完工时间的概率,如16周内完工的概率。
为求此概率,可以先求u值。
式中的T为预定完工时间16,E(T)=15,算得u=0.976。
查正态分布函数表可知概率为0.8355。
即16周内完工的概率为83.55%.,完成工序所需时间与关键路线,26,其正态分布图如图12-12所示:
16,图12-12,完成工序所需时间与关键路线,27,四、网络优化(P275)得到初始的计划方案,但通常要对初始方案进行调整与完善。
根据计划目标,综合考虑资源和降低成本等目标,进行网络优化,确定最优的计划方案。
1.时间-资源优化做法:
1)优先安排关键工序所需的资源。
2)利用非关键工序的时差,错开各工序的开始时间。
3)统筹兼顾工程进度的要求和现有资源的限制,多次综合平衡。
下面列举一个拉平资源需要量最高峰的实例。
在例5中,若加工工人为65人,并假定这些工人可完成这5个工序任一个,下面来寻求一个时间-资源最优方案。
如表12-9所示:
网络优化,28,表12-9,若上述工序都按最早开始时间安排,那么从第60天至第135天的75天里,所需的机械加工工人人数如图12-13所示。
网络优化,29,在图的上半部中,工序代号后的数字是人数,线下面的数字是非关键工序时差长度。
图的下半部表示从第60天至135天内的75天里,所需机械加工工人数,这样的图称为资源负荷图。
2,7,4,6,3,5,f(22人),18,h(39人),15,58人,64人,80人,81人,42人,26人,65人,6080100120130,d(58人),i(26人),g(42人),30,20,25,图12-13,网络优化,30,同时我们应优先安排关键工序所需的工人,再利用非关键工序的时差,错开各工序的开始时间,从而拉平工人需要量的高峰。
经过调整,我们让非关键工序f从第80天开始,工序h从第110天开始。
找到了时间-资源优化的方案,如图12-18所示,在不增加工人的情况下保证了工程按期完成。
2,4,6,7,5,3,f(22人),h(39人),d(58人),i(26人),g(42人),工人数,65人,6080100120130,58人,42人,64人,26人,65人,图12-14,网络优化,31,2.时间-费用优化(P278)需要考虑时间与费用的问题:
在既定的时间前工程完工的前提下,使得所需的费用最少,或者在不超工程预算的条件下使工程最早完工。
这些是时间-费用优化要研究和解决的问题。
直接费用:
为了加快工程进度,需要增加人力、设备和工作班次,这需要增加一笔费用,成为直接费用。
间接费用:
由于工程早日完工,减少了管理人员的工资办公费等费用称为间接费用。
一般说工序越短,直接费用越多,间接费用越少。
网络优化,32,工序的最快完成时间:
指完成时间的最高限度。
我们设完成工序j的正常所需时间为Tj;直接费用为cj;完成工序j的最快完成时间为Tj,直接费用为cj。
这样我们可以计算出缩短工序j的一天工期所增加的直接费用,用kj表示,称为直接费用变动率。
有,时间-费用优化问题可建立两个线性规划模型。
网络优化,33,模型一,在既定的时间T完工的前提下,问各工序的完成时间为多少才使因缩短工期而增加的直接费用最少。
设工序(i,j)的提前完工时间为Yij,我们用Tij,Tij分别表示正常完工时间与最快完工的时间,则有工序(i,j)的实际完工时间为:
Tij-Yij。
我们用Cij,Cij表示用正常完工时间和最快完成时间完成工序所需要的费用,Kij为工序(i,j)的直接费用变动率。
得到这个问题的线性规划模型如下:
minf=(Kij*Yij)(i,j)S.t.Xj-XiTij-Yij,对一切弧(i,j)YijTij-Tij,对一切弧(i,j)Xn-X1T,Xi0,Yij0。
网络优化,34,例7.例5所提供的信息都作为本例的信息,另外还给出了在装配过程中各道工序所需正常完工时间与最快完工时间,以及对应正常完工时间与最快完工时间的所需的直接费用和每缩短一天工期所需增加的直接费用,如表12-10所示。
表12-10,网络优化,35,该工程要求在150天内完工,问每个工序应比正常完工时间提前多少天完成,才能使整个工程因缩短工期而增加的直接费用为最少。
如果工期要求在140天完工呢?
1,2,3,4,5,6,7,8,a,b,f,e,c,h,g,i,j,d,图12-15,网络优化,36,解:
绘出如图12-15所示,根据此网络图建立数学模型。
设此网络图上第i点发生的时间为xi,工序提前完工的时间为yij。
目标函数minf=120y27+300y23+400y24+500y25+230y37+350y46+400y57+290y67.s.t.x2-x160-y12,x7-x245-y27x3-x210-y23x4-x220-y24x5-x240-y25x7-x318-y37x6-x430-y46x5-x40虚拟弧(4,5)x7-x515-y57x7-x625-y67x1=0,y120,网络优化,y2715,y235y2410y255y378y4610y575y780x8150xi0,yij0.(对一切可能的ij)运算得到结果:
f=6400。
网络优化,模型二:
我们知道直接费用是随着完成时间的缩短而增加,而间接费用却会随着完成时间的缩短而减少,设单位时间的间接费用为d,计划期的间接费用与总工期成正比,即为d(xn-x1),那么求使包括间接费用与直接费用在内的总费用最少的整个工程最优完成时间T和各个工序最优完成时间的模型为:
目标函数minf=d(xn-x1)+(Kij*Yij)(i,j)s.t.xj-xiTij-yij,对一切弧(i,j)yijTij-Tij,对一切弧(i,j)xi0,yij0。
37,网络优化,例8如果在例7中,每天的间接费用为330元,求使包括间接费用与直接费用在内的总费用最少的整个工程最优完成时间T和各个工序最优完成间。
解:
决策变量的含义同例7。
此数学模型的目标函数为:
minf=330(x8-x1)+120y27+300y23+400y24+500y25+230y37+350y46+290y67此模型的约束条件与例7的约束条件基本相同,只要在例子的约束条件中去掉x8150就得到了例8模型的约束条件了。
计算得到以下结果f=55700.x1=0,y12=0,y67=10,x2=60,y27=0,y78=0.,38,网络优化,x3=125,y23=0,x4=107,y24=0,x5=110,y25=0,x6=110,y37=0,x7=125,y46=0,x8=160,y57=0,也就是说整个工程工期为160天时总费用最少为55700元,各个工序开始时间如解所示,工序i要提前10天完工,其余的工序按正常时间完工。
39,Thanks!
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第十二 统筹 方法