机器 A
B
在机器A上的作业时间
总加工周期
Fmax
时间

• 假定所有工件的到达时间都为0，则Fmax等 于排在末位加工的工件在车间的停留时间。
• 计算Fmax的几个假定条件：
– 机器M1不会发生空闲；
– 对其它机器，能对某一工件加工必须具备2个条 件：机器必须完成排前一位的工件的加工；要加 工的工件的上道工序已经完工。
工件编号 J1 J2 J3 J4 J5
设备A
3 67 15
设备B
2 86 43
解：由约翰逊法可知，表中最小加工时间值是1个
时间单位，它又是出现在设备1上，根据约翰逊法 的规则，应将对应的工件4排在第一位，即得：
J4 - * - * - * - * 去掉J4，在剩余的工件中再找最小值，不难看出，
最小值是2个时间单位，它是出现在设备2上的，
流水作业排序问题的基本特征：
• 每个工件的加工路线都一样。如车—铣—磨。这里 指的是工件的加工流向一致，并不要求每个工件必 须在每台机器上加工。如有的工件为车—磨，有的 为铣—磨。
• 不仅加工路线一致，而且所有工件在各台机器上的 加工顺序也一样，这种排序称为排列排序（同顺序 排序）。如工件排序为：J1—J3—J2，则表示所有机 器都是先加工J1，然后加工J3，最后加工J2。
单件车间排序问题的基本特征：
• 每个工件都有其独特的加工路线，工件没有 一定的流向。
表示方法
一般正规的表示方法为：n/m/A/B n：工件数；m：机器数； A：作业类型（F、P、G）；B：目标函数
4、排序常用的符号
Ji----工件i，i=1,2,....n Mj ----机器,j=1,2…m
di----工件i的交货期 pij----工件i在机器j上的加工时间,j=1,…,m Pi----工件i的加工时间, m
所以，作业排序也就是要确定工件在机器上 的加工顺序，可用一组工件代号的一种排列 来表示。
如可用（1，6，5，4，3，2）表示加工顺序： J1—J6—J5—J4—J3—J2。
2、作业计划（Scheduling）
• 作业计划是安排零部件（作业、活动）的出 产数量、设备及人工使用、投入时间及出产 时间。
Pi pij j 1
m
Wi----工件i在系统内的等待时间,Wi
wij
j 1
wij----工件i在机器j前的等待时间, j=1,…,m
• Ci----工件i的完成时间, 在工件都已到达的 情况下, Ci= Pi+ Wi
• Fi----工件i的流程时间，在工件都已到达
的情况下, Fi= Pi+ Wi
• 排序的作用
– 油漆生产顺序：某企业生产白、灰、红、 蓝四种油漆，每次生产前都有清洗容器的 调整准备时间。按怎样的顺序，总的调整 准备时间最少？
– 复印排序问题：有四人同时到达复印室， 每人的复印量不同，如何安排顺序，使得 他们的平均等待时间和平均流程时间最小？
白
灰
红
蓝
白
0
1
2
3
灰
5
0
1
2
红
7
第八章 生产作业计划
Operations Scheduling and Controlling
第一节 生产作业排序 第二节 生产作业控制
第一节 生产作业排序
一、基本概念
1、排序
• 排序就是要将不同的工作任务安排一个执行 的顺序，使预定的目标最优化。
• 实际上就是要解决如何按时间的先后，将有 限的人力、物力资源分配给不同工作任务， 使预定目标最优化的问题。
• Li----工件i的延误时间, Li= Ci- di , Li<=0
按期或完成提前；
•
Li>0 延误
• Ti----工件i的延期量, Ti=max{0, Li}
• Ei----工件i提前完成的时间
5、排序问题的假设条件
• 工件同时到达。 • 一个工件不能同时在几台不同的机器上加工。 • 工件在加工过程中采取平行移动方式。 • 不允许中断。 • 每道工序只在一台机器上完成。 • 每台机器同时只能加工一个工件。
• 作业计划与排序不是一回事，它不仅要确定 工件的加工顺序，而且还要确定每台机器加 工每个工件的开工时间和完工时间。
• 如果按最早可能开（完）工时间来编排作业 计划，则排序完后，作业计划也就确定了。
3、排序问题的分类与表示
• 根据机器数的多少 单台机器的排序问题 多台机器的排序问题
• 根据加工路线的特征 单件作业排序(Job Shop) 流水型排序(Flow Shop)
6
0
1
蓝
9
8
6
0
• 方案1：白-灰-红-蓝 T-setup=12 方案2：蓝-红-灰-白 T-setup=20
排序中常用的几个概念
• 工件（Job）：服务对象； • 机器（Machine、Processor）：服务者。
如： • n个零件在机器上加工，则零件是工件，设备
是机器；
• 工人维修设备，出故障的设备是工件，工人 是机器。
3、 Fmax问题的算法
• 两台机器排序的目标是使Fmax最短。
• 假定：ai为工件Ji在机器M1上的加工时间， bi为工件Ji在机器M2上的加工时间，每个工 件按M1—M2的路线加工。
• Johnson算法：
– 从加工时间矩阵中找出最短的加工时间。 – 若最短时间出现在M1上，则对应的工件尽可能往
• 工件数、机器数和加工时间已知，加工时间与加工 顺序无关。
二、两台机器的排序问题
1、 两台机器排序问题的含义
• n个工件都必须经过机器1和机器2的加工，即工 艺路线是一致的。
J1 J2
机器1
J3
Jn
到达系统工件的
集合
机器2
离开系统（机 器）
2、最长流程时间
• 最长流程时间（加工周期Fmax ）：从第一个工件 在第一台机器上加工起到最后一个工件在最后一台 机器上加工完毕为止所经过的时间。
所以应将对应的工件J1排在最后一位，即：
J4 - * - * - * - J1
再去掉J1，在剩余的J2、J3、J5中重复上述步骤， 求解过程为：
前排。
– 若最短时间出现在M2上，则对应的工件尽可能往 后排。
– 若最短时间有多个，则任选一个。 – 划去已排序的工件。 – 若所有工件都已排序，则停止，否则重复上述步
骤。
例：某一班组有A、B两台设备，要完成5个工件的加
工任务。每个工件在设备上的加工时间如下表所示。 求总加工周期最短的作业顺序。
工件在两台设备上的加工时间