第十一章 作业排序

1、第十一章第十一章 作业排序作业排序 第一节第一节 作业排序的基本概念作业排序的基本概念 一、作业计划与排序（一、作业计划与排序（scheduling and sequencing） w 工件等待 w 机器空闲 二、作业排序问题的分类二、作业排序问题的分类 w 劳动力作业排序（服务业）劳动力作业排序（服务业） w 生产作业排序（制造业）生产作业排序（制造业） 单件车间（job-shop） n按机器的种类和数量分 流水车间 (flow-shop) 静态排序 n按工件到达车间情况分 动态排序 单目标（平均流程时间最短） n按目标函数的性质分 多目标 (误期完工工件数最少) 三、作业排序的任务和目标三

2、、作业排序的任务和目标 有效的作业排序系统应能做到： （1） 对将要做的工作进行优先权设定； （2）以可利用和所需的能力为基础，针对具体设备分配任务及 人力； （3） 以实施为目标分配工作，使工作任务如期完成； （4） 不断（周期性）监督以确保任务的完成； （5） 辨识实施中的问题或异常情况，运用其它方法解决问题； （6） 根据现状或订单的变化对目前的作业排序进行回顾和修改。 第二节第二节 制造业中的生产作业排序制造业中的生产作业排序 一、甘特图一、甘特图 w 作业进度图 w 机器图 图图11-1 作业进度甘特图作业进度甘特图 工作 4/17 4/18 4/19 4/20 4/21 4/22

3、4/23 4/24 4/25 4/26 A B C 图图11-2 机器甘特图机器甘特图 机器 4/22 4/23 4/24 4/25 4/26 4/27 4/28 4/29 磨床 抛光机 A B A C B C 图例： 开始工作 结束工作 计划时间 实际进度 非生产时间 二、作业排序方案的评价标准二、作业排序方案的评价标准 （1）工件流程时间 n工作可以开始加工至完工的时间，包括工件在各机器之间的移动时间、等待时间、加 工时间以及由于机器故障、部件无法得到等问题引起的延迟时间等。 （2）全部完工时间 n 完成一组工作所需的全部时间。 （3）延迟 n可以用比预定完工时间延迟了的时间部分来表示；可

4、也可以用来按预定时间完工的工 件数占总工件数的百分比表示。 （4）在制品库存（WIP） n可以用工件个数、货币价值或可供应的周数表示。 （5）总库存 n计划入库量和现有库存量的总和。 （6）利用率 n一台机器或一个工人的有效时间占总工作时间的百分比。 上述标准可以用具有平均和偏差的统计分布来表示，且它们之间并不完全独立。 三、优先调度规则三、优先调度规则 利用优先调度（排序）规则，在同一工作地等待加工的工作中决定下一项 应该进行加工的工作。而所谓调度方法，就是运用若干预先规定的优先顺序规 则，顺次决定下一个应被加工的工件的排序方法。 （1） FCFS(First Come First Serv

5、e)规则； （2） SPT (Shortest Processing Time) 规则； （3） EDD(Earliest Due Date ) 规则； （4） SCR (Smallest Critical Ration) 规则； n临界比=到交货期为止的剩余时间/剩余加工时间（拥有/需要） （5） MWKR(Most Work Remaining)； n 优先选择剩余加工时间最长工件加工。 （6） LMKR(Least Work Remaining)规则； n 优先选择剩余加工时间最短工件加工。 （7） MOOPNR(Most Operations Remaining)规则； n优先选择剩余

6、工序数最多工件加工。 （8）RANDOM规则。 n随机挑选下一个工件。 w SPT可使工件的平均流程时间最短，从而减少在制品数量； w FCFS来自排队论，对工件比较公平； wEDD和SCR可使工件延误时间最小； wMWKR使不同工作量的工件完工时间尽量接近； wLWKR使工作量小的工件尽快完成。 SPT+MWKR+RANDOM 排序要求信息：加工要求（工艺）和实际完成情况： 加工要求信息：计划完工期（交货期）、工艺路线、标准作业交换时间（准 终）、加工时间（单件）、各工序预计等待时间（如需要）、各工序可替代 设备以及所需的原材料和零件等。 实际完成情况：工件目前位置（在某道工序上加工、或等待

7、加工）、已完成 工序、在每一工序的实际到达和离开时间、实际加工时间和作业交换时间、 各工序所产业的废品等。 四、局部与整体优先规则四、局部与整体优先规则 w优先规则为局部优先规则（排序时仅以单个工作地队 列的信息为依据）：EDD、FCFS、SPT，和整体规 则（不仅根据工件正在排序的工序的工艺参数，而且 还要考虑其他工序）：SCR、MWKR、LWKR 和 MOPNR。 （一）局部优先规则（一）局部优先规则 表11-1 发动机机壳的加工与取货信息 发动机机壳 机壳1 机壳2机壳3机壳4机壳5 标准加工时间（h）8615312 预计取货时间（h）1012201822 表表11-2 SPT规则排序结

8、果规则排序结果 机壳加 工次序 开 始 时间 加 工 时间 结束 时间 流程 时间 预 计 取 货时间 实际取 货时间 提前拖延 机壳40333181815 机壳2369912123 机壳198171710177 机壳51712292922297 机壳329154444204424 总数441021201838 平均数20.43.67.6 平均在制品库存=102/44=2.32个 平均总库存=120/44=2.73个 平均在制品库存=各工件流程时间之和/全部加工时间 平均总库存=各工件实际取货时间之和/全部加工时间 总库存=在制品+已完成、正等待顾客取走的完成品 表表11-3 EDD规则排序结

9、果规则排序结果 机壳加 工次序 开 始 时间 加 工 时间 结束时 间 流程 时间 预 计 取 货时间 实际取 货时间 提前拖延 机壳1088810102 机壳286141412122 机壳4143171718181 机壳317153232203212 机壳532124444224422 总数44115118336 平均数23.00.67.2 平均在制品库存=115/44=2.61个 平均总库存=118/44=2.68个 比较表11-2和表11-3可以看出，用SPT规则排序，其平 均流程更短，平均在制品库存更少；而用EDD规则排序， 可给顾客提供更好的服务：平均延迟和总延迟均较少， 也提供了更

10、低的总库存水平。 局部优先规则可用于多工作地排序问题。 （二）整体优先规则（二）整体优先规则 w运用前述整体优先规则排序。 w两台机器的流水车间作业排序问题：待加工工件的工艺路线相同。 w使在流水车间中两台机器上加工一组工件的完工时间最小使第二台机器的空 闲时间最小。 wSMJohnson（1954年）提出的算法： （1）设 为工件i（i=1， ，n）在机器j(j=1,2)上的加工时间。在矩阵中找出最小的 值， 如果有两个以上相同的最小值，则任选一个。 （2）若最小 出现在机器1上（j=1），则对应工件尽量往前排；若最短加工时间出现在机 器2上，则对应的工件尽可能往后排。 （3）从加工矩阵（

11、）中划去已排序的工件，然后重复步骤（1）和（2），直至全部工件 被安排。 w一般求解采用启发式算法。 ij a ij a ij a ij a 应用事例应用事例11-1 五台仪器修复作业排序。五台仪器修复作业排序。 表11-4 修理时间（h） 仪器 Y1Y2Y3 Y4Y5 工序1 12451510 工序2 2253168 表11-5 排序结果 步骤 排序 1 2 3 4 5 Y3 Y2 Y3 Y2 Y5 Y3 Y2 Y1 Y5 Y3 Y2 Y1 Y4 Y5 Y3 五、作业排序中的两种不同约束环境五、作业排序中的两种不同约束环境 w 设备数有限、人员无限（以上情况）； w 人员数有限、设备数无限，

12、或人员数小于设备数。可 采用与前类似的调度规则来作出人员安排决策。 第三节第三节 服务业中的服务作业排序服务业中的服务作业排序 一、服务作业排序与生产作业排序的主要区别一、服务作业排序与生产作业排序的主要区别 （1）所提供产品的类型 服务生产中，有顾客的参与，作业排序对他们有直接影响， 因而成为服务的一部人；在制造业中，生产作业排序地最终产品使用者无直接 影响。 （2）排序内容 服务业中，作业排序要定义服务交易的时间或消耗点；制造业中，仅 定义产品生产的操作步骤。 （3）过程控制 服务业中，用户参与服务过程，并对全部操作时间施加影响；制造业 中用户仅与最终产品或交货时间相关。 （4）人员规模 在顾客化服务业中，服务的输出与劳动的最佳规模之间的关系很难确 定；制造业中，两者有紧密联系，最优的作业排序可以算出。 顾客化服务：“先到先服务”、“预约式”、顾客出参与决策过程， 通常作为驱动者。 服务业服务 标准化服务（交通运输、零售业），更多与设备、工具相连。 服务业中其作业组织和排序更困难，对其绩效果影响也更大。 w两种基本方法： （1） 将服务需求分配到服务能力的不同时间段内； （2） 将服务人员安排到顾客需求