《《精编》生产运作管理制造业作业计划与控制课件》由会员分享，可在线阅读，更多相关《《精编》生产运作管理制造业作业计划与控制课件（108页珍藏版）》请在金锄头文库上搜索。
1、第十一章制造业作业计划与控制 引言通过MRP确定各车间的零部件投入出产计划 从而将全厂性的产品出产计划变成了各车间生产作业计划 将车间的生产任务变成各个班组 各个工作地和各个工人的任务 只有将计划安排到工作地和工人 任务才算真正落到实处 将任务安排到工作地 牵涉到任务分配和作业排序问题 这正是本章要讨论的 11 1作业计划问题的基本概念11 2流水作业排序问题11 3单件作业的排序问题11 4生产作业控制 11收入 费用和利润 要求掌握 最长流程时间的计算2 约翰逊算法3 一般流水作业排序问题的3种启发式算法4 相同零件的3种移动方式下机器加工周期的计算方法 学习目的与要求 重点最长流程时间的
2、计算约翰逊算法相同零件的3种移动方式下机器加工周期的计算方法难点一般流水作业排序问题的启发式算法 教学重点与难点 生产任务的最终落实 MRP确定各车间的零部件投入出产计划 将全厂性的产品出产计划变成了各车间的生产任务 各车间要将车间的生产任务变成各个班组 各个工作地和各个工人的任务 将任务安排到工作地 牵涉到作业计划 编制作业计划要解决的问题 由于每台机器都可能被分配了多项任务 就带来了零件在机器上加工的顺序问题 编制作业计划要解决先加工哪个工件 后加工哪个工件的加工顺序问题确定机器加工每个工件的开始时间和完成时间例如 医院要安排病人手术 为此要安排手术室 配备手术器械 手术医师和护士 第一节
3、排序问题的基本概念 一 名词术语排序 确定工件在机器上的加工顺序 作业计划 不仅要确定工件的加工顺序 而且还要确定机器加工每个工件的开始时间和完成时间 通常情况下都是按最早可能开 完 工时间来编制作业计划 派工 按作业计划的要求 将具体生产任务安排到具体的机床上加工 赶工 实际进度已落后于计划进度时采取的行动 机器 可以是工厂里的各种机床 也可以是维修工人 表示 服务者 零件 代表 服务对象 零件可以是单个零件 也可以是一批相同的零件 加工顺序 则表示每台机器加工n个零件的先后顺序 是排序和编制作业计划要解决的问题 二 假设条件和符号说明 假设条件 1 一个工件不能同时在几台不同的机器上加工
4、2 工件在加工过程中采取平行移动方式 即当上一道工序完工后 立即送下道工序加工 3 不允许中断 一个工件一旦开始加工 必须一直进行到完工 不得中途停止插入其他工件 4 每道工序只在一台机器上完成 5 工件数 机器数和加工时间已知 加工时间与加工顺序无关 6 每台机器同时只能加工一个工件 有关符号 Ji 工件i i 1 2 nMj 机器j j 1 2 npij为Ji在Mj上的加工时间ri为Ji的到达时间 指Ji从外部进入车间 可以加工的最早时间di为Ji的完工期限Ci为Ji的完工时间Cmax为最长完工时间Fi为Ji的流程时间 即工件在车间的实际停留时间Fmax为最长流程时间Li为工件的延迟时间L
5、max为最长延迟时间 三 排序问题的分类 根据机器数的多少单台机器的排序问题多台机器的排序问题对于多台机器排序问题 根据加工路线的特征 分成单件作业排序 Job Shop 问题流水作业排序 Flow Shop 问题工件的加工路线不同 是单件作业排序问题的基本特征 所有工件的加工路线完全相同 是流水作业排序问题的基本特征 也就是说 每个零件都顺序地经过线上不同机器加工 它们的加工路线一致 根据工件到达系统的情况静态排序动态排序根据参数的性质确定型排序随机型排序 4参数法 n m A B其中 n为工件数m为机器数A车间类型 在A的位置若标以标以 P 则表示流水作业排列排序问题 若标以 G 则表示一
6、般单件作业排序问题 当m 1 则A处为空白 B为目标函数 通常是使其值最小例如 n 3 P Cmax 四 作业排序方案的评价标准 1 工作流程时间从工件可以开始加工至完工的时间 包括在各个机器之间的移动时间 等待时间 加工时间以及由于机器故障 部件无法得到等问题引起的延误时间等 2 加工周期完成一组工作所需的全部时间 它是从第一个工件在第一台机器上开始加工时算起 到最后一个工件在最后一台机器上完工时为止所经过的时间 3 在制品库存 WIP 在制品是对介于原材料和成品之间的生产过程中的产品的称谓 一个工件正从一个工作地移向另一个 由于一些原因被拖延加工 正在被加工或放置于零件库中 都可以看作在制
7、品库存 4 利用率用一台机器或一个工人的有效生产时间占总工作时间的百分比来表示 五 优先调度规则 调度方法 所谓调度方法 就是运用若干预先规定的优先顺序规则 顺次决定下一个应被加工的工件的排序方法 一个工作地可选择的下一个工件会有很多种 因此 按什么样的准则来选择 对排序方案的优劣有很大影响 常用的优先顺序规则 FCFS规则优先选择最早进入可排序集合的工件 EDD规则优先选择完工期限最紧的工作 SPT规则优先选择加工时间最短的工件 SCR规则优先选择临界比最小的工件 临界比为工作允许停留时间和工件余下加工时间之比 MWKR规则优先选择余下加工时间最长的工件 LWKR规则优先选择余下加工时间最短
8、的工件 MOPNR规则优先选择余下工序数最多的工件 RANDOM规则随机地挑选下一个工件 一般作业排序的目标满足顾客或下一道工序的交货期要求流程时间最短准备时间最短或成本最小化在制品库存最低机器设备或劳动力利用最大化 例 一个加工车间负责加工发动机机壳 现在共有5个机壳等待加工 只有一名技工在岗 做此项工作 现在已经估算出各个机壳的标准加工时间 顾客也已经明确提出了他们所希望的完工时间 下表显示了周一上午的情况 顾客的取货时间用从周一上午开始 还有多少工作小时来计算 SPT规则排序结果 顾客实际取货时间基于以下假设 顾客不会在预定取货时间之前来取货 如果有拖延发生 他们将在加工结束时马上取走
9、流程时间 等待时间 加工时间平均在制品库存 各工件流程时间之和 加工周期平均总库存 各工件实际取货时间之和 加工周期 EDD规则排序结果 顾客实际取货时间基于以下假设 顾客不会在预定取货时间之前来取货 如果有拖延发生 他们将在加工结束时马上取走 比较SPT规则和EDD规则的排序结果 用SPT规则排序 其平均流程时间更短 在制品库存更少 用EDD规则 可以给顾客提供更好的服务 平均延迟时间较少 它也提供了更低的总库存水平 优先调度法则 按SPT法则可使工件的平均流程时间最短 从而减少在制品量 FCFS法则来自排队论 它对工件较公平 EDD法则可使工件延误时间最小 MWKR法则使不同工作量的工件的
10、完工时间尽量接近 LWKR法则 使工作量小的工件尽快完成 第二节流水作业排序问题 流水作业排序问题的基本特征是每个工件的加工路线都一致 加工路线一致 是指工件的流向一致 并不要求每个工件必须经过加工路线上每台机器加工 对于流水作业排序问题 工件在不同机器上的加工顺序不尽一致 排列排序问题 所有工件在各台机器上的加工顺序都相同的情况 一 最长流程时间Fmax的计算 n m P Fmax问题 n个零件要按相同的加工路线经过m台机器加工 目标是使这批零件的最长流程时间最短 最长流程时间又称加工周期 它是从第一个零件在第一台机器开始加工时算起 到最后一个零件在最后一台机器上完成加工时为止所经过的时间
11、例有一个6 4 P Fmax问题 其加工时间如下表所示 当按顺序S 6 1 5 2 4 3 加工时 求Fmax i pi1 pi2 pi3 pi4 6 1 5 2 4 3 2 5 5 1 4 4 5 4 4 4 5 3 2 5 8 2 1 7 5 3 3 6 7 4 2 6 10 12 13 16 7 11 15 20 27 33 12 17 22 30 35 42 13 21 25 32 38 46 二 两台机器排序问题 两个或更多的作业必须在两台机器上以相同的工序进行加工 要使加工周期最短 约翰逊于1954年提出了一个有效算法 那就是著名的Johnson算法 约翰逊算法包括以下几个步骤 1
12、 列出每个作业在两台机器上的加工时间 2 选择最短的加工时间 如果有两个相同的值 则任选一个 3 如果最短的加工时间来自第一台机器 那么先完成这个作业 如果来自第二台机器 那么这个作业就放在最后完成 然后从加工时间矩阵中划去已排序工件的加工时间 4 对于剩余的作业重复第二步和第三步 直到整个排序完成 例 求如表所示的6 2 F Fmax问题的最优解 将零件2排第1位2将零件3排第6位23将零件5排第2位253将零件6排第3位2563将零件4排第5位25643将零件1排第4位256143 例题 有5件任务都需要两步操作 先1后2 来完成 下表给出了相应的时间 1 根据Johnson算法安排工作顺
13、序 2 计算加工周期 例题 根据Johnson算法求以下8 2 F Fmax问题的最优解 1 将所有ai bi的工件按ai值不减的顺序排成一个序列A 2 将ai bi的工件按bi值不增的顺序排成一个序列B 3 将A放到B之前 就构成了一个最优加工顺序 改进算法 练习 某公司要生产4种产品 需要两台机器1和2 其中 有3种产品需要先在机器1上加工 下表给出了两台机器上加工各产品所需的时间 1 安排生产顺序 使得在最短时间内完成生产 2 机器1共需工作多长时间 3 机器2应该在机器1开始工作后多长时间开始运转 9 5 三 一般n m P Fmax问题的启发式算法 启发式算法是一个基于直观或经验构造
14、的算法 在可接受的花费 时间 占用空间等 下给出待解决组合优化问题的可行解 启发式方法因其易于实现 计算复杂度低等原因 目前应用得最为广泛 一 Palmer法 1965年 D S Palmer提出按斜度指标排列工件的启发式算法 称之为Palmer法 工件的斜度指标可按下式计算 k l 2 m式中 m为机器数 pik为工件i在Mk上的加工时间 按照各工件 i不增的顺序排列工件 可得出令人满意的顺序 例有一个4 3 F Fmax问题 其加工时间如下表所示 试用帕尔默法求最优顺序 解 对于本例 i Pi1 Pi3于是 1 P11 P13 1 4 3 2 P21 P23 2 5 3 3 P31 P33
15、 6 8 2 4 P41 P43 3 2 1按 i不增的顺序排列工件 得到加工顺序 1 2 3 4 和 2 1 3 4 恰好这两个顺序都是最优顺序 如不是这样 则从中挑选较优者 在最优顺序下 Fmax 28 二 关键零件法 步骤如下 1 计算每个零件的总加工时间 找出加工时间最长的零件C 将其作为关键零件 2 对于余下的零件 若pi1 pim 则按pi1不减的顺序排成一个序列Sa 若pi1 pim 则按pim不增的顺序排成一个序列Sb 3 顺序 Sa C Sb 即为所求顺序 例有一个4 3 F Fmax问题 其加工时间如下表所示 试用关键零件法求最优顺序 解 总加工时间最长的为3号零件 pi1
16、 pi3的零件为1和2 按pi1不减的顺序排成Sa 1 2 pi1 pi3的零件为4号零件 Sb 4 这样得到的加工顺序为 1 2 3 4 例题 用关键工件法求解下表的最优排序 解 总加工时间最长的为2号零件 pi1 pi4的零件为1和3 按pi1不减的顺序排成sa 1 4 pi1 pi4的零件为4号零件 sb 3 这样得到的顺序为 1 4 2 3 三 CDS法 康坎贝尔 杜德克 史密斯三人提出了一个启发式算法 简称CDS法 具体做法是 对加工时间用Johnson算法求 m 1 次加工顺序 取其中最好的结果 m 2时 l 1 加工时间分别为pi1和pi2 m 3时 l 1 2 加工时间分别为 1 l 1 pi1和pi3 2 l 2 pi1 pi2和pi2 pi3m 4时 l 1 2 3 加工时间分别为 1 l 1 pi1和pi4 2 l 2 pi1 pi2和pi3 pi4 3 l 3 pi1 pi2 pi3和pi2 pi3 pi4 l A 加工时间 B 加工时间 1 t 1 t m 2 t 1 t 2 t m 1 t m 3 t 1 t 2 t 3 t m 2 t m 1 t m m
