生产调度及智能优化chen

生产调度及智能优化

陈静杰博士

教授航空自动化学院航空电子系

中国民航大学数据分析研究所jjchen@

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