返回目录
《生产与运作管理》 3 单件作业计划问题

是十分复杂的一种作业计划问题，内容和方法。 描述

n个零件在m台机器上进行作业，使加工时间最短的 单件作业排序结果。

表示
n/m/G/Fmax

实质是任务分配问题：匈牙利算法。
《生产与运作管理》
从加工时间（费用）矩阵中寻找每一行的最小元素 将每一行元素减去该行最小元素 从加工时间（费用）矩阵中寻找每一列的最小元素 将每一列元素减去该列最小元素
CDS法举例

对l=1,2,…,m-1分别排序，取最优者。 当l＝1时，按Johnson算法得到加工顺序(1，2，3，4) ，F max ＝28 ； 当l＝2时，得到加工顺序(2，3，1，4)。对于顺序(2，3，1， 4)，相应的Fmax＝29； 所以，取顺序(1，2，3，4)。这就是最优顺序。
《生产与运作管理》
《生产运作管理》
第十一章 制造业作业计划与控制
1
《生产与运作管理》 引导案例-忙碌，不代表有效率

某忙碌的制造企业的生产准备会议



史黛西（生产主管）坐在会议桌旁，前面堆了一大堆文件， 她手上拿着一张名单，似乎已经准备好应付围攻。她说：“ 对，已经查出来了。事实上，昨天晚上我一直忙着追踪和查 证这些资料。结果，我发现出问题的零件有三十种。” 钟纳说：“你确定原材料都发出去了吗？” “没错，” 史黛西说，“他们已经根据时间表，把原材料发 出去了，但是在最后装配部还看不到这些零件，零件卡在新 瓶颈那里了。” “等一等，你怎么知道那真的是瓶颈呢？” 她说：“因为这些零件被耽搁了，我觉得一定是······”
来自上游 工作地的 工件
工件 排 队等 待 加工
工作地
加工完毕的 工件流向下 一工作地
《生产与运作管理》
排序的概念(续)


生产作业排序就是指对于等候某个设备或工作中 心加工的多个任务，确定这些任务加工的先后次 序。 目的：

提高设备或工作中心的效率 减少在制品占用量 缩短生产周期 保证按期交货
2
《生产与运作管理》
思考

目前现状

大量（超过30种）零部件延迟，未按期交货； 可能设备生产能力出现瓶颈，但生产能力事先已知；
生产过程存在一定的约束，包括人力、时间、设备等；
基于一定的优先策略，零部件的加工存在优先顺序；

假定排除设备故障等意外情况发生，问题出在哪 里？

任务分配 作业排序
生产作业计划与控制出了问题！
订单
市场分析 需求预测 生产计划 MRP
《生产与运作管理》
生产系统选址和布置 产品R&D 项目及网络计划 库存管理 设备管理
BPR 质量管理
生产作业计划 生产控制
JIT、LN、OPT等先进生产方式 战略管理
文化管理
《生产与运作管理》 主要内容
1. 2. 3. 4. 作业计划问题基本概念 流水车间的作业计划问题 单件车间的作业计划问题 生产作业控制
《生产与运作管理》
排序问题的分类
单台机器排序问题
按机器
排 序 问 题 分 类 多台机器排序问题
单件作业排序问题
流水线作业排序问题
静态的排序问题 按零件到达车间的情况 动态的排序问题 按目标函数的性质分类
确定型排序问题
按参数 随机型排序问题
《生产与运作管理》
单台机器的排序问题

n个工件全部经由一台机器处理
《生产与运作管理》
一般n/m/G/Fmax问题的启发式算法

可以采用分支定界法或整数规划法求得最优解。

但都是效率较低的算法，不能用于生产实际中； 启发式方法是求解一般单件车间排序问题使用最多的 方法。
两种作业计划 三种启发式算法
《生产与运作管理》
两种作业计划

两种作业计划的构成

半能动作业计划：各工序都按最早可能开工时 间安排的作业计划；
《生产与运作管理》
一般n/m/P/Fmax问题的启发式算法

一般的流水车间排列排序问题如想求得精确解可 用分支界定法：

但计算量比较大，以至于计算机也无法求解，因此 常用一些启发式算法求近似解。

作为一般生产实际中的排序问题，近优解能够满 足需要。

Palmer法
关键零件法 CDS法
《生产与运作管理》
返回目录
《生产与运作管理》 2 流水车间的作业计划问题
《生产与运作管理》
流水车间的作业计划问题

问题的描述

n个不同零件要按相同的加工路线经过m台机器加工 ，目标是使这批零件的加工周期最短（加工路线确 定，对不同的零件，根据目标求各个零件的加工次 序）

问题的表示
n/m/P/Fmax
《生产与运作管理》
《生产与运作管理》
Palmer法举例

【例】有一个4/3/P/Fmax问题，其加工时间如下表所示 ，试用Palmer法求解。
《生产与运作管理》
关键零件法

1 找出关键零件C，序号为m。


2 对余下的零件，若pi1≤pim，则按照pi1不减的顺序排序为Sa ，否则按pim不增的顺序排序为Sb。 3 顺序（ Sa ，C，Sb）即为近优解。
任务分配：每个工人、每个工作地的日生产任务； 生产排序：通过排序方法编制生产计划，提高生产 效率。 否

作业计划与作业排序是一回事么？

《生产与运作管理》
作业计划与作业排序

二者含义差别

作业计划是安排零部件的出产数量、设备及人工使用、投入 时间及出产时间。

分配资源给不同的任务，按照既定的优化目标，确定各种 资源利用的时间问题。
单件作业排序问题描述

一般的单件作业排序问题中单个工件可以描述为： 工件i的第j道工序是在机器k上进行
i, j, k
i — —工件代号 j — —工序号 k — —完成工件i的j道工序的机器的代号
【例】下列加工矩阵所代表的含义？
1， 1 1， 2， 3 1， 3， 2 1， D 2， 1 ， 3 2 ， 2 ， 1 2 ， 3 ， 2
《生产与运作管理》
任务分配的匈牙利算法举例

【例】如左上表，请用匈牙利法求出任务分配。
《生产与运作管理》
任务分配的匈牙利算法举例(续)
结果矩阵表示： 零件1由机器3加工(J1—M3) 零件2由机器2加工(J2—M2) 零件3由机器4加工(J3—M4) 零件4由机器1加工(J4—M1)
《生产与运作管理》

③若所有零件都已排序，停止。否则，转步骤①。
《生产与运作管理》
Johnson算法举例

【例】求如下6/2/P/Fmax问题的最优解。

求解过程如下：
《生产与运作管理》
Johnson算法步骤的改进

把Johnson算法作些改变，改变后的算法按以下步骤进 行：


①将所有ai≤bi的零件按ai值不减的顺序排成一个序列A； ②将所有ai＞bi的零件按bi值不增的顺序排成一个序列B； ③将A放到B之前，就构成了最优加工顺序。

排序，给出零部件在一台或一组设备上加工的先后顺序的工 作。 但是，编制作业计划的主要工作之一就是要确定出最佳的作 业顺序。

编制作业计划与排序的概念和目的都是不同的。

《生产与运作管理》
举例-工艺专业化
车床 仓 压床 车床 车床 钻床 钻床 焊接 油漆 焊接 焊接 仓
库
铣床
铣床
ቤተ መጻሕፍቲ ባይዱ铣床
铣床
磨床
磨床
装配

能动作业计划：任何一台机器的每段空闲时间都不 足以加工一道可加工工序的半能动计划；
无延迟作业计划：没有任何延迟出现的能动作业计 划。

《生产与运作管理》
若干算法符号

假设：


{St}——t道工序之前已排序工序构成的部分作业计 划； {Ot}——第t道工序可以安排的工序集合； Tk——{Ot}中工序Ok最早可能开工时间； Tk′——{Ot}中工序Ok最早可能完工时间。
《生产与运作管理》
加工路线示意图
《生产与运作管理》
排序问题的参数表示方法
n/ m/ A/ B
其中， n ——零件数 m ——机器数 A——车间类型 m 1，为空白 m 1时 如果为“F”，表示流水线作业排序问题 如果为“P”，表示流水线作业排列排序问题 如果为“G”，表示一般单件作业排序问题 B ——目标函数，通使其值最小
任务分配的 匈牙利算法
划出能覆盖尽可能多的零元素的直线
线条数等于矩阵的行数？ 是 从仅有一个零的行或列开始，找出零元素对 应的分配方案，每行和每列仅能确定一个元 素，最后使每行和每列都有一个零元素 零元素对应的就是最优分配方案
否 矩阵中未被线条穿过的 元素中减去这些元素中 的最小值，并将这个最 小值加到直线交叉的元 素上，其余元素不变
J1 J2 J3 Jn 到达系统工 件的集合 离开系统 （机器）
机器
为实现任务总等待时间最短的目标，保证尽可能多的 对象早日加工出来，加速资金周转，只需根据最短加工 时间准则对加工对象排序即可。
《生产与运作管理》
n项任务在两台机器的排序问题

n个工件都必须经过机器1和机器2的加工，即工艺路 线是一致的。
《生产与运作管理》 1 作业计划问题基本概念

MRP->零部件投入出产计划

车间生产作业计划； 落实车间生产任务到班组、工作地、工人；
涉及到任务分配和作业排序的问题。