作业排序与控制

1、精选课件1作业排序与控制作业排序与控制精选课件2一、作业排序问题的概念1、作业排序与作业计划作业排序（Sequencing）是指为每台设备、每位员工具体确定每天的工作任务和工作顺序的过程。作业排序与作业计划（Scheduling）是有区别的。一般来说，作业排序只是确定工件在机器设备上的加工顺序，而作业计划则不仅要确定工件的加工顺序，还要确定机器设备加工每个工件的开始时间和完成时间。精选课件3作业排序问题的概念2、作业排序的主要目标满足交货日期的需要。降低在制品库存，加快流动资金周转。缩短提前期。降低机器设备的准备时间和准备成本。充分利用机器设备和劳动力。精选课件4作业排序问题的概念3、作业排序

2、问题的分类根据行业的不同，排序问题可分为制造业的排序问题和服务业的排序问题。根据排序的对象分，可分为劳动力（或服务者）排序和生产作业（或服务对象）排序。对于多台设备的排序问题，又可根据加工路线分为单件作业（Job shop）排序问题和流水作业（Flow shop）排序问题。按工件或顾客到达工作地或服务台的具体情况，可分为静态排序问题和动态排序问题。精选课件5二、制造业中的n/m排序问题只讨论所有工件在各个工作地的加工顺序都相同的情况。为了便于说明，我们将n种工件在m台设备上加工的排序问题表示为n/m。精选课件61、n/1 排序的优先规则最短加工时间规则SPT（shortest processi

3、ng time）或SOT（shortest operation time）：优先选择加工时间最短的工件。最早到期规则EDD（earliest due date）：优先选择完工期限最早的工件。先到先服务规则FCFS（first come first served）：优先选择最早进入排序集合的工件。最少工作量规则LWKR（Least work remaining）：优先选择余下加工时间最短的工件。最多工作量规则MWKR（most work remaining）：优先选择余下加工时间最长的工件。最小关键比例规则SCR（smallest critical ratio）：优先选择关键比例最小的工件，其中

4、，关键比例 =（交货期 - 当前期）/ 余下的加工时间。精选课件7n/1 排序在评价作业排序方案时，工件流程时间、工件延期交货天数、时间跨度和平均工件库存数是几个主要的绩效评价指标。精选课件8n/1排序问题例如，某加工车间要为2003年9月份加工的6批产品进行作业排序，每批的件数相同，都是1000件，公司对各种产品的加工时间都设定了工时定额，销售部门提出了各种产品的预定交货期。精选课件9n/1排序问题 方案1：遵循FCFS规则排序。FCFS的排序顺序是按照待加工的产品从上一道工序转到该加工工序的先后顺序来确定的，即如表11-3所示，BY050GL310GM270BY471 LN002LY120

5、总流程时间总流程时间 = 158 天天平均流程时间平均流程时间 = 总流程时间总流程时间/型号数型号数=158/6=26.3天天平均延期交货天数平均延期交货天数 = 延期交货总天数延期交货总天数/型号数型号数=53/6=8.83天天时间跨度时间跨度 = 40 天天平均在制品库存数平均在制品库存数 = 总流程时间总流程时间/时间跨度时间跨度批量批量=158/401000=3950件件精选课件10n/1排序问题 方案2：采用SPT规则。SPT优先规则为优先选择加工时间最短的产品。根据SPT规则，这六批不同的产品在该加工工序的顺序为LN002LY120BY471GL310GM270BY050总流程时

6、间总流程时间 = 120 天天平均流程时间平均流程时间 = 120/6=20天天平均延期交货天数平均延期交货天数 = 38/6=6.3天天时间跨度时间跨度 = 40 天天平均在制品库存数平均在制品库存数 = 120/401000=3000件件精选课件11n/1排序问题 方案3：采用EDD规则。EDD规则将最早预定交货期限作为优先选择标准。根据EDD规则，这六批产品的加工顺序为CAEBDF总流程时间总流程时间 = 144 天天平均流程时间平均流程时间 = 144/6=24天天平均延期交货天数平均延期交货天数 = 37/6=6.17天天时间跨度时间跨度 = 40 天天平均在制品库存数平均在制品库存

7、数 = 144/401000=3600台台精选课件12n/1排序问题 方案4：采用SCR规则。关键比例=（预期交货期当前日期）/检验时间，根据SCR规则，这六批产品的加工顺序为GM270GL310BY050BY471LY120LN002总流程时间总流程时间 = 155 天天平均流程时间平均流程时间 = 155/6=25.8天天平均延期交货天数平均延期交货天数 = 47/6=7.83天天时间跨度时间跨度 = 40 天天平均在制品库存数平均在制品库存数 = 155/401000=3875台台精选课件13n/1排序问题 将以上四种规则的排序结果汇总，得以下表格从以上例子可知，从以上例子可知，FCFS

8、和和SCR两种规则的效率较低，既导致较高的平均流程时间，两种规则的效率较低，既导致较高的平均流程时间，有造成较多的在制品库存。一般而言，有造成较多的在制品库存。一般而言，SPT和和EDD是两种较优的排序规则，是企业是两种较优的排序规则，是企业排序时常用的优先规则。排序时常用的优先规则。SPT规则可使工件的平均流程时间最短，从而减少在制品规则可使工件的平均流程时间最短，从而减少在制品的库存数量，从而减少企业的资金占用，降低成本。的库存数量，从而减少企业的资金占用，降低成本。EDD规则可使工件延期交付时规则可使工件延期交付时间较小，能够导致较高的客户满意水平。间较小，能够导致较高的客户满意水平。精

9、选课件14n/2排序问题n/2排序问题是指n种工件在2台机器设备（工作地）上进行加工的排序问题。假设有n个工件的加工要经过两台设备，并且所有工件的加工路线都相同。在这种情况下，全部完工时间是一个关键的评价标准，排序的目标是使全部完工时间最短对n/2的排序问题，Johnson于1954年提出了一个有效算法精选课件15n/2排序问题Johnson算法的适用条件排序的目标函数是使全部完工时间最小工件在两台设备上的加工顺序完全相同所有工作同时到达第一台设备等待加工每种工件在每台设备上的加工时间均已知精选课件16Johnson算法的步骤 先作n个工件在两台设备上的加工时间的工时矩阵。在工时矩阵M中找出最小元素aij，若最小元素不止一个，可任选其一。如果最短的加工时间出现在第一台设备上，则对应的工件应排在最前位置；如果最短的加工时间出现在第二台设备上，则对应