生产运作管理_制造业作业计划与控制.ppt

第十一章制造业作业计划与控制 引言通过MRP确定各车间的零部件投入出产计划 从而将全厂性的产品出产计划变成了各车间生产作业计划 将车间的生产任务变成各个班组 各个工作地和各个工人的任务 只有将计划安排到工作地和工人 任务才算真正落到实处 将任务安排到工作地 牵涉到任务分配和作业排序问题 这正是本章要讨论的 11 1作业计划问题的基本概念11 2流水作业排序问题11 3单件作业的排序问题11 4生产作业控制 11收入 费用和利润 要求掌握 最长流程时间的计算2 约翰逊算法3 一般流水作业排序问题的3种启发式算法4 相同零件的3种移动方式下机器加工周期的计算方法 学习目的与要求 重点最长流程时间的计算约翰逊算法相同零件的3种移动方式下机器加工周期的计算方法难点一般流水作业排序问题的启发式算法 教学重点与难点 生产任务的最终落实 MRP确定各车间的零部件投入出产计划 将全厂性的产品出产计划变成了各车间的生产任务 各车间要将车间的生产任务变成各个班组 各个工作地和各个工人的任务 将任务安排到工作地 牵涉到作业计划 编制作业计划要解决的问题 由于每台机器都可能被分配了多项任务 就带来了零件在机器上加工的顺序问题 编制作业计划要解决先加工哪个工件 后加工哪个工件的加工顺序问题确定机器加工每个工件的开始时间和完成时间例如 医院要安排病人手术 为此要安排手术室 配备手术器械 手术医师和护士 第一节排序问题的基本概念 一 名词术语排序 确定工件在机器上的加工顺序 作业计划 不仅要确定工件的加工顺序 而且还要确定机器加工每个工件的开始时间和完成时间 通常情况下都是按最早可能开 完 工时间来编制作业计划 派工 按作业计划的要求 将具体生产任务安排到具体的机床上加工 赶工 实际进度已落后于计划进度时采取的行动 机器 可以是工厂里的各种机床 也可以是维修工人 表示 服务者 零件 代表 服务对象 零件可以是单个零件 也可以是一批相同的零件 加工顺序 则表示每台机器加工n个零件的先后顺序 是排序和编制作业计划要解决的问题 二 假设条件和符号说明 假设条件 1 一个工件不能同时在几台不同的机器上加工 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为工件的延迟时间Lmax为最长延迟时间 三 排序问题的分类 根据机器数的多少单台机器的排序问题多台机器的排序问题对于多台机器排序问题 根据加工路线的特征 分成单件作业排序 Job Shop 问题流水作业排序 Flow Shop 问题工件的加工路线不同 是单件作业排序问题的基本特征 所有工件的加工路线完全相同 是流水作业排序问题的基本特征 也就是说 每个零件都顺序地经过线上不同机器加工 它们的加工路线一致 根据工件到达系统的情况静态排序动态排序根据参数的性质确定型排序随机型排序 4参数法 n m A B其中 n为工件数m为机器数A车间类型 在A的位置若标以标以 P 则表示流水作业排列排序问题 若标以 G 则表示一般单件作业排序问题 当m 1 则A处为空白 B为目标函数 通常是使其值最小例如 n 3 P Cmax 四 作业排序方案的评价标准 1 工作流程时间从工件可以开始加工至完工的时间 包括在各个机器之间的移动时间 等待时间 加工时间以及由于机器故障 部件无法得到等问题引起的延误时间等 2 加工周期完成一组工作所需的全部时间 它是从第一个工件在第一台机器上开始加工时算起 到最后一个工件在最后一台机器上完工时为止所经过的时间 3 在制品库存 WIP 在制品是对介于原材料和成品之间的生产过程中的产品的称谓 一个工件正从一个工作地移向另一个 由于一些原因被拖延加工 正在被加工或放置于零件库中 都可以看作在制品库存 4 利用率用一台机器或一个工人的有效生产时间占总工作时间的百分比来表示 五 优先调度规则 调度方法 所谓调度方法 就是运用若干预先规定的优先顺序规则 顺次决定下一个应被加工的工件的排序方法 一个工作地可选择的下一个工件会有很多种 因此 按什么样的准则来选择 对排序方案的优劣有很大影响 常用的优先顺序规则 FCFS规则优先选择最早进入可排序集合的工件 EDD规则优先选择完工期限最紧的工作 SPT规则优先选择加工时间最短的工件 SCR规则优先选择临界比最小的工件 临界比为工作允许停留时间和工件余下加工时间之比 MWKR规则优先选择余下加工时间最长的工件 LWKR规则优先选择余下加工时间最短的工件 MOPNR规则优先选择余下工序数最多的工件 RANDOM规则随机地挑选下一个工件 一般作业排序的目标满足顾客或下一道工序的交货期要求流程时间最短准备时间最短或成本最小化在制品库存最低机器设备或劳动力利用最大化 例 一个加工车间负责加工发动机机壳 现在共有5个机壳等待加工 只有一名技工在岗 做此项工作 现在已经估算出各个机壳的标准加工时间 顾客也已经明确提出了他们所希望的完工时间 下表显示了周一上午的情况 顾客的取货时间用从周一上午开始 还有多少工作小时来计算 SPT规则排序结果 顾客实际取货时间基于以下假设 顾客不会在预定取货时间之前来取货 如果有拖延发生 他们将在加工结束时马上取走 流程时间 等待时间 加工时间平均在制品库存 各工件流程时间之和 加工周期平均总库存 各工件实际取货时间之和 加工周期 EDD规则排序结果 顾客实际取货时间基于以下假设 顾客不会在预定取货时间之前来取货 如果有拖延发生 他们将在加工结束时马上取走 比较SPT规则和EDD规则的排序结果 用SPT规则排序 其平均流程时间更短 在制品库存更少 用EDD规则 可以给顾客提供更好的服务 平均延迟时间较少 它也提供了更低的总库存水平 优先调度法则 按SPT法则可使工件的平均流程时间最短 从而减少在制品量 FCFS法则来自排队论 它对工件较公平 EDD法则可使工件延误时间最小 MWKR法则使不同工作量的工件的完工时间尽量接近 LWKR法则 使工作量小的工件尽快完成 第二节流水作业排序问题 流水作业排序问题的基本特征是每个工件的加工路线都一致 加工路线一致 是指工件的流向一致 并不要求每个工件必须经过加工路线上每台机器加工 对于流水作业排序问题 工件在不同机器上的加工顺序不尽一致 排列排序问题 所有工件在各台机器上的加工顺序都相同的情况 一 最长流程时间Fmax的计算 n m P Fmax问题 n个零件要按相同的加工路线经过m台机器加工 目标是使这批零件的最长流程时间最短 最长流程时间又称加工周期 它是从第一个零件在第一台机器开始加工时算起 到最后一个零件在最后一台机器上完成加工时为止所经过的时间 例有一个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 列出每个作业在两台机器上的加工时间 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算法安排工作顺序 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问题的启发式算法 启发式算法是一个基于直观或经验构造的算法 在可接受的花费 时间 占用空间等 下给出待解决组合优化问题的可行解 启发式方法因其易于实现 计算复杂度低等原因 目前应用得最为广泛 一 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 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 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 1 t 1 t 2 t m 1 t 2 t m 1 t m 当l 1时 按 Johnson 算法得到加工顺序 1 2 3 4 当l 2时 得到加工顺序 2 3 1 4 对于 2 3 1 4 相应的Fmax 29 所以 取顺序 1 2 3 4 用Palmer法 关键工件法和CDS法求以下4 4 P Fmax问题的最优解 并比较三种方法的结果 四 相同零件 不同移动方式下加工周期的计算 排序问题针对的是不同零件 如果n个零件相同 则没有排序问题 但零件在加工过程中采取的移动方式不同 会导致一批零件的加工周期不同 三种典型的移动方式顺序移动方式 串行工程 平行移动方式 平行工程 平行顺序移动方式 一 顺序移动方式 一批零件在上道工序全部加工完毕后才整批地转移到下道工序继续加工 设零件批量为n 件 工序数目为m 一批零件不计算工序间运输时间 只考虑加工时间 设其加工的周期为T 分钟 零件在i道工序的单件工时为ti 分钟 件 i 1 2 n 则该批零件的加工周期为 已知n 4 t1 10分钟 t2 5分钟 t3 15分钟 t4 10分钟 则T顺 4 10 5 15 10 160分钟 二 平行移动方式 每个零件在前道工序加工完毕后 立即转移到后道工序去继续加工 形成前后工序交叉作业 零件平行移动的加工周期为 已知n 4 t1 10分钟 t2 5分钟 t3 15分钟 t4 10分钟 则T平 10 5 15 10 4 1 15 85分钟 三 平行顺序移动方式 既要求每道工序连续进行加工 又要求各道工序尽可能平行地加工 1 当ti ti 1时 零件按平行移动方式转移 2 当ti ti 1时 以i工序最后一个零件的完工时间为基准 往前推移 n 1 ti 1作为零件在 i 1 工序的开始时间 具体做法 1 当ti ti 1时 零件按平行移动方式转移 2 当ti ti 1时 以i工序最后一个零件的完工时间为基准 往前推移 n 1 ti 1作为零件在 i 1 工序的开始时间 平行顺序移动加工周期计算 已知n 4 t1 10分钟 t2 5分钟 t3 15分钟 t4 10分钟 则T平顺 4 10 5 15 10 4 1 5 5 10 100分钟 例 已知n 4 t1 10分钟 t2 5分钟 t3 15分钟 t4 10分钟 求三种移动方式下的加工周期 解 T顺 4 10 5 15 10 160分钟T平 10 5 15 10 4 1 15 85分钟T平顺 4 10 5 15 10 4 1 5 5 10 100分钟 零件三种移动方式的比较 已知m 5 n 4 t1 10 t2 4 t3 8 t4 12 t5 6 分别求在顺序移动 平行移动和平行顺序移动方式下 这批零件的加工周期 第三节单件作业排序问题 11 3 1指派问题11 3 2单件作业排序问题的描述11 3 3两种作业计划的构成11 3 4求解一般n m G Fmax问题的启发式方法 1 指派问题的形式表述给定了一系列所要完成的任务 tasks 以及一系列完成任务的被指派者 assignees 所需要解决的问题就是要确定出哪一个人被指派进行哪一项任务 2 指派问题的假设被指派者的数量和任务的数量是相同的每一个被指派者只完成一项任务每一项任务只能由一个被指派者来完成每个被指派者和每项任务的组合有一个相关成本目标是要确定怎样进行指派才能使得总成本最小 11 3 1指派问题 设n个人被分配去做n件工作 每人只能完成一项任务 每项任务只能由一人完成 已知第i个人去做第j件工作的的效率为Cij i 1 2 n j 1 2 n 并假设Cij 0 问应如何分配才能使总效率 时间或费用 最高 3 指派问题模型 TheModelforAssignmentProblem 典型问题 例1 有一份说明书 要分别译成英 日 德 俄四种文字 交与甲 乙 丙 丁四个人去完成 因各人专长不同 他们完成翻译不同文字所需要的时间 小时 如表所示 规定每项工作只能交与其中的一个人完成 每个人只能完成其中的一项工作 问 如何分配 能使所需的总时间最少 建立模型 设xij 1 0 若第i项工作交与第j个人完成 若第i项工作不交与第j个人完成 译英文 x11 x12 x13 x14 1 译日文 x21 x22 x23 x24 1 译德文 x31 x32 x33 x34 1 译俄文 x41 x42 x43 x44 1 甲 x11 x21 x31 x41 1 乙 x12 x22 x32 x42 1 丙 x13 x23 x33 x43 1 丁 x14 x24 x34 x44 1 xij 0或1 i 1 2 3 4 j 1 2 3 4 4 指派问题的匈牙利解法 2 4 9 7 第1步 变换指派问题的系数矩阵 cij 使各行各列中都出现0元素 1 从 cij 的每行元素都减去该行的最小元素 2 再从所得新系数矩阵无零元素的列中减去该列的最小元素 4 2 在变化后的效率矩阵中找尽可能多的独立0元素 若能找出n个独立0元素 就以这n个独立0元素对应解矩阵 xij 中的元素为1 其余为0 这就得到最优解 第2步 进行试指派 即确定独立零元素 2 若独立零元素的数目m等于矩阵的阶数n 那么这指派问题的最优解已得到 若m n 则转入下一步 例2有甲 乙 丙 丁四个工人 要分别派他们完成四项不同的任务 分别记作A B C D 他们完成各项任务所需时间如下表所示 问如何分派任务 可使总时间最少 第1步 变换系数矩阵 5 第2步 确定独立零元素 找到3个独立零元素 但m 3 n 4 求解过程如下 第3步 作最少的直线覆盖所有零元素 5 对没有打 号的行画横线 有打 号的列画纵线 这就得到覆盖所有零元素的最少直线数 1 对没有独立零元素的行打 号 2 对已打 号的行中所有含划掉零元素的列打 号 3 再对打有 号的列中含独立零元素的行打 号 4 重复 2 3 直到得不出新的打 号的行 列为止 第4步 在没有被直线覆盖的所有元素中找出最小元素 然后将所在行 或列 都减去这最小元素 在出现负数的列 或行 都加上这最小元素 以保证系数矩阵中不出现负元素 新系数矩阵的最优解和原问题仍相同 转回第2步 5 11 3 2问题的描述 加工描述矩阵D为 D 1 1 11 2 31 3 22 1 32 2 12 3 2 对于一般单件作业排序问题 每个工件都有其独特的加工路线 工件没有一定的流向 要描述一道工序 需要用三个参数 3个参数 i j和k i表示工件代号 j表示工序号 k表示完成工序i的第j道工序的机器代号 i j k 表示工件i的第j道工序在机器k上进行 11 3 3两种作业计划的构成 各工序都按最早可能完工时间安排的作业计划称为能动作业计划 各工序都按最早可能开始时间安排的作业计划称为无延迟作业计划 无延迟作业计划是没有任何延迟出现的能动作业计划 符号说明每安排一道工序称为一 步 St t步之前已排序工序构成的部分作业计划 Ot t步可排序工序的集合 Tk为 Ot 中工序Ok的最早可能开始时间 T k为 Ot 中工序Ok的最早可能完成时间 一 能动作业计划的构成步骤 1 设t 1 S1 为空集 O1 为各工件第一道工序的集合 2 求T min T k 并求出T 所出现的机器M 如果M 有多台 则任选一台 3 从 Ot 中选出满足以下两个条件的工序Oj 需要M 加工 且Tj T 4 将选定的工序Oj放入 St 从 Ot 中消去Oj 并将Oj的紧后工序放入 Ot 使t t 1 5 若还有未安排的工序 转步骤 2 否则 停止 例有一个2 3 G Fmax问题 其加工描述矩阵D和加工时间矩阵T分别为 D 1 1 11 2 31 3 22 1 32 2 12 3 2 T 241345 试构成一个能动作业计划 能动作业计划的构成 2 3 2 M2 13 13 8 2 3 2 6 1 3 2 M2 8 812 77 1 3 22 3 2 5 2 2 1 M1 7 87 73 1 3 22 2 1 4 1 2 3 M3 7 77 33 1 2 32 2 1 3 2 1 3 M3 3 63 20 1 2 32 1 3 2 1 1 1 M1 2 23 00 1 1 12 1 3 1 Oj M T T k Tk Ot t 能动作业计划的甘特图 2 3 2 1 1 12 2 1 1 3 2 2 1 31 2 3 37 7813 237 0 时间 机器 M1 M2 M3 二 无延迟作业计划构成步骤 1 设t 1 S1 为空集 O1 为各工件第一道工序的集合 2 求T min Tk 并求出T 所出现的机器M 如果M 有多台 则任选一台 3 从 Ot 中选出满足以下两个条件的工序Oj 需要M 加工 且Tj T 4 将选定的工序Oj放入 St 从 Ot 中消去Oj 并将Oj的紧后工序放入 Ot 使t t 1 5 若还有未安排的工序 转步骤 2 否则 停止 无延迟作业计划的构成 1 3 2 M2 12 13 12 1 3 2 6 2 3 2 M2M2 77 812 77 1 3 22 3 2 5 2 2 1 M1 3 87 73 1 3 22 2 1 4 1 2 3 M3M1 33 77 33 1 2 32 2 1 3 2 1 3 M3 0 63 20 1 2 32 1 3 2 1 1 1 M1M3 00 23 00 1 1 12 1 3 1 Oj M T T k Tk Ot t 无延迟作业计划的甘特图 2 3 2 1 1 12 2 1 2 1 31 2 3 37 71213 237 0 时间 机器 M1 M2 M3 1 3 2 能动作业计划和无延迟作业计划尽管不一定是最优作业计划 但一般是较好的作业计划 特别是无延迟作业计划能提供令人满意的解 一般能动作业计划和无延迟作业计划都有多个 一般来说 以构成无延迟作业计划的步骤为基础的启发式算法比以构成能动作业计划的步骤为基础的启发算法的效果要好 练习 1 南希汽车座椅罩和喷漆工厂正在竞标一份为爱得旧车交易所提供全部客户服务的合同 取得合同的主要要求是快速交货 爱得说 如果南希厂可以在24小时内将爱得收到的5辆车全部整修并且重新喷漆 合同就归该厂 下面是这5辆车在整修和喷漆车间各自需要的时间 假定车子在重新喷漆前要经过重新整修的步骤 南希厂可以满足时间要求并且得到合同吗 2 有一个2 3 G Fmax问题 其加工描述矩阵D和加工时间矩阵T分别为 试构成一个能动作业计划和无延迟作业计划 D 1 1 11 2 31 3 22 1 32 2 22 3 1 T 352243 4 1 2 M2 0 6 0 4 1 2 0 4 0 3 1 1 11 8 2 2 1 12 5 1 2 2 3 0 6 0 4 1 2 0 4 0 3 1 1 11 8 2 2 1 1 1 1 M1 0 5 0 1 1 1 2 0 6 0 4 1 2 0 4 0 3 1 1 2 1 3 M3 0 8 0 2 1 3 0 5 0 1 1 1 1 Oj M T T k Tk Ot t 16 9 4 3 1 13 9 3 2 4 12 9 2 2 1 1 2 2 M2 6 13 6 1 2 2 6 4 2 4 M4 6 8 6 4 2 4 13 9 3 2 4 12 9 2 2 1 6 13 6 1 2 2 5 8 6 4 2 4 3 1 1 M1 5 9 5 3 1 1 11 8 2 2 1 13 6 1 2 2 4 Oj M T T k Tk Ot t 4 3 1 M1 12 19 12 4 3 1 18 13 3 3 3 17 13 2 3 4 19 13 1 3 3 9 19 12 4 3 1 3 2 4 M4 9 13 9 3 2 4 16 12 2 3 4 19 13 1 3 3 8 9 16 9 4 3 1 9 13 9 3 2 4 2 2 1 M1 9 12 9 2 2 1 19 13 1 3 3 7 Oj M T T k Tk Ot t 22 19 4 4 3 18 19 18 3 4 2 18 27 18 2 4 3 1 3 3 M3 18 24 18 1 3 3 12 22 19 4 4 3 3 3 3 M3 13 18 13 3 3 3 26 17 2 4 3 13 19 13 1 3 3 11 22 19 4 4 3 13 18 13 3 3 3 2 3 4 M4 13 17 13 2 3 4 13 19 13 1 3 3 10 Oj M T T k Tk Ot t 2 4 3 M3 27 36 27 2 4 3 4 4 3 M3 24 27 24 4 4 3 24 33 24 2 4 3 24 27 24 4 4 3 24 33 24 2 4 3 1 4 4 M4 24 26 24 1 4 4 14 27 24 4 4 3 3 4 2 M2 18 19 18 3 4 2 33 24 2 4 3 26 24 1 4 4 13 Oj M T T k Tk Ot t 15 16 11 3 3求解一般n m G Fmax问题的启发式方法 三类启发式算法 优先调度法则随机抽样法概率调度法 1 优先调度法则 SPT Shortestprocessingtime 法则优先选择加工时间最短的工序可使工件的平均流程时间最短 从而减少在制品量FCFS Firstcomefirstserved 法则优先选择最早进入可排工序集合的工件来自排队论 对工件较公平EDD Earliestduedate 法则优先选择完工期限紧的工件可使工件最大延误时间最小MWKR Mostworkremaining 法则优先选择余下加工时间最长的工件不同工作量的工件的完工时间尽量接近 1 优先调度法则 续 LWKR Leastworkremaining 法则优先选择余下加工时间最短的工件使工作量小的工件尽快完成MOPNR Mostoperationsremaining 法则优先选择余下工序数最多的工件与MWKR法则类似 只不过考虑工件在不同机器上的转运排队时间是主要的SCR Smallestcriticalratio 法则优先选择临界比最小的工件 临界比 工件允许停留时间与工件余下加工时间之比 保证工件延误最少RANDOM法则随机地挑一个工件 2 随机