第9章 排序与统筹方法（课堂PPT）

1,第九章排序与统筹方法,运筹学,广东外语外贸大学,GuangdongUniversityofForeignStudies,2,第九章排序与统筹方法,第一节车间作业计划模型第二节统筹方法,在本章中，我们将介绍车间作业计划模型和统筹方法。这两个问题尽管处理的方法有所不同，但当我们面临必须完成若干项不能同时进行的工作时，它们都将帮助我们应该按照怎样的次序、怎样的时间表来做这些工作，使得效果最佳（例如完成全部工作所用时间最短或费用最少等等）。,3,1车间作业计划模型,车间作业计划是指一个工厂生产工序的计划和安排。一、一台机器、n个零件的排序问题二、两台机器、n个零件的排序问题,4,一、一台机器、n个零件的排序问题例1.某车间只有一台高精度的磨床，常常出现很多零件同时要求这台磨床加工的情况，现有六个零件同时要求加工，这六个零件加工所需时间如下表所示。应该按照什么样的加工顺序来加工这六个零件，才能使得这六个零件在车间里停留的平均时间为最少？,1车间作业计划模型,5,例1解：如果我们用Pi表示安排在第i位加工的零件所需的时间，用Tj表示安排在第j位加工的零件在车间里总的停留时间，则有Tj=P1+P2+Pj-1+Pj=不同的加工顺序得到不同的各零件的平均停留时间，如何得到一个使得各零件的平均停留时间最少的排序呢？这就是我们最后要解决的优化问题，而且我们要设法找到一种简便的算法。对于某种加工顺序，我们知道安排在第j位加工的零件在车间里总的停留时间为Tj，Tj=,1车间作业计划模型,6,可知这六个零件的停留时间为：T1+T2+T3+T4+T5+T6P1+(P1+P2)+(P1+P2+P3)+(P1+P2+P3+P4)+(P1+P2+P3+P4+P5)+(P1+P2+P3+P4+P5+P6)6P1+5P2+4P3+3P4+2P5+P6.那么各个零件平均停留时间为,从上式可知，对于一台机器n个零件的排序问题，只要系数越大，配上加工时间越少的，即按照加工时间排出加工顺序，加工时间越少的零件排在越前面，加工时间越多的零件排在越后面，可使各零件的平均停留时间最少。,1车间作业计划模型,7,二、两台机器、n个零件例2.某工厂根据合同定做一些零件，这些零件要求先在车床上车削，然后再在磨床上加工，每台机器上各零件加工时间如下表所示。应该如何安排这五个零件的先后顺序才能使完成这五个零件的总的加工时间为最少？,1车间作业计划模型,8,解：由于每个零件必须先进行车床加工，再进行磨床加工，所以在车床上加工零件的顺序与在磨床上加工零件的顺序是一样的。如果这些零件在车床上和磨床上加工顺序都为1，2，3，4，5。我们用图12-1中的线条图来表示各零件加工的开始时间与完成时间，这种图是由一根时间轴和车床、磨床在每个时间段的状况的图形所构成。,1车间作业计划模型,图12-1从上图中我们可以看出，加工时间的延长主要是由于磨床的停工待料造成的，只要减少磨床的停工待料的时间就能减少整个加工任务的总时间。为了减少磨床的停工待料，我们应该一方面把在车床上加工时间越短的零件越早加工，减少磨床等待的时间；另一方面把在磨床上加工时间越短的零件越晚加工，以便充分利用前面的时间，这样我们就得到了使完成全部零件加工任务所需总时间最少的零件排序方法。,1.5,2.0,1.0,1.25,0.75,0.5,0.25,1.75,2.5,1.25,9,10,寻找例2的最优解：我们在上表中找到所列出的最短加工时间是0.25,它是第二道工序磨床加工零件2的所需时间，由于这个时间与磨床有关，故我们把零件2放在加工顺序的末尾，即第五位，并在表中划去零件2所在行。如表中红色线条所示。,1车间作业计划模型,11,接着，我们又找到最短加工时间为0.5，这一时间与磨床（第二工序）有关，我们把磨床加工时间为0.5的零件1放到除第五外的加工顺序的末尾，即第四位加工，同时把表中的零件1所在的行划去。如表中黄色线条所示。,1车间作业计划模型,12,下一个最短加工时间为0.75，这个加工时间是车床（第一工序）加工零件5的所需时间，故把零件5排在加工顺序的第一位上，同时把表中的零件5所在的行划去。如表中蓝色线条所示。,1车间作业计划模型,13,同样，下一个最短加工时间为1，这是车床加工零件3的所需时间，故把零件3排在第二位上，同时把零件3所在的行划去。如表中黑色线条所示。,1车间作业计划模型,14,这样就得到了最优加工顺序：5，3，4，1，2。,0.75,1.0,1.25,1.5,2.0,1.25,1.75,2.5,0.5,0.25,5,磨床,车床,3,4,1,2,5,3,4,1,2,7,这样一共只需7个小时就能完成全部加工。,1车间作业计划模型,15,从例2中我们可以归纳出关于两台机器n个零件的排序问题，使得全部任务总的时间最短的排序算法。步骤1:在加工所需时间表上选出最短加工时间tij，这是第i工序加工j零件所需时间，步骤2:当i=1时，将零件j的顺序尽量靠前，若i=2时，将零件j的顺序尽量靠后。步骤3:在表上划去零件j的所在行，回到步骤1。,1车间作业计划模型,16,思考题：m台机器n个零件的排序问题如何解决？,1车间作业计划模型,17,2统筹方法,统筹法又称网络计划法。它是以网络图反映、表达计划安排，据以选择最优工作方案，组织协调和控制生产（项目）的进度（时间）和费用（成本），使其达到预定目标，获得更佳经济效益的一种优化决策方法。1957年，美国化学公司DuPont的M.R.Walker与Rand通用电子计算机公司的J.E.Kelly为了协调公司内部不同业务部门的工作,共同研究出关键路线方法（简记作CPM）.首次把这一方法用于一家化工厂的筹建，结果筹建工程提前两个月完成.随后又把这一方法用于工厂的维修，结果使停工时间缩短了47个小时，当年就取得节约资金达百万元的要观效益。,1958年，美国海军武器规划局特别规划室研制含约3000项工作任务的北极星导弹潜艇计划，参与的厂商达11000多家。为了有条不紊地实施如此复杂的工作，特别规划室领导人W.Fazar积极支持与推广由专门小组创建的计划评审技术（简记作PERT）。结果研制计划提前两个完成，取得了极大的成功。CPM在民用企业与PERT在军事工业中的显著成效,自然引起了普遍的重视。很快CPM与PERT就被应用于工业、农业、国防与科研等等复杂的计划管理工作中,随后又推广到世界各国。在应用推广CPM与PERT的过程中,又派生出多种各具特点，各有侧重的类似方法。但是万变不离其宗，各种有所不同的方法，其基本原理都源于CPM与PERT。,18,19,CPM与PERT两种方法实质上大同小异，因此，人们把CPM与PERT及其他类似方法统称为网络计划技术，简称为网络技术或网络方法，简记为统筹法。统筹方法包括绘制计划网络图、进度安排、网络优化等环节，下面进行分别讨论：一、计划网络图统筹方法的第一步工作就是绘制计划网络图，也就是将工序（或称为活动）进度表转换为统筹方法的网络图。,2统筹方法,20,网络图画法,(一)、结构网络图中的点表示一个事件,是一个或若干个工序的开始或结束,是相邻工序在时间上的分界点,点用圆圈表示,圆圈里的数字表示点的编号。弧表示一个工序（或活动），弧的方向是从工序开始指向工序的结束，弧上是各工序的代号，下面标以完成此工序所需的时间（或资源）等数据，即为对此弧所赋的权数。例如：,5,a,1,2,2统筹方法,21,(二)、画法注意事项：,(1)、从左右,2统筹方法,22,(2)、两事项间只有一个工序,2统筹方法,23,(3)、不允许回路,2统筹方法,24,正确表达工序的前行、后续关系(连结、隔离),解决画法中问题：网络图中只有一个始点和一个终点，中间点前后均要有弧相连接，不允许中断。,2统筹方法,25,2统筹方法,26,2统筹方法,27,例1、假设某工作有a,b,c,d四个工序,c在a,b完工后开始，d在b完工后开始。,2统筹方法,28,例3、某公司研制新产品的部分工序与所需时间以及它们之间的相互关系都显示在其工序进度表如表12-8所示，请画出其统筹方法网络图。,2统筹方法,29,解：用网络图表示上述的工序进度表。,a,b,c,d,e,60,13,8,38,15,2统筹方法,30,例、把例的工序进度表做一些扩充，如下表，请画出其统筹方法的网络图。,2统筹方法,31,1,5,2,6,4,3,a,60,b,15,8,e,10,13,d,c,38,f,7,g,16,8,由于是的紧前工序，故的结束应该是的开始，所以代表的弧的起点应该是，由于工序的结束也是，所以工序也成了工序的紧前工序，与题意不符。,为此我们设立虚工序。虚工序是实际上并不存在而虚设的工序，用来表示相邻工序的衔接关系，不需要人力、物力等资源与时间。,2统筹方法,32,1,5,2,6,4,3,a,60,b,15,8,e,10,13,d,c,38,f,g,16,在统筹方法的网络图中不允许两个点之间多于一条弧，因此需增加一个点和虚工序,2统筹方法,33,1,5,2,6,4,3,a,60,b,15,8,e,10,13,d,c,38,f,7,16,g,8,h,5,在绘制统筹方法的网络图时，要注意图中不能有缺口和回路。,2统筹方法,练习,34,35,2统筹方法,36,二、网络时间与关键路线路线：在网络图上从始点（发点）开始，沿弧的方向（即按各工序的顺序）连续不断地到终点（收点）的一条路线。例如：,2统筹方法,37,关键路线：网络中最长的路线，通常可用双线标出。关键路线的长等于该路线上各工序的时间之和，又称为工程时间或工期，其它路线称为非关键路线。关键（非关键）工序：关键路线上的各工序，其它工序称为非关键工序。,工期T18,2统筹方法,38,显然，缩短工期就是要缩短关键路线的长度，也就是说要加快关键工序的进度。而缩短非关键路线的长度或缩短非关键工序的时间均不能缩短工期。,工期T18,2统筹方法,39,在绘制出网络图之后，我们可以由网络图求出：1、完成此工程项目所需的最少时间。2、每个工序的开始时间与结束时间。3、关键路线及其应用的关键工序。4、非关键工序在不影响工程的完成时间的前提下，其开始时间与结束时间可以推迟多久。例5、某公司装配一条新的生产线，具体过程如下表,求：完成此工程的最少时间，关键路线及相应的关键工序，各工序的最早开始时间和非关键工序在不影响工程完成时间的前提下，其开始时间与结束时间可以推迟多久。,2统筹方法,40,2统筹方法,41,解：据表绘制网络图如图。,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,如图,-就是一条关键路线，我们要干完所有的工序就必须走完所有这样的路线，由于很多工序可以同时进行，所以网络中最长的路线就决定了完成整个工程所需的最少时间，这条路线就是关键路线。,2统筹方法,42,下面我们给出找关键路线的办法首先，从网络的发点开始，按顺序计算出每个工序的最早开始时间（ES)和最早结束时间（EF)，设一个工序所需的时间为t，这对于同一个工序来说，有:EF=ES+t。,工序a的最早开始时间,工序a的最早完成时间,1,1,a0，60,60,2统筹方法,43,g80,110,30,d60.80,20,e60.100,h100,115,15,j135,170,a0,60,60,其次,从网络的收点开始计算出在不影响整个工程最早结束时间的情况下各个工序的最晚开始时间(缩写为LS)和最晚结束时间（缩写为LF),显然对同一工序有:LS=LF-t,8,5,b60,105,45,35,i110,135,40,25,f70,88,18,4,10,1,7,2,6,3,c60,70,2统筹方法,f70,88,10107,117,4080,120,e60.100,3080,110,g80,110,d60.80,2060,80,i110.135,15120,135,j135,170,35135,170,a0,60,600,60,运用此法则，可以从首点开始计算出每个工序的LF与LS，如下图所示。,1,8,5,b60,105,4590,135,c60,70,h100,115,25110,135,18117,135,4,接着，可以计算出每一个工序的时差，把在不影响工程最早结束时间的条件下，工序最早开始（或结束）的时间可以推迟的时间，成为该工序的时差，对每个工序来说其时差记为Ts有Ts=LS-ES=LF-EF,7,2,3,6,44,45,最后将各工序的时差，以及其他信息构成工序时间表如下表所示。一般来说，关键工序的时差为零。,这样就找到了一条由关键工序a,d,g,i和j依次连接成的从发点到收点的关键路线。,2统筹方法,46,练习：设某工程的资料如以下网络图所示，用时差的方法求关键线路。,1,2,5,3,4,1,1,2,5,2,2,4,8,9,6,7,4,2,3,a,b,c,d,e,4,f,g,h,i,j,k,2统筹方法,47,三、完成工序所需时间与关键路线当完成工序所需时间不确定的情况下如何求网络时间和关键路线？例6.长征研究院培训中心负责明年春天的各干部的工商管理培训,培训中心列出有关培训组织的各项活动的信息如表12-12所示,要求绘制出统筹方法的网络图，设法求出网络时间和关键路线，并确定开始这个组织工作的时间以保证培训工作如期举行。,2统筹方法,48,2统筹方法,49,由于是第一次搞培训，缺乏统计来确定完成每个活动所需时间，但对所需时间做了三种估计：1.乐观时间。指所需最少时间，用a表示。2.最可能时间。指正常时间，用m表示。3.悲观时间。指不顺利情况下，最多时间，用b表示。如下表（单位：周）所示：,50,51,显然这三种完成活动所需时间都具有一定概率，由经验，我们可以可以假定这些时间的概率分布近似服从分布。我们可以用如下公式计算出完成活动所需的平均时间：以及方差,2统筹方法,52,例如：完成工作g所需平均时间：同时求出方差为,2统筹方法,53,同样可以求出每个活动的完成所需平均时间及方差，如下表：,2统筹方法,i13,15,2,i13,15,下面就用平均时间代替完成活动所需时间，并在网络图上标上每个活动最早开始时间和最早结束时间，如图12-14所示。,2,3,4,5,8,7,6,同样也可以标上最晚开始时间和最晚完成时间等。,a0,2,g5,9,b2,5,e5,6,d2,4,f6,8,c0,2,h9,13,3,2,2,2,1,4,2,4,1,2,3,4,5,8,7,6,a0,2,g5,9,b2,5,e5,6,d2,4,f6,8,c0,2,h9,13,21,3,110,11,45,9,49,13,23,5,20,2,32,5,213,15,211,13,图12-14,图12-15,1,54,55,从表12-15上我们找到了一条从发点到收点由关键工序a,b,g,h,i组成的关键路线，用双线标出来。则完成培训工作所需的平均时间为各关键路线的时间之和：=2+3+4+4+2=15（周）同时完成时间近似服从一定的概率分布正态分布，则均值为关键路线上各关键活动之均值之和15，方差也为关键路线上各关键活动方差之和1.05。由此我们可以计算出此项培训组织工作不同完工时间的概率，如16周内完工的概率。,2统筹方法,56,为求此概率，可以先求u值。式中的T为预定完工时间16，E（T）=15，算得u=0.976。查正态分布函数表可知概率为0.8355。即16周内完工的概率为83.55%.,2统筹方法,57,其正态分布图如图12-16所示：,16,图12-16,2统筹方法,58,四、网络优化得到初始的计划方案，但通常要对初始方案进行调整与完善。根据计划目标，综合考虑资源和降低成本等目标，进行网络优化，确定最优的计划方案。1.时间-资源优化做法：1）优先安排关键工序所需的资源。2）利用非关键工序的时差，错开各工序的开始时间。3）统筹兼顾工程进度的要求和现有资源的限制，多次综合平衡。,2统筹方法,59,下面列举一个拉平资源需要量最高峰的实例。在例5中，若加工工人为65人，并假定这些工人可完成这5个工序任一个，下面来寻求一个时间-资源最优方案。如表12-16所示：,表12-16,2统筹方法,d(58人）,20,15,h(39人),g(42人）,i(26人）,在图的上半部中，工序代号后的数字是人数，线下面的数字是非关键工序时差长度。图的下半部表示从第60天至135天内的75天里，所需机械加工工人数，这样的图称为资源负荷图。,2,7,4,6,3,5,f(22人）,18,58人,64人,80人,81人,42人,26人,65人,6080100120130,30,25,图12-17,若上述工序都按最早开始时间安排，那么从第60天至第135天的75天里，所需的机械加工工人人数如图12-17所示。,60,h(39人）,g(42人）,d(58人）,i(26人）,同时我们应优先安排关键工序所需的工人，再利用非关键工序的时差，错开各工序的开始时间，从而拉平工人需要量的高峰。经过调整，我们让非关键工序f从第80天开始，工序h从第110天开始。找到了时间-资源优化的方案，如图12-18所示，在不增加工人的情况下保证了工程按期完成。,2,4,6,7,5,3,f(22人）,工人数,65人,6080100120130,58人,42人,64人,26人,65人,图12-18,61,62,2.时间-费用优化需要考虑时间与费用的问题：在既定的时间前工程完工的前提下，使得所需的费用最少，或者在不超工程预算的条件下使工程最早完工。这些是时间-费用优化要研究和解决的问题。直接费用：为了加快工程进度，需要增加人力、设备和工作班次，这需要增加一笔费用，成为直接费用。间接费用：由于工程早日完工，减少了管理人员的工资办公费等费用称为间接费用。一般说工序越短，直接费用越多，间接费用越少。,2统筹方法,63,工序的最快完成时间：指完成时间的最高限度。我们设完成工序j的正常所需时间为Tj;直接费用为cj;完成工序j的最快完成时间为Tj,直接费用为cj。这样我们可以计算出缩短工序j的一天工期所增加的直接费用，用kj表示，称为直接费用变动率。有时间-费用优化问题可建立两个线性规划模型。模型一，在既定的时间T完工的前提下，问各工序的完成时间为多少才使因缩短工期而增加的直接费用最少。,2统筹方法,64,设工序（i,j)的提前完工时间为Yij,我们用Tij,Tij分别表示正常完工时间与最快完工的时间，则有工序（i,j)的实际完工时间为：Tij-Yij。我们用Cij,Cij表示用正常完工时间和最快完成时间完成工序所需要的费用，Kij为工序（i,j)的直接费用变动率。得到这个问题的线性规划模型如下：S.t.Xj-XiTij-Yij,对一切弧（i,j)YijTij-Tij,对一切弧（i,j)Xn-X1T,Xi0，Yij0。,2统筹方法,65,例7.例5所提供的信息都作为本例的信息，另外还给出了在装配过程中各道工序所需正常完工时间与最快完工时间，以及对应正常完工时间与最快完工时间的所需的直接费用和每缩短一天工期所需增加的直接费用，如表12-17所示。,2统筹方法,66,67,c,该工程要求在150天内完工，问每个工序应比正常完工时间提前多少天完成，才能使整个工程因缩短工期而增加的直接费用为最少。如果工期要求在140天完工呢？,1,2,3,4,5,6,7,8,a,b,f,e,h,g,i,j,d,2统筹方法,解：根据此网络图建立数学模型。设此网络图上第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-y25x