《管理运筹学》第12章 排序与统筹方法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,管 理 运 筹 学,管 理 运 筹 学,第十二章 排序与统筹方法,1,车间作业计划模型,2,统筹方法,在本章中，我们将介绍车间作业计划模型和统筹方法。这两个问题尽管处理的方法有所不同，但当我们面临必须完成若干项不能同时进行的工作时，它们都将帮助我们应该按照怎样的次序、怎样的时间表来做这些工作，使得效果最佳（例如完成全部工作所用时间最短或费用最少等等）。,1,1,车间作业计划模型,车间作业计划是指一个工厂生产工序的计划和安排。,一、一台机器、,n,个零件的排序问题,二、两台机器、,n,个零件的排序问题,2,1车间作业计划模型,一、一台机器、,n,个零件的排序问题,例,1.,某车间只有一台高精度的磨床，常常出现很多零件同时要求这台,磨床加工的情况，现有六个零件同时要求加工，这六个零件加工所需时间,如下表所示。,应该按照什么样的加工顺序来加工这六个零件，才能使得这六个零,件在车间里停留的平均时间为最少？,零件,加工时间（小时）,零件,加工时间（小时）,1,2,3,1.8,2.0,0.5,4,5,6,0.9,1.3,1.5,3,1,车间作业计划模型,例,1,解：如果我们用,P,i,表示安排在第,i,位加工的零件所需的时间，用,T,j,表示安排在第,j,位加工的零件在车间里总的停留时间，则有,T,j,=P,1,+,P,2,+,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,个零件的排序问题，只要系数越大，配上加工时间越少的，即按照加工时间排出加工顺序，加工时间越少的零件排在越前面，加工时间越多的零件排在越后面，可使各个零件的平均停留时间为最少。,4,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,5,1,车间作业计划模型,图,121,从上图中我们可以看出，加工时间的延长主要是由于磨床的停工待料,造成的，只要减少磨床的停工待料的时间就能减少整个加工任务的总时间。,为了减少磨床的停工待料，我们应该一方面把在车床上加工时间越短的零,件越早加工，减少磨床等待的时间；另一方面把在磨床上加工时间越长的,零件越晚加工，以便充分利用前面的时间，这样我们就得到了使完成全部,零件加工任务所需总时间最少的零件排序方法。,1,2,3,4,5,1,车床,磨床,2,3,4,5,0,10,6,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,7,同样，下一个最短加工时间为,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,车间作业计划模型,8,2,统筹方法,统筹方法包括绘制计划网络图、进度安排、网络优化等环节，下面进,行分别讨论：,一、计划网络图,统筹方法的第一步工作就是绘制计划网络图，也就是将工序（或称为,活动）进度表转换为统筹方法的网络图。,例,3,、某公司研制新产品的部分工序与所需时间以及它们之间的相互,关系都显示在其工序进度表如表,12-8,所示，请画出其统筹方法网络图。,表,12-8,工序代号,工序内容,所需时间（天,),紧前,工序,a,b,c,d,e,产品设计与工艺设计,外购配套零件,外购生产原料,自制主件,主配可靠性试验,60,15,13,38,8,-,a,a,c,b,d,9,2,统筹方法,解,:,用网络图表示上述的工序进度表,网络图中的点表示一个事件,是一个或若干个工序的开始或结束,是相,邻工序在时间上的分界点,点用圆圈表示,圆圈里的数字表示点的编号。弧,表示一个工序（或活动），弧的方向是从工序开始指向工序的结束，弧上,是各工序的代号，下面标以完成此工序所需的时间（或资源）等数据，即,为对此弧所赋的权数,a,b,c,d,e,60,13,8,38,15,图,12-4,10,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,，,，,11,2,统筹方法,解：我们把工序扩充到图,12-4,发生了问题，由于是的紧前工序，故的结束应该是的开始，所以代表的弧的起点应该是,，由于工序的结束也是,，所以工序也成了工序的紧前工序，与题意不符。,为此我们设立虚工序。虚工序是实际上并不存在而虚设的工序，用来表示相邻工序的衔接关系，不需要人力、物力等资源与时间。,1,5,2,6,4,3,a,60,b,15,8,e,10,13,d,c,38,f,图,12-5,12,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,13,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,14,2,统筹方法,二、网络时间与关键路线,在绘制出网络图之后，我们可以由网络图求出：,1,、完成此工程项目所需的最少时间。,2,、每个工序的开始时间与结束时间。,3,、关键路线及其应用的关键工序。,4,、非关键工序在不影响工程的完成时间的前提下，其开始时间与结束时,间可以推迟多久。,例,5,、某公司装配一条新的生产线，具体过程如表,12-10,求：完成此,工程的最少时间，关键路线及相应的关键工序，各工序的最早开始时间和,非关键工序在不影响工程完成时间的前提下，其开始时间与结束时间可以,推迟多久。,15,2,统筹方法,表,12-10,工序代号,工序内容,所需时间（天）,紧前工序,a,b,c,d,e,f,g,h,ij,生产线设计,外购零配件,下料、锻件,工装制造,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,16,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,17,2,统筹方法,下面我们给出找关键路线的办法,首先，从网络的发点开始，按顺序计算出每个工序的最早开始时间,（,ES),和最早结束时间（,EF),，,设一个工序所需的时间为,t,，,这对于同一,个工序来说，有,EF=,ES+t,。,工序,a,的最早,开始时间,工序,a,的最早,完成时间,1,1,a0，60,60,图,12-9,18,2,统筹方法,图,12-10,其次,从网络的收点开始计算出在不影响整个工程最早结束时间的情,况下各个工序的最晚开始时间,(,缩写为,LS),和最晚结束时间（缩写为,LF),显然对同一工序有,LS=LFt,1,2,3,6,7,8,5,a0,60,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,19,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,105,4590,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,20,2,统筹方法,最后将各工序的时差，以及其他信息构成工序时间表如表,12-11,所,示。,这样就找到了一条由关键工序,a,d,g,i,和,j,依次连接成的从发点到收点的,关键路线。,21,