A3（3） 空闲A5（10） 空闲 A1（22） A4（6） 机床2 空闲 A2（5）
全部流程时间：55、59 （三）n项作业在m台机床上的排序 要求最优，计算量相当大，甚至连计算机也难以求解 ——无法用于实际生产中。
人们提出了多种启发式算法，以便以最小的计算量得到足 够好的结果。
第三节 服务业作业排序 一、服务业作业排序与生产作业排序的主要区别 区别的根本原因：服务不能储存 （一）所提供的产品类型 服务有顾客的参与，顾客是服务的一部分——作业排序对 顾客有直接影响
5、总库存：计划入库量与现有库存量的总和
6、利用率：一台机器或一个工人的有效生产时间占总工作时间 的百分比。
注：这些标准之间并不完全独立
二、优先调度规则 根据不同的目标确定优先规则，按优先规则确定各任务的优先 权，由此排定加工顺序。 1、SPT（Shortest Processing Time）规则（最短加工时间规则） 优先选择加工时间最短的工件 ——使工件的平均流程时间最短，从而减少在制品量。 2、FCFS（First Come First Served）规则（先到先服务规则） 按订单的先后顺序进行加工（优先选择最早进入可排工序 集合的工件）——来自排队论，对工件较公平 3、EDD（Earliest Due Date）规则 优先选择完工期限最紧的工件 ——使工件延误时间最少 4、MWKR（Most Work Remaining）规则 优先选择余下加工时间最长的工件 ——使不同工作量的工件完工时间尽量接近。
三、作业排序的任务和目标 有效的作业排序应做到以下几点： 1、对将要做的工作进行优先权设定，以使工作任务按最 有效顺序排列； 2、针对具体设备分配任务及人力，通常以可利用的能力为 基础； 3、以实施为目标分配工作，以使工作任务如期完成。 满足交货期要求 目标 极小化提前期 极小化准备时间或成本 极大化设备利用或劳动力的利用
单班次问题： 1、保证工人每周有两个休息日； 2、保证工人每周有两个休息日为连休。
启发式算法：
第一步：从每周的人员需求量中，找出全部具有最少人员需求量 的两个连续日，再从中找出两日需求量总和最小者； 第二步：指定一名人员在上述两日休息，从其余准备安排该人员 工作的各日的人员需求量中减去1人的需求量； 第三步：重复第一、二步
（二）制造业作业排序的分类 1、按机器的种类和数量 单台机器的排序问题 单件作业（Job-shop）排序问题： 工件的加工路线不同 多台机器的排序问题 流水作业（Flow-shop）排序问题： 所有工件的加工路线完全相 2、按工件到达车间的情况同 静态排序问题 动态排序问题 3、按目标函数的性质 平均流程时间最短的排序问题 使误期完工的工件数最少的排序问题 ……
三、优先调度规则事例 在理论方面，排序问题的难度随着机床数量的增加而增大，而 不是随需加工的作业数量的增加而增大。 （一）n个作业单台机床的排序 零件 所需标准加工时间（h） 顾客预计取货时间（h） A 8 10 B 6 12
C D E
15 3 12
20 18 22
用SPT规则得出的作业排序 加工 开始 加工 结束 流程 预计取 实际取 提前小 拖延 顺序 工作 时间 工作 时间 货时间 货时间 时数 时间 D B A 0 3 9 3 6 8 3 9 17 3 9 17 18 12 10 18 12 17 15 3 7
星期一 星期二 星期三 星期四 星期五
4 工人1 4 3 3 4 4 2 2 3 3
星期六 星期日
1 1 2 * 2 * 2 * 1 1 * 0 * * *
工人2
工人3 工人4
3 2
1 0
2 1
0 0 *
3 2 1
1
1 0
* 0 0
2 2 1
0
*
1 1 1
0
工人5
作业 1、有7个作业必须全部进行A和B两种作业，顺序是先A后B。 用约翰逊规则决定各作业的顺序。 工件 1 2 3 4 5 6 7 （小时）
服务业有两种基本的排序方式： 1、将顾客需求分配到服务能力的不同时间段内； 2、将服务人员安排到顾客需求的不同时间段内。 二、安排顾客需求 在这种方式下，服务能力保持一定，而顾客需求被适当安排， 以提供准时服务和充分利用能力。
（一）预约——顾客化程度高 一个预约系统给予顾客特定的服务时间——及时的顾客服务 和服务人员的高效率。 （二）预定——顾客化程度低 通常用于顾客接受服务时需占据或使用相关的服务设施。
（三）排队等待 各种优先规则可用来决定服务先后顺序—— 通常的规则是先到先服务。 重要问题：应尽量使顾客等待时间缩短——排队论的方法 三、安排服务人员——人员班次计划 制定全年、每个月以至每周的人员需求计划
作业排序
每一个人日常的排班计划 班次计划 单班次问题：每天只有一个班次，部门每天都要营业 的种类 多班次问题：每天有多班，一般为两班或三班
E C
总数 平均
17 29
12 15
29 44
29 44 102 20.4
22 20
29 44 120
18
3.6
7 24 38 7.6
平均在制品库存 平均总库存
102/44=2.32（个） 120/44=2.78（个）
EDD规则 加工 开始 加工 结束 流程 预计取 实际取 提前小 拖延 顺序 工作 时间 工作 时间 货时间 货时间 时数 时间 A B D 0 8 14 8 6 3 8 14 17 8 14 17 10 12 18 10 14 18 1 2 2
工件 A1 机床1 12 机床2 22
A2 4 5
A3 A4 5 15 3 16
A5 10 8
A3
A2 A2 A2 A2
A1
A5 A5
A1
A4
A5
A3 A3 A3 A3
甘特图：
机床1 A2（4） A1（12） A4（15）A5（10）A3（5） 空闲 机床2 空闲 A2（5） 空闲 A1（22） A4（6） A5（8）A3（3） 比较：A2、A3、A5、A1、A4 机床1 A2（4） A3（5） A5（10） A1（12） A4（15） 空闲
工序A 9 8 7 6 1 2 4 工序B 6 5 7 3 2 6 7 2、江铂饭店正试图建立一个所需工人数最少的连续休息两天的 计划。请用下列资料建立该计划。
日期 星期一 星期二 星期三 星期四 星期五
2 1 3 3
星期六
4
星期天2Βιβλιοθήκη 人员需 2 求量C
E 总数
17
32
15
12
32
44
32
44 115
20
22
32
44 118 3
12
22 36
平均
平均在制品库存
23
115/44=2.61（个）
0.6
7.2
平均总库存
118/44=2.68（个）
SPT规则：平均流程时间最短，在制品库存量更少。 EDD规则：平均延迟时间较少，可以给顾客提供更好的服务， 也提供了更低的总库存水平。 从数学上可以证明：SPT规则是最优的方案。 （二）n个作业两台机床的排序——流水作业排序 约翰逊规则（方法）——目标函数是使全部完工时间最少 约翰逊规则的基本步骤： 1、列出每个作业在两台机床上的作业时间； 2、选择最短的作业时间； 3、如果最短的作业时间来自于第一台机床，则首先进行该作业； 如果最短的作业时间来自于第二台机床，则该作业最后完成。 4、对剩余的作业重复进行步骤2和3，直到排序完成。
5、LWKR（Least Work Remaining ）规则 优先选择余下加工时间最短的工件 ——使工作量小的工件尽快完成 6、MOPNR（Most Operations Remaining）规则 优先选择余下工序数最多的工件 7、SCR（Smallest Critical Ratio）规则 优先选择临界比最小的工件——使工件延误时间最小 临界比=工件允许停留时间/工件余下加工时间 8、RANDOM规则 随机地挑选下一个
第七章 作业排序
流程规划 战略能力计划 综合计划
主生产计划（MPS）
物料需求计划（MRP） 生产作业计划
——将MRP转化为各个车间、班组、工作地的任务 第一节 作业排序的基本概念 一、名词术语 排序（Sequencing）：确定工件在机器上的加工顺序。
加工顺序：每台机器加工n个工件的先后顺序
作业计划（Scheduling）：不仅包括确定工件的加工顺序， 而且还包括确定机器加工每个工件的开始时间与完成时间。
第二节 制造业的作业排序 一、作业排序方案的评价标准 1、工件流程时间：从工件开始加工至完工的时间。 包括在各个机器之间的移动时间、等待时间、加工时间等。 2、全部完工时间（最长流程时间） 完成一组工件所需的全部时间——从第一个工件在第一台机器 开始加工，到最后一个工件在最后一台机器上完成加工时为止 所经过的时间。 3、延迟：比预定完工时间延迟的时间部分 4、在制品库存
生产作业排序对最终使用者或消费者无直接影响 （二）排序内容 服务要定义服务交易的时间和地点 制造业仅仅定义产品生产的操作步骤
（三）过程控制 服务业中，用户参与服务过程，并且对全部操作时间施加影响； 制造业中，用户仅与最终产品或交付时间相关。
（四）人员规模 顾客化服务业中，服务的输出与劳动力的最佳规模之间的关系 很难确定； 制造业中，两者之间有紧密联系，可以算出最优的作业排序
加工路线：工件加工在技术上的约束 ——工件加工的工艺过程决定 二、作业排序问题的分类
（一）两种基本形式
1、劳动力作业排序（人员排序）：主要确定人员何时工作
2、生产作业排序：将不同工件安排到不同设备上或安排 不同的人做不同的工作。
在制造业中，生产作业排序是最主要的——加工工件是焦点； 在服务业中，劳动力作业排序是主要的——服务的及时性 是影响公司竞争力的主要因素。