流水作业的排序问题.pptVIP

第九章流水作业的排序问题 9 1排序问题概述9 2流水作业排序问题 9 1排序问题概述一 排序问题的基本概念排序是确定工件 零部件 在一台或一组设备上加工的先后顺序 在一定约束条件下 寻找总加工时间最短的安排产品加工顺序的方法 就是生产作业排序 例如 考虑32项任务 工件 有32 2 6 1035种方案 假定计算机每秒钟可以检查1billion个顺序 全部检验完毕需要8 4 1015个世纪 如果只有16个工件 同样按每秒钟可以检查1billion个顺序计算 也需要2 3年 以上问题还没有考虑其他的约束条件 如机器 人力资源 厂房场地等 如果加上这些约束条件 所需要的时间就无法想象了 所以 很有必要去寻找一些有效算法 解决管理中的实际问题 假设条件 1 一个工件不能同时在几台不同的机器上加工 2 工件在加工过程中采取平行移动方式 即当上一道工序完工后 立即送下道工序加工 3 不允许中断 当一个工件一旦开始加工 必须一直进行到完工 不得中途停止插入其它工件 4 每道工序只在一台机器上完成 5 工件数 机器数和加工时间已知 加工时间与加工顺序无关 6 每台机器同时只能加工一个工件 排序常用的符号 Ji 工件i i 1 2 n Mj 机器j j 1 2 m pij 工件Ji在机器Mj上的加工时间 j 1 mPi 工件Ji的加工时间 di 工件Ji的完工期限 Ci 工件Ji的完成时间 Fi 工件Ji的流程时间 即工件在车间的实际停留时间 在工件都已到达的情况下 Fi Pi WiWi 工件Ji在加工过程中总的等待时间Li 工件Ji的延误时间 Li Ci di Li0延误Fmax 最长流程时间 Fmax max Fi 二 排序问题的分类和表示法 1 排序问题的分类 1 根据机器数的多少单台机器的排序问题多台机器的排序问题 2 根据加工路线的特征单件作业排序 JobShop 工件加工路线不同流水作业排序 FlowShop 所有工件加工路线完全相同 3 根据工件到达系统的情况静态排序 进行排序时 所有工件都已到达 可以一次对他们排序动态排序 工件陆续到达 要随时安排他们的加工顺序 4 根据参数的性质确定型排序 指加工时间和其他参数是已知确定的量随机型排序 指加工时间和有关参数为随机变量 5 根据要实现的目标单目标排序多目标排序 2 排序问题的表示法 排序问题常用四个符号来描述 n m A B其中 n 工件数 m 机器数 A 车间类型 F 流水作业排序 P 流水作业排列排序G 一般类型 即单件型排序B 目标函数 9 2流水作业排序问题 一 最长流程时间Fmax的计算工件Si在机器MK上的完工时间为CKSi工件Si在机器MK上的加工时间为PSiKC1Si C1Si 1 PSi1CKSi max C k 1 Si CkSi 1 PSik 举例 有一个6 4 p Fmax问题 其加工时间如下表所示 当按顺序S 6 1 5 2 4 3 加工时 求Fmax 二 两台机器排序问题 两台机器排序的目标是使最大完成时间 总加工周期 Fmax最短 实现两台机器排序的最大完成时间Fmax最短的目标 一优化算法就是著名的约翰逊法 Johnson sLaw 其具体求解过程如下例所示 约翰逊 贝尔曼法则 约翰逊法解决这种问题分为4个步骤 1 列出所有工件在两台设备上的作业时间 2 找出作业时间最小者 3 如果该最小值是在设备1上 将对应的工件排在前面 如果该最小值是在设备2上 则将对应的工件排在后面 4 排除已安排好的工件 在剩余的工件中重复步骤 2 和 3 直到所有工件都安排完毕 举例AB两台设备完成6个零件的加工任务 每个工件在设备上的加工时间如下表所示 求总加工周期最短的作业顺序 机器 工件编号 求解过程 由约翰逊法可知 表中最小加工时间值是1个时间单位 出现在设备1上 根据约翰逊法的规则 应将对应的工件2排在第一位 即得 J2 去掉J2 在剩余的工件中再找最小值 最小值是2个时间单位 它是出现在设备2上 所以应将对应的工件J3排在最后一位 即 J2 J3再去掉J3 在剩余的J1 J4 J5 J6中重复上述步骤 求解过程为 J2 J5 J3J2 J5 J6 J3J2 J5 J6 J4 J3J2 J5 J6 J1 J4 J3当同时出现多个最小值时 可从中任选一个 J2 J5 J6 J1 J4 J3或J2 J5 J1 J6 J4 J3 求得最优顺序下的Fmax 28 Johnson算法的改进 1 将所有ai bi的工件按ai值不减的顺序排成一个序列A 2 将ai bi的工件按bi值不增的顺序排成一个序列B 3 将A放到B之前 就构成了一个最优加工顺序 ai bi工件按ai值不减的顺序 由小到大 排列 J2 J5 J6 J1 ai bi的工件按bi值不增的顺序 由大到小 排列 J4 J3最后排序J2 J5 J6 J1 J4 J3 三 m m 3 台机器排序问题的算法 一般采用启发式算法解决这类问题 斜度指标法关键工件法CDS法 一 Palmer 斜度指标法 工件的斜度指标计算公式 k 1 2 m式中 m机器数 Pik为工件i在Mk上的加工时间 按照各工件 i不增的顺序排列工件 可得出令人满意的顺序 i 举例 有一个4 3 F Fmax问题 其加工时间如下表所示 用Palmer法求解 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 k 1 2 3 Fmax 28 Fmax 28加工顺序 1 2 3 4 或 2 1 3 4 二 关键工件法 1 计算Pi 找出其中最大者 定义为关键工件Jc 2 除Jc外 将满足Pi1 Pim的工件 按Pi1值的大小 从小到大排在Jc的前面 3 除Jc外 将满足pi1 pim的工件 按Pim值的大小 从大到小排在Jc的后面 1 工件3加工时间最长 作为关键工件 2 满足Pi1pi3的工件是4 将4排在3的后面 所以加工顺序为 1 2 3 4 举例 具体过程 1 找出关键工件 工作负荷最大的40 对应的是工件6 Jc J6 2 满足Pi1 Pi5的工件有J1 J4 J5 按Pi1值由小到大排在关键工件前面 所以有J4 J5 J1 J6 3 满足pi1 pi5的工件有J2 J3 按Pi5值由大到小排在关键工件的后面 所以有 J6 J2 J3J4 J5 J1 J6 J2 J3Fmax 51 三 CDS法 Campbell Dudek Smith三人于1970年共同提出了一个启发式算法 简称CDS法 他们把Johnson算法用于一般的n m P Fmax问题 得到 m一1 个加工顺序 取其中优者 具体做法是 对加工时间和 l 1 2 m 1 用Johnson算法求 m 1 次加工顺序 取其中最好的结果 举例 当l 1时 按Johnson算法得到加工顺序 1 2 3 4 Fmax 28 当l 2时 得到加工顺序 2 3 1 4 对于顺序 2 3 1 4 Fmax 29所以 取顺序 1 2 3 4 四 相同零件 不同移动方式下加工周期的计算1 顺序移动一批零件在上道工序全部加工完毕后才整批转移到下道工序继续加工 一批零件的加工周期为 例 已知n 4 t1 10分 t2 5分钟 t3 15分钟 t4 10分钟 求T顺 T顺 4 10 5 15 10 160 分钟 2 平行移动方式每个零件在前道工序加工完毕后 立即转移到下道工序继续加工 形成前后交叉作业 一批零件的加工周期为 T平 10 5 15 10 4 1 15 85 分钟 3 平顺移动方式当t1 ti 1时 零件按平行移动方式转移 当t1 ti 1时 以I工序最后一个零件的完工时间为准 往前推移 n 1 ti 1 作为零件在 i 1 工序的开工时间 一批零件的加工周期为 T平顺 4 10 5 15 10 4 1 5 5 10 100 分钟 三种移动方式的比较 练习题 设某种零件批量为5件 加工工序数为4 每道工序单件加工时间为t1 6小时 t2 10小时 t3 8小时t4 16小时 试求三种移动方式下该批零件的加工周期 T顺 5 6