4.2 两台机器排序问题的目标
• 两台机器排序的目标是使最大完成时间（总加工周期） Fmax最短。 Fmax的含义见如下的甘特图(Gantt Chart)。
机器 A
在机器A上的作业时间
B
总加工周期
Fmax
时间
• 多台机器排序的目标一般也是使最大完成时间（总加工 周期） Fmax最短。
4.3 两台机器排序问题的算法（重点）
确定出最佳的作业顺序看似容易，只要列出所有的顺序， 然后再从中挑出最好的就可以了，但要实现这种想法几乎 是不可能的。 例如，考虑32项任务（工件），有32！2.61035种方案, 假定计算机每秒钟可以检查1 billion个顺序, 全部检验完毕 需要8.41015个世纪. 如果只有16个工件, 同样按每秒钟可以检查1 billion个顺 序计算, 也需要2/3年. 以上问题还没有考虑其他的约束条件, 如机器、人力资源、 厂房场地等，如果加上这些约束条件，所需要的时间就无 法想象了。 所以，很有必要去寻找一些有效算法，解决管理中的实 际问题。
1.2 作业计划的种类 大量生产类型的作业计划 成批生产类型的作业计划 单件小批生产类型作业计划
另外，还有其他分类： 车间作业计划(Job Floor scheduling) 人力计划(Personnel Scheduling) 设施计划(Facilities Scheduling) 车辆调度计划(Vehicle Scheduling) 供应商计划(Vendor Scheduling) 工程项目计划(Project Scheduling) 动态计划和静态计划(Dynamic versus Static Scheduling)
1 机器A 机器B 机器C
解: 检查上表, 发现: min Ai = 4 max Bi = 6 min Ci = 6
2 913 619
3 821 223 635
4 627 330
5 532 436
44 59
817 1029
742 1153
3.3 求平均流程时间最短的排序问题
• 求平均流程时间最短的作业顺序，采用SPT原则。
按工件加工时间的长短，按不减的顺序从小到大安排各 项作业。
•例：一个车间有一台加工中心，现有5个工件需要该机器加 工。相关的加工时间和要求完成时间（交货期）如下表所示， 求平均流程时间最短的作业顺序。
J1 加工时间 交货期 11 61 J2 29 45 J3 31 31 J4 1 33 J5 2 32
第11章
重难点：
车间作业计划与控制
---作业计划问题的基本概念 ---流水车间作业计划问题： 1、加工周期的计算 2、两台机器排序问题的最优算法 ---生产作业控制
层次性：
---年度生产计划 ---零部件投入出产计划 ---车间生产作业计划 （班组、各工作地、各工人的任务）
第1节 作业计划问题的基本概念
实现两台机器排序的最大完成时间Fmax最短的目标，一优化算 法就是著名的约翰逊法(Johnson’s Law)。其具体求解过程如下例 所示（或见课本P210例11-2）。 约翰逊法解决这种问题分为4个步骤： (1)列出所有工件在两台设备上的作业时间。 (2)找出作业时间最小者。 (3)如果该最小值是在设备1上，将对应的工件排在前面；如果 该最小值是在设备2上，则将对应的工件排在后面。 (4)排除已安排好的工件，在剩余的工件中重复步骤(2)和(3)， 直到所有工件都安排完毕。
第3节 单台机器的排序问题
3.1 单台机器排序问题 n个工件全部经由一台机器处理
J1 J2 J3 Jn 离开系统 （机器）
机器
到达系统工 件的集合
3.2 常见单台机器排序问题的目标函数
1) 平均流程时间最短
定义:
1 n F Fi n i 1
_
为n个零件经由一台机器的平均流程时间。
目标函数 MIN:
(a) J1 - J2 - J3- J4 - J5
A B 30
(b) J4 - J2 - J3- J5 - J1
A B 26 可以看出，初始作业顺序的总加工周期是30，用约翰逊法排出的作业顺 序总加工周期是26，显然后者的结果优于前者。
4.4 两台机器排序问题算法的扩展(N)
一般情况下，当机器数为3台以上时，就很难找到最优解了。 但是，对于n个工件由三台机器流水作业时，在满足某些条件 后可以采用Johnson’s Law解决问题。 设：A、B、C为三台机器，如果工件在三台机器上的加工时 间满足以下条件，则可以转化为两台机器的排序问题： min Ai>=max Bi or min Ci >= max Bi 定义：A’i = Ai+ Bi , B’i = Bi +Ci 例: 考虑以下问题. 5个工件由3台机器加工, 作业时间见下表. 求: 总加工周期最短的作业顺序.
1.3 制定作业计划的影响因素
• • • • • 工件到达的方式 车间内机器的数量 车间拥有的人力资源 工件移动方式 不同调度准则的评价
• 1.4 作业计划与控制的关系 • 作业计划：给生产活动制定详细时间表 • 生产控制：以生产计划和作业计划为依据，检查、落 实计划执行情况，发现偏差即采取纠正措施，保证实 现各项各项计划目标。
1 n F Fi n i 1
_
2）最大延期量最小
定义:
Tmax maxTi 为最大延期量。
目标函数
min Tmax
根据排序目标的不同，可以选择不同的排 序规则，有时又称为确定优先权(Priorities)。
常见的优先权规则(Priority rules)有： SPT---Shortest Process Time, EDD---Earliest Due Date FCFS---First Come First Served CR---Critical Rate 等, 分别用于解决不同的问题。
B-----目标函数
2.5
编制作业计划问题的一些假设：
• 1、一个零件不能同时在几台不同的机器上加工； • 2、零件在加工过程中采取平行移动方式，即当上道工 序完工后立即送下道工序加工； • 3、不允许中断：一个零件一旦开始加工，必须一直加 工到完成，不得中间插入其他零件加工； • 4、每道工序只能在一台机器上完成； • 5、零件数、机器数和加工时间已知； • 6、每台机器同时只能加工一个零件；
进一步考虑：在最大延期量不变的情况下，如何使平 均流程时间缩短？如果想同时满足这两个目标，就是 多目标排序。
第4节 n项任务在两台机器的排序问题
4.1 两台机器排序问题的含义
n个工件都必须经过机器1和机器2的加工，即工艺路线是一致的。
J1 J2 J3 Jn
机器1
机器2
离开系统 （机器）
到达系统工 件的集合
第2节 排序的基本概念 (Sequencing)
2.1 排序与编制作业计划的差别
上面讲了编制作业计划的问题. 在编制作业计划过程中,有一 个问题需要管理人员注意,即投入生产过程的作业顺序的安排. ·作业计划是安排零部件（作业、活动）的出产数量、设备及 人工使用、投入时间及出产时间。 ·排序，给出零部件在一台或一组设备上加工的先后顺序的工 作。 所以,编制作业计划与排序的概念和目的都是不同的。但是， 编制作业计划的主要工作之一就是要确定出最佳的作业顺序。
例：某一班组有A、B两台设备，要完成5个工件的加 工任务。每个工件在设备上的加工时间如下表所示。 求总加工周期最短的作业顺序。
工件在两台设备上的加工时间 工件编号 J1 J2 J3 J4 J5
设备A
设备B
3
2
6
8
7
6
1
4ห้องสมุดไป่ตู้
5
3
解：由约翰逊法可知，表5-8中最小加工时间值是 1个时间单 位，它又是出现在设备 1 上，根据约翰逊法的规则，应将 对应的工件4排在第一位，即得： J4 - * - * - * - * 去掉J4，在剩余的工件中再找最小值，不难看出，最小值 是2个时间单位，它是出现在设备2上的，所以应将对应的 工件J1排在最后一位，即： J4 - * - * - * - J1 再去掉 J1 ，在剩余的 J2 、 J3 、 J5 中重复上述步骤，求解过 程为： J4 - * - * - J5 - J1 J4 - J2 - * - J5 - J1 J4 - J2 - J3- J5 - J1 当同时出现多个最小值时，可从中任选一个。最后得 J4 - J2 - J3- J5 - J1
3.4 求最大延期量最小的排序问题
• 求最大延期量最小的作业顺序采用EDD原则。 EDD(Earliest Due Date): Jobs are sequenced in increasing order of their due dates. • 例：借用上面的例子，求最大延期量最小的作业顺序。 解：根据EDD原则，得出：
解：根据SPT原则，得出：
J4 -J5 -J1 -J2 -J3
有关项目的计算：
加工时间 J4 J5 J1 J2 1 2 11 29 31
_
完成时间
交货期 33 32 61 45 31
延迟 0 0 0 0 43
1 3 14 43 74
J3
1 n F Fi 135 / 5 27.0 n i 1
J3 -J5 -J4-J2 -J1
加工时间 J3 J5 J4 31 2 1 完成时间 31 33 34 交货期 31 32 33 延迟 0 1 1
J2
J1
29
11
63
74
45
61
18
13
1 n F Fi 235 / 5 47.0 n i 1
_
平均延迟=33/5=6.6
Tmax =18
等待时间, j=1,…,m