第 7章 作业计划与控制
Operations Scheduling and Controlling
第 1节 作业计划 (Scheduling)
１,1 作业计划的含义与作用
作业计划 (Scheduling):作业计划是安排零部件（作业、活动）的
出产数量、设备及人工使用、投入时间及出产时间。
通过制定作业计划，可以使企业,
满足交货期要求 Meet Due Dates
使在制品库存最小 Minimize work-in-process inventory
使平均流程时间最小 Minimize the average flow time through the system
提供准确的工件状态信息 Provide for accurate job status information
提高机器 /工人的时间利用率 Provide for high machine/worker time
utilization(Minimize worker idle time)
减少调整准备时间 Reduce setup times
使生产和人工成本最低 Minimize production and worker costs
1.2 作业计划的种类
大量生产类型的作业计划 (Scheduling in High-Volume Systems)
成批生产类型的作业计划 (Scheduling in Intermediate-Volume
Systems)
单件小批生产类型作业计划 (Scheduling in Low-Volume Systems)
另外，还有其他分类,
车间作业计划 (Job Floor scheduling)
人力计划 (Personnel Scheduling)
设施计划 (Facilities Scheduling)
车辆调度计划 (Vehicle Scheduling)
供应商计划 (Vendor Scheduling)
工程项目计划 (Project Scheduling)
动态计划和静态计划 (Dynamic versus Static Scheduling)
1.3 制定作业计划的影响因素
? 工件到达的方式 (The job arrival pattern)
? 车间内机器的数量 (Number and variety of machines in the shop)
? 车间拥有的人力资源 (Number of workers in the shop)
? 工件移动方式 (Particular flow patterns)
? 不同调度准则的评价 (Evaluations of alternative rules)
1.4 作业计划与控制的关系
? 作业计划：给生产活动 (Production Activities)制定详细时间表
? 生产控制：以生产计划和作业计划为依据，检查、落实计划执
行情况，发现偏差即采取纠正措施，保证实现各项各项计划目
标。
第 2节 排序的基本概念 (Sequencing)
2.1 排序与编制作业计划的差别
上面讲了编制作业计划的问题, 在编制作业计划过程中,有一
个问题需要管理人员注意,即投入生产过程的作业顺序的安排,
· 作业计划是安排零部件（作业、活动）的出产数量、设备及
人工使用、投入时间及出产时间。
· 排序，给出零部件在一台或一组设备上加工的先后顺序的工
作。
所以,编制作业计划与排序的概念和目的都是不同的。但是，
编制作业计划的主要工作之一就是要确定出最佳的作业顺序。
确定出最佳的作业顺序看似容易，只要列出所有的顺序，
然后再从中挑出最好的就可以了，但要实现这种想法几乎
是不可能的。
例如，考虑 32项任务（工件），有 32！ ?2.6?1035种方案,
假定计算机每秒钟可以检查 1 billion个顺序,全部检验完毕
需要 8.4?1015个世纪,
如果只有 16个工件,同样按每秒钟可以检查 1 billion个顺
序计算,也需要 2/3年,
以上问题还没有考虑其他的约束条件,如机器、人力资源、
厂房场地等，如果加上这些约束条件，所需要的时间就无
法想象了。
所以，很有必要去寻找一些有效算法，解决管理中的实
际问题。
2.2 排序问题的分类
? 根据机器数的多少
单台机器的排序问题
多台机器的排序问题
? 根据加工路线的特征
单件车间排序 (Job Shop)
流水型排序 (Flow Shop)
? 根据工件到达系统的情况
静态排序
动态排序
? 根据参数的性质
确定型排序
随机型排序
? 根据要实现的目标
单目标排序
多目标排序
2.3 排序常用的符号
Ji----工件 i,i=1,2,....n
di----工件 i的交货期
Pi----工件 i的加工时间,,pij----工件 i在机器 j上的加工
时间,j=1,…,m ??
? m
j
iji pP
1
?
?
? m
j
iji wW
1
Wi----工件 i在系统内的等待时间,,wij----工件 i在机器 j
前的等待时间,j=1,…,m
Ci----工件 i的完成时间,在工件都已到达的情况下,Ci= Pi+ Wi
Fi----工件 i的流程时间, 在工件都已到达的情况下,Fi= Pi+ Wi
Li----工件 i的延误时间,Li= Ci- di,Li<=0 按期或完成提前 ；
Li>0 延误
Ti----工件 i的延期量,Ti=max{0,Li}
Ei----工件 i提前完成的时间
2.4 排序问题的表示方法
排序问题常用四个符号来描述,
n/m/A/B
其中,n-----工件数；
m-----机器数；
A----车间类型,F=流水型排序
P=排列排序
G=一般类型,即单件型排序
B-----目标函数
第 3节 单台机器的排序问题
3.1 单台机器排序问题
n个工件全部经由一台机器处理
J1
J2
J3
J
n
机器
到达系统工
件的集合
离开系统
（机器）
3.2 常见单台机器排序问题的目标函数
1) 平均流程时间最短
F n F i
i
n_
?
?
?1
1
为 n个零件经由一台机器的平均流程时间。 定义,
F n F i
i
n_
?
?
?1
1
目标函数 MIN,
2）最大延期量最小
? ?T T im a x m a x?定义, 为最大延期量。
目标函数 m in m a x T
根据排序目标的不同，可以选择不同的排
序规则，有时又称为确定优先权 (Priorities)。
常见的优先权规则 (Priority rules)有,
SPT---Shortest Process Time,
EDD---Earliest Due Date
FCFS---First Come First Served
CR---Critical Rate
等,分别用于解决不同的问题。
3.3 求平均流程时间最短的排序问题
? 求平均流程时间最短的作业顺序，采用 SPT原则。
按工件加工时间的长短，按不减的顺序从小到大安排各
项作业。
?例：一个车间有一台加工中心，现有 5个工件需要该机器加
工。相关的加工时间和要求完成时间（交货期）如下表所示，
求平均流程时间最短的作业顺序。
J1
J2
J3
J4
J5
加工时间
11
29
31
1
2
交货期
61
45
31
33
32
解：根据 SPT原则，得出,
J4 -J5 -J1 -J2 -J3
有关项目的计算,
加工时间
完成时间 交货期
延迟
J4
1
1
33
0
J5 2 3 32 0
J1
11
14
61
0
J2 29 43 45 0
31 74 31 43 J3
F n F i
i
n_ /,? ? ?
?
?1 135 5 27 0
1
3.4 求最大延期量最小的排序问题
? 求最大延期量最小的作业顺序采用 EDD原则。
EDD(Earliest Due Date),Jobs are sequenced in increasing
order of their due dates,
? 例：借用上面的例子，求最大延期量最小的作业顺序。
解：根据 EDD原则，得出,
J3 -J5 -J4-J2 -J1
加工时间
完成时间
交货期
延迟
J3
31
31
31
0
J5 2 33 32 1
J4
1
34
33
1
J2 29 63 45 18
J1
11
74
61
13
平均延迟 =33/5=6.6
F n F i
i
n_
/,? ? ?
?
?1 235 5 47 0
1
Tmax =18
进一步考虑：在最大延期量不变的情况下，如何使平
均流程时间缩短？如果想同时满足这两个目标，就是
多目标排序。
第 4节 n项任务在两台机器的排序问题
Scheduling n Jobs on Two Machines
4.1 两台机器排序问题的含义
n个工件都必须经过机器 1和机器 2的加工，即工艺路线是一致的。
机器 1
到达系统工
件的集合
离开系统
（机器）
J1
J2
J3
Jn
机器 2
4.2 两台机器排序问题的目标
? 两台机器排序的目标是使最大完成时间（总加工周期）
Fmax最短。 Fmax的含义见如下的甘特图 (Gantt Chart)。
? 多台机器排序的目标一般也是使最大完成时间（总加工
周期） Fmax最短。
Fmax 时间
机器
A
B
在机器 A上的作业时间
总加工周期
4.3 两台机器排序问题的算法
实现两台机器排序的最大完成时间 Fmax最短的目标，一优
化算法就是著名的约翰逊法 (Johnson’s Law)。其具体求解过
程如下例所示。
约翰逊法解决这种问题分为 4个步骤,
(1)列出所有工件在两台设备上的作业时间 。
(2)找出作业时间最小者 。
(3)如果该最小值是在设备 1上, 将对应的工件排在前面,
如果该最小值是在设备 2上, 则将对应的工件排在后面 。
(4)排除已安排好的工件，在剩余的工件中重复步骤 (2)和
(3)，直到所有工件都安排完毕。
例：某一班组有 A,B两台设备，要完成 5个工件的加
工任务。每个工件在设备上的加工时间如下表所示。
求总加工周期最短的作业顺序。
工件在两台设备上的加工时间
工件编号
J1 J2 J3 J4 J5
设备 A
3 6 7 1 5
设备 B
2 8 6 4 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
(a) J1 - J2 - J3- J4 - J5
30
A
B
26
A
B
(b) J4 - J2 - J3- J5 - J1
可以看出，初始作业顺序的总加工周期是 30，用约翰逊法排出的作业顺
序总加工周期是 26，显然后者的结果优于前者。
4.4 两台机器排序问题算法的扩展 (Extension to Three Machines)
一般情况下，当机器数为 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 2 3 4 5
机器 A
44 913 821 627 532
机器 B
59 619 223 330 436
机器 C
817 1029 635 742 1153
解, 检查上表,发现,
min Ai = 4
max Bi = 6
min Ci = 6
因此,满足以上条件,建立两台机器的作业时间表,
应用 Johnson法则，得出,
１－４－５－２－３
总加工周期为,
1 2 3 4 5
机器 A’
9 15 10 9 9
机器 B’
13 16 8 10 15
1 4 5 2 3
机器 A 44 610 515 924 832
机器 B 59 313 419 630 234
机器 C
817 724 1135 1045 651
4.5 m(m?3)台机器排序问题的算法
? 一般采用启发式算法 (Heuristics)解决这类问题。
? 关键工件法
步骤 1 计算,找出其中最大者，定义为关键工件 JC。 ?
?
m
j ij
p
1
步骤 2 除 JC外，将满足 pi1<p1m的工件，按 ti1值的大小，从
小到大排在 JC的前面。
步骤 3 除 JC外，将满足 pi1>p1m的工件，按 tim值的大小，从
大到小排在 JC的后面。
步骤 4 除 JC外，将满足 pi1=p1m的工件，排在 JC的前面或者后面。
步骤 5 如有多个方案，可再加比较，从中选优。
? 关键工件法举例
J1 J2 J3 J4 J5 J6
机器 1 pi1 5 5 4 1 2 10
机器 2 pi2 5 5 5 3 6 10
机器 3 pi3 8 3 3 4 7 4
机器 4 pi4 2 8 2 1 5 6
机器 5 pi5 5 2 1 2 8 10
总和 25 23 15 11 28 40
找出关键工件：工作负荷最大的 40，对应的是工件 6，所以 JC=J6
确定排在关键工件前面的工件：满足步骤 2条件的有 J4,J5,所以有 J4 – J5 –J6 –
确定排在关键工件后面的工件：满足步骤 3条件的有 J2,J3,所以有 – J6 – J2 –J3
满足步骤 4条件的有 J1,所以有 – J6 – J1,或者 –J1 – J6
最后有,J4 – J5 –J6– J1 – J2 –J3, 或者 J4 – J5 –J1 – J6 – J2 –J3
第 5节 服务业企业作业排序问题
5.1 服务作业排序与生产作业排序的主要区别
l 所提供产品的类型
由于服务过程有顾客参与,作业排序对他们有直接影响,并因此成为
服务的一部分,而在生产作业排序对产品的最终使用者没有直接影响
l 排序内容
在服务业中,排序要定义服务交易的时间或消耗点；而在制造业中
仅仅定义产品生产的操作步骤
l 过程控制
在服务业中,顾客参与服务过程,并且对全部操作过程施加影响,
l 人员规模
在顾客化服务中,服务的输出与劳动力的最佳规模之间的关系很难确
定；而生产作业中,两者之间的关系有紧密联系,因此最佳的作业顺序可
以被计算出来
5.2 服务作业排序方法之一 —— 安排顾客需求
预约：如医生、律师等的服务
预定：顾客预定旅馆房间、火车或飞机票
排队等待：一种为顾客排序的不太准确的方法是允许需
求积压，让顾客排队等待。例如，餐馆、银行、零售商
店等。
5.3 服务作业排序方法之二 —— 安排服务人员
当需要快速响应顾客需求、且需求量大致可以预计时，
通常使用这种方法。如邮局营业员、护士、警察的工作
日和休息日安排；一天营业 24小时、一周 7天都营业的商
店保安人员安排；等等
第 6节 车间生产控制
Shop-Floor Control
6.1 车间生产控制
6.2 车间作业控制的主要功能是
– 确定车间作业指令
– 获取在制品占用信息
– 将车间作业状况信息反馈给上级及有关部门
– 提供实际产出信息
– 提供成本核算所需要的车间生产和在制品信息
– 提供人力、设备等的利用率、效率和生产率信息
6.3 车间作业控制的主要工具
甘特图 (Gantt Chart)
输入 /输出控制 (Input/Output Control)
派工单 (Dispatching)
计算机辅助作业控制
Operations Scheduling and Controlling
第 1节 作业计划 (Scheduling)
１,1 作业计划的含义与作用
作业计划 (Scheduling):作业计划是安排零部件（作业、活动）的
出产数量、设备及人工使用、投入时间及出产时间。
通过制定作业计划，可以使企业,
满足交货期要求 Meet Due Dates
使在制品库存最小 Minimize work-in-process inventory
使平均流程时间最小 Minimize the average flow time through the system
提供准确的工件状态信息 Provide for accurate job status information
提高机器 /工人的时间利用率 Provide for high machine/worker time
utilization(Minimize worker idle time)
减少调整准备时间 Reduce setup times
使生产和人工成本最低 Minimize production and worker costs
1.2 作业计划的种类
大量生产类型的作业计划 (Scheduling in High-Volume Systems)
成批生产类型的作业计划 (Scheduling in Intermediate-Volume
Systems)
单件小批生产类型作业计划 (Scheduling in Low-Volume Systems)
另外，还有其他分类,
车间作业计划 (Job Floor scheduling)
人力计划 (Personnel Scheduling)
设施计划 (Facilities Scheduling)
车辆调度计划 (Vehicle Scheduling)
供应商计划 (Vendor Scheduling)
工程项目计划 (Project Scheduling)
动态计划和静态计划 (Dynamic versus Static Scheduling)
1.3 制定作业计划的影响因素
? 工件到达的方式 (The job arrival pattern)
? 车间内机器的数量 (Number and variety of machines in the shop)
? 车间拥有的人力资源 (Number of workers in the shop)
? 工件移动方式 (Particular flow patterns)
? 不同调度准则的评价 (Evaluations of alternative rules)
1.4 作业计划与控制的关系
? 作业计划：给生产活动 (Production Activities)制定详细时间表
? 生产控制：以生产计划和作业计划为依据，检查、落实计划执
行情况，发现偏差即采取纠正措施，保证实现各项各项计划目
标。
第 2节 排序的基本概念 (Sequencing)
2.1 排序与编制作业计划的差别
上面讲了编制作业计划的问题, 在编制作业计划过程中,有一
个问题需要管理人员注意,即投入生产过程的作业顺序的安排,
· 作业计划是安排零部件（作业、活动）的出产数量、设备及
人工使用、投入时间及出产时间。
· 排序，给出零部件在一台或一组设备上加工的先后顺序的工
作。
所以,编制作业计划与排序的概念和目的都是不同的。但是，
编制作业计划的主要工作之一就是要确定出最佳的作业顺序。
确定出最佳的作业顺序看似容易，只要列出所有的顺序，
然后再从中挑出最好的就可以了，但要实现这种想法几乎
是不可能的。
例如，考虑 32项任务（工件），有 32！ ?2.6?1035种方案,
假定计算机每秒钟可以检查 1 billion个顺序,全部检验完毕
需要 8.4?1015个世纪,
如果只有 16个工件,同样按每秒钟可以检查 1 billion个顺
序计算,也需要 2/3年,
以上问题还没有考虑其他的约束条件,如机器、人力资源、
厂房场地等，如果加上这些约束条件，所需要的时间就无
法想象了。
所以，很有必要去寻找一些有效算法，解决管理中的实
际问题。
2.2 排序问题的分类
? 根据机器数的多少
单台机器的排序问题
多台机器的排序问题
? 根据加工路线的特征
单件车间排序 (Job Shop)
流水型排序 (Flow Shop)
? 根据工件到达系统的情况
静态排序
动态排序
? 根据参数的性质
确定型排序
随机型排序
? 根据要实现的目标
单目标排序
多目标排序
2.3 排序常用的符号
Ji----工件 i,i=1,2,....n
di----工件 i的交货期
Pi----工件 i的加工时间,,pij----工件 i在机器 j上的加工
时间,j=1,…,m ??
? m
j
iji pP
1
?
?
? m
j
iji wW
1
Wi----工件 i在系统内的等待时间,,wij----工件 i在机器 j
前的等待时间,j=1,…,m
Ci----工件 i的完成时间,在工件都已到达的情况下,Ci= Pi+ Wi
Fi----工件 i的流程时间, 在工件都已到达的情况下,Fi= Pi+ Wi
Li----工件 i的延误时间,Li= Ci- di,Li<=0 按期或完成提前 ；
Li>0 延误
Ti----工件 i的延期量,Ti=max{0,Li}
Ei----工件 i提前完成的时间
2.4 排序问题的表示方法
排序问题常用四个符号来描述,
n/m/A/B
其中,n-----工件数；
m-----机器数；
A----车间类型,F=流水型排序
P=排列排序
G=一般类型,即单件型排序
B-----目标函数
第 3节 单台机器的排序问题
3.1 单台机器排序问题
n个工件全部经由一台机器处理
J1
J2
J3
J
n
机器
到达系统工
件的集合
离开系统
（机器）
3.2 常见单台机器排序问题的目标函数
1) 平均流程时间最短
F n F i
i
n_
?
?
?1
1
为 n个零件经由一台机器的平均流程时间。 定义,
F n F i
i
n_
?
?
?1
1
目标函数 MIN,
2）最大延期量最小
? ?T T im a x m a x?定义, 为最大延期量。
目标函数 m in m a x T
根据排序目标的不同，可以选择不同的排
序规则，有时又称为确定优先权 (Priorities)。
常见的优先权规则 (Priority rules)有,
SPT---Shortest Process Time,
EDD---Earliest Due Date
FCFS---First Come First Served
CR---Critical Rate
等,分别用于解决不同的问题。
3.3 求平均流程时间最短的排序问题
? 求平均流程时间最短的作业顺序，采用 SPT原则。
按工件加工时间的长短，按不减的顺序从小到大安排各
项作业。
?例：一个车间有一台加工中心，现有 5个工件需要该机器加
工。相关的加工时间和要求完成时间（交货期）如下表所示，
求平均流程时间最短的作业顺序。
J1
J2
J3
J4
J5
加工时间
11
29
31
1
2
交货期
61
45
31
33
32
解：根据 SPT原则，得出,
J4 -J5 -J1 -J2 -J3
有关项目的计算,
加工时间
完成时间 交货期
延迟
J4
1
1
33
0
J5 2 3 32 0
J1
11
14
61
0
J2 29 43 45 0
31 74 31 43 J3
F n F i
i
n_ /,? ? ?
?
?1 135 5 27 0
1
3.4 求最大延期量最小的排序问题
? 求最大延期量最小的作业顺序采用 EDD原则。
EDD(Earliest Due Date),Jobs are sequenced in increasing
order of their due dates,
? 例：借用上面的例子，求最大延期量最小的作业顺序。
解：根据 EDD原则，得出,
J3 -J5 -J4-J2 -J1
加工时间
完成时间
交货期
延迟
J3
31
31
31
0
J5 2 33 32 1
J4
1
34
33
1
J2 29 63 45 18
J1
11
74
61
13
平均延迟 =33/5=6.6
F n F i
i
n_
/,? ? ?
?
?1 235 5 47 0
1
Tmax =18
进一步考虑：在最大延期量不变的情况下，如何使平
均流程时间缩短？如果想同时满足这两个目标，就是
多目标排序。
第 4节 n项任务在两台机器的排序问题
Scheduling n Jobs on Two Machines
4.1 两台机器排序问题的含义
n个工件都必须经过机器 1和机器 2的加工，即工艺路线是一致的。
机器 1
到达系统工
件的集合
离开系统
（机器）
J1
J2
J3
Jn
机器 2
4.2 两台机器排序问题的目标
? 两台机器排序的目标是使最大完成时间（总加工周期）
Fmax最短。 Fmax的含义见如下的甘特图 (Gantt Chart)。
? 多台机器排序的目标一般也是使最大完成时间（总加工
周期） Fmax最短。
Fmax 时间
机器
A
B
在机器 A上的作业时间
总加工周期
4.3 两台机器排序问题的算法
实现两台机器排序的最大完成时间 Fmax最短的目标，一优
化算法就是著名的约翰逊法 (Johnson’s Law)。其具体求解过
程如下例所示。
约翰逊法解决这种问题分为 4个步骤,
(1)列出所有工件在两台设备上的作业时间 。
(2)找出作业时间最小者 。
(3)如果该最小值是在设备 1上, 将对应的工件排在前面,
如果该最小值是在设备 2上, 则将对应的工件排在后面 。
(4)排除已安排好的工件，在剩余的工件中重复步骤 (2)和
(3)，直到所有工件都安排完毕。
例：某一班组有 A,B两台设备，要完成 5个工件的加
工任务。每个工件在设备上的加工时间如下表所示。
求总加工周期最短的作业顺序。
工件在两台设备上的加工时间
工件编号
J1 J2 J3 J4 J5
设备 A
3 6 7 1 5
设备 B
2 8 6 4 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
(a) J1 - J2 - J3- J4 - J5
30
A
B
26
A
B
(b) J4 - J2 - J3- J5 - J1
可以看出，初始作业顺序的总加工周期是 30，用约翰逊法排出的作业顺
序总加工周期是 26，显然后者的结果优于前者。
4.4 两台机器排序问题算法的扩展 (Extension to Three Machines)
一般情况下，当机器数为 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 2 3 4 5
机器 A
44 913 821 627 532
机器 B
59 619 223 330 436
机器 C
817 1029 635 742 1153
解, 检查上表,发现,
min Ai = 4
max Bi = 6
min Ci = 6
因此,满足以上条件,建立两台机器的作业时间表,
应用 Johnson法则，得出,
１－４－５－２－３
总加工周期为,
1 2 3 4 5
机器 A’
9 15 10 9 9
机器 B’
13 16 8 10 15
1 4 5 2 3
机器 A 44 610 515 924 832
机器 B 59 313 419 630 234
机器 C
817 724 1135 1045 651
4.5 m(m?3)台机器排序问题的算法
? 一般采用启发式算法 (Heuristics)解决这类问题。
? 关键工件法
步骤 1 计算,找出其中最大者，定义为关键工件 JC。 ?
?
m
j ij
p
1
步骤 2 除 JC外，将满足 pi1<p1m的工件，按 ti1值的大小，从
小到大排在 JC的前面。
步骤 3 除 JC外，将满足 pi1>p1m的工件，按 tim值的大小，从
大到小排在 JC的后面。
步骤 4 除 JC外，将满足 pi1=p1m的工件，排在 JC的前面或者后面。
步骤 5 如有多个方案，可再加比较，从中选优。
? 关键工件法举例
J1 J2 J3 J4 J5 J6
机器 1 pi1 5 5 4 1 2 10
机器 2 pi2 5 5 5 3 6 10
机器 3 pi3 8 3 3 4 7 4
机器 4 pi4 2 8 2 1 5 6
机器 5 pi5 5 2 1 2 8 10
总和 25 23 15 11 28 40
找出关键工件：工作负荷最大的 40，对应的是工件 6，所以 JC=J6
确定排在关键工件前面的工件：满足步骤 2条件的有 J4,J5,所以有 J4 – J5 –J6 –
确定排在关键工件后面的工件：满足步骤 3条件的有 J2,J3,所以有 – J6 – J2 –J3
满足步骤 4条件的有 J1,所以有 – J6 – J1,或者 –J1 – J6
最后有,J4 – J5 –J6– J1 – J2 –J3, 或者 J4 – J5 –J1 – J6 – J2 –J3
第 5节 服务业企业作业排序问题
5.1 服务作业排序与生产作业排序的主要区别
l 所提供产品的类型
由于服务过程有顾客参与,作业排序对他们有直接影响,并因此成为
服务的一部分,而在生产作业排序对产品的最终使用者没有直接影响
l 排序内容
在服务业中,排序要定义服务交易的时间或消耗点；而在制造业中
仅仅定义产品生产的操作步骤
l 过程控制
在服务业中,顾客参与服务过程,并且对全部操作过程施加影响,
l 人员规模
在顾客化服务中,服务的输出与劳动力的最佳规模之间的关系很难确
定；而生产作业中,两者之间的关系有紧密联系,因此最佳的作业顺序可
以被计算出来
5.2 服务作业排序方法之一 —— 安排顾客需求
预约：如医生、律师等的服务
预定：顾客预定旅馆房间、火车或飞机票
排队等待：一种为顾客排序的不太准确的方法是允许需
求积压，让顾客排队等待。例如，餐馆、银行、零售商
店等。
5.3 服务作业排序方法之二 —— 安排服务人员
当需要快速响应顾客需求、且需求量大致可以预计时，
通常使用这种方法。如邮局营业员、护士、警察的工作
日和休息日安排；一天营业 24小时、一周 7天都营业的商
店保安人员安排；等等
第 6节 车间生产控制
Shop-Floor Control
6.1 车间生产控制
6.2 车间作业控制的主要功能是
– 确定车间作业指令
– 获取在制品占用信息
– 将车间作业状况信息反馈给上级及有关部门
– 提供实际产出信息
– 提供成本核算所需要的车间生产和在制品信息
– 提供人力、设备等的利用率、效率和生产率信息
6.3 车间作业控制的主要工具
甘特图 (Gantt Chart)
输入 /输出控制 (Input/Output Control)
派工单 (Dispatching)
计算机辅助作业控制
