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

1、生产调度及智能优化 陈静杰博士教授航空自动化学院航空电子系中国民航大学数据分析研究所24092499（O）/136520379392022-8-15生产调度生产调度与运筹学2022-8-15生产调度什么是生产调度？即按时间分配资源完成任务/作业的过程或方法。要求：任务/作业必须是可分割的。生产调度问题生产调度问题Q：现场有哪些？：现场有哪些？2022-8-15生产调度生产调度与生产计划都是对生产过程的规划与控制（均考虑优化的目的），主要区别是考虑的时间尺度不同，理论上均称调度问题；生产调度是生产计划的可行性验证过程生产计划侧重于经营计划和生产能力的平衡，考虑的时间以月或年计的中长期粗生产调度则

2、在较短的时间内进行，最主要的任务是生产作业的安排与资源的具体分配，涉及实际生产环境的各种约束细2022-8-15生产调度生产调度与生产计划生产计划的制定以企业的利润最大化为目标，而生产调度则以生产过程的平稳过渡/顺畅接续为目标。生产计划的制定，一般是考虑静态情况。当生产因素比较稳定和比较理想时才能达到优化的预期目标生产过程是动态的，要求生产调度系统有一定的柔性，能适应生产过程中内、外因素的异动，以便准确而灵活地完成生产计划；生产调度侧重于生产装置的分配利用和物料平衡。2022-8-15生产调度生产计划优化系统优化系统可根据企业的产、供、销状况，以企业综合效益为目标，建立合适的数学模型，依一定方

3、法求解，分别考虑企业内外约束，进而获得最优计划；计划的实施，必须充分利用现有资源，优化资源配置，提高生产决策的科学性，实现效益的最大化。2022-8-15生产调度生产调度系统的功能计划的分解：一般采用时间分配方法，即滚动计划；动态监控：实时监控，包括数据的采集、关键参数的历史趋势图分析、图表及工艺流程的显示。平衡协调，包括外部的生产和经营两大系统产供销，内部生产过程人员工位器具等2022-8-15生产调度生产调度系统的特点复杂性；随机性；多约束；多目标。Q:维修作业调维修作业调度度系统特点的表达系统特点的表达?2022-8-15生产调度生产调度问题的一般描述语义描述：目标-任务集合-资源集合-

4、约束条件；数学描述数学描述调度问题的数学符号表达调度问题的数学符号表达。生产调度问题的性能指标1.能力指标：最大生产率、最短生产周期等；2.成本指标：最大利润、最小费用等；3.客户满意度指标：最短交付期（提前拖期惩罚）等2022-8-15生产调度生产调度问题的分类1.依模型变量分类：1）连续变量问题；2）离散变量问题/组和优化问题（combinatorial optimization problem:COP）2.依生产过程输出：1）连续生产过程（连续的产品流）；2）间隙生产过程（离散批量）/批处理过程批处理调度问题；3）离散生产过程（离散数量）车间调度问题3.按调度目标：总的作业时间最短、总的

5、延迟时间最小等4.其他：依人物特点：可否终端、加工时限、顺序约束等2022-8-15生产调度问题的分类1.车间调度问题：束考虑工序的先后顺序约时需个工件的某道工序，同在任一时刻只能加工某道工序，每一台机器台机器上加工需个工件在kmn车间调度加工设备的分配工件的加工时间与加工顺序实质生产调度2022-8-15生产调度问题的分类小序，使最大流程时间最是求工件的最优加工顺是给定的，目标工时间上的加在机器，工件台机器上加工顺序相同在个工件个工件的某道工序，在任一时刻只能加工某道工序，每一台机器台机器上加工需个工件在mjnitjimnkmnij,2,1;,2,12.流水车间调度问题：max/cFmn 简

6、记：分类（基于加工时间或交付期）：确定型、随机型和模糊型分类（基于加工时间或交付期）：确定型、随机型和模糊型/满意型满意型生产调度2022-8-15NP难题工程近似可用解生产调度生产调度问题的分类3.作业车间调度问题：行有效的排序。度的调度，即对作业进目标是找到最小时间长束考虑工序的先后顺序约时需个工件的某道工序，同在人一时刻只能加工某道工序，每一台机器台机器上加工需个工件在，kmnJSP问题可以采用整数线性规划模型描述。前问题可以采用整数线性规划模型描述。前提假设：所有的任务在零时刻都可用，且无提假设：所有的任务在零时刻都可用，且无设备故障，任务在机器上执行时间事先已知设备故障，任务在机器上

7、执行时间事先已知JSPproblemschedulingshopjob:2022-8-15生产调度生产调度问题的分类4.间隙生产调度问题：分类：多产品（分类：多产品（multi-product）间隙生产过程）间隙生产过程所有所有产品生产顺序相同，加工路径相同，整个生产过程分产品生产顺序相同，加工路径相同，整个生产过程分成若干个生产阶段，每个阶段包含若干并行设备。类成若干个生产阶段，每个阶段包含若干并行设备。类似似Flow-shop和多用途或多目的（和多用途或多目的（multi-purpose）间隙生产过程间隙生产过程可以是不同的生产线、不同的路径、不可以是不同的生产线、不同的路径、不同的工序，

8、可通过设备的组织来调整。类似同的工序，可通过设备的组织来调整。类似Job-shop排序的排序的问题问题中间产品中间产品存储策略存储策略等待时间等待时间切换时间切换时间上层组织路经与时间分配上层组织路经与时间分配下层设备与资源分配决策下层设备与资源分配决策2022-8-15生产调度生产调度问题的分类5.动态调度问题：静态调度：调度环境和任务已知的前提下的所谓的事前调度方法例行维修作业例行维修作业动态调度：也称再调度，指在调度环境和任务存在不可预见的扰动情况下的调度方案，即依赖于事前调度环境和任务也与当前状态有关例行例行+非例行维修作业非例行维修作业为适应生产过程的不确定性和随机性，一为适应生产过

9、程的不确定性和随机性，一般采用周期性调度和再调度相结合的策略般采用周期性调度和再调度相结合的策略2022-8-15生产调度生产调度问题的分类5.动态调度问题（续）：动态调度形式：滚动调度（rolling scheduling）和被动调度（reactive scheduling）被动调度目标是尽可能被动调度目标是尽可能维持原静态调度水平，维持原静态调度水平，既保持原有的性能指标既保持原有的性能指标滚动调度：移动时间段内的生产调度；滚动调度：移动时间段内的生产调度；被动调度：随生产过程变化而不可行的调度的修正被动调度：随生产过程变化而不可行的调度的修正动态调度的动态调度的实时性要求实时性要求Q：变

10、化（加工时间、：变化（加工时间、任务、设备故障任务、设备故障等）等）调机作业调机作业2022-8-15生产调度生产调度方法分类：优化调度方法和启发式调度方法优化调度：精确求解解析模型而获得最优解、近似求解得次优解；基础：数学规划；适用：小规模优化问题启发式调度：包括基于规则的方法、基于人工智能的方法、随机搜索方法、基于仿真的方法等，立足当前，追求局部最优而非全局最优方向：二者结合方向：二者结合启发推理启发推理2022-8-15生产调度生产调度方法（续）数学规划数学规划等式与等式与不不等式约等式约束束分支定界法分支定界法Lagrangian松弛法松弛法贝叶斯启发方法贝叶斯启发方法规则调规则调度方

11、法度方法简单规则简单规则复合规则复合规则启发式规则启发式规则动态调度动态调度依靠机器学习的依靠机器学习的动态选择规则动态选择规则利用神经网络实利用神经网络实现智能选择规则现智能选择规则基于人工基于人工智能方法智能方法启发式启发式搜索规则搜索规则基于规则与基于规则与知识的方法知识的方法智能求智能求解方法解方法ANNsGAFuzzy SetsModel-based and model-free2022-8-15生产调度的启发式算法启发式算法（heuristics algorithm）语义性描述：一个基于直观或者经验构造的算法，在语义性描述：一个基于直观或者经验构造的算法，在可接受的代价下，给出待解

12、决组合优化问题的一个可可接受的代价下，给出待解决组合优化问题的一个可行解行解未定义可行解与未定义可行解与最优解的距离最优解的距离2022-8-15生产调度的启发式算法启发式算法（heuristics algorithm）Johnson问题：以最大流程时间为目标的两台机器流问题：以最大流程时间为目标的两台机器流水车间调度问题水车间调度问题依依Johnson规则确定其最优调度规则确定其最优调度问题描述：问题描述：n 个工件在机器个工件在机器1和机器和机器2上的加工时间分上的加工时间分别为别为ti1和和ti2，目标是给出最短生产周期的产品序列，目标是给出最短生产周期的产品序列ni,2,1前在，则工件

13、规则：jittttiiii1221,min,minJohnson2121,iiiitttt2022-8-15生产调度的启发式算法启发式算法（heuristics algorithm）基于基于Johnson规则构造最优调度，步骤如下：规则构造最优调度，步骤如下：组；余的工件归，其在机器1上加工时间长组的工件在机器2上比两组，分组的原则是：和个工件分成步骤1：将QPQPN间地间顺序排列组工件按机器2加工时间递增顺序排列，组工件按机器1加工时步骤2：QP最优工件顺序便构成生产周期最短的，组工件顺序连接在一起组工件顺序和步骤3：将QP2022-8-15生产调度的启发式算法启发式算法（heuristic

14、s algorithm）例：例：3,16,5,4,2QP 步骤1：、1,36,5,2,4:QP、排序-步骤2周期是37最短生产是步骤3：最优加工顺序，136524工件123456机器1上加工时间10511379机器2上加工时间47981015问题的关键问题的关键是启发式规是启发式规则的建立则的建立启发式算法启发式算法通常是以牺通常是以牺牲计算时间牲计算时间为代价为代价2022-8-15生产调度的启发式算法启发式算法（heuristics algorithm）常用启发式规则：常用启发式规则：1.用优先分配规则来解决工序中可能的加工冲用优先分配规则来解决工序中可能的加工冲突（要求算法有识别所有加工

15、冲突的能力）突（要求算法有识别所有加工冲突的能力）2.基于随机分配规则的启发式算法：每一工序基于随机分配规则的启发式算法：每一工序都对应启发式规则集都对应启发式规则集/族中的任意规则，规则族中的任意规则，规则可重用，全部工序遍历一遍后即可找到生产可重用，全部工序遍历一遍后即可找到生产活动调度活动调度工序顺序集工序顺序集2022-8-15遗传算法遗传算法：借鉴生物界自然选择和自然遗传机制的随机算法p原理：始于多个初始解，然后通过一定规则原理：始于多个初始解，然后通过一定规则进行逐步迭代产生新的解，合成解集，通过进行逐步迭代产生新的解，合成解集，通过对解集中解的性质的判断，筛出需要的解对解集中解的

16、性质的判断，筛出需要的解2022-8-15遗传算法遗传算法：借鉴生物界自然选择和自然遗传机制的随机算法p算法设计的内容：算法设计的内容：l 编码解空间l 适应度函数解的质量的度量/目标函数l 选择策略大适值解对应大存活概率/机会l 控制参数种群规模、算法代数/终止准则、遗传操作概率等l 遗传算子选择/遗传、交叉、变异缺点：没有利缺点：没有利用目标函数梯用目标函数梯度等信息，造度等信息，造成了解的无方成了解的无方向性向性2022-8-15基于遗传算法的车间调度问题遗传算法：把调度问题参数表达成按一定结构组成的染色体编码p部分算法设计内容：部分算法设计内容：l 编码工件加工顺序l 适应度函数完成加

17、工作业可能的最大流程时间的倒数（流程时间越短越好）l 选择策略大适值解对应大存活概率/机会l 控制参数种群规模、算法代数/终止准则、遗传操作概率等l 遗传算子选择/遗传、交叉、变异2022-8-15基于遗传算法的模糊车间调度方法主要解决提前/拖期费用调度问题利用模糊量表示客户对交货期的满意程度Q：航班延误问题：航班延误问题A1：可用随机规则调度法：可用随机规则调度法A2：也可用模糊调度法：也可用模糊调度法2022-8-15基于同一时间离散化生产调度把调度范围分成许许多多等长度的时间段民航维修作业标准工时下的派工问题，然后明确约束条件（分配约束、容量约束、物料平衡、公共及人力资源限制），最终可表达为以利润最大为目标函数的调度问题一个经典一个经典的调度问的调度问题题2022-8-15不确定性生产调度问题生产系统的不确定性：1）加工期的不确定性，如：备件与故障件的不匹配；2）存储容量的不确定性，如：最优库存容量问题即存储容量的上下限的确定；3）人的行为的不确定性不确定因素的处理方法：1）用精确数来表示不确定性，比如各类各级工程技术人员的标准人工时测度；2）随机概率分布函数表达，如机务工程作业中可靠性/度的表达；3）模糊理论方法模糊冗余处理+学习过程2022-8-15谢谢！