排序与统筹方法.ppt

《排序与统筹方法.ppt》由会员分享，可在线阅读，更多相关《排序与统筹方法.ppt（47页珍藏版）》请在三一办公上搜索。

1、第十二章 排序与统筹方法,1,1 车间作业计划模型2 统筹方法,在本章中，我们将介绍车间作业计划模型和统筹方法。这两个问题尽管处理的方法有所不 同，但当我们面临必须完成若干项不能同时进行的工作时，它们都将帮助我们应该按照怎样的次序、怎样的时间表来做这些工作，使得效果最佳（例如完成全部工作所用时间最短或费用最少等等）。,1车间作业计划模型,车间作业计划是指一个工厂生产工序的计划和安排。一、一台机器、n个零件的排序问题二、两台机器、n个零件的排序问题,2,1车间作业计划模型,一、一台机器、n个零件的排序问题 例1.某车间只有一台高精度的磨床，常常出现很多零件同时要求这台磨床加工的情况，现有六个零件

2、同时要求加工，这六个零件加工所需时间如下表所示。应该按照什么样的加工顺序来加工这六个零件，才能使得这六个零件在车间里停留的平均时间为最少？,3,1车间作业计划模型,4,解：如果我们用Pi表示安排在第i位加工的零件所需的时间，用Tj表示安排在第j位加工的零件在车间里总的停留时间，则有 Tj=P1+P2+Pj-1+Pj=不同的加工顺序得到不同的各零件的平均停留时间，如何得到一个使得各零件的平均停留时间最少的排序呢？这就是我们最后要解决的优化问题，而且我们要设法找到一种简便的算法。对于某种加工顺序，我们知道安排在第j位加工的零件在车间里总的停留时间为Tj，Tj=可知这六个零件的停留时间为：T1+T2

3、+T3+T4+T5+T6 P1+(P1+P2)+(P1+P2+P3)+(P1+P2+P3+P4)+(P1+P2+P3+P4+P5)+(P1+P2+P3+P4+P5+P6)6 P1+5 P2+4P3+3P4+2P5+P6.那么各个零件平均停留时间为 从上式可知，对于一台机器n个零件的排序问题，只要系数越大，配上加工时间越少的，即按照加工时间排出加工顺序，加工时间越少的零件排在越前面，加工时间越多的零件排在越后面，可使各个零件的平均停留时间为最少。,1车间作业计划模型,二、两台机器、n个零件 例2.某工厂根据合同定做一些零件，这些零件要求先在车床上车削，然后再在磨床上加工，每台机器上各零件加工时间

4、如表12-5所示。表12-5 应该如何安排这五个零件的先后顺序才能使完成这五个零件的总的加工时间为最少？解：由于每个零件必须先进行车床加工，再进行磨床加工，所以在车床上加工零件的顺序与在磨床上加工零件的顺序是一样的。如果这些零件在车床上和磨床上加工顺序都为1，2，3，4，5。我们用图12-1中的线条图来表示各零件加工的开始时间与完成时间，这种图是由一根时间轴和车床、磨床在每个时间段的状况的图形所构成。,5,1车间作业计划模型,图 12-1 从上图中我们可以看出，加工时间的延长主要是由于磨床的停工待料造成的，只要减少磨床的停工待料的时间就能减少整个加工任务的总时间。为了减少磨床的停工待料，我们应

5、该一方面把在车床上加工时间越短的零件越早加工，减少磨床等待的时间；另一方面把在磨床上加工时间越短的零件越晚加工，以便充分利用前面的时间，这样我们就得到了使完成全部零件加工任务所需总时间最少的零件排序方法。,6,1车间作业计划模型,寻找例2的最优解：我们在表12-5中找到所列出的最短加工时间是0.25,它是第二道工序磨床加工零件2的所需时间，由于这个时间与磨床有关，故我们把零件2放在加工顺序的末尾，即第五位，并在表中划去零件2 所在行。如表12-6中红色线条所示。接着，我们又找到最短加工时间为0.5，这一时间与磨床（第二工序）有关，我们把 磨床加工时间为0.5的零件1放到除第五外的加工顺序的末尾

6、，即第四位加工，同时把 表中的零件1所在的行划去。如表12-6中黄色线条所示。下一个最短加工时间为0.75，这个加工时间是车床（第一工序）加工零件5的所需时间，故把零件5排在加工顺序的第一位上，同时把表中的零件5所在的行划去。如表12-6中蓝色线条所示。,7,表12-6,1车间作业计划模型,同样，下一个最短加工时间为1，这是车床加工零件3的所需时间，故把零件3排在第二位上，同时把零件3所在的行划去。如表12-6中黑色线条所示。这样就得到了最优加工顺序：5，3，4，1，2。一共只需7个小时就能完成全部加工。从例2中我们可以归纳出关于两台机器n个零件的排序问题，使得全部任务总的时间 最短的排序算法

7、。在加工所需时间表上选出最短加工时间tij，这是第i工序加工j零件所需时间，当i=1时，将零件j的顺序尽量靠前，若i=2时，将零件j的顺序尽量靠后。在表上划去零件j的所在行，回到步骤1。,8,2统筹方法,统筹方法包括绘制计划网络图、进度安排、网络优化等环节，下面进行分别讨论：一、计划网络图 统筹方法的第一步工作就是绘制计划网络图，也就是将工序（或称为活动）进度表转换为统筹方法的网络图。例3、某公司研制新产品的部分工序与所需时间以及它们之间的相互关系都显示在其工序进度表如表12-8所示，请画出其统筹方法网络图。表12-8,9,2统筹方法,解:用网络图表示上述的工序进度表 网络图中的点表示一个事件

8、,是一个或若干个工序的开始或结束,是相邻工序在时间上的分界点,点用圆圈表示,圆圈里的数字表示点的编号。弧表示一个工序（或活动），弧的方向是从工序开始指向工序的结束，弧上是各工序的代号，下面标以完成此工序所需的时间（或资源）等数据，即对此弧所赋的权数,10,a,b,c,d,e,60,13,8,38,15,图12-4,2统筹方法,例、把例的工序进度表做一些扩充，如表12-9，请画出其统筹方法的网络图。表12-9,11,2统筹方法,解：我们把工序扩充到图12-4发生了问题，由于是的紧前工序，故的结束应该是的开始，所以代表的弧的起点应该是，由于工序的结束也是，所以工序也成了工序的紧前工序，与题意不符。

9、为此我们设立虚工序。虚工序是实际上并不存在而虚设的工序，用来表示相邻工序的衔接关系，不需要人力、物力等资源与时间。,12,1,5,2,6,4,3,a,60,b,15,8,e,10,13,d,c,38,f,图12-5,2统筹方法,在网络图上添加、工序得网络图12-6。在统筹方法的网络图中不允许两个点之间多于一条弧，因此增加了一个点和虚工序如图12-7。,13,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,2统筹方法,在绘制统筹方法的网络图时，要注意图中不能有缺口和回路。,14,1,2,5,7,8,3,4,a,60,15,b,e

10、,c,13,d,38,8,h,5,10,f,6,16,g,图12-7,0,0,2统筹方法,二、网络时间与关键路线 在绘制出网络图之后，我们可以由网络图求出：1、完成此工程项目所需的最少时间。2、每个工序的开始时间与结束时间。3、关键路线及其应用的关键工序。4、非关键工序在不影响工程的完成时间的前提下，其开始时间与结束时间可以推迟多久。例5、某公司装配一条新的生产线，具体过程如表12-10,求：完成此工程的最少时间，关键路线及相应的关键工序，各工序的最早开始时间及结束时间和非关键工序在不影响工程完成时间的前提下，其开始时间与结束时间可以推迟多久。,15,2统筹方法,表12-10,16,2统筹方法

11、,解：据表12-10,绘制网络图如图12-8。图12-8 如图12-8,-就是一条关键路线，我们要干完所有的工序就必须走完所有这样的路线，由于很多工序可以同时进行，所以网络中最长的路线就决定了完成整个工程所需的最少时间，这条路线称为关键路线。,17,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统筹方法,下面我们给出找关键路线的办法 首先，从网络的发点开始，按顺序计算出每个工序的最早开始时间（ES)和最早结束时间（EF)，设一个工序所需的时间为t，这对于同一个工序来说，有 EF=ES+t。,18,工序a的最

12、早开始时间,工序a的最早完成时间,1,2,a0，60,60,图12-9,2统筹方法,19,图12-10 其次,从网络的收点开始计算出在不影响整个工程最早结束时间的情况下各个工序的最晚开始时间(缩写为LS)和最晚结束时间（缩写为LF),显然对同一工序有 LS=LF-t,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,2统筹方法,20,运用此法则，可以从首点开始计算出每个工序的LF与LS，如图12-1

13、1所示。图12-11 接着，可以计算出每一个工序的时差，把在不影响工程最早结束时间的条件下，工序最早开始（或结束）的时间可以推迟的时间，称为该工序的时差，对每个工序来说其时差记为Ts有 Ts=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,2统筹方法,

14、最后将各工序的时差，以及其他信息构成工序时间表如表12-11所示。表12-11 这样就找到了一条由关键工序a,d,g,i和j依次连成的从发点到收点的关键路线。,21,三、完成工序所需时间与关键路线 当完成工序所需时间不确定的情况下如何求网络时间和关键路线？例6.长征研究院培训中心负责明年春天的各干部的工商管理培训，培训中心列出有关培训组织的各项活动的信息如表12-12所示，要求绘制出统筹方法的网络图，设法求出网络时间和关键路线，并确定开始这个组织工作的时间以保证培训工作如期举行。解：由表12-12，绘出统筹方法的网络图如图12-12所示。,22,图12-12,2统筹方法,2统筹方法,23,表1

15、2-12,2统筹方法,由于是第一次搞培训，缺乏经验和有关统计资料来确定完成每个活动所需时间，但对所需时间做了三种估计：1.乐观时间。指在顺利情况下,完成活动所需最少时间，用a表示。2.最可能时间。指在正常情况下,完成活动所需时间，用m表示。3.悲观时间。指不顺利情况下，完成活动所需最多时间，用b表示。如表12-13所示.,24,表12-13 单位：周,25,2统筹方法,显然这三种完成活动所需时间都具有一定概率，由经验，我们可以可以假定这些时间的概率分布近似服从 分布。我们可以用如下公式计算出完成活动所需的平均时间：以及方差 例如：完成活动g所需平均时间：同时求出方差为,26,2统筹方法,同样可

16、以求出每个活动的完成所需平均时间及方差，如表12-14：表12-14,27,2统筹方法,下面就用平均时间代替完成活动所需时间，并在网络图上标上每个活动最早开始时间和最早结束时间，如图12-14所示。,28,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,图12-14,同样也可以标上最晚开始时间和最晚完成时间等。,29,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,4

17、9,13,23,5,20,2,32,5,213,15,211,13,图12-15,30,表 12-15,2统筹方法,从表12-15上我们找到了一条从发点到收点由关键工序a,b,g,h,i组成的关键路线，用双线标出来。则完成培训工作所需的平均时间为各关键路线的时间之和：=2+3+4+4+2=15（周）同时完成时间近似服从一定的概率分布正态分布，则均值为关键路线上各关键活动之均值之和15，方差也为关键路线上各关键活动方差之和1.05。由此我们可以计算出此项培训组织工作不同完工时间的概率，如16周内完工的概率。为求此概率，可以先求 值。式中的T为预定完工时间16，E（T）=15，算得=0.976。查

18、正态分布函数表可知概率为0.8355。即16周内完工的概率为83.55%.,31,2统筹方法,其正态分布图如图12-16所示：,32,16,图12-16,15,2统筹方法,四、网络优化 得到初始的计划方案，但通常要对初始方案进行调整与完善。根据计划目标，综合考虑进度、资源和降低成本等目标，进行网络优化，确定最优的计划方案。1.时间-资源优化 做法：1）优先安排关键工序所需的资源。2）利用非关键工序的时差，错开各工序的开始时间，拉平资源需要量的高峰。3）统筹兼顾工程进度的要求和现有资源的限制，往往要经过多次综合平衡，才能得到比较合理的计划方案。下面列举一个拉平资源需要量最高峰的实例。在例5中，若

19、机械加工工人人数为65人，并假定这些工人可完成这5个工序任一个，下面来寻求一个时间-资源最优方案。如表12-16所示：,33,2统筹方法,表12-16,34,若上述工序都按最早开始时间安排，那么从第60天至第135天的75天里，所需的机械加工工人人数如图12-17所示。,2统筹方法,在图的上半部中，工序代号后的数字是所需机械加工工人数，点划线下面的数字是非关键工序时差长度。图的下半部表示从第60天至135天内的75天里，所需机械加工工人数，这样的图称为资源负荷图。,35,2,7,4,6,3,5,f(22人）,18,h(39人),15,58人,64人,80人,81人,42人,65人,60 80

20、100 120 130,d(58人）,i(26人）,g(42人）,30,20,25,图12-17,26人,65人,工人数,时间/天,2统筹方法,同时我们应优先安排关键工序所需的工人，再利用非关键工序的时差，错开各工序的开始时间，从而拉平工人需要量的高峰。经过调整，我们让非关键工序f从第80天开始，工序h从第110天开始。找到了时间-资源优化的方案，如图12-18所示，在不增加工人的情况下保证了工程按期完成。,36,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

21、人,图12-18,时间/天,2统筹方法,2.时间-费用优化 需要考虑时间与费用的问题：在既定的时间前工程完工的前提下，使得所需的费用最少，或者在不超工程预算的条件下使工程最早完工。这些是时间-费用优化要研究和解决的问题。直接费用：为了加快工程进度，需要增加人力、设备和工作班次，这需要增加一笔费用，成为直接费用。间接费用：由于工程早日完工，减少了管理人员的工资办公费等费用称为间接费用。一般说工序作业时间越短，直接费用越多，间接费用越少。,37,2统筹方法,缩短工序的作业时间有一定的限度，这个限度称为工序的最快完成时间。我们设完成工序j的正常所需时间为Tj;直接费用为cj;完成工序j的最快完成时间

22、为Tj,直接费用为cj。这样我们可以计算出缩短工序j的一天工期所增加的直接费用，用kj表示，称为直接费用变动率。有 时间-费用优化问题可建立两个线性规划模型。模型一，在既定的时间T完工的前提下，问各工序的完成时间为多少才使因缩短工期而增加的直接费用最少。设工序（i,j)的提前完工时间为yij,我们用Tij,Tij分别表示正常完工时间与最快完工的时间，则有工序（i,j)的实际完工时间为：Tij-Yij。我们用cij,cij表示用正常完工时间和最快完成时间完成工序所需要的费用，kij为工序（i,j)的直接费用变动率。得到这个问题的线性规划模型如下：minf=（kij*yij)（i,j)s.t.xj

23、-xi Tij-yij,对一切弧（i,j)yij Tij-Tij,对一切弧（i,j)xn-x1 T,xi 0，yij 0。,38,2统筹方法,例7.例5所提供的信息都作为本例的信息，另外还给出了在装配过程中各道工序所需正常完工时间与最快完工时间，以及对应正常完工时间与最快完工时间的所需的直接费用和每缩短一天工期所需增加的直接费用，如表12-17所示。,39,表12-17,40,缩短一天工期增加的直接费用（费用变动率元/天）,2统筹方法,该工程要求在150天内完工，问每个工序应比正常完工时间提前多少天完成，才能使整个工程因缩短工期而增加的直接费用为最少。如果工期要求在140天完工呢？,41,1,

24、2,3,4,5,6,7,8,a,b,f,e,c,h,g,i,j,d,图12-19,2统筹方法,解：网络图如图12-19所示，根据此网络图建立数学模型。设此网络图上第i点发生的时间为xi，工序提前完工的时间为yij。目标函数minf=120y27+300y23+400y24+500y25+230y37+350y46+400y57+290y67.s.t.x2-x1 60-y12 x7-x2 45-y27 x3-x210-y23 x4-x220-y24 x5-x240-y25 x7-x318-y37 x6-x430-y46 x5-x40，虚拟弧（4，5）x7-x515-y57 x7-x625-y67

25、 x8-x735-y78,42,2统筹方法,x1=0,y120,y2715,y23 5 y24 10 y25 5 y37 8 y46 10 y57 5 y67 10 y78 0 x8 150 xi 0，yij 0.（对一切可能的ij),43,用“管理运筹学”软件进行计算，很快得到以下结果：,44,2统筹方法,模型二，我们知道直接费用是随着完成时间的缩短而增加，而间接费用却会随着完成时间的缩短而减少，设单位时间的间接费用为d,计划期的间接费用与总工期成正比，即为d(xn-x1),那么求使包括间接费用与直接费用在内的总费用最少的整个工程最优完成时间T和各个工序最优完成时间的模型为：目标函数min

26、f=d(xn-x1)+s.t.xj-xi Tij-yij，对一切弧（i,j)yijTij-Tij，对一切弧（i,j)xi 0，yij 0。,45,2统筹方法,例8 如果在例7中，每天的间接费用为330元，求使包括间接费用与直接费用在内的总费用最少的整个工程最优完成时间T和各个工序最优完成时间。解：决策变量xi和yij的含义同例7。此数学模型的目标函数为：min f=330(x8-x1)+120y27+300 y23+400y24+500y25+230y37+350y46+400y57+290y67 此模型的约束条件与例7的约束条件基本相同，只要在例子的约束条件中去掉x8 150就得到了例8模型的约束条件了。计算得到以下结果：f=55700.x1=0,y12=0,y67=10,x2=60,y27=0,y78=0.,46,2统筹方法,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天完工，其余的工序按正常时间完工。,47,