生产计划_作业排序与生产作业计划培训课件

2020 2 20 1 第十章作业排序与生产作业计划 第一节作业排序的基本概念第二节流水作业排序问题第三节单件作业排序问题第四节多台设备作业排序 引言在确定了各车间的零部件投入 出产计划 将全厂的生产计划变成了各车间的生产任务后 各车间还应将零部件的投入 出产计划变成车间的作业计划 即将车间的生产任务变成各工段 班组 各工作地的生产任务 编制车间生产作业计划 应该解决工件加工顺序问题 这就是我们要讨论的作业排序问题 采用排序理论与方法 可以得出工件加工的最优或令人满意的顺序 第一节作业排序的基本概念 一 编制生产作业计划与排序的关系编制生产作业计划与作业排序不同 排序只是确定工件在机器上的加工顺序 可以用一组工件的代号的排列来表示这组工件的加工顺序 而编制生产作业计划不仅包括确定工件的加工顺序 而且包括确定机器加工每个工件的开始时间和完成时间 所以 只有生产作业计划才能指导工人的生产活动 在编制生产作业计划时常常出现一个工件在某道工序加工完之后 加工它的下一道工序的机器还在加工前一个工件 这时该工件不得不等待一段时间才能开始在下一道工序的机器上加工 这种情况称为 工件等待 当某台机器已加工完一个工件 而下一个工件尚未到达 这种情况称为 机器空闲 第一节作业排序的基本概念 由于编制生产作业计划的主要问题是确定各台机器上工件的加工顺序 并且一般都是按最早可能开工时间或最早可能完工时间来编制生产作业计划 所以 当工件的加工按一定的时间确定了加工顺序后 作业计划也就确定了 这就造成了人们通常不加区别的使用 排序 与 编制作业计划 两个术语 第一节作业排序的基本概念 2020 2 20 5 几个名词术语 排序 工件在机器上的加工顺序派工 将生产任务安排到具体机床上加工 调度范围 赶工 实际进度落后于计划进度时采取的行动 调度范围 调度 发现实际进度落后于计划进度时而采取的调配资源的行动 机器 服务者工件 服务对象加工路线 工件加工的工艺过程工序 加工路线上的每一个具体工作地 机器 1 一个工件不能同时在几台不同的机器上被加工 2 采取平行移动方式移送被加工的工件 3 不允许中断 当一个工件一旦开始加工 必须一直进行到完工 不得中途停止插入其它工件 4 工件在每道工序的加工只在一台机器上进行 5 工件数 或批量 机器数已知 单件加工时间已知 完成加工的时间与加工顺序无关 6 每台机器同时只能加工一个工件 第一节作业排序的基本概念 二 假设条件与符号说明为了便于采用数学模型来分析研究排序问题 做下列假设 2020 2 20 7 第一节作业排序的基本概念 符号说明 Ji 第i工件 i 1 2 n Mj 第j台机器 j 1 2 m i j k Ji的第j道工序在Mk上进行 ri Ji到达工序时间 即可以开始加工的最早时间 di Ji的完工期限 ai Ji在车间允许停留的时间 Ji进入车间到完工时刻之间的时间间隔 ai di ri Wij Ji在第j道工序前的等待时间 Ji总的等待时间 Ci ri Pij Wij ri Pi Wi Li Ci di ri Pi Wi di Pi Wi di ri Fi ai Fi Ci ri Pi Wi 第一节作业排序的基本概念 Ci Ji的完工时间 Cmax 最长完工时间 Cmax max Ci 即一批工件中的最长完工时间 Fi Ji的流程时间 即工件在车间的实际停留时间 Fmax 最长流程时间 Fmax max Fi 即一批工件中的最长流程时间 Li Ji工件的延迟时间 第一节作业排序的基本概念 当Li 0时为正延迟 即Ji的实际完工时间超过了完工期限 当Li 0时为负延迟 即Ji提前完工 当Li 0时为零延迟 即Ji按期完工 Lmax 最长延迟时间 Lmax max Li 即在一批工件中找出的最大延迟时间 三 排序问题的分类和表示法 排序问题常见的分类方法有按机器 工件 目标函数的特征分类 1 按机器的种类和数量不同 可以分成 单台机器的排序问题 多台机器的排序问题 对于多台机器的排序问题 按工件加工路线的特征 可以分成 第一节作业排序的基本概念 2 按工件到达车间的情况不同 可以分成 静态的排序问题 排序时所有工件都已到达 可以一次对它们进行排序 动态的排序问题 排序时工件陆续到达 要随时安排它们的加工顺序 3 按目标函数的性质不同 也可划分不同的排序问题 单台机器的排序 多台机器的排序 不同目标排序问题 单目标排序问题 以往研究的对象 多目标排序问题 很少有人研究 第一节作业排序的基本概念 4 另外 按参数的性质 可以划分为 确定型排序问题 指加工时间和有关参数是已知确定的量 随机型排序问题 加工时间和有关参数为随机变量 这两种排序问题的解法本质上不同 现只讨论几种有代表性的排序问题 第一节作业排序的基本概念 通常采用Conway等人提出的排序方法 这个方法主要涉及到4个参数 只用4个参数就可以表示大多数不同的排序问题 这4个参数通常表示为 n m A B n为工件数 m为机器数 B为目标函数 通常是使其值最小 A为车间类型 通常有以下几种情况 在A的位置 1 若标以 F 则代表流水作业排序问题 2 若标以 P 则表示流水作业排列排序问题 也常被称为 同顺序 排序问题 3 若标以 G 则表示一般单件作业排序问题 第一节作业排序的基本概念 当m 1时 A处为空白 因为对于单台机器的排序问题来说 不存在所谓的加工路线问题 当然也就谈不到是流水作业排序问题还是单件作业的排序问题了 通过n m A B这4个符号 就可以简捷的表述一般的排序问题了 例如 n 3 P Cmax表示n个工件经3台机器加工的流水作业排列排序问题 目标函数是使最长完工时间最短 第一节作业排序的基本概念 2020 2 20 15 第十章作业排序与生产作业计划回顾 排序问题常见的分类方法有按机器 工件 目标函数的特征分类 排序问题由4个参数表示 n m A B n为工件数 m为机器数B为目标函数 通常是使其值最小A为车间类型 通常有以下几种情况 在A的位置 1 若标以 F 则代表流水作业排序问题 2 若标以 P 则表示流水作业排列排序问题 也常被称为 同顺序 排序问题 3 若标以 G 则表示一般单件作业排序问题 Cmax 最长完工时间 Fmax 最长流程时间 Lmax 最长延迟时间 Lmax max Li 即在一批工件中找出的最大延迟时间 当Li 0时为正延迟 即Ji的实际完工时间超过了完工期限 当Li 0时为负延迟 即Ji提前完工 当Li 0时为零延迟 即Ji按期完工 例如 n 3 P Cmax表示n个工件经3台机器加工的流水作业排列排序问题 目标函数是使最长完工时间最短 流水作业排序问题的基本特征是每个工件的加工路线都一致 在流水生产线上制造不同的零件 遇到的就是流水作业排序问题 我们说加工路线一致 是指工件的流向一致 并不要求每个工件必须经过加工路线上每台机器加工 如果某些工件不经某些机器加工 则设相应的加工时间为零 一般说来 对于流水作业排序问题 工件在不同机器上的加工顺序不尽一致 但本节要讨论的是一种特殊情况 即所有工件在各台机器上的加工顺序都相同的情况 这就是排列排序问题 流水作业排列排序问题常被称作 同顺序 排序问题 对于一般情形 排列排序问题的最优解不一定是相应的流水作业排序问题的最优解 但一般是比较好的解 对于仅有2台和3台机器的特殊情况 可以证明 排列排序问题下的最优解一定是相应流水作业排序问题的最优解 本节只讨论排列排序问题 但对于2台机器的排序问题 实际上不只是排列排序问题 因为两者的最优解及其解法是相同的 第二节流水作业排序问题 一 最长流程时间Fmax的计算最长流程时间就是工件在车间实际停留的最长时间 本节所讨论的是n m Fmax问题 目标函数是使最长流程时间最短 最长流程时间又称作加工周期 它是从第一个工件在第一台机器开始加工时算起 到最后一个工件在最后一台机器上完成加工时为止所经过的时间 由于假设所有工件的到达时间都为零 r 0 i 1 2 n 所以Fmax等于排在末位加工的工件在车间的停留时间 也等于一批工件的最长完工时间Cmax 第二节流水作业排序问题 设n个工件的加工顺序为S S1 S2 Sn 其中Si为排第i位加工的工件的代号 以Ck si 表示工件Si在机器Mk上的完工时间 Psik表示工件Si在Mk上的加工时间 k 1 2 m i 1 2 n则Ck si 可按以下公式计算 C1 si C1 si 1 Psi1Ck si max Ck 1 si Ck si 1 Psik 11 1 第二节流水作业排序问题 显然 当ri 0时 Fmax Cm sn 在知道了上述计算Fmax公式后 便可直接在工件加工的时间矩阵上从左向右计算完工时间 第二节流水作业排序问题 例11 1有一个6 4 p Fmax问题 其加工时间如下表所示 当按顺序S 6 1 5 2 4 3 加工时 求Fmax 表11 1加工时间矩阵 2020 2 20 20 表11 2顺序S下的加工时间矩阵 2 6 10 12 13 16 7 11 15 20 27 33 12 17 22 30 35 42 13 21 25 32 38 46 Fmax 46 Johnson算法 1 从加工时间矩阵中找出最短的加工时间 2 若最短的加工时间出现在M1上 则对应的工件尽可能往前排 若最短加工时间出现在M2上 则对应工件尽可能往后排 然后 从加工时间矩阵中划去已排序工件的加工时间 若最短加工时间有多个 则任挑一个往前排 3 若所有工件都已排序 停止 否则 转步骤 1 第二节流水作业排序问题 二 n 2 F Fmax问题的最优算法 第二节流水作业排序问题 二 n 2 F Fmax问题的最优算法 例11 2求表1 所示的6 Fmax问题的最优解 表11 3加工时间矩阵 5 6 14 19 22 26 13 15 17 23 30 34 Fmax0 1 2 3 4 5 6 34 2020 2 20 23 表11 4改进算法见教材303页 Johnson改进算法 将所有ai bi的工件按ai值不减的顺序排成一个列 将所有ai bi的工件按bi值不增的顺序排成一个列 将 放到 之前 就构成了最优加工顺序 1 2 3 4 A 2 5 6 1 5 6 B 4 3 S 2 5 6 1 4 3 1 4 8 13 18 26 3 11 15 23 27 29 Fmax 2 5 6 1 4 3 29 当我们从应用Johnson法则求得的最优顺序中任意去掉一些工件时 余下的工件仍构成最优顺序 如对例11 2的最优顺序 2 5 6 1 4 3 若去掉一些工件 得到的顺序 5 6 1 4 3 2 6 4 3 2 6 1 4 等仍为余下工件的最优顺序 但是 工件的加工顺序不能颠倒 否则不一定是最优顺序 同时 我们还要指出 Johnson法则只是一个充分条件 不是必要条件 不符合这个法则的加工顺序 也可能是最优顺序 对例11 2顺序 2 5 6 4 1 3 不符合Johnson法则 但它也是一个最优顺序 第二节流水作业排序问题 2020 2 20 25 例11 2顺序 2 5 6 4 1 3 3 1 4 8 13 18 26 11 15 19 27 29 Fmax 2 5 6 4 1 3 29 第二节流水作业排序问题 三 一般n m P Fmax问题的启发式算法对于3台机器的流水车间排序问题 只有几种特殊类型的问题找到了有效算法 对于一般的流水车间排列排序问题 可以用分支定界法 用分支定界法可以保证得到一般n m P Fmax问题的最优解 但对于实际生产中规模较大的问题 计算量相当大 以至连电子计算机也无法求解 同时 还需考虑经济性 如果为了求最优解付出的代价超过了这个最优解所带来的好处 也是不值得的 为了解决生产实际中的排序问题 人们提出了各种启发式算法 启发式算法以小的计算量得到足够好的结果 因而十分适用 下面介绍求一般n m p Fmax问题近优解 Nearoptimalsolution 的启发式算法 第二节流水作业排序问题 一 帕尔姆 Palmer 法1965年 D S Palmer提出按工件斜度指标排序的启发式算法 设 工件的斜度指标为 i k为笫k台设备 m为设备数 Pik为i工件在Mk上加工时间 k为设备的任意序数 k 1 2 3 m 从该式中求出各工件的 i 再按着不使 i增加的原则排列各个工件的加工顺序 就可以得出令人满意的结果 1 3 9 12 9 15 13 24 13 26 18 28 表11 5加工时间矩阵 例11 3有一个4 3 F Fmax排序问题 即4个工件3台设备 流水作业排序问题 目标是使最长流程时间最短 各个工件在每台设备上的加工时间如下面的加工时间矩阵表所示 试采用Palmer法求解 Fmax 28 2020 2 20 29 按照排序为 S 2 1 3 4 2 3 9 12 6 14 16 25 11 18 26 28 Fmax 28 第二节流水作业排序问题 解 由 可知 见教材304页 按照 i从大到小的顺序排列就是最优排列顺序 最优排列顺序S 1 2 3 4 或 S 2 1 3 4 2020 2 20 31 P322习题2 请用帕尔玛法排序并计算最长流程时间 求解过程 排序为 S 1 4 3 2 2020 2 20 32 按照S 1 4 3 2 计算最长流程时间 1 5 10 19 26 6 9 16 10 15 19 32 16 23 26 34 Fmax 34 二 关键工件法关键工件法是1983年提出的一个启发式算法 其步骤如下 1 计算每个工件的总加工时间Pi Pij 找出总加工时间最长的工件C j 1 2 3 m 将其作为关键工件 2 对于余下的工件 若Pi1 Pim 则按Pi1不减的顺序排成一个序列Sa 若Pi1 Pim 则按Pim不增的顺序排列成一个序列Sb 3 顺序 sa C Sb 即为所求顺序 近优解 第二节流水作业排序问题 表11 6工件在每台设备上的单件工时与总工时 见教材305页 第二节流水作业排序问题 例 有4个工件 在3台设备上加工 每个工件在每台设备上加工的单件工时消耗如表11 6所示 试采用关键工件法求近优解 近优排序 i 1 2 3 4 m 1 2 3 3 1 2 4 解 1 计算每个工件的总加工时间 填写在表11 6上 分别为 13 11 16 14 可见总加工时间最长的工件为3号工件 总加工时间P3 16 2 余下的工件为1 2 4号工件 Pi1 Pi3的工件为1 2号 按Pi1不减 相等或增加 P11 1 P21 2 的顺序排成一个序列Sa 1 2 Pi1 Pim的工件为4号工件 按Pim不增 相等或减少 顺序排成一个序列Sb 4 只有一个工件 3 近优解的顺序 Sa C Sb 为 工件1 2 3 4 第二节流水作业排序问题 2020 2 20 36 表11 6工件在每台设备上的单件工时与总工时 1 3 9 12 9 13 15 24 13 18 26 28 Fmax计算过程 2020 2 20 37 P322习题2 请用关键工件法排序并计算最长流程时间 排序为 S 1 4 2 3 关键工件法求解过程如下 2020 2 20 38 按照S 1 4 2 3 计算最长流程时间 1 5 14 19 6 9 21 27 10 15 27 30 16 23 29 33 Fmax 33 三 CDS法 Campbell Dudek Smith三人提出 见教材305页 第二节流水作业排序问题 表11 7用CDS法求解 L 1时 按照Johnson法得到加工顺序为 1 2 3 4 L 2时 按照Johnson法得到加工顺序为 2 3 1 4 8 9 12 6 18 10 27 11 23 19 29 Fmax计算如下表所示 Fmax 29 若加工顺序为 2 3 1 4 时 按Johnson算法Fmax 29 所以取加工顺序 1 2 3 4 Fmax 28为最优解 第二节流水作业排序问题 2 2020 2 20 41 P322习题2 请用CDS法排序并计算最长流程时间 关键工件法求解过程如下 2020 2 20 42 排序为 S1 1 4 3 2 1 L 1时 2020 2 20 43 排序为 S1 1 4 3 2 1 5 10 19 6 9 16 26 10 15 19 32 16 23 26 34 Fmax 34 2020 2 20 44 排序为 S1 1 4 2 3 2 L 2时 2020 2 20 45 排序为 S1 1 4 2 3 1 5 14 19 6 9 21 27 10 15 27 30 16 23 29 33 Fmax 33 2020 2 20 46 排序为 S1 1 4 2 3 3 L 3时 2020 2 20 47 排序为 S1 1 4 2 3 1 5 14 19 6 9 21 27 10 15 27 30 16 23 29 33 Fmax 33 所以最终排序为 S1 1 4 2 3 满意解 2020 2 20 48 三 采用Johnson法则解决多个工件在三台设备上的作业排序 若存在一个n 3 P Fmax问题 且mint1i maxt2i或mint3i mint2i i 1 2 n 则可采用Johnson法排序 求解步骤为 1 先找出mint1i maxt2i或mint3i mint2i关系 2 将3台设备变换成2台假想设备MA和MB 并令tAi t1i t2i tBi t2i t3i 3 依据tAi和tBi 采用Johnson法则进行作业排序 试采用Johnson法则进行作业排序 表11 17加工时间表 例 有一个4 3 P Fmax问题 其加工时间如表11 17所示 2020 2 20 49 解 mint1i 6maxt2i 6存在mint1i maxt2imint3i 4mint2i 1存在mint3i mint2i 可采用Johnson法求解该作业排序问题 具备其一即可 计算tAi和tBi 列于表11 18中 表11 18tAi tBi与排序结果 依据11 18中的tAi和tBi 采用Johnson法进行作业排序 排序结果与Fmax如表11 18及图11 4所示 Fmax 48 2020 2 20 50 J2J4J3J1 812615 1653 892026314144 8202641 10754 9192633384448 M1 M2 M3 时间 图11 4排序结果甘特图 单件作业排序是最一般的排序问题 也是最复杂的一种排序问题 该问题本身容易表达 也能看出该问题所需要求解的是什么 但是朝着求解方向作任何推进都是极为困难的 许多人在此问题上都进行了探索 但一无所获者大有人在 第三节单件作业排序问题 第三节单件作业排序问题 一 问题的描述对一般的单件作业排序问题 每个工件都有其独特的加工路线 工件没有一定的流向 但是 对于流水作业的排序问题 第k道工序永远在MK上进行 没有必要将工序号与机器号分开 而对于一般的单件作业排序问题 要描述一道工序需要i j k三个参数 即i j k表示第i个工件的第j道工序在Mk 第k台机器上 上进行的 所以 可以用加工描述矩阵的形式来描述所有工件的加工 加工描述矩阵的形式如加工描述矩阵D所示 加工描述矩阵的每一行描述一个工件的加工过程 第1行描述第一个工件的加工过程 第二行描述第2个工件的加工过程 D的每一组数中的第1列数表示工件序号 D的每组数中的第2列数码相同 说明第2列表示工序号 D的每一组数中的第3列数表示设备序号 第三节单件作业排序问题 二 一般n m G Fmax问题的启发式算法n m G Fmax为n个工件 m台机器 一般单件作业排序问题 使最大流程时间最短 对这类作业排序问题 可以用分支定界法或整数规划法求最优解 但是 都是无效的方法 为此 在实际工作中 多采用启发式算法 为了对研究启发式算法有所帮助 先介绍两种十分重要的作业计划及其构成方法 一 两种作业计划的构成一般说来 在可行的加工顺序下 可以拟定出无数种作业计划 其中 各工序都按最早可能开始工作的时间安排作业计划 称为半能动作业计划 任何一台机器的每段空闲时间都不足以加工一道可加工工序的半能动作业计划 又称为能动作业计划 无延迟作业计划是指没有任何延迟出现的能动作业计划 所谓 延迟 是指工件等待加工时 机器出现空闲 即使这段空闲时间不足以完成一道工序的加工 能动作业计划和无延迟作业计划在研究一般单件作业排序问题时有重要作用 二 一般n m G Fmax问题的启发式算法 2020 2 20 55 能动作业计划与无延迟作业计划构成过程中涉及到的4个符号 若将每安排一道工序称为 一步 设 St 为第t步之前已排序工序构成的部分作业计划 Ot 为第t步可以排序的工序集合 Tk 为 Ot 中工序Ok的最早可能开工时间 T k 为 Ot 中工序Ok的最早可能完工时间 显然 Ok工序的作业时间 T k Tk 设t 1 S1 为空集 O1 为各工件第一道工序的集合 求T min T k 并求出T 出现的机器M 如果M 有多台 则任选一台 从 Ot 中挑出满足以下两个条件的工序Oj 需要机器M 加工 且Tj T 将确定的工序Oj放入 St 从 Ot 中消去Oj 并将Oj的紧后工序放入 Ot 使t t 1 若还有未安排的工序 转步骤 2 否则 停止 二 一般n m G Fmax问题的启发式算法 一 两种作业计划的构成P310 1 能动作业计划的构成步骤 2020 2 20 57 例11 5 有一个2 3 G Fmax问题 其加工描述矩阵D和加工时间矩阵T分别为 试构成一个能动作业计划 P310 按表11 9所示的能动作业计划构成过程 可绘出图11 4能动作业计划时间安排 排序 图 能动作业计划 2020 2 20 58 表11 9能动作业计划的构成T min T k 下期工序最早可能开工时间 1 1 1 2 1 3 1 2 3 2 2 1 1 3 2 2 3 2 1 1 12 1 3 1 2 32 1 3 1 2 32 2 1 1 3 22 2 1 1 3 22 3 2 2 3 2 00 20 33 73 77 8 23 43 44 14 15 5 23 63 77 87 812 13 2 3 7 7 8 13 M1 M3 M3M1 M1 M2 M2 或 一个2 3 G Fmax问题 2020 2 20 59 能动作业计划的甘特图 最大流程 Fmax 13 012345678901234 M1 M2 M3 1 1 1 2 2 1 2 3 7 2 1 3 1 2 3 7 3 1 3 2 2 3 2 7 8 13 对表11 9所示的能动作业计划 作业时间排序 构成过程可描述为下列过程 1 当t 1时 O1 为 2个工件 可以在第1道工序上 进行第1步排序的集合 即 O1 1 1 1 2 1 3 它们的最早可能开工时间Tk T1 0 工序 1 1 1 的最早可能完工时间T k T 1 2 工序 2 1 3 的T k T 1 3 T min T k 2 可见 T 2出现的机器M M1 在这一步中M1上仅有一道工序 1 1 1 可以排序 所以 首先安排 1 1 1 在M1上加工 2 3 略 4 当t 4时 O4 1 3 2 2 2 1 T4 7或3 T 4 8或7 T 7 出现在M1上 将 2 2 1 安排在M1上加工 5 略 6 当t 6时 O6 2 3 2 T6 8 T 6 13 此时只剩下 2 3 2 将 2 3 2 安排在M2上加工 该排序问题最后完工时间为13 1 能动作业计划的构成步骤 一 两种作业计划的构成 在作业计划中 延迟 是指工件等待加工 而机器出现空闲 空闲时间不能完成一道工序的加工作业 所以 无延迟作业计划是指没有任何延迟出现的能动作业计划 无延迟作业计划的构成步骤设t 1 S1 为空集 O1 为各工件第一道工序的集合 求T min T k 并求出T 出现的机器M 如果M 有多台 则任选一台 从 Ot 中挑出满足以下两个条件的工序Oj 需要机器M 加工 且Tj T 将确定的工序Oj放入 St 从 Ot 中消去Oj 并将Oj的紧后工序放入 Ot 使t t 1 若还有未安排的工序 转步骤 2 否则 停止 2 无延迟作业计划的构成 排序 步骤P311 2020 2 20 62 例 对例11 5 有一个2 3 G Fmax问题 其加工描述矩阵D和加工时间矩阵T分别为 试构成一个无延迟作业计划 P312 解 表11 10无延迟作业计划的构成 最大流程 Fmax 13 2020 2 20 63 无延迟作业计划的甘特图 最大流程 Fmax 13 012345678901234 M1 M2 M3 1 1 1 2 2 1 2 3 7 2 1 3 1 2 3 7 3 1 3 2 2 3 2 7 12 13 二 作业排序的三类启发式算法 1 优先调度法 见教材311 314页 对应用优先调度法则的说明 2 随机抽样法 3 概率调度法 8个主要的优先调度法则 P312 二 一般n m G Fmax问题的启发式算法 1 SPT法则 最短加工时间规则 例题SPT法则就是优先选择加工时间最短的工序 即排序时将各个工件的加工时间由短到长进行排队 排在前面的加工时间最短的工序优先按排加工 其优点是 使平均流程时间F最短 使在制品的占用量减少 其缺点是没有考虑交货期 有可能会使部分工件延误了交货期 例 现有一个6 1 F问题 其加工时间与交货期如表11 10所示 试采用SPT法则进行作业排序 三 优先调度法则例题 此为单台设备排序问题例题 表11 10加工时间与交货期表 1 SPT法则 最短加工时间规则 例题 解 由求解过程可知 按SPT法则排序顺序为 J3 J6 J1 J4 J2 J5 流程时间分别为 2 5 9 14 22 31 F 13 8 工件J4延期交货8个时间单位 其余提前完成 4 统计延期交货状况 3 计算平均流程时间 2 计算各工件加工流程时间 标在加工时间的右上角 1 将各个工件加工时间由短到长排队为 J32 J63 J14 J45 J28 J59 表11 11延期交货统计表 转后例 2 EDD规则 最早预定交货规则 例题EDD规则就是优先选择完工期限紧的工件 即 在进行工件作业排序时 按工件完工期限由紧到松进行排序 排在前面的完工期限最紧的工件优先按排加工 EDD法则的优点是考虑了交货期 有利于做到按期交货 使工件中的最大延迟时间最小 其缺点是使平均流程时间F增加 增大了在制品占用量 三 优先调度法则例题 此为单台设备排序问题例题 试进行作业排序 使Lmax最小 表11 10加工时间与交货期 例 仍采用上例 有一个6 1 Lmax问题 即6个工件 1台机器 使最大延迟时间最小 其加工时间与交货期如表11 10所示 由表11 12计算可知 该例采用EDD法则排序为 J4 J3 J6 J2 J1 J5 且各工件延迟时间均为0 平均流程时间F 15 5 三 优先调度法则例题 此为单台设备排序问题例题 2 EDD规则 最早预定交货规则 例题 解 根据EDD法则是将完工期限最紧的工序优先按排 为此采用表11 12把交货期短的工件先按排 再求出流程时间与交货期相比较 检查是否存在有延迟时间的工件 延迟时间是多少 是否可以在排序上再进行调整 5 7 10 18 22 31 表11 12延迟时间分析表 0 0 0 0 0 0 转前例 3 SPT与EDD混合 结合 法则例题这是将SPT规则 最短加工时间规则 与EDD规则 最早预定交货规则 结合起来的在单台设备上的排序方法 这种排序方法克服了SPT与EDD两个单一规则只能达到一个目标的缺点 可以获得较为理想的结果 为了说明问题方便 仍以表11 10所示的排序问题为例 三 优先调度法则例题 此为单台设备排序问题例题 表11 10加工时间与交货期表 三 优先调度法则例题 此为单台设备排序问题例题 3 SPT与EDD混合 结合 法则例题 按SPT与EDD结合的规则排序步骤如下 1 首先根据EDD规则排序 即安排一个使Lmax min 使最长延迟时间最短 的初步方案 若该初步方案出现Lmax 0 说明该初步方案已满足要求 例如表11 10的例子 可按交货期最短的先安排加工 即根据交货期排序 所以 其排序为 J4 J3 J6 J2 J1 J5 按此排序可以求得 Lmax max Li 1 满足要求 2 计算全部生产任务的总流程时间 F总 Fmax max Fi F5 Pi P4 P3 P6 P2 P1 P5 31 3 找出初步方案中预定交货期大于Fmax的工件 可能有多件 并按SPT规则 把其中加工时间最长的工件排在最后加工 在本例中 预定交货期大于Fmax 31的工件只有J5 当然应该将J5排在最后加工 4 舍弃第 3 步中已排在最后的J5 余下J4 J3 J6 J2 J1重复第 2 步 此时出现情况如表11 13所示 三 优先调度法则例题 此为单台设备排序问题例题 3 SPT与EDD混合 结合 法则例题 由表11 13可知 余下5个工件中J1的F最大 Fmax 22 预定交货期大于Fmax 22的有J1和J2 其中J2的加工时间P2 8为较大者 P2 8 P1 4 故按SPT规则将J2排在第5顺序 倒数第2位 加工 即将J2排在次后顺序上加工 表11 13余下工件的F与预订交货期 5 7 10 18 22 反复进行 2 3 步 直到实现既使Lmax 0 又使F 平均流程时间 为Fmin的排序方案为止 5 7 10 14 22 31 表11 14排序方案及各参数结果表 三 优先调度法则例题 此为单台设备排序问题例题 按SPT与EDD结合规则排序 可得出表11 10的排序问题的排序为 J4 J3 J6 J1 J2 J5 表11 10排序问题的结论如表11 14所示 3 SPT与EDD混合 结合 法则例题 平均流程时间F 14 8 现有一个n 2 F Fmax n个工件 2台设备 流水作业排序问题 使最长流程时间最短 问题 此问题可采用S M Johnson算 解 按照Johnson法则 1 如果最短的加工时间出现在M1上 则对应工件排在最前面 第一个 加工 如果最短的加工时间出现在M2上 则对应工件排在最后面 倒数第一个 加工 如果最短的加工时间同时出现在M1 M2上 则该工件排在最前或最后加工均可 2 划去已排序工件 在余下来的未排序工件中仍然按上述方法进行作业排序 直到全部工件安排完为止 自己练习 表11 15加工时间 例 有一个7 2 F Fmax问题 其加工时间如表11 15所示 试进行作业排序 第四节多台设备作业排序 流水作业排序 4 1 5 2 6 3 7 一 多个工件在两台设备上的作业排序 3112691852 表11 16加工时间与排序结果表 391624354771 6204655737880 3 运用Johnson法则对此问题求解如表11 16和图11 3所示 J4J1J5J2J6J3J7 3678111224 391624354771 369204655737880 M1 M2 时间 Fmax 80 图11 3作业排序甘特图 J4J1J5J2J6J3J7 若存在一个n 3 P Fmax问题 且mint1i maxt2i或mint3i mint2i i 1 2 n 则可采用Johnson法排序 求解步骤为 1 先找出mint1i maxt2i或mint3i mint2i关系 2 将3台设备变换成2台假想设备MA和MB 并令tAi t1i t2i tBi t2i t3i 3 依据tAi和tBi 采用Johnson法则进行作业排序 二 多个工件在三台设备上的作业排序 采用Johnson法则 试采用Johnson法则进行作业排序 表11 17加工时间表 例 有一个4 3 P Fmax问题 其加工时间如表11 17所示 解 mint1i 6maxt2i 6存在mint1i maxt2imint3i 4mint2i 1存在mint3i mint2i 可采用Johnson法求解该作业排序问题 具备其一即可 计算tAi和tBi 列于表11 18中 表11 18tAi tBi与排序结果 学生自己练习绘制排序结果甘特图 依据11 18中的tAi和tBi 采用Johnson法进行作业排序 排序结果与Fmax如表11 18及图11 4所示 Fmax 48 J2J4J3J1 812615 1653 892026314144 8202641 10754 9192633384448 M1 M2 M3 时间 图11 4排序结果甘特图 n个工件在m台设备上排序是比较困难的 但是 对于2个工件在m台设备上排序问题 运用图解法虽然不一定求到最佳解 却可以求到比较令人满意的解 例 2个工件在4台机器上加工 每个工件的加工顺序不同 J1的加工顺序是M1 M2 M3 M4 J2的加工顺序是M4 M2 M1 M3 其加工时间如表11 19所示 显然 这是一个非流水作业排序问题 是一个一般的排序问题 故可用2 4 G Fmax表示 也可用2 4 G Cmax表示 三 两个工件在m台设备上的作业排序 该问题亦可用加工描述矩阵D与加工时间矩阵T表示为 表11 19加工时间表 一 用图解法求解 2020 2 20 79 第四节多台设备作业排序 1 画平面直角坐标 横 纵轴分别为J1 J2的加工时间 对应横轴下部的甘特图与对应纵轴左侧的甘特图分别表示J1 J2加工顺序及其所对应的加工时间 原点O为时间起点 找出表示J1 J2总加工时间的坐标点D 12 16 2 划去不可能同时加工两个工件的时间 开始时 J1在M1上加工 M1便不能加工J2 故划去方格 的区域 同理划去方格 的区域 3 从原点开始 在未划去的区域中 连线到终点D 连线若为45 角 表示2个工件同时在被加工 例如A点 6 6 表示J1在M1上加工早已完毕 正在M2上加工 J2在M4上加工刚好完毕 正准备进入M2上加工 但由于M2正在加工J1 所以 又等了1个单位时间到B点 7 6 此时 M2刚好加工完J1 从B点开始 M2加工J2 M3加工J1 接着M1加工J2 M4加工J1 到了C点 12 11 M4刚好加工完J1 M2刚好加工完J2 C点到D点是竖直线 此段时间J1已加工完毕 M1和M3只加工J2 三 两个工件在m台设备上的作业排序 例 解 该问题可采用图解法求作业排序的解 例 解 3 由原点向D点引连线时 尽量按45 角方向引线 并使等待时间最小 在实际操作上 这种排序方法常常通过目视 徒手画的方法完成的 所以 不能保证求得最佳的排序结果 只能求得较令人满意的结果 从作图求解过程可知 J1工件没有等待时间 F1max 12 J2加工等待时间为1 所以 F2max 17 当然此问题也可写成C1max 12 C2max 17 该图解法求解2 4 G Cmax问题的过程如图11 5所示 2020 2 20 81 图11 5图解法求解2 4 G Cmax过程图 M1 M2 2 7 M3 11 M4 12 M4 M2 6 11 M1 13 M3 16 I II III IV A 6 6 B 7 6 C 12 11 D 12 16 例 解 上述作业排序问题2 4 G Fmax 三 两个工件在m台设备上的作业排序 的排序结果如图11 6所示 2020 2 20 83 三 两个工件在m台设备上的作业排序 二 用启发式算法求解 1 请同学们按能动作业计划构成步骤求解 前述的2 4 G Fmax 可采用按能动作业计划构成步骤求 解 其求解 排序 过程及结果如表11 20与图11 7所示 2020 2 20 84 表11 20能动作业计划构成表 2020 2 20 85 二 用启发式算法求解 1 按能动作业计划构成步骤求解根据11 20可绘出如图11 7所示的该问题作业排序甘特图 由图11 7可见 采用启发式算法 按能动作业计划构成步骤进行求解 作业排序结果甘特图与图解法得出的图11 6所示的甘特图相同 说明两种方法求解结果相同 1 1 1 2 3 1 1 2 2 2 2 2 1 3 3 2 4 3 2 1 4 1 4 4 2 212 2 14 2 5 7 5 12 7 4 1114 3 17 6 61112 1 Fmax Cmax 17 J1 J2 J2 J2 J2 J1 J1 J1 M1 M2 M3 M4 o 时间 图11 7作业排序甘特图 二 用启发式算法求解 2 按无延迟作业计划构成步骤求解 其求解 排序 过程及结果如表11 21与图11 7所示 见下一页 由表11 2中的栏与栏可看出 构成作业计划 排序 中所选中的设备与工件及其安排次序均与表11 20相同 说明排序结果相同 绘出的表示作业排序结果的甘特图肯定也与图11 7相同 这里不再另外绘出 前述的2 4 G Fmax 可采用按无延迟作业计划构成步骤求解 2020 2 20 87 表11 21无延迟作业计划的构成表 Fmax Cmax 17 2020 2 20 88 课堂练习 5种零件在三台机床上的加工时间如下表所示 表1零件加工时间表 小时 请用约翰逊法则排序并计算最大流程时间 2020 2 20 89 2 两种零件的加工描述矩阵 和加工时间矩阵 如下 请用能动作业计划表 图解法 确定两种零件的投产方案并绘制甘特图确定加工作业周期 2020 2 20 90 1题解答 n 3 P Fmax问题 满足mint1i maxt2i或mint3i mint2i i 1 2 n 则可采用Johnson法排序 求解步骤为 1 判断mint1i 3 maxt2i 3或mint3i 2 mint2i1满足关系 可以应用Johnson法排序 2 将3台设备变换成2台假想设备MA和MB 并令tAi t1i t2i tBi t2i t3i 3 依据tAi和tBi 采用Johnson法则进行作业排序 2020 2 20 91 结果为 J1 J5 J3 J2 J4 3 10 16 21 26 5 12 19 24 27 10 18 23 27 29 最大流程时间Fmax 29 小时 2020 2 20 92 2题解答 图解法确定两种零件的投产方案并绘制甘特图 图解法确定两种零件的投产方案 M1 M1 M3 M4 01234567890123 109876543210 M4 M2 M3 M2 I IV II III J1 J2 Q 13 10 F2 15 2 1 4 1 3 2 2 F1 16 1 4 1 6 2 2 2020 2 20 93 第二方案甘特图Fmax 15 小时 0123456789012345 时间 小时 M2 M1 M3 M4 1 1 1 1 2 2 1 3 3 1 4 4 2 1 1 2 2 4 2 3 2 3 3 3 11 11 13 2 3 2 7 7 8 2 4 3 15 J1 J2 J2 J2 J1 J1 2020 2 20 94 排序问题作业练习 P321 1 2 补充4 有一个2 5 G Cmax的问题 零件1的工艺路线次序为经过机器 1 2 3 4 5 零件2的工艺路线次序为经过机器 4 1 2 5 3 工序加工时间见下表 试用图解法求完成总时间最少的排序 并绘出甘特图 2020 2 20 95 第五节生产作业监控与调度规则 生产作业计划实施过程总会出现一些难以预见防碍的因素 因此 要对生产的全过程进行监控 及时发现计划执行中已发生或即将发生的各种偏差 并采取措施预防和纠正它 作业监控是生产管理工作的基本职能之一 在编制生产作业进度计划时 一般考虑静态情况较多 只有当生产因素比较稳定和比较理想的情况才能得到最优化 但在动态的生产实施过程中 影响生产实施的一些因素会发生变化 如零件加工时间有随机性 原材料供应误期 上一工序延期交付 零件加工中的报废 工具 设备发生故障 工人缺勤等等 以及外部因素 如市场需求发生变化而影响生产计划的数量来因此 在生产实施时期 生产控制必须及时 全面地了解和掌握生产过程情况 采取有效措施保证完成计划期内预定的生产目标 这对多品种的成批和单件批小生产尤为重要 2020 2 20 96 一 生产控制功能 生产控制包括以下两个基本功能 1 生产系统控制生产系统控制是控制从原材料到最终产品的物质流 包括 控制时间 交付期 和产量的生产控制 狭义的生产控制 保证产品具有要求的质量和可靠性的质量控制 控制原材料 产品的库存控制 生产过程中的成本控制等 2 生产资源控制生产资源控制主要是指对生产设备的控制功能 它的基本活动是防止生产设备损坏和修复已损坏的生产设备 即生产设备的维修工作 2020 2 20 97 二 对时间和产量的生产控制 生产进度计划规定的产量和进度 或交付日期 是生产实施阶段的生产标准 经常检查实际产量和完工时间并和计划标准比较 如果发生偏差 就要采取有效措施以保证完成计划 图11 28是表示生产控制的一般反馈过程 对计划进度与实际实施情况发生的偏差 应及时报告有关管理人员和领导 迅速作出决策以追补或调整偏差 生产标准 计划产量与时间 生产实施 度量生产效果 实际产量与时间 比较计划与实际效果 修正偏差 图10 28生产控制系统反馈过程 2020 2 20 98 对时间 进度 和产量的生产控制 要求经常检查车间 或工段 之间 车间内部的产品 零件 部件 毛坯 的交付期限 原材料供应和投入情况 以及生产过程中的库存的在制品储备情况 对生产实施情况的检查 传统的办法是利用各种形式的图表来对比出产量的计划进度和实际进度 如用横道图表示的产品 零 部件 出产量进度完成情况如图表 产品配套计划完成情况图表以及主要零件各道工序的进度完成情况图表 对于在制品的库存和周转情况也可采用各种形式的图表对比检查 除了检查生产进度完成情况外 还应检查和督促生产准备工作进行情况 劳动力配备情况 设备运转和维修情况 运输 动力运行情况以及主要的技术关键等情况 生产控制工作要求反映情况的及时性 准确性 全面性 作出决策处理问题的迅速性 计算机辅助生产信息系统 有利于实现这些要求 从数据的收集 数据存储 数据取出 数据处理 数据传输到数据显示 它使生产系统能够适时地精确地处理各种信息 作出适当的决策 采取相应的措施 从而适应动态地变化着的外部环境 2020 2 20 99 三 调度规则 我们在