生产调度及智能优化讲义总结30

生产调度及及智能优化化陈静杰博士

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