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

1、生严调度及智育皂优化陈静杰博士教授航空自动化学院航空电子系中国 民航大学数据分析研究所jjchen24092499 (O) /产调度A什么是生产调度？即按时间分配资源完成任务/作业的过程或方法。要求：任务/作业必须是可分割的。2013-5-2生产调度A生产调度与生产计划都是对生产过程的规划与控制（均考虑优化 的目的），主要区别是考虑的时间尺度不同, 理论上均称调度问题；生产调度是生产计划 的可行性验证过程生产计划侧重于经营计划和生产能力的平衡，考虑的 时间以月或年计的中长期粗生产调度则在较短的时间内进行，最主要的任务是生 产作业的安排与资源的具体分配，涉及实际生产环境

2、 的各种约束细A生产调度与生产计划生产计划的制定以企业的利润最大化为目标, 而生产调度则以生产过程的平稳过渡/顺畅接 续为目标。生产计划的制定，一般是考虑静态情况。当生产因素 比较稳定和比较理想时才能达到优化的预期目标生产过程是动态的，要求生产调度系统有一定的柔性， 能适应生产过程中内、外因素的异动，以便准确而灵 活地完成生产计划；生产调度侧重于生产装置的分配 利用和物料平衡。A生产计划优化系统优化系统可才艮据企业的产、供、销状况， 以企业综合效益为目标，建立合适的数学 模型，依一定方法求解，分别考虑企业内 外约束，进而获得最优计划；计划的实施, 必须充分利用现有资源，优化资源配置， 提高生产

3、决策的科学性，实现效益的最大 化。2013-5-2生产调度A生产调度系统的功能计划的分解：一般采用时间分配方法，即 滚动计划；动态监控：实时监控，包括数据的采集、 关键参数的历史趋势图分析、图表及工艺 流程的显示。平衡协调，包括外部的一 生产和经营两大系统一产供销,内部一生 产过程一人员工位器具等2013-5-2生产调度A生产调度系统的特点 复杂性； 随机性；/多约束； 多目标。V2013-5-2生产调度生产调度问题的一般描述语义描述：目标-任务集合-资源集合-约束 条件；数学描述一调度问题的数学符号表达。A生产调度问题的性能指标1. 能力指标：最大生产率、最短生产周期等；2. 成本指标：最大

4、利润、最小费用等；3. 客户满意度指标：最短交付期（提前拖期惩罚）等A生产调度问题的分类1. 依模型变量分类：1）连续变量问题；2）离散变量问题/ 组和优化问题 （combinatorial optimization problem: COP）2. 依生产过程输出：1 ）连续生产过程（连续的产品流）； 2）间隙生产过程（离散批量）/批处理过程一批处理调 度问题；3）离散生产过程（离散数量）一车间调度问题3. 按调度目标：总的作业时间最短、总的延迟时间最小等其他：依人物特点：可否终端、加工时限、顺序约束等2013-5-2生产调度A生产调度问题的分类1.车间调度问题：个工件在 加台机器上加工需P道

5、工序，每一台机器在任一时刻只能加工某个工件的某道工序，同时需考虑工序的先后顺序约束M3生产调度A生产调度问题的分类2.流水车间调度问题:简记:n/m/F/cmax个工件在 加台机器上加工需 k道工序，每一台机器 在任一时刻只能加工某个工件的某道工序， n个工件在m台机器上加工顺序相同,工件i在机器j上的加工时间tjj （i = 1, 2，；丿=1, 2 ,，加）是给定的，目标 是求工件的最优加工顺序，使最大流程时间最 小分类（基于加工时间或交付期）：确定型、随机型和模糊型/满意型2013-5-2生产调度3. 作业车间调度问题:n个工件在 m台机器上加工需 在人一时刻只能加工某 考虑工序的先后顺

6、序约 度的调度，即对作业进A生产调度问题的分类(job - shop scheduling problem : JSP )NP难题工程近似可用解k道工序，每一台机器 个工件的某道工序，同时需束，目标是找到最小时间长 行有效的排序。JSP问题可以采用整数线性规划模型描述。前 提假设：所有的任务在零时刻都可用，且无 设备故障，任务在机器上执行时间事先已知A生产调度问题的分类4.间隙生产调度问题：等待时间 中间产品切换时间 存储策略分类：多产品(multiproduct)间隙生产过程所有 产品生产顺序相同，加工路径相同，整个生产过程分 成若干个生产阶段，每个阶段包含若干并行设备。类 似Flow-sh

7、op和多用途或多目的(multi-purpose) 间隙生产过程可以是不同的生产线.不同的路径.不上层组织路经与时间分配 下层设备与资源分配决策问题排序的L同的工序，可蠢过设备的组织乗调整。类似Job-shopA生产调度问题的分类5.动态调度问题：鼬例行维修作业动态调度：也称再调度，指在调度环境和 任务存在不可预见的扰动情况下的调度方 案，即依赖于事前调度环境和任务也与当 祈状态有关一为适应生产过程的不确定性和随机性，一 般采用周期性调度和再调度相结合的策略2013-5-2生产调度A生产调度问题的分类5.动态调度问题(续)：动态调度的r 实时性要求丄动态调度形式：滚动调度(rolling sc

8、heduling)和 被动调度(reactive scheduling )滚动调度：移动时间段内的生产调度； 被动调度：随生产过程变化而不可行的调度的修正Q:变化(加工时间、 任务、设备故障 等)一调机作业被动调度目标是尽可能 维持原静态调度水平， 既保持原有的性能指标2013-5-2生产调度生产调度A生产调度方法方向：二者结合2013-5-2生产调度2013-5-2生产调度分类：优化调度方法和启发式调度方法优化调度：精确求解解析模型而获得最优解、近似求解 得次优解；基础：数学规划；适用：小规模优化问题启发推理启发式调度：包括基于规则的方法、基于人工智能的方 法、随机搜索方法、基于仿真的方法等

9、，立足当前，追 求局部最优而非全局最优2013-5-2生产调度A生产调度方法（续）2013-5-2生产调度2013-5-2生产调度等式与 不数学规划ANNS GA Fuzzy f基于人工 看能方法三分支定界法简单规则 复合规则 启发式规则依靠机器学习的 -乡态选择规则利用神经网络实 现智能选择规则° 一2013-5-2生产调度的启发式算法启发式算法(heuristics algorithm)语义性描述：一个基于直观或者经验构造的算法，在可接受的代价下，给出待解决组合优化问题的一个可未定义可行解与最优解的距离生产调度的启发式算法A启发式算法(heuristics algorithm)J

10、ohnson问题：以最大流程时间为目标的两台机器流 阿题描述：门个工件在机器1和机器2上的加工时间分 协为如和目标是给出最短生产周期的产品序列卜二 1. 2 .门 IJohnson 规则：min f订，ti2 < min tj2 , t门,则工件 2在 丿前生产调度的启发式算法A启发式算法(heuristics algorithm)将 N个工件分成 戶和0两组，分组的原则是: 组的工件在机器2上比在机器1上加工时间长余的工件归 Q组；户组工件按机器1加工时间递増顺序排列、0组工件按机器2加工时 间地间顺序排列0组工件顺序连接在一起 便构成生产周期最短的最优工件顺序2013-5-22013

11、-生产调度的启发式算法启发式算法(heuristics algorithm)例:工件15机器1上加工时间机器2上加工时间123105114799 A s 人】1 r) JH a i、0 1“F 序)：P = 4,2,5,6、2 = 3,1 r>启发式算法 通常是以牺 牲计算时间 为代价期疋37'优加工顺序是4,2,5,6,3,1,最短生产2013-生产调度的启发式算法启发式算法(heuristics algorithm)常用启发式规则：1 用优先分配规则来解决工序中可能的加工冲突（要求算法有识别所有加工冲突的能力）2基于随机分配规则的启发式算法：每一工序都対应启发式规则集/族申的

12、任意规则,规则可重用，全部工序遍历一遍后即可找到生产 活动调度一工序顺序集遗传算法A遗传算法：借鉴生物界自然选择和自然遗 传机制的随机算法原理：始于多个初始解，然后通过一定规则 进行逐步迭代产生新的解，合成解集，通过 对解集中解的性质的判断，筛出需要的解A遗传算法：借鉴生物界自然远勺 传机制的随机算法、丄Y A遗传算法算法设计的内容：编码 解空间M彎 “适应度函数一解的质量白庚量/Il标函数选择策略一大适值解对应大存活概率/机会 控制参数一种群规模、算法代数/终止准则、遗传操作概率等遗传算子一选择/遗传、交叉、变异基于遗传算法的车间调度问题A遗传算法：把调度问题参数表达成按一定 结构组成的染色

13、体编码部分算法设计内容：编码一工件加工顺序适应度函数一完成加工作业可能的最大流程 时间的倒数（流程时间越短越好）选择策略一大适值解对应大存活概率/机会控制参数一种群规模、算法代数/终止准则、 遗传操作概率等遗传算子一选择/遗传、交叉、变异基于遗传算法的模糊车间调度方法主要解决提前/拖期费用调度问题一利用模 糊量表示客户对交货期的满意程度2013-5-22013-5-22013-5-2基于同一时间离散化生产调度A把调度范围分成许许多多等长度的时间 段一民航维修作业标准工时下的派工问题，然后明确约束条件（分配约束、容量约束、物料平衡、公共及人力资源限 制）,最终可表达为以利润最大为目标2013-5-2函数的调度问题2013-5-2不确定性生产调