《作业排序》PPT课件.ppt

第十一章作业排序 本章主要介绍制造业的作业排序问题 2020 3 23 武汉理工大学管理学院袁付礼 2 一 作业排序的概念和类型 1 概念对一定期间内分配给生产单位的作业任务 根据产品 零件 的工艺路线和设备负荷可能性 确定各个生产单位作业任务的先后顺序 作业排序问题通常表述为 n项作业任务在m个生产单位的排序的问题 2020 3 23 武汉理工大学管理学院袁付礼 3 一 作业排序的概念和类型 2 作业排序的类型 流水型m n排序问题指n项任务在m台设备上加工 所有任务的工艺顺序相同 有n 个排序方案 非流水型m n排序问题指n项任务在m台设备上加工 所有任务的工艺顺序不同 有 n m个排序方案 2020 3 23 武汉理工大学管理学院袁付礼 4 一 作业排序的概念和类型 作业排序的表示方法为生产单位数 作业任务数 排序问题类型 评价尺度 优化目标 如m n FLW Fmax表示m个生产单位完成n项作业任务 流水型排序问题和以最大流程时间作为评价尺度 2020 3 23 武汉理工大学管理学院袁付礼 5 二 作业排序的评价尺度 最大流程时间平均流程时间最大延期量平均延期量在制品占用量总调整时间 2020 3 23 武汉理工大学管理学院袁付礼 6 计算公式 设n为作业任务数 m为机床数 Ji为第i项作业任务 Oij为第i项作业任务的和j工序 tij为第i项作业任务在第j台机床上的作业时间 ri为任务Ji可以开始加工的时刻 di为Ji的要求完成时刻 wij为Oij在进行加工前的等候时间 如果没有等候 wij 0 第i项任务的完成时刻 ci 为ci ri ti1 wi1 ti2 wi2 tim wim 2020 3 23 武汉理工大学管理学院袁付礼 7 计算公式 续 令ti为作业任务i的总作业时间 则 令wi为作业任务i的总等候时间 则 则ci ri ti wi 2020 3 23 武汉理工大学管理学院袁付礼 8 计算公式 续 第i项作业任务在机床组的流程时间为 Fi ci ri ti wi如果作业任务i的完成时刻ci已超过要求完成时刻di 则形成交货延期 延期量Di为 Di ci di Fi ri di如果ci未超过di 则延期量Di为0 2020 3 23 武汉理工大学管理学院袁付礼 9 排序问题解法的约定 一个工件不能同时在不同的设备上加工 每道工序只在一台设备上完成 每台设备只完成一道工序 每台设备同时只能加工一个工件 工件在加工过程中采取平行移动方式 工件数 n 设备数 m 与加工时间均已知 允许工件在工序之间等待 允许设备在工件未到达时闲置 2020 3 23 武汉理工大学管理学院袁付礼 10 三 单台机床作业排序方法 1 n流水排序型问题的优先规则 先到先服务 FCFS 最短作业时间 SPT 最短交货延期量 EDD SPT与EDD结合原则最小松弛时间 SST 后到先服务 LCFS 按期完成作业项目最多的原则 按期完成作业项目最多的原则 即先按交货期优先原则逐项安排作业顺序 并依次计算每项任务是否拖期 如果遇到某项任务拖期 则将其移至最后加工 之后 若又有任务拖期 则又将其移至最后加工 2020 3 23 武汉理工大学管理学院袁付礼 11 三 单台机床作业排序方法 例 下表是在某工作中心等待加工的6项作业的加工时间 包含换产时间 与预定日期 假设工作的到达顺序与表中顺序相符 根据以下规则来决定其作业顺序 FCFS SPT EDD SST并对它们分别进行评价 2020 3 23 武汉理工大学管理学院袁付礼 12 按FCFS规则排序 排序的结果是A B C D E F 2020 3 23 武汉理工大学管理学院袁付礼 13 按SPT规则 作业顺序是A C E B D F 2020 3 23 武汉理工大学管理学院袁付礼 14 按EDD规则 作业顺序是C A E B D F 2020 3 23 武汉理工大学管理学院袁付礼 15 按SST规则 松弛时间 预定日期 加工时间 按松弛时间从小到大排列 可得顺序 C A F D B E 2020 3 23 武汉理工大学管理学院袁付礼 16 四 两台机床作业排序方法 加工顺序相同的若干个作业在两台机床上的加工排序 我们运用约翰逊 Johnson 规则解决 其步骤如下 1 列出每个作业在两台机床上的作业时间 2 选择最短的作业时间 3 如果最短的作业时间来自第一台机床 则首先进行这个作业 如果最短的作业时间来自第二台机床 则最后进行这个作业 4 重复上述步骤 直到排序完成 2020 3 23 武汉理工大学管理学院袁付礼 17 约翰逊 贝尔曼规则 例 4项作业在两台设备上进行加工 其加工顺序相同 作业时间如下表所示 T 2 4 8 6 5 25 2020 3 23 武汉理工大学管理学院袁付礼 18 五 3台机器上N项作业的排序 简称为N 3排序 此方法是约翰逊 Johnson 规则的扩展方法 它是将三台设备合并为两台假想的设备 然后按约翰逊 Johnson 规则进行排序 2020 3 23 武汉理工大学管理学院袁付礼 19 约翰逊 Johnson 规则的扩展方法 例 4项作业在三台设备上进行加工 其加工顺序相同 作业时间如下表所示 2020 3 23 武汉理工大学管理学院袁付礼 20 续 2 T 7 6 12 6 9 6 46 作业题 排序并计算加工周期 2020 3 23 武汉理工大学管理学院袁付礼 21 六 M台机器上N项作业的排序 简称为N M排序 一般解法 分枝定界法启发式算法 称为CDS算法 该算法是将N 3的约贝扩展方法进一步扩展到一般的N M问题 以求得一个近似的最优解 也叫坎贝尔 杜达克 史密斯法 关键零件法最小排序系数 2020 3 23 武汉理工大学管理学院袁付礼 22 CDS算法的步骤 第一步 根据第1台与第M台 即最后一台 机器的两组操作时间 应用约贝规则排出第1个作业顺序方案 第二步 根据第1台与第2台机器的操作时间合并 以及第 M 1 与第M台机器的操作时间合并 得到两组操作时间 应用约贝规则排出第2个作业顺序方案 第三步 根据第1 第2 第3台 三台机器的操作时间合并 以及第 M 2 第 M 1 第M台三台机器的操作时间合并 又得到两组操作时间 应用约贝规则 排出第3个作业顺序方案 2020 3 23 武汉理工大学管理学院袁付礼 23 CDS算法的步骤 续 第四步 重复以上运算 最后将第1 第2 第 M 1 共 M 1 台机器和操作时间合并 以及将第2 第3 第M共