生产运作管理-第十一章-流水作业的排序问题.ppt

《生产运作管理-第十一章-流水作业的排序问题.ppt》由会员分享，可在线阅读，更多相关《生产运作管理-第十一章-流水作业的排序问题.ppt（43页珍藏版）》请在装配图网上搜索。

1、 第十一章 流水作业的排序问题 一、排序问题的基本概念 排序 是确定工件（零部件）在一台 或一组设备上加工的先后顺序。 在一定约束条件下，寻找总加工时 间最短的安排产品加工顺序的方法，就 是 生产作业排序。 例如，考虑 32项任务（工件），有 32！ 2.61035种 方案 ,假定计算机每秒钟可以检查 1 billion个顺序 , 全部检验完毕需要 8.41015个世纪。 如果只有 16个工件 , 同样按每秒钟可以检查 1 billion 个顺序计算 , 也需要 2/3年。 以上问题还没有考虑其他的约束条件 , 如机器、人 力资源、厂房场地等，如果加上这些约束条件，所 需要的时间就无法想象了。

2、 所以，很有必要去寻找一些有效算法，解决管理中 的实际问题。 排序困难性 假设条件 1.一个工件不能同时在几台不同的机器上加工 。 2.工件在加工过程中采取平行移动方式 ， 即当上一道工 序完工后 ， 立即送下道工序加工 。 3.不允许中断 。 当一个工件一旦开始加工 ， 必须一直进 行到完工 ， 不得中途停止插入其它工件 。 4.每道工序只在一台机器上完成 。 5.工件数 、 机器数和加工时间已知 ， 加工时间与加工顺 序无关 。 6.每台机器同时只能加工一个工件 。 排序常用的符号 Ji-工件 i， i=1,2,.n。 Mj - 机器 j， j 1， 2， ， m. di-工件 Ji 的完

3、工期限 。 pij-工件 Ji在机器 Mj上的加工时间 ,j=1, ,m Pi-工件 Ji的加工时间 , wij-工件 Ji在机器 Mj前的等待时间 , j=1, ,m Wi-工件 Ji在加工过程中总的等待时间 , Ci-工件 Ji 的完成时间 , Fi-工件 Ji 的流程时间 ， 即工件在车间的实际停留时间 ， 在工 件都已到达的情况下 , Fi= Pi+ Wi Li-工件 Ji 的延误时间 , Li= Ci- di , Li0 延误 Fmax-最长流程时间 ， Fmax maxFi 二、排序问题的分类和表示法 1、排序问题的分类： 根据机器数的多少 单台机器的排序问题 多台机器的排序问题

4、根据加工路线的特征 单件作业排序 (Job Shop) 流水作业排序 (Flow Shop) 根据工件到达系统的情况 静态排序 动态排序 根据参数的性质 确定型排序 随机型排序 根据要实现的目标 单目标排序 多目标排序 2、 排序问题的表示法 排序问题常用四个符号来描述 : n/m/A/B 其中 , n-工件数； m-机器数； A-车间类型； F=流水型排序 ， P=排列排序 G=一般类型 ,即单件型排序 B-目标函数 三、流水作业排序问题 1、最长流程时间 Fmax的计算 举例：有一个 6/4/p/ Fmax问题，其加工时 间如下表所示。当按顺序 S（ 6， 1， 5， 2， 4， 3） 加

5、工时，求 Fmax。 i 1 2 3 4 5 6 Pi1 Pi2 Pi3 pi4 4 2 3 1 4 2 4 5 6 7 4 5 5 8 7 5 5 5 4 2 4 3 3 1 i 6 1 5 2 4 3 Pi1 Pi2 Pi3 pi4 2 4 4 2 1 3 5 4 4 5 7 6 5 5 5 8 5 7 1 4 3 2 3 4 最长流程时间的计算 2 7 12 13 6 10 12 13 16 11 15 20 27 33 17 22 30 35 42 21 25 32 38 46 最长流程时间的计算 举例 2 i 1 4 6 3 5 2 Pi1 4 5 3 4 8 6 Pi2 3 9 1

6、 3 7 5 Pi3 7 6 8 2 5 9 Pi4 5 6 3 9 2 4 4 9 12 16 24 30 7 14 19 18 19 22 31 36 24 32 34 39 48 30 35 44 46 52 2、两台机器排序问题 两台机器排序的目标是使最大完成时间（总 加工周期） Fmax最短 。 实现两台机器排序的最大完成时间 Fmax最短 的目标，一优化算法就是著名的约翰逊法 (Johnsons Law)。 其具体求解过程如下例所 示。 约翰逊贝尔曼法则 约翰逊法解决这种问题分为 4个步骤： (1)列出所有工件在两台设备上的作业时间 。 (2)找出作业时间最小者 。 (3)如果该最

7、小值是在设备 1上 ， 将对应的工件排在 前面 ， 如果该最小值是在设备 2上 ， 则将对应的工件 排在后面 。 (4)排除已安排好的工件，在剩余的工件中重复步 骤 (2)和 (3)，直到所有工件都安排完毕。 举例 AB两台设备完成 5个零件的加工任务，每个 工件在设备上的加工时间如下表所示。求总 加工周期最短的作业顺序。 设备 工件编号 J1 J2 J3 J4 J5 设备 A 3 6 7 1 5 设备 B 2 8 6 4 3 求解过程 由约翰逊法可知 ， 表 5-8中最小加工时间值是 1个时间单位 ， 它又是 出现在设备 1上 ， 根据约翰逊法的规则 ， 应将对应的工件 4排在 第一位 ，

8、即得： J4 - * - * - * - * 去掉 J4， 在剩余的工件中再找最小值 ， 不难看出 ， 最小值是 2个 时间单位 ， 它是出现在设备 2上的 ， 所以应将对应的工件 J1排 在最后一位 ， 即： J4 - * - * - * - J1 再去掉 J1， 在剩余的 J2、 J3、 J5中重复上述步骤 ， 求解过程为： J4 - * - * - J5 - J1 J4 - J2 - * - J5 - J1 J4 - J2 - J3- J5 - J1 当同时出现多个最小值时，可从中任选一个。最后得 J4 - J2 - J3- J5 - J1 (a) J1 - J2 - J3- J4 -

9、J5 30 A B (b) J4 - J2 - J3- J5 - J1 26 A B 比较 可以看出，初始作业顺序的总加工周期 是 30，用约翰逊法排出的作业顺序总加工 周期是 26，显然后者的结果优于前者。 将工件 2排在第 1位 2 将工件 3排在第 6位 2 3 将工件 5排在第 2位 2 5 3 将工件 6排在第 3位 2 5 6 3 将工件 4排在第 5位 2 5 6 4 3 将工件 1排在第 4位 2 5 6 1 4 3 最优加工顺序为 S=(2,5,6,1,4,3), Fmax =28 I 1 2 3 4 5 6 Ai 5 1 8 5 3 4 Bi 7 2 2 4 7 4 两台机

10、器排序问题的算法（续） Johnson算法的改进 1. 将所有 ai bi的工件按 ai值不减的 顺序排成一个序列 A； 2. 将 ai bi的工件按 bi值不增的顺序排 成一个序列 B； 3. 将 A放到 B之前，就构成了一个最优 加工顺序。 改进算法举例 工件号 1 2 3 4 5 6 ai 5 1 8 5 3 4 bi 7 2 2 4 7 4 最优顺序： 2 5 6 1 4 3 1 3 4 5 5 8 2 7 4 7 4 2 ai bi 最优顺序下的加工周期为 28 1 4 8 13 18 26 3 11 15 22 26 28 3、 m(m 3)台机器排序问题 的算法 一般采用启发式算

11、法解决这类问 题。 关键工件法 斜度指标法 CDS法 （ 1）关键工件法 1、 计算 Pi= , 找出其中最大者，定义为关键工件 Jc。 2、 除 Jc外，将满足 Pi1pim的工件，按 Pim值的大小， 从大到小排在 Jc的后面。 4、除 Jc外，将满足 Pi1=Pim的工件，排在 Jc的前面或者 后面 步骤 5 如有多个方案，可再加比较，从中选优。 m j Pij 1 举例 J1 J2 J3 J4 J5 J6 机器 1 pi1 5 5 4 1 2 10 机器 2 pi2 5 5 5 3 6 10 机器 3 pi3 8 3 3 4 7 4 机器 4 pi4 2 8 2 1 5 6 机器 5

12、pi5 5 2 1 2 8 10 总和 25 23 15 11 28 40 具体过程 找出关键工件：工作负荷最大的 40，对应的是工件 6， 所以 Jc=J6 确定排在关键工件前面的工件：满足步骤 2条件的有 J4, J5, 所以有 J4 J5 J6 确定排在关键工件后面的工件：满足步骤 3条件的有 J2, J3, 所以有 J6 J2 J3 满足步骤 4条件的有 J1, 所以有 J6 J1， 或者 J1 J6 最后有： J4 J5 J6 J1 J2 J3 ， 或 J4 J5 J1 J6 J2 J3 关键工件法（续） 工件 i 1 2 3 4 Pi1 2 1 6 3 Pi2 4 8 2 9 Pi

13、3 5 4 8 2 11 13 16 14 JC Sa (2,1) Sb(4) 所求顺序： （ 2,1,3,4） 练习 J1 J2 J3 J4 J5 J6 机器 1 pi1 8 3 5 4 2 4 机器 2 pi2 2 8 2 1 5 6 机器 3 pi3 5 2 1 2 8 10 机器 4 pi4 5 5 4 1 7 10 总和 20 18 12 8 22 30 练习 J5 J2 J6 J1 J3 J4 机器 1 pi1 2 3 4 8 5 4 机器 2 pi2 5 8 6 2 2 1 机器 3 pi3 8 2 10 5 1 2 机器 4 pi4 7 5 10 5 4 1 2 5 9 17

14、22 26 7 15 22 15 21 23 25 27 17 31 36 37 39 27 41 46 50 51 练习 J1 J2 J3 J4 J5 J6 机器 1 pi1 8 3 5 4 2 4 机器 2 pi2 2 8 2 1 5 6 机器 3 pi3 5 2 1 2 8 10 机器 4 pi4 5 5 4 1 7 10 8 11 16 20 22 26 10 15 20 19 21 22 27 33 21 22 24 35 45 26 30 31 42 55 (2) Palmer（ 斜度指标法） i= P i kmk m k 1 2/)1( 工件的斜度指标计算公式 k 1， 2， m

15、 式中 ， m机器数； Pik为工件 i在 Mk上 的加工时间 。 举例 有一个 4/3/P/Fmax问题，其加工时间如下 表所示，用 Palmer法求解。 i 1 2 3 4 Pi1 Pi2 Pi3 1 2 6 3 8 4 2 9 4 5 8 2 求解过程 求解过程 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 P i kk k 3 1 2/

16、)13( k=1， 2， 3 计算 Fmax i 1 2 3 4 Pi1 Pi2 Pi3 1 2 6 3 8 4 2 9 4 5 8 2 1 3 9 12 9 13 15 24 13 18 26 28 （ 3） CDS法 Campbell, Dudek, Smith三人于 1970年共同 提出了一个启发式算法，简称 CDS法。他 们把 Johnson算法用于一般的 n /m /P/Fmax 问题，得到（ m一 1)个加工顺序，取其中 优者。 具体做法是，对加工时间 和 （ l=1， 2， ， m-1） ， 用 Johnson算法求 （ m-1)次加工顺序 ， 取其中最好的结果 。 l k Pi

17、k 1 m lmk P ik 1 举例 有一个 4/3/P/Fmax问题，其加工时间如下 表所示，用 Palmer法求解。 i 1 2 3 4 Pi1 Pi2 Pi3 1 2 6 3 8 4 2 9 4 5 8 2 i 1 2 3 4 l=1 Pi1 1 2 6 3 P i3 4 5 8 2 l=2 Pi1+Pi2 9 6 8 12 P i2+Pi3 12 9 10 11 举例 当 l 1时 ， 按 Johnson算法得到加工顺 序 （ 1， 2， 3， 4） ；当 l=2时 ， 得到加 工顺序 (2， 3， 1， 4)。 对于顺序 （ 2， 3， 1， 4） ， 相应的 Fmax=29。 所

18、以 ， 取 顺序 （ 1， 2， 3， 4） 。 三种方法比较 以上三种方法，优度最高的是 CDS法， 其次是关键工件法， Palmer法最低。 从计算工作量来讲，关键工件法最简便， Palmer法次之， CDS最复杂。 四、相同零件不同移动方式下 加工周期的计算 当 n个零件相同，则无排序问题。但不 同移动方式下的加工周期不同 三种典型的移动方式 顺序移动方式：一批零件全部加工完成后， 整批移动到下道工序加工 平行移动方式：单个零件加工完成后，立 即移动到下道工序加工 平行顺序移动方式：两者混合 服务业企业作业排序问题 服务作业排序与生产作业排序的主要区别 l 所提供产品的类型 由于服务过程

19、有顾客参与 ,作业排序对他们有直接影响 ,并因 此成为服务的一部分 ,而在生产作业排序对产品的最终使用 者没有直接影响。 l 排序内容 在服务业中 , 排序要定义服务交易的时间或消耗点；而在制造 业中仅仅定义产品生产的操作步骤。 l 过程控制 在服务业中 ,顾客参与服务过程 ,并且对全部操作过程施加影响。 l 人员规模 在顾客化服务中 ,服务的输出与劳动力的最佳 规模之间的关系很难确定；而生产作业中 ,两者 之间的关系有紧密联系 ,因此最佳的作业顺序可 以被计算出来 。 服务作业排序方法之一 安排顾客需求 预约：如医生、律师等的服务 预定：顾客预定旅馆房间、火车或飞机票 排队等待：一种为顾客排序的不太准确的 方法是允许需求积压，让顾客排队等待。 例如，餐馆、银行、零售商店等。 服务作业排序方法之二 安排服务人员 当需要快速响应顾客需求、且需求 量大致可以预计时，通常使用这种 方法。如邮局营业员、护士、警察 的工作日和休息日安排；一天营业 24小时、一周 7天都营业的商店保 安人员安排；等等 。