第9章流水作业的排序问题.ppt

第九章 流水作业的排序问题;9.1 排序问题概述 一、排序问题的基本概念 排序是确定工件（零部件）在一台或一组设备 上加工的先后顺序。 在一定约束条件下，寻找总加工时间最短的安 排产品加工顺序的方法，就是生产作业排序。 ;例如，考虑32项任务（工件），有32！?2.6?1035种方案,假定计算机每秒钟可以检查1 billion个顺序, 全部检验完毕需要8.4?1015个世纪. 如果只有16个工件, 同样按每秒钟可以检查1 billion个顺序计算, 也需要2/3年. 以上问题还没有考虑其他的约束条件, 如机器、人力资源、厂房场地等，如果加上这些约束条件，所需要的时间就无法想象了。 所以，很有必要去寻找一些有效算法，解决管理中的实际问题。;假设条件;排序常用的符号;二、排序问题的分类和表示法;（4）根据参数的性质 确定型排序：指加工时间和其他参数是已知确定的量 随机型排序：指加工时间和有关参数为随机变量 （5）根据要实现的目标 单目标排序 多目标排序 ;2、排序问题的表示法;9.2 流水作业排序问题;举例：有一个6/4/p/ Fmax问题，其加工时间如下表所示。当按顺序S＝（6，1，5，2，4，3）加工时，求Fmax。 ;i;二、两台机器排序问题 ;约翰逊－贝尔曼法则 ;举例 AB两台设备完成6个零件的加工任务，每个工件在设备上的加工时间如下表所示。求总加工周期最短的作业顺序。 ;求解过程; J2 – J5 – J6- J1- J4－J3或 J2 – J5 –J1-J6 - J4－J3;i; Johnson算法的改进;;三、m(m≥ 3)台机器排序问题的算法 ;（一）Palmer（斜度指标法）;举例;λi ＝ ＝ -Pi1+Pi3 λ1＝-P11+P13= -1＋4＝3 λ2＝-P21+P23= -2+5=3 λ3＝-P31+P33= -6+8=2 λ4＝-P41+P43= -3+2=-1 按λi不增的顺序排列工件，得到加工顺序 （1，2，3，4）或（2，1，3，4） ;i;;（二）关键工件法;i;i;举例;具体过程; （三）CDS法; i ; 当l＝1时，按Johnson算法得到加工顺序 （1，2，3，4） ;当l=2时，得到加工顺序(2，3，1，4) 对于顺序（2，3，1，4）;四、相同零件、不同移动方式下加工周期的计算 1、顺序移动 一批零件在上道工序全部加工完毕后才整批转移到下道工序继??加工。一批零件的加工周期为： ;例：已知n=4,t1=10分，t2＝5分钟，t3＝15分钟， t4＝10分钟，求T顺;2、平行移动方式 每个零件在前道工序加工完毕后，立即转移到下道工序继续加工，形成前后交叉作业。一批零件的加工周期为：;T平＝（10＋5＋15＋10）＋（4-1) ×15 = 85 (分钟）;3、平顺移动方式 当t1ti+1时，零件按平行移动方式转移； 当t1≥ti+1时，以I工序最后一个零件的完工时间为准，往前推移（n-1) × ti+1,作为零件在（i+1)工序的开工时间。一批零件的加工周期为：;t1;三种移动方式的比较;练习题： 设某种零件批量为5件，加工工序数为4，每道工序单件加工时间为t1=6小时，t2=10小时，t3=8小时t4=16小时，试求三种移动方式下该批零件的加工周期？ T顺=5*(6+10+8+16)=5*40=200小时 T平=(5-1)*16+40=4*16+40=64+40=104小时 T平顺=5*40-(5-1)*(6+8+8)=200-4*22=200-88=112小时;作业题： 某零件批量为6件,共5道工序,各工序的单件工时分别为:t1=5分, t2=2分, t3=5分, t4=3分,t5 =4分,试计算该批零件不同移动方式的生产周期(工序间其他时间不计).