0排序与统筹方法

《0排序与统筹方法》由会员分享，可在线阅读，更多相关《0排序与统筹方法（50页珍藏版）》请在金锄头文库上搜索。

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

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

3、对于一台机器n个零件的排序问题，只要系数越大，配上加工时间越少的，即按照加工时间排出加工顺序，加工时间越少的零件排在越前面，加工时间越多的零件排在越后面，可使各个零件的平均停留时间为最少。也就是按照3，4，5，6，1，2的顺序来加工零件，可使各个零件的平均停留时间为最少。,5,1 车间作业计划模型,按照3，4，5，6，1，2的顺序来加工零件，各个零件的停留时间如表12-4所示。 各个零件的平均停留时间为这与用“先到先加工”顺序所需平均停留时间4.93相比较，有很大的进步。对于一台机器n个零件的排序问题，我们按照加工时间从少到多排出加工零件的顺序就能使各个零件的平均停留时间为最少。,表12-4,

4、6,1 车间作业计划模型,二、两台机器、n个零件例2.某工厂根据合同定做一些零件，这些零件要求先在车床上车削，然后再在 磨床上加工，每台机器上各零件加工时间如表12-5所示。 表12-5应该如何安排这五个零件的先后顺序才能使完成这五个零件的总的加工时间为 最少？解：由于每个零件必须先进行车床加工，再进行磨床加工，所以在车床上加 工零件的顺序与在磨床上加工零件的顺序是一样的。如果这些零件在车床上和磨床上加工顺序都为1，2，3，4，5。我们用图12-1 中的线条图来表示各零件加工的开始时间与完成时间，这种图是由一根时间轴和 车床、磨床在每个时间段的状况的图形所构成。,7,1 车间作业计划模型,图

5、12-1从上图中我们可以看出，加工时间的延长主要是由于磨床的停工待料 造成的，只要减少磨床的停工待料的时间就能减少整个加工任务的总时间。 为了减少磨床的停工待料，我们应该一方面把在车床上加工时间越短的零 件越早加工，减少磨床等待的时间；另一方面把在磨床上加工时间越短的 零件越晚加工，以便充分利用前面的时间，这样我们就得到了使完成全部 零件加工任务所需总时间最少的零件排序方法。,8,1 车间作业计划模型,寻找例2的最优解：我们在表12-5中找到所列出的最短加工时间是0.25,它是第二道工序磨床 加工零件2的所需时间，由于这个时间与磨床有关，故我们把零件2放在加工顺序的末尾，即第五 位，并在表中划

6、去零件2 所在行。如表12-6中红色线条所示。接着，我们又找到最短加工时间为0.5，这一时间与磨床（第二工序）有关，我们把 磨床加 工时间为0.5的零件1放到除第五外的加工顺序的末尾，即第四位加工，同时把 表中的零件1所在 的行划去。如表12-6中黄色线条所示。下一个最短加工时间为0.75，这个加工时间是车床（第一工序）加工零件5的所需时间，故 把零件5排在加工顺序的第一位上，同时把表中的零件5所在的行划去。如表12-6中蓝色线条所 示。,表12-6,9,同样，下一个最短加工时间为1，这是车床加工零件3的所需时间，故 把零件3排在第二位上，同时把零件3所在的行划去。如表12-6中黑色线条 所示

7、。这样就得到了最优加工顺序：5，3，4，1，2。一共只需7个小时就能 完成全部加工。从例2中我们可以归纳出关于两台机器n个零件的排序问题，使得全部 任务总的时间 最短的排序算法。在加工所需时间表上选出最短加工时间tij，这是第i工序加工j零件所需 时间，当i=1时，将零件j的顺序尽量靠前，若i=2时，将零件j的顺序尽量 靠后。在表上划去零件j的所在行，回到步骤1。,1 车间作业计划模型,10,2 统筹方法,统筹方法包括绘制计划网络图、进度安排、网络优化等环节，下面进 行分别讨论： 一、计划网络图统筹方法的第一步工作就是绘制计划网络图，也就是将工序（或称为 活动）进度表转换为统筹方法的网络图。例

8、3、某公司研制新产品的部分工序与所需时间以及它们之间的相互 关系都显示在其工序进度表如表12-8所示，请画出其统筹方法网络图。表12-8,11,2 统筹方法,解:用网络图表示上述的工序进度表网络图中的点表示一个事件,是一个或若干个工序的开始或结束,是相 邻工序在时间上的分界点,点用圆圈表示,圆圈里的数字表示点的编号。弧 表示一个工序（或活动），弧的方向是从工序开始指向工序的结束，弧上 是各工序的代号，下面标以完成此工序所需的时间（或资源）等数据，即 对此弧所赋的权数,a,b,c,d,e,60,13,8,38,15,图12-4,12,2 统筹方法,例. 把例的工序进度表做一些扩充，如表12-9，

9、请画出其统筹方法的网络图。表12-9,13,2 统筹方法,解：我们把工序扩充到图12-4发生了问题，由于是的紧前工序，故的结束应该是的开始，所以代表的弧的起点应该是，由于工序的结束也是，所以工序也成了工序的紧前工序，与题意不符。为此我们设立虚工序。虚工序是实际上并不存在而虚设的工序，用来表示相邻工序的衔接关系，不需要人力、物力等资源与时间。,1,5,2,6,4,3,a,60,b,15,8,e,10,13,d,c,38,f,图12-5,14,2 统筹方法,在网络图上添加、工序得网络图12-6。在统筹方法的网络图中不允许两个点之间多于一条弧，因此增加了一个点和虚工序如图12-7。,1,2,5,6,

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

11、的生产线，具体过程如表12-10,求：完成此 工程的最少时间，关键路线及相应的关键工序，各工序的最早开始时间及结束时 间和非关键工序在不影响工程完成时间的前提下，其开始时间与结束时间可以 推迟多久。,17,2 统筹方法,表12-10,18,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,

12、20,40,25,f,18,15,19,2 统筹方法,下面我们给出找关键路线的办法首先，从网络的发点开始，按顺序计算出每个工序的最早开始时间 （ES )和最早结束时间（EF) ，设一个工序所需的时间为t，这对于同一 个工序来说，有 EF=ES+t。,工序a的最早 开始时间,工序a的最早 完成时间,1,2,a0，60,60,图12-9,20,2 统筹方法,图12-10其次,从网络的收点开始计算出在不影响整个工程最早结束时间的情 况下各个工序的最晚开始时间(缩写为LS)和最晚结束时间（缩写为LF), 显然对同一工序 LS=LF-t,1,2,3,6,7,8,5,a0,60,60,b60,105,45

13、,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,21,2 统筹方法,运用此法则，可以从首点开始计算出每个工序的LF与LS，如图12-11 所示。图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,

14、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,22,2 统筹方法,最后将各工序的时差，以及其他信息构成工序时间表如表12-11所 示。 表12-11这样就找到了一条由关键工序a,d,g,i和j依次连成的从发点到收点的 关键路线。,23,三、完成工序所需时间不确定时的网络时间和关键路线当完成工序所需时间不确定的情况下怎样求网络时间和关键路线呢，下面我们结合案例介绍求解办法.例6. 长征

15、研究院培训中心负责明年春天的各干部的工商管理培训，培训中心列出有关培训组织的各项活动的信息如表12-12所示，要求绘制出统筹方法的网络图，设法求出网络时间和关键路线，并确定开始这个组织工作的时间以保证培训工作如期举行。解：由表12-12，绘出统筹方法的网络图如图12-12所示。,图12-12,2 统筹方法,24,2 统筹方法,表12-12,25,2 统筹方法,由于是第一次搞培训，缺乏经验和有关统计资料来确定 完成每个活动所需时间，但对所需时间做了三种估计： 1.乐观时间。指在顺利情况下,完成活动所需最少时间，用a表示。 2.最可能时间。指在正常情况下,完成活动所需时间，用m表示。 3.悲观时间。指不顺利情况下，完成活动所需最多时间，用b表示。如表12-13所示.,26,表12-13 单位：周,27,2 统筹方法,显然这三种完成活动所需时间都具有一定概率，由经验，我们可以 可以假定这些时间的概率分布近似服从 分布。我们可以用如下公式计 算出完成活动所需的平均时间：以及方差例如：完成活动g所需平均时间：同时求出方差为,