第9章 作业排序与控制

（一）概念、分类1、排序----确定任务（工件）在机器上的加工顺序•任务（服务对象）•机器（服务者）2、分类按机器数量的不同分为：•单台机器(单服务者)的排序问题•多台机器(多服务者)的排序问题按工件的加工路线不同又分为：流程型排序(流水作业排序问题)--所有任务的加工路线相同随机型排序(单件作业排序问题)--所有任务的加工路线不同按工件到达车间的情况不同•静态排序问题--所有工件都已到达，可一次对它们进行排序•动态排序问题--工件是陆续到达，要随时安排它们的加工排序按目标函数的性质不同•目标是使平均流程时间最短•目标是使误期完工的工件数最少•排序目标——如何在尽可能满足各种约束条件的情况下，给出一个令人满意的排序方案（二）排序准则1、先到先服务准则（firstcome，firstserved，简FCFS）——按照任务到达的先后次序排序2、最短加工时间准则（shortestprocessingtime，简SPT）——根据加工时间由短到长进行排序3、交货期最早准则（earliestduedate，简EDD）——按照交货期从早到晚进行排序4、最短松弛时间准则（shortestslacktime，简SST）——根据松弛时间由短到长进行排序松弛时间：当前时点距离交货期的剩余时间与该项任务的加工时间之差（三）排序准则评价流程时间——任务在生产系统中的总停留时间，(排队等候时间+加工时间)，实际上也是任务的完工时间延误时间——任务完工时间超出交货期的时间延误时间＝流程时间－交货期若计算结果为负值时，说明任务完工时间小于交货期，延误时间取为0例：有关数据如下表排序准则任务排序加工时间交货期流程时间延误时间A350+3=30B483+4=70C277+2=99-7=2D569+5=1414-6=8E1414+1=1515-4=11先到先服务合计4821E140+1=10C271+2=30A353+3=66-5=1B486+4=1010-8=2D5610+5=1515-6=9最短加工合计3512排序准则任务排序加工时间交货期流程时间延误时间E140+1=10A351+3=40D564+5=99-6=3C279+2=1111-7=4B4811+4=1515-8=7交货期最早合计4014D560+5=50A355+3=88-5=3E148+1=99-4=5B489+4=1313-8=5C2713+2=1515-7=8最短松弛时间合计5021比较而言，按最短加工时间准则排序时，总流程时间最小（四）制造业中的n/m作业排序问题1、n/1作业排序问题一台设备面对多个加工对象的情况总流程时间最短——按最短加工时间准则排序2、n/2排序问题两台设备面对多个加工对象的情况对n/2的排序问题,约翰逊（S．Ｍ．Johnson）于1954年提出了一个有效算法,用于解决多种工件在2台设备上加工的流水作业排序问题.2、n/2排序问题约翰逊算法的适用条件：1)排序的目标函数是要使全部完工时间最小;2)加工对象在两台设备上的加工顺序相同(流程型排序问题);3)所有加工对象都已到达(静态排序问题);4)每种加工对象在每台设备上的加工时间均已知.2、n/2排序问题约翰逊（S．Ｍ．Johnson）算法：①找出加工对象在两台设备的加工时间中的最小值；②若最小值属于第一台设备，则将该加工对象排在第1位；若隶属于第二台设备，则将该加工对象排在最后一位；③对剩余的加工对象重复上述步骤，直至全部加工对象的顺序全部决定为止例：有5个零部件需依次经由设备A、B进行加工，所需时间如表所示。若直接按照编号顺序进行加工，容易求出总加工周期为44天。若按照最优排序准则，则最优排序为1→5→2→3→4，总加工周期为38天，下降了13.6%零件12345A379105B5864103、n/3排序问题三台设备面对多个加工对象的情况——假想设备组约翰逊扩展方法•步骤:①当符合下列两个条件之一，则三台→两台（假想）mintiA≥maxtiBmintiC≥maxtiB②如A、B、C→假想G、HtiG=tiA+tiBtiH=tic+tiB③对新表使用约翰逊法则④当不符合上述条件时，可以采用启发式算法求解n项任务与m台机器排序问题的近优解。第九章内容提要•1.理解排序的概念;•2.掌握n项任务与1台机器的排序准则及其结论;•3.掌握n项任务与2台机器排序问题的约翰逊算法，n项任务与3台机器排序问题的约翰逊扩展法;•4.掌握n项任务在m台机器上加工的加工周期的计算.