现代制造系统_周凯编__清华大学出版社_第八章_制造系统的调度控制

第九章制造系统的调度控制 概述流水排序调度方法非流水排序调度方法基于规则的调度方法基于仿真的调度方法 第一节概述 调度控制的根本任务实施战术层下达的生产作业计划 控制工件的投放和在系统中的流动以及资源的使用 如 某机床某时刻开始对某零件的某道工序进行加工 等 调度控制系统的基本结构 第一节概述 工作过程 调度控制器根据输入信息R 包括来自上级的生产作业计划 设计要求和工艺规程 和反馈信息X 即生产现场的实际状态 进行实时决策 产生控制信息U 即调度控制指令 制造过程在调度控制指令的控制下运行 克服外界扰动D的影响 生产出满足输入信息要求的产品C 闭环自动控制系统 静态调度动态调度动态调度是指调度控制系统能对外部输入信息 制造过程状态和系统环境的动态变化作出实时响应的调度控制系统 第一节概述 调度控制系统的分类 调度控制问题中的难点 信息处理的实时性要求被控对象的建模调度控制器的设计外界扰动对系统的影响 第一节概述 解决调度控制问题的方法 静态调度方法和动态调度方法两类 具体方法 基于排序理论的调度方法基于规则的调度方法基于离散事件系统仿真的调度方法基于人工智能的调度方法 第一节概述 第二节流水排序调度方法 应用场合 用于具有相同工艺路线的一批工件的加工情况 流水排序问题描述 设有n个工件和m台设备 每个工件均需按相同的顺序通过这m台设备进行加工 要求以某种性能指标最优 如制造总工期最短等 为目标 求出n个工件进入系统的顺序 第二节流水排序调度方法 属静态调度方法流水排序调度的实施过程 先通过作业排序得到调度表 然后按调度表控制生产过程的运行 如果生产过程中出现异常情况 如设备负荷不均匀 工件加工出现堵塞现象等 则重新排序 再按新排出的调度表继续控制生产过程的运行 排序算法 单机排序算法两机排序算法三机排序算法m机排序算法 第二节流水排序调度方法 1 n作业单机排序 问题描述 n个工件和1台设备 要求以某种性能指标最优为目标 求出这n个工件的加工顺序或者说进入系统的顺序 性能指标 对于n作业单机排序 为实现最优作业排序 以作业平均通过时间 meanflowtime MFT 最短作为性能指标 计算公式如下 式中 i作业的完工时间 i作业的等待和加工时间 1 n作业单机排序 基本原理 排序方法 按最短加工时间 SPT 优先原则排序可使MFT最短 即具有最短加工时间的作业优先加工 处理 推论 MFT最小可保证作业平均延误时间 meanlateness ML 最小 1 n作业单机排序 问题描述 n个工件和2台设备M1 M2 每个工件均需按相同的顺序先在M1上加工 再在M2进行加工 要求以某种性能指标最优为目标 求出n个工件进入系统的顺序 2 n作业两机排序 性能指标 以制造总工期L最短作为最优目标 基本原理 调度方法 规则1 在M1上加工时间最短者应最先加工 规则2 在M2上加工时间最短者应最后加工 2 n作业两机排序 实施步骤 排序算法 1 列出各项作业在M1 M2上的加工时间 2 扫视全部加工时间 找出最小加工时间 3 如果最小加工时间发生在M1 则该作业最先加工 如果最小加工时间发生在M2 则该作业最后加工 4 消去已排序作业 重复 2 3 两步 直到全部排序完成 5 如果发生在M1 M2上加工时间相等的情况 则可任意排在最先或最后 而不影响总工期 2 n作业两机排序 2 n作业两机排序 应用举例 某车间有6项作业 均需先在M1上加工 后在M2上加工 加工时间数据见表 试找出最优排序使完成全部任务的总工期最短 最优排序 J3 J1 J2 J6 J5 J4 J3 J1 J6 J5 J4 J2 问题描述 n个工件和3台设备M1 M2 M3 每个工件均需按相同的顺序先在M1上加工 再在M2进行加工 再在M3进行加工 要求以某种性能指标最优为目标 求出n个工件进入系统的顺序 3 n作业三机排序 3 n作业三机排序 性能指标 以制造总工期L最短作为最优目标 基本原理 调度方法 分支定界法 用树形结构描述问题的求解过程 每一节点表示一种待定的排序 计算当前全部节点的制造工期下限值 然后从下限值最低的节点继续分枝 直至找到最优排序 工期下限计算方法 从三台设备无空闲着手分析所以三机流水生产情况下 节点P上制造工期下限为 3 n作业三机流水排序 求解步骤 从根节点开始求各节点的工期下限值先求已排序作业集合通过的总时间 通过的总时间 通过的总时间求最小工期下限求每层各节点的工期下限值比较同一层各节点的工期下限值 以LB最小节点为根继续分枝 画分枝图 3 n作业三机流水排序 第三节非流水排序调度方法 应用场合 适用于具有相似工艺路线的n个工件的加工情况非流水排序问题描述 给定n个工件 每个工件以不同的顺序和时间通过m台设备进行加工 要求以某种性能指标最优为目标 求出这些工件在m台机床上的最优加工顺序 第三节非流水排序调度方法 属于静态调度方法实施过程 先通过作业排序得到调度表 然后按调度表控制生产过程的运行 如果运行过程出现异常情况 则需重新排序 再按新排出的调度表继续控制生产过程运行 性能指标 完成两作业的总工期L最短 基本原理 图解法 两作业合成轨迹总长度最短 两作业m机非流水排序 图解法 问题描述 2个工件 每个工件以不同的顺序和时间通过m台设备进行加工 要求以某种性能指标最优为目标 求出这些工件在m台机床上的最优加工顺序 求解步骤 画直角坐标系 其横轴表示作业1的加工工序和时间 纵轴表示作业2的加工工序和时间 将两作业需占用同一机器的时间用方框标出 表示不可行区 用水平线 垂直线和45度线3种线段表示两作业推进过程的合成轨迹 水平线表示作业1加工 作业2等待 垂直线表示作业2加工 作业1等待 45度线表示两作业同时加工 为使制造总工期最短 应使45度线段占的比例最大 通过本步应找出所有可能的合成轨迹 以轨迹总长度最短为目标 通过直观对比和计算 从第 步确定的候选合成轨迹中找出最优合成轨迹 求解最优合成轨迹上的时间转折点 得到调度表 两作业m机非流水排序 图解法 随着作业数量和机器数量的增加 排序计算量大 在实际应用中无法对较大规模的排序问题求得最优解 存在的问题 两作业m机非流水排序 图解法 第四节基于规则的调度方法 调度控制系统的基本结构框图 基本原理 系统运行时 调度控制器根据输入信息和制造过程的反馈信息按一定的调度规则进行决策 对制造过程的运行操作实现控制 调度规则 简单优先规则直接根据系统状态和参数确定下一步操作的调度规则 采用简单优先规则可保证系统某一或某几个性能参数达到一个较好的效果 组合优先规则是根据某些参数 如队列长度等 交替运用两种以上简单优先规则对零件进行处理的复合规则 加权优先规则是通过引入加权系数对简单优先规则和组合优先规则进行综合运用而构成的复合规则 启发式规则利用人工智能的复杂调度规则 先进先出 根据零件到达工作站的先后顺序来执行加工作业 先来的先进行加工 最短加工时间规则 优先选择具有最短加工时间的零件进行处理 是一种经常使用的规则 最早到期日规则 根据订单交货期的先后顺序安排加工 即优先选择具有最早交付期的零件进行处理 最少作业数规则 根据剩余作业数来安排加工顺序 剩余作业数越少的零件越先加工 较少的作业意味着较少的等待时间 下一队列工作量规则 优先选择下一队列工作量最少的零件进行处理 下一队列工作量是指零件下一工序加工处的总工作量 加工零件和排队零件的工作量之和 剩余松弛时间规则 剩余松弛时间越短越先加工 剩余松弛时间是将在交货期前所剩余的时间减去剩余的总加工时间所得的差值 几种典型简单优先规则 规则调度方法的局限性 上述任何一种规则只能使系统在某一方面 或针对某一特定的性能参数取得一个好的效果 所以每一种规则相对其他规则并没有绝对的优势 这种静态的 固定应用某种调度规则的调度方法对于动态变化的系统环境很难适应 规则动态切换调度控制系统 原理 根据制造系统的实际状态 确定适当调度规则集 并设计规则动态选择逻辑和相关的计算决策装置 系统运行时 根据实际状态 动态选择规则集中的规则 通过实时决策实现调度控制 运行过程 动态选择模块根据输入指令和系统状态动态选择规则集中的某一条规则Ri 计算决策模块根据被选中的规则计算每一候选调度方案对应的性能准则值 然后根据准则值的大小做出选择调度方案的决策 并向制造过程发出相应的调度控制指令 第五节基于仿真的调度方法 基本原理 基于仿真的调度方法是一种以仿真作为制造系统控制决策的决策支持系统 辅助调度控制器进行决策优化 实现制造系统优化控制的一种方法 运行过程 当调度控制器接收来自上级的输入信息和来自生产现场的状态反馈信息后 通过初始决策确定若干候选调度方案 然后将各方案送往计算机仿真系统进行仿真 最后由调度控制器对仿真结果进行分析 做出方案选择决策 并据此生成调度控制指令来控制制造过程的运行 基于仿真调度方法的关键问题仿真建模 建立能准确描述实际系统的仿真模型是实现仿真调度方法的前提 目前在调度控制仿真中所用的模型主要是逻辑模型 实验设计 那如何安排实验或进行实验设计 以最少的试验次数从可选方案中选择出最佳的方案是仿真控制方法的一个重要问题 目前常用的实验设计和结过分析方法有回归分析方法 扰动分析方法和正交设计方法等 基于仿真调度方法的关键问题仿真运行 计算机仿真模型及其仿真运行都是通过计算机编程来实现的 目前常用的仿真和编程语言有C语言 专业仿真语言和仿真软件包等 控制决策 控制决策的任务是对仿真结果进行分析从中选出最佳方案 并据此生成调度控制指令控制制造过程的运行 目前一些实际系统中多由人机结合的方式来完成决策任务 第六节智能调度方法 基本原理 基于智能的调度方法是根据制造系统的实际情况 确定适当的调度规则集 系统运行时 根据生产过程的实际状态 通过专家系统动态选择规则几种的规则进