流水作业排单——关注哪单先做单件作业排单——关注谁做哪单前提：同等紧急、同等重要单台机器流水排单——短的优先两台机器流水排单——短的先排，前前后后三台以上（CDS）——转化、排单、计算三台以上（陈荣秋）工期：第一行、第一列直接加、其他的取大加工序能力测评双限公差单限公差上单限公差下稳定性测评价均值控制图极差控制图抽样检验AQL(批量\检验水平\次数\严格度\AQL)流水作业排序问题的基本特征是每个零件的加工路线都一致。即工件流向一致.只要加工路线一致：M1，M2,M3，…..，Mm,不要求每个零件都经过每台机器加工作业排序的优先规则例：一个车间有一台加工中心，现有5个工件需要该机器加工。相关的加工时间和要求完成时间（交货期）如下表所示。排序准则排序准则1、SPT准则一般是作业通过时间最少和工作中心作业平均数最少及利用率最大的最好方法。其主要缺点是让耗时长的作业等待，特别当新的时间短的作业不断添加到系统中时，等待的时间可能会相当长。2、FCFS主要局限在于加工时间过长，常会使其它作业延期。3、SST考虑到了各任务在完成过程中的松紧缓急4、EDD会造成有的作业等待加工的时间很长，使在加工存货与车间的拥挤程度增加。机器：同时只能完成一个任务的生产单元单台机器排单原则：短的先排前提：同等紧急、同等重要顺序：1紧急且重要2紧急不重要3重要不紧急4不紧急不重要流水作业：每一个任务由几台机器配合完成重点是订单的先后顺序单件作业：每一个任务由一台机器独立完成重点是订单的分配问题单台机器也是处理订单的先后顺序，所以也归结为流水作业。单台机器的排序问题六、n项任务在两台机器的排序问题1、两台机器排序的目标使最大完成时间（总加工周期）Fmax最短。Fmax的含义见如下的甘特图。2两台机器排序问题的算法实现两台机器排序的最大完成时间最短的目标，优化算法就是著名的约翰逊法。约翰逊法解决这种问题分为4个步骤：列出所有工件在两台设备上的作业时间。找出作业时间最小者。如果该最小值是在设备1上，将对应的工件排在前面，如果该最小值是在设备2上，则将对应的工件排在后面。排除已安排好的工件，在剩余的工件中重复步骤(2)和(3)，直到所有工件都安排完毕。例：某一班组有A、B两台设备，要完成5个工件的加工任务。每个工件在设备上的加工时间如下表所示。求总加工周期最短的作业顺序。解：由约翰逊法可知，表中最小加工时间值是1个时间单位，它又是出现在设备A上，根据约翰逊法的规则，应将对应的工件4排在第一位，即得：J4-*-*-*-*去掉J4，在剩余的工件中再找最小值，不难看出，最小值是2个时间单位，它是出现在设备B上的，所以应将对应的工件J1排在最后一位，即：J4-*-*-*-J1再去掉J1，在剩余的J2、J3、J5中重复上述步骤，求解过程为：J4-*-*-J5-J1J4-J2-*-J5-J1J4-J2-J3-J5-J1当同时出现多个最小值时，可从中任选一个。最后得J4-J2-J3-J5-J1(a)J1-J2-J3-J4-J5习题一、最长流程时间Fmax的计算二、n/2/F/Fmax问题的最优算法例题：求表11-3所示的6/2/F/Fmax问题的最优解。课堂作业：Johnson法则，最优排序！以及计算Fmax（二）算法步骤的改进序列A为(2，5，6，1)，序列B为(4，3)，构成最优顺序为(2，5，6，1，4，3)，与Johnson算法结果一致。三、求一般n/m/P/Fmax问题近优解(Nearoptimalsolution)的启发式算法例：有一个4/3/P/Fmax问题，其加工时间如下表所示，用Palmer法求解。λ1=-P11+P13=-1+4=3λ2=-P21+P23=-2+5=3λ3=-P31+P33=-6+8=2λ4=-P41+P43=-3+2=-1作业：用Palmer法求解2、关键工件法（1）计算每个工件的总加工时间，找出加工时间最长的工件C，将其作为关键工件；（2）对于余下的工件若Pi1≤Pim，则按Pi1不减的顺序排成一个序列Sa，若Pi1＞Pim，则按Pim不增的顺序排列成一个序列Sb。（3）顺序（Sa，C，Sb）即为所求顺序。作业：用关键工件法求解3、CDS法CDS法可以总结为：L=1时，求第1道和最后一道工序的加工时间矩阵L=2时，求前2道和后2道工序的加工时间和的矩阵L=3时，求前3道和后3道工序的加工时间和的矩阵L=4时，求前4道和后4道工序的加工时间和的矩阵L=m-1，求前m-1道和后m-1道工序的加工时间和的矩阵如：用CDS求机器数M为3时的加工顺序。首先，计算L=1时的加工时间，当L＝1时，按Johnson算法得到加工顺序(1，2，3，