大学运筹学经典课件第十二章——排序与统筹方法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,管 理 运 筹 学,1,第十二章 排序与统筹方法,1,车间作业计划模型,2,统筹方法,在本章中，我们将介绍车间作业计划模型和统筹方法。这两个问题尽管处理的方法有所不同，但当我们面临必须完成若干项不能同时进行的工作时，它们都将帮助我们应该按照怎样的次序、怎样的时间表来做这些工作，使得效果最佳（例如完成全部工作所用时间最短或费用最少等等）。,2,1,车间作业计划模型,车间作业计划是指一个工厂生产工序的计划和安排。,一、一台机器、,n,个零件的排序问题,二、两台机器、,n,个零件的排序问题,3,1,车间作业计划模型,一、一台机器、,n,个零件的排序问题,例,1.,某车间只有一台高精度的磨床，常常出现很多零件同时要求这台,磨床加工的情况，现有六个零件同时要求加工，这六个零件加工所需时间,如下表所示。,应该按照什么样的加工顺序来加工这六个零件，才能使得这六个零,件在车间里停留的平均时间为最少？,零件,加工时间（小时）,零件,加工时间（小时）,1,2,3,1.8,2.0,0.5,4,5,6,0.9,1.3,1.5,4,1,车间作业计划模型,例,1,解：如果我们用,P,i,表示安排在第,i,位加工的零件所需的时间，用,T,j,表示安排在第,j,位加工的零件在车间里总的停留时间，则有,T,j,=,P,1,+,P2,+,P,j-1,+,P,j,=,不同的加工顺序得到不同的各零件的平均停留时间，如何得到一个使得各零件的平均停留时间最少的排序呢？这就是我们最后要解决的优化问题，而且我们要设法找到一种简便的算法。,对于某种加工顺序，我们知道安排在第,j,位加工的零件在车间里总的停留时间为,T,j,，,T,j,=,可知这六个零件的停留时间为：,T,1,+,T,2,+,T,3,+,T,4,+,T,5,+,T,6,P,1,+(,P,1,+,P,2,)+(,P,1,+,P,2,+,P,3,)+(,P,1,+,P,2,+,P,3,+,P,4,)+,(,P,1,+,P,2,+,P,3,+,P,4,+,P,5,)+(,P,1,+,P,2,+,P,3,+,P,4,+,P,5,+,P,6,),6,P,1,+5,P,2,+4,P,3,+3,P,4,+2,P,5,+,P,6,.,那么各个零件平均停留时间为,从上式可知，对于一台机器,n,个零件的排序问题，只要系数越大，配上加工时间越少的，即按照加工时间排出加工顺序，加工时间越少的零件排在越前面，加工时间越多的零件排在越后面，可使各个零件的平均停留时间为最少。,5,1,车间作业计划模型,二、两台机器、,n,个零件,例,2.,某工厂根据合同定做一些零件，这些零件要求先在车床上车削，然后再在,磨床上加工，每台机器上各零件加工时间如表,12-5,所示。,表,12-5,应该如何安排这五个零件的先后顺序才能使完成这五个零件的总的加工时间为,最少？,解：由于每个零件必须先进行车床加工，再进行磨床加工，所以在车床上加,工零件的顺序与在磨床上加工零件的顺序是一样的。,如果这些零件在车床上和磨床上加工顺序都为,1,，,2,，,3,，,4,，,5,。我们用图,12-1,中的线条图来表示各零件加工的开始时间与完成时间，这种图是由一根时间轴和,车床、磨床在每个时间段的状况的图形所构成。,零件,车床,磨床,零件,车床,磨床,1,2,3,1.5,2.0,1.0,0.5,0.25,1.75,4,5,1.25,0.75,2.5,1.25,6,1,车间作业计划模型,图,12-1,从上图中我们可以看出，加工时间的延长主要是由于磨床的停工待料,造成的，只要减少磨床的停工待料的时间就能减少整个加工任务的总时间。,为了减少磨床的停工待料，我们应该一方面把在车床上加工时间越短的零,件越早加工，减少磨床等待的时间；另一方面把在磨床上加工时间越长的,零件越晚加工，以便充分利用前面的时间，这样我们就得到了使完成全部,零件加工任务所需总时间最少的零件排序方法。,1,2,3,4,5,1,车床,磨床,2,3,4,5,0,10,7,1,车间作业计划模型,寻找例,2,的最优解：我们在表,12-5,中找到所列出的最短加工时间是,0.25,它是第二道工序磨床,加工零件,2,的所需时间，由于这个时间与磨床有关故我们把零件,2,放在加工顺序的末尾，即第五,位，并在表中划去零件,2,所在行。如表,12-6,中红色线条所示。,接着，我们又找到最短加工时间为,0.5,，这一时间与磨床（第二工序）有关，我们把 磨床加,工时间为,0.5,的零件,1,放到除第五外的加工顺序的末尾，即第四位加工，同时把 表中的零件,1,所在,的行划去。如表,12-6,中黄色线条所示。,下一个最短加工时间为,0.75,，这个加工时间是车床（第一工序）加工零件,5,的所需时间，故,把零件,5,排在加工顺序的第一位上，同时把表中的零件,5,所在的行划去。如表,12-6,中蓝色线条所,示。,零件,车床,（第一工序）,磨床,（第二工序）零件,车床,（第一工序）,磨床,（第二工序）,1,2,3,1.5,2.0,1.0,0.5,0.25,1.75,4,5,1.25,0.75,2.5,1.25,表,12-6,8,同样，下一个最短加工时间为,1,，这是车床加工零件,3,的所需时间，故,把零件,3,排在第二位上，同时把零件,3,所在的行划去。如表,12-6,中黑色线条,所示。,这样就得到了最优加工顺序：,5,，,3,，,4,，,1,，,2,。一共只需,7,个小时就能,完成全部加工。,从例,2,中我们可以归纳出关于两台机器,n,个零件的排序问题，使得全部,任务总的时间 最短的排序算法。,在加工所需时间表上选出最短加工时间,t,ij,，这是第,i,工序加工,j,零件所需,时间，当,i,=1,时，将零件,j,的顺序尽量靠前，若,i,=2,时，将零件,j,的顺序尽量,靠后。在表上划去零件,j,的所在行，回到步骤,1,。,1,车间作业计划模型,9,2,统筹方法,统筹方法包括绘制计划网络图、进度安排、网络优化等环节，下面进,行分别讨论：,一、计划网络图,统筹方法的第一步工作就是绘制计划网络图，也就是将工序（或称为,活动）进度表转换为统筹方法的网络图。,例,3,、某公司研制新产品的部分工序与所需时间以及它们之间的相互,关系都显示在其工序进度表如表,12-8,所示，请画出其统筹方法网络图。,表,12-8,工序代号,工序内容,所需时间（天),紧前工序,a,b,c,d,e,产品设计与工艺设计,外购配套零件,外购生产原料,自制主件,主配可靠性试验,60,15,13,38,8,-,a,a,c,b,d,10,2,统筹方法,解,:,用网络图表示上述的工序进度表,网络图中的点表示一个事件,是一个或若干个工序的开始或结束,是相,邻工序在时间上的分界点,点用圆圈表示,圆圈里的数字表示点的编号。弧,表示一个工序（或活动），弧的方向是从工序开始指向工序的结束，弧上,是各工序的代号，下面标以完成此工序所需的时间（或资源）等数据，即,为对此弧所赋的权数,a,b,c,d,e,60,13,8,38,15,图,12-4,11,2,统筹方法,例、把例的工序进度表做一些扩充，如表,12-9,，请画出其统筹方法的网络图。,表,12-9,工序代号,所需时间（天）,紧前工序,工序代号,所需时间（天）,紧前工序,a,b,c,d,60,15,13,38,a,a,c,e,f,g,h,8,10,16,5,b,，,d,d,e,，,12,2,统筹方法,解：我们把工序扩充到图,12-4,发生了问题，由于是的紧前工序，故的结束应该是的开始，所以代表的弧的起点应该是，由于工序的结束也是，所以工序也成了工序的紧前工序，与题意不符。,为此我们设立虚工序。虚工序是实际上并不存在而虚设的工序，用来表示相邻工序的衔接关系，不需要人力、物力等资源与时间。,1,5,2,6,4,3,a60,b,15,8,e,10,13,d,c,38,f,图,12-5,13,2,统筹方法,在网络图上添加、工序得网络图,12-6,。,在统筹方法的网络图中不允许两个点之间多于一条弧，因此增加了一个点和虚工序如图,12-7,。,1,2,5,6,7,3,4,a,60,15,b,e,c,13,d,38,8,h,5,10,f,g,16,图,12-6,14,2,统筹方法,在绘制统筹方法的网络图时，要注意图中不能有缺口和回路,。,1,2,5,7,8,3,4,a,60,15,b,e,c,13,d,38,8,h,5,10,f,6,16,g,图,12-7,15,2,统筹方法,二、网络时间与关键路线,在绘制出网络图之后，我们可以由网络图求出：,1,、完成此工程项目所需的最少时间。,2,、每个工序的开始时间与结束时间。,3,、关键路线及其应用的关键工序。,4,、非关键工序在不影响工程的完成时间的前提下，其开始时间与结束时,间可以推迟多久。,例,5,、某公司装配一条新的生产线，具体过程如表,12-10,求：完成此,工程的最少时间，关键路线及相应的关键工序，各工序的最早开始时间和,非关键工序在不影响工程完成时间的前提下，其开始时间与结束时间可以,推迟多久。,16,2,统筹方法,表,12-10,工序代号,工序内容,所需时间（天）,紧前工序,a,b,c,d,e,f,g,h,i,j,生产线设计,外购零配件,下料、锻件,工装制造,1,木模、铸件,机械加工,1,工装制造,2,机械加工,2,机械加工,3,装配调试,60,45,10,20,40,18,30,15,25,35,/,a,a,a,a,c,d,d,e,g,b,i,f,h,17,2,统筹方法,解：据表,12-10,绘制网络图如图,12-8,。,图,12-8,如图,12-8,-,就是一条关键路线，我们要干完所有的工序,就必须走完所有这样的路线，由于很多工序可以同时进行，所以网络中最,长的路线就决定了完成整个工程所需的最少时间，这条路线称为关键路,线。,1,2,3,4,6,7,8,5,a,60,b,45,e,c,h,j,35,i,g,10,30,d,20,40,25,f,18,15,18,2,统筹方法,下面我们给出找关键路线的办法,首先，从网络的发点开始，按顺序计算出每个工序的最早开始时间,（,ES),和最早结束时间（,EF),，设一个工序所需的时间为,t,，这对于同一,个工序来说，有,EF=ES+t,。,工序,a,的最早,开始时间,工序,a,的最早,完成时间,1,1,a0,，,60,60,图,12-9,19,2,统筹方法,图,12-10,其次,从网络的收点开始计算出在不影响整个工程最早结束时间的情,况下各个工序的最晚开始时间,(,缩写为,LS),和最晚结束时间（缩写为,LF),显然对同一工序有,LS=LF-t,1,2,3,6,7,8,5,a060,60,b60,105,45,e60.100,c60,70,h100,115,j135,170,35,i110.135,g80,110,30,d60.80,20,40,25,f70,88,18,4,10,15,20,2,统筹方法,运用此法则，可以从首点开始计算出每个工序的,LF,与,LS,，如图,12-11,所示。,接着，可以计算出每一个工序的时差，把在不影响工程最早结束时间,的条件下，工序最早开始（或结束）的时间可以推迟的时间，成为该工序,的时差，对每个工序来说其时差记为,T,s,有,T,s,=LS-ES=LF-EF,1,2,3,6,7,8,5,a0,60,600,60,b60,1054590,135,e60.100,c60,70,h100,115,j135,170,35135,170,i110.135,g80,110,3080,110,d60.80,2060,80,4080,120,25110,135,f70,88,18117,135,4,10107,117,15120,135,21,2,统筹方法,最后将各工序的时差，以及其他信息构成工序时间表如表,12-11,所,示。,这样就找到了一条由关键工序,a,d,g,i,和,j,依次连接成的从发点到收点的,关键路线。,22,三、完成工序所需时间与关键路线,当完成工序所需时间不确定的情况下如何求网络时间和关键路线？,例,6.,长征研究院培训中心负责明年春天的各干部的工商管理培训，培训中心列出有关培训组织的各项活动的信息如表,12-12,所示，要求绘制出统筹方法的网络图，设法求出网络时间和关键路线，并确定开始这个组织工作的时间以保证培训工作如期举行。,解：由表,12-12,，绘出统筹方法的网络图如图,12-12,所示。,1,2,3,5,6,4,8,7,a,b,e,c,d,f,g,h,i,图,12-12,2,统筹方法,23,2,统筹方法,活动（工序）,活动（工序）内容,紧前活动（工序）,a,b,c,d,e,f,g,h,i,制定培训计划,选聘培训教师,列出一些可供选择的培训地点,确定培训地点,确定培训的日程安排,落实教学设备，器材，资料,发培训通知并确定学员名单,订旅馆房间,处理最后的一些事务,-,a,-,c,b,d,e,b,d,g,f,g,24,2,统筹方法,由于是第一次搞培训，缺乏统计来确定完成每个活动所需时间，,但对所需时间做了三种估计：,1.,乐观时间。指所需最少时间，用,a,表示。,2.,最可能时间。指正常时间，用,m,表示。,3.,悲观时间。指不顺利情况下，最多时间，用,b,表示。如表,12-13,所示：,表,12-13,单位：周,活动,乐观时间,最可能时间,悲观时间,a,b,c,d,e,f,g,h,i,1.5,2.0,1.0,1.5,0.5,1.0,3.0,3.0,1.5,2.0,2.5,2.0,2.0,1.0,2.0,3.5,4.0,2.0,2.5,6.0,3.0,2.5,1.5,3.0,7.0,5.0,2.5,25,2,统筹方法,显然这三种完成活动所需时间都具有一定概率，由经验，我们可以,可以假定这些时间的概率分布近似服从 分布。我们可以用如下公式计,算出完成活动所需的平均时间：,以及方差,例如：完成工作,g,所需平均时间：,同时求出方差为,26,2,统筹方法,同样可以求出每个活动的完成所需平均时间及方差，如表,12-14,：,表,12-14,活动,T,（平均时间）,方差,活动,T,方差,a,2,0.028,f,2,0.111,b,3,0.445,g,4,0.445,c,2,0.111,h,4,0.111,d,2,0.028,i,2,0.028,e,1,0.028,27,2,统筹方法,下面就用平均时间代替完成活动所需时间，并在网络图上标上每个活,动最早开始时间和最早结束时间，如图,12-14,所示。,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,4913,23,5,20,2,32,5,213,15,211,13,图,12-14,图,12-15,28,2,统筹方法,从表,12-15,上我们找到了一条从发点到收点由关键工序,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%.,29,2,统筹方法,其正态分布图如图,12-16,所示：,16,图,12-16,30,2,统筹方法,四、网络优化,得到初始的计划方案，但通常要对初始方案进行调整与完善。根据计,划目标，综合考虑资源和降低成本等目标，进行网络优化，确定最优的计,划方案。,1.,时间,-,资源优化,做法：,1,）优先安排关键工序所需的资源。,2,）利用非关键工序的时差，错开各工序的开始时间。,3,）统筹兼顾工程进度的要求和现有资源的限制，多次综合平衡。,下面列举一个拉平资源需要量最高峰的实例。在例,5,中，若加工工人,为,65,人，并假定这些工人可完成这,5,个工序任一个，下面来寻求一个时间,-,资源最优方案。如表,12-16,所示：,31,2,统筹方法,表,12-16,工序,需要人数,最早开始时间,所需时间,时差,d,58,60,20,0,f,22,70,18,47,g,42,80,3,0,h,39,100,15,20,i,26,110,25,0,若上述工序都按最早开始时间安排，那么从第,60,天至第,135,天的,75,天里，所需的机械加工工人人数如图,12-17,所示。,32,2,统筹方法,在图的上半部中，工序代号后的数字是人数，线下面的数字是非关键,工序时差长度。图的下半部表示从第,60,天至,135,天内的,75,天里，所需机械,加工工人数，这样的图称为资源负荷图。,2,7,4,6,3,5,f(22,人）,18,h(39,人,),15,58,人,64,人,80,人,81,人,42,人,26,人,65,人,60 80 100 120 130,d(58,人）,i(26,人）,g(42,人）,30,20,25,图,12-17,33,2,统筹方法,同时我们应优先安排关键工序所需的工人，再利用非关键工序的时,差，错开各工序的开始时间，从而拉平工人需要量的高峰。经过调整，我,们让非关键工序,f,从第,80,天开始，工序,h,从第,110,天开始。找到了时间,-,资源,优化的方案，如图,12-18,所示，在不增加工人的情况下保证了工程按期完,成。,2,4,6,7,5,3,f(22,人）,h(39,人）,d(58,人）,i(26,人）,g(42,人）,工人数,65,人,60 80 100 120 130,58,人,42,人,64,人,26,人,65,人,图,12-18,34,2,统筹方法,2.,时间,-,费用优化,需要考虑时间与费用的问题：在既定的时间前工程完工的前提下，使,得所需的费用最少，或者在不超工程预算的条件下使工程最早完工。这些,是时间,-,费用优化要研究和解决的问题。,直接费用：为了加快工程进度，需要增加人力、设备和工作班次，这,需要增加一笔费用，成为直接费用。,间接费用：由于工程早日完工，减少了管理人员的工资办公费等费用,称为间接费用。一般说工序越短，直接费用越多，间接费用越少。,35,2,统筹方法,工序的最快完成时间：指完成时间的最高限度。,我们设完成工序,j,的正常所需时间为,T,j,;,直接费用为,c,j,;,完成工序,j,的最快完成时,间为,T,j,直接费用为,c,j,。这样我们可以计算出缩短工序,j,的一天工期所增加的直接,费用，用,k,j,表示，称为直接费用变动率。有,时间,-,费用优化问题可建立两个线性规划模型。,模型一，在既定的时间,T,完工的前提下，问各工序的完成时间为多少才使因,缩短工期而增加的直接费用最少。,设工序（,i,j),的提前完工时间为,Y,ij,我们用,T,ij,T,ij,分别表示正常完工时间与最快,完工的时间，则有工序（,i,j),的实际完工时间为：,T,ij,-Y,ij,。我们用,C,ij,C,ij,表示用正,常完工时间和最快完成时间完成工序所需要的费用，,K,ij,为工序（,i,j),的直接费用,变动率。得到这个问题的线性规划模型如下：,minf=,（,K,ij,*Y,ij,),（,i,j),S.t.X,j,-X,i,T,ij,-Y,ij,对一切弧（,i,j),Y,ij,T,ij,-T,ij,对一切弧（,i,j),X,n,-X,1,T,X,i,0,，,Y,ij,0,。,36,2,统筹方法,例,7.,例,5,所提供的信息都作为本例的信息，另外还给出了在装配过程中各道工序所需正常完工时间与最快完工时间，以及对应正常完工时间与最快完工时间的所需的直接费用和每缩短一天工期所需增加的直接费用，如表,12-17,所示。,表,12-17,工序,T,ij,正常完工,C,ij,直接费用,T,ij,最快完工,C,ij,直接费用,直接费用变动率,a,60,10000,60,10000,-,b,45,4500,30,6300,120,c,10,2800,5,4300,300,d,20,7000,10,11000,400,e,40,10000,35,12500,500,f,18,3600,10,5440,230,g,30,9000,20,12500,350,h,15,3750,10,5750,400,i,25,6250,15,9150,290,j,35,12000,35,12000,-,37,2,统筹方法,该工程要求在,150,天内完工，问每个工序应比正常完工时间提前多少天,完成，才能使整个工程因缩短工期而增加的直接费用为最少。如果工期要,求在,140,天完工呢？,1,2,3,4,5,6,7,8,a,b,f,e,c,h,g,i,j,d,图,12-19,38,2,统筹方法,解：绘出如图,12-19,所示，根据此网络图建立数学模型。,设此网络图上第,i,点发生的时间为,x,i,，工序提前完工的时间为,y,ij,。,目标函数,minf=120y,27,+300y,23,+400y,24,+500y,25,+230y,37,+350y,46,+400y,57,+290y,67,.,s.t.x,2,-x,1,60-y,12,x,7,-,x,2,45-,y,27,x,3,-x,2,10-,y,23,x,4,-x,2,20-,y,24,x,5,-x,2,40-,y,25,x,7,-x,3,18-,y,37,x,6,-x,4,30-,y,46,x,5,-x,4,0,虚拟弧（,4,，,5,）,x,7,-x,5,15-,y,57,x,7,-x,6,25-,y,67,39,2,统筹方法,x,1,=0,y,12,0,y,27,15,y,23,5,y,24,10,y,25,5,y,37,8,y,46,10,y,57,5,y,78,0,x,8,150,x,i,0,，,y,ij,0.,（对一切可能的,ij),运算得到结果：,f=6400,。,40,2,统筹方法,模型二，我们知道直接费用是随着完成时间的缩短而增加，而间接费用却会随着完成时间的缩短而减少，设单位时间的间接费用为,d,计划期的间接费用与总工期成正比，即为,d(x,n,-x,1,),那么求使包括间接费用与直接费用在内的总费用最少的整个工程最优完成时间,T,和各个工序最优完成时间的模型为：,目标函数,min f=d(x,n,-x,1,)+,s.t.x,j,-x,i,T,ij,-y,ij,，对一切弧（,i,j),y,ij,T,ij,-T,ij,，对一切弧（,i,j),x,i,0,，,y,ij,0,。,41,2,统筹方法,例,8,如果在例,7,中，每天的间接费用为,330,元，求使包括间接费用与直接费,用在内的总费用最少的整个工程最优完成时间,T,和各个工序最优完成时间。,解：决策变量的含义同例,7,。,此数学模型的目标函数为：,min f=330(x,8,-x,1,)+120,y,27,+300,y,23,+400,y,24,+500,y,25,+230,y,37,+350,y,46,+290y,67,此模型的约束条件与例,7,的约束条件基本相同，只要在例子的约束条件中去,掉,x,8,150,就得到了例,8,模型的约束条件了。,计算得到以下结果：,f=55700.,x,1,=0,y,12,=0,y,67,=10,x,2,=60,y,27,=0,y,78,=0.,42,2,统筹方法,x,3,=125,y,23,=0,x,4,=107,y,24,=0,x,5,=110,y,25,=0,x,6,=110,y,37,=0,x,7,=125,y,46,=0,x,8,=160,y,57,=0,也就是说整个工程工期为,160,天时总费用最少为,55700,元，各个,工序开始时间如解所示，工序,i,要提前,10,天完工，其余的工序按正,常时间完工。,