生产作业排序的问题课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《生产作业排序的问题课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 生产 作业 排序 问题 课件
- 资源描述:
-
1、生产作业排序一、基本概念一、基本概念二、最长流程时间二、最长流程时间三、三、n/2/F/Fmax问题的算法问题的算法四、一般四、一般n/m/P/Fmax问题的启发式算法问题的启发式算法五、单件车间排序问题五、单件车间排序问题一、基本概念 排序就是要将不同的工作任务安排一个执行的顺序,使预定的目标最优化。实际上就是要解决如何按时间的先后,将有限的人力、物力资源分配给不同工作任务,使预定目标最优化的问题。一、基本概念排序中常用的几个概念排序中常用的几个概念 工件(Job):服务对象;机器(Machine、Processor):服务者。如:n个零件在机器上加工,则零件是工件,设备是机器;工人维修设备
2、,出故障的设备是工件,工人是机器。一、基本概念 所以,作业排序也就是要确定工件在机器上的加工顺序,可用一组工件代号的一种排列来表示。如可用(1,6,5,4,3,2)表示加工顺序:J1J6J5J4J3J2。一、基本概念 作业计划与排序不是一回事,它不仅要确定工件的加工顺序,而且还要确定每台机器加工每个工件的开工时间和完工时间。如果按最早可能开(完)工时间来编排作业计划,则排序完后,作业计划也就确定了。一、基本概念1)单台机器与多台机器的排序问题。2)流水车间与单件车间排序问题。一、基本概念流水车间排序问题的基本特征:流水车间排序问题的基本特征:每个工件的加工路线都一样。如车铣磨。这里指的是工件的
3、加工流向一致,并不要求每个工件必须在每台机器上加工。如有的工件为车磨,有的为铣磨。不仅加工路线一致,而且所有工件在各台机器上的加工顺序也一样,这种排序称为排列排序(同顺序排序)。如工件排序为:J1J3J2,则表示所有机器都是先加工J1,然后加工J3,最后加工J2。一、基本概念单件车间排序问题的基本特征:单件车间排序问题的基本特征:每个工件都有其独特的加工路线,工件没有一定的流向。一、基本概念3)表示方法 一般正规的表示方法为:n/m/A/B n:工件数;m:机器数;A:车间类型(F、P、G);B:目标函数一、基本概念4)一般来说,排列排序问题的最优解不一定是相应流水车间排序问题的最优解,但一般
4、是比较好的解。而对于仅有2台或3台机器的情况,则排列排序问题的最优解一定是相应流水车间排序问题的最优解。一、基本概念 一个工件不能同时在几台不同的机器上加工。工件在加工过程中采取平行移动方式。不允许中断。每道工序只在一台机器上完成。每台机器同时只能加工一个工件。工件数、机器数和加工时间已知,加工时间与加工顺序无关。二、最长流程时间 最长流程时间(加工周期):从第一个工件在第一台机器上加工起到最后一个工件在最后一台机器上加工完毕为止所经过的时间。假定所有工件的到达时间都为0,则Fmax等于排在末位加工的工件在车间的停留时间。二、最长流程时间计算Fmax的几个假定条件:机器M1不会发生空闲;对其它
5、机器,能对某一工件加工必须具备2个条件:机器必须完成排前一位的工件的加工;要加工的工件的上道工序已经完工。二、最长流程时间表表 6-1 加工时间矩阵加工时间矩阵i1 2 3 4 5 6Pi14 2 3 1 4 2Pi24 5 6 7 4 5Pi35 8 7 5 5 5Pi44 2 4 3 3 1二、最长流程时间ipi1pi2pi3pi4615243255144544453258217533674261012131671115202733121722303542132125323846三、n/2/F/Fmax问题的算法 假定:ai为工件Ji在机器M1上的加工时间,bi为工件Ji在机器M2上的加工
6、时间,每个工件按M1M2的路线加工。三、n/2/F/Fmax问题的算法 从加工时间矩阵中找出最短的加工时间。若最短时间出现在M1上,则对应的工件尽可能往前排。若最短时间出现在M2上,则对应的工件尽可能往后排。若最短时间有多个,则任选一个。划去已排序的工件。若所有工件都已排序,则停止,否则重复上述步骤。四、一般n/m/P/Fmax问题的启发式算法 对于一般的n/m/P/Fmax问题,可以用分支定界法求得最优解,但计算量很大。实际中,可以用启发式算法求近优解。四、一般n/m/P/Fmax问题的启发式算法1 1、PalmerPalmer法法 计算工件斜度指标计算工件斜度指标 i i:m:m:机器数机
7、器数 p pikik :工件:工件i i在机器在机器k k上的加工时间。上的加工时间。i=1,2,i=1,2,n,n 排序方法排序方法:按按 i i从大到小的顺序排列。从大到小的顺序排列。按排序的顺序计算按排序的顺序计算FmaxFmaxm1kikip2/)1m(k四、一般n/m/P/Fmax问题的启发式算法2 2、关键工件法、关键工件法:计算Pi=Pij,找出Pi最长的工件,将之作为关键工件C。对其余工件,若Pi1Pim,则按Pi1由小到大排成序列SA。若Pi1 Pim,则按Pim由大到小排成序列SB。顺序(SA,C,SB)即为近优解。四、一般n/m/P/Fmax问题的启发式算法用关键工件法求
8、解用关键工件法求解i 1 2 3 4Pi1 1 2 6 3Pi2 8 4 2 9Pi3 4 5 8 2pi 13 11 16 14得到的加工顺序为得到的加工顺序为(1,2,3,4)四、一般n/m/P/Fmax问题的启发式算法3 3、CDS法法:CDS法法是Johnson算法算法的扩展方法,从M-1个排序中找出近优解。加工顺序 A 加工时间 B 加工时间1t1tm2t1+t2tm-1+tm3t1+t2+t3tm-2+tm-1+tmm-1t1+t2+tm-1t2+tm-1+tm四、一般n/m/P/Fmax问题的启发式算法 L1,按Johnson算法得到加工顺序(1,2,3,4),Fmax28 L2
9、,按Johnson算法得到加工顺序(2,3,1,4),Fmax29 取顺序(1,2,3,4)为最优顺序。用用 CDS 法法求求解解i 1 2 3 4Pi1 1 2 6 3L=1Pi3 4 5 8 2Pi1+pi2 9 6 8 12L=2Pi2+pi3 12 9 10 11五、单件车间排序问题(n/m/G/Fmax)1 1、问题描述问题描述(i,j,k):表示工件i的第j道工序是在机器k上进行。加工描述矩阵D:每一行描述一个工件的加工,每一列的工序序号相同。D=1,1,1 1,2,3 1,3,22,1,3 2,2,1 2,3,2五、单件车间排序问题(n/m/G/Fmax)加工时间矩阵T:与D相对
展开阅读全文