生产调度及智能优化(chen)ppt课件

25 04 2020 生产调度及智能优化 航空自动化学院航空电子系中国民航大学数据分析研究所 jjchen 24092499 O25 04 2020 生产调度 生产调度与运筹学 Q 区别 联系 生产调度 运筹学 25 04 2020 生产调度 什么是生产调度 即按时间分配资源完成任务 作业的过程或方法 要求 任务 作业必须是可分割的 生产调度问题Q 现场有哪些 25 04 2020 生产调度 生产调度与生产计划 都是对生产过程的规划与控制 均考虑优化的目的 主要区别是考虑的时间尺度不同 理论上均称调度问题 生产调度是生产计划的可行性验证过程 生产计划侧重于经营计划和生产能力的平衡 考虑的时间以月或年计的中长期 粗 生产调度则在较短的时间内进行 最主要的任务是生产作业的安排与资源的具体分配 涉及实际生产环境的各种约束 细 25 04 2020 生产调度 生产调度与生产计划 生产计划的制定以企业的利润最大化为目标 而生产调度则以生产过程的平稳过渡 顺畅接续为目标 生产计划的制定 一般是考虑静态情况 当生产因素比较稳定和比较理想时才能达到优化的预期目标 生产过程是动态的 要求生产调度系统有一定的柔性 能适应生产过程中内 外因素的异动 以便准确而灵活地完成生产计划 生产调度侧重于生产装置的分配利用和物料平衡 25 04 2020 生产调度 生产计划优化系统 优化系统可根据企业的产 供 销状况 以企业综合效益为目标 建立合适的数学模型 依一定方法求解 分别考虑企业内外约束 进而获得最优计划 计划的实施 必须充分利用现有资源 优化资源配置 提高生产决策的科学性 实现效益的最大化 25 04 2020 生产调度 生产调度系统的功能 计划的分解 一般采用时间分配方法 即滚动计划 动态监控 实时监控 包括数据的采集 关键参数的历史趋势图分析 图表及工艺流程的显示 平衡协调 包括外部的 生产和经营两大系统 产供销 内部 生产过程 人员工位器具等 25 04 2020 生产调度 生产调度系统的特点 复杂性 随机性 多约束 多目标 Q 维修作业调度系统特点的表达 25 04 2020 生产调度 生产调度问题的一般描述 语义描述 目标 任务集合 资源集合 约束条件 数学描述 调度问题的数学符号表达 生产调度问题的性能指标 能力指标 最大生产率 最短生产周期等 成本指标 最大利润 最小费用等 客户满意度指标 最短交付期 提前拖期惩罚 等 25 04 2020 生产调度 生产调度问题的分类 依模型变量分类 1 连续变量问题 2 离散变量问题 组和优化问题 combinatorialoptimizationproblem COP 依生产过程输出 1 连续生产过程 连续的产品流 2 间隙生产过程 离散批量 批处理过程 批处理调度问题 3 离散生产过程 离散数量 车间调度问题按调度目标 总的作业时间最短 总的延迟时间最小等其他 依人物特点 可否终端 加工时限 顺序约束等 25 04 2020 生产调度问题的分类 车间调度问题 车间调度 加工设备的分配 工件的加工时间与加工顺序 实质 生产调度 25 04 2020 生产调度问题的分类 流水车间调度问题 分类 基于加工时间或交付期 确定型 随机型和模糊型 满意型 生产调度 25 04 2020 NP难题工程近似可用解 生产调度 生产调度问题的分类 作业车间调度问题 JSP问题可以采用整数线性规划模型描述 前提假设 所有的任务在零时刻都可用 且无设备故障 任务在机器上执行时间事先已知 25 04 2020 生产调度 生产调度问题的分类 间隙生产调度问题 分类 多产品 multi product 间隙生产过程 所有产品生产顺序相同 加工路径相同 整个生产过程分成若干个生产阶段 每个阶段包含若干并行设备 类似Flow shop 和多用途或多目的 multi purpose 间隙生产过程 可以是不同的生产线 不同的路径 不同的工序 可通过设备的组织来调整 类似Job shop 排序的问题 中间产品存储策略 等待时间切换时间 上层组织路经与时间分配下层设备与资源分配决策 25 04 2020 生产调度 生产调度问题的分类 动态调度问题 静态调度 调度环境和任务已知的前提下的所谓的事前调度方法 例行维修作业 动态调度 也称再调度 指在调度环境和任务存在不可预见的扰动情况下的调度方案 即依赖于事前调度环境和任务也与当前状态有关 例行 非例行维修作业 为适应生产过程的不确定性和随机性 一般采用周期性调度和再调度相结合的策略 25 04 2020 生产调度 生产调度问题的分类 动态调度问题 续 动态调度形式 滚动调度 rollingscheduling 和被动调度 reactivescheduling 被动调度目标是尽可能维持原静态调度水平 既保持原有的性能指标 滚动调度 移动时间段内的生产调度 被动调度 随生产过程变化而不可行的调度的修正 动态调度的实时性要求 Q 变化 加工时间 任务 设备故障等 调机作业 25 04 2020 生产调度 生产调度方法 分类 优化调度方法和启发式调度方法 优化调度 精确求解解析模型而获得最优解 近似求解得次优解 基础 数学规划 适用 小规模优化问题 启发式调度 包括基于规则的方法 基于人工智能的方法 随机搜索方法 基于仿真的方法等 立足当前 追求局部最优而非全局最优 方向 二者结合 启发推理 25 04 2020 生产调度 生产调度方法 续 Model basedandmodel free 25 04 2020 生产调度的启发式算法 启发式算法 heuristicsalgorithm 语义性描述 一个基于直观或者经验构造的算法 在可接受的代价下 给出待解决组合优化问题的一个可行解 未定义可行解与最优解的距离 25 04 2020 生产调度的启发式算法 启发式算法 heuristicsalgorithm Johnson问题 以最大流程时间为目标的两台机器流水车间调度问题 依Johnson规则确定其最优调度 问题描述 n个工件在机器1和机器2上的加工时间分别为ti1和ti2 目标是给出最短生产周期的产品序列 25 04 2020 生产调度的启发式算法 启发式算法 heuristicsalgorithm 基于Johnson规则构造最优调度 步骤如下 25 04 2020 生产调度的启发式算法 启发式算法 heuristicsalgorithm 例 问题的关键是启发式规则的建立 启发式算法通常是以牺牲计算时间为代价 25 04 2020 生产调度的启发式算法 启发式算法 heuristicsalgorithm 常用启发式规则 用优先分配规则来解决工序中可能的加工冲突 要求算法有识别所有加工冲突的能力 基于随机分配规则的启发式算法 每一工序都对应启发式规则集 族中的任意规则 规则可重用 全部工序遍历一遍后即可找到生产活动调度 工序顺序集 25 04 2020 遗传算法 遗传算法 借鉴生物界自然选择和自然遗传机制的随机算法 原理 始于多个初始解 然后通过一定规则进行逐步迭代产生新的解 合成解集 通过对解集中解的性质的判断 筛出需要的解 25 04 2020 遗传算法 遗传算法 借鉴生物界自然选择和自然遗传机制的随机算法 算法设计的内容 编码 解空间适应度函数 解的质量的度量 目标函数选择策略 大适值解对应大存活概率 机会控制参数 种群规模 算法代数 终止准则 遗传操作概率等遗传算子 选择 遗传 交叉 变异 缺点 没有利用目标函数梯度等信息 造成了解的无方向性 25 04 2020 基于遗传算法的车间调度问题 遗传算法 把调度问题参数表达成按一定结构组成的染色体编码 部分算法设计内容 编码 工件加工顺序适应度函数 完成加工作业可能的最大流程时间的倒数 流程时间越短越好 选择策略 大适值解对应大存活概率 机会控制参数 种群规模 算法代数 终止准则 遗传操作概率等遗传算子 选择 遗传 交叉 变异 25 04 2020 基于遗传算法的模糊车间调度方法 主要解决提前 拖期费用调度问题 利用模糊量表示客户对交货期的满意程度 Q 航班延误问题A1 可用随机规则调度法A2 也可用模糊调度法 25 04 2020 基于同一时间离散化生产调度 把调度范围分成许许多多等长度的时间段 民航维修作业标准工时下的派工问题 然后明确约束条件 分配约束 容量约束 物料平衡 公共及人力资源限制 最终可表达为以利润最大为目标函数的调度问题 一个经典的调度问题 25 04 2020 不确定性生产调度问题 生产