《生产调度及智能优化优秀PPT.ppt》由会员分享,可在线阅读,更多相关《生产调度及智能优化优秀PPT.ppt(30页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、生产调度及智能优化 陈静杰博士教授航空自动化学院航空电子系中国民航高校数据分析探讨所11/4/2022生产调度生产调度与运筹学Q:区分?:区分?联系?联系?生产调度生产调度运筹学运筹学11/4/2022生产调度什么是生产调度?即按时间安排资源完成任务/作业的过程或方法。要求:任务/作业必需是可分割的。生产调度问题生产调度问题Q:现场有哪些?:现场有哪些?11/4/2022生产调度生产调度与生产支配都是对生产过程的规划与限制(均考虑优化的目的),主要区分是考虑的时间尺度不同,理论上均称调度问题;生产调度是生产支配的可行性验证过程生产支配侧重于经营支配和生产实力的平衡,考虑的时间以月或年计的中长期
2、粗生产调度则在较短的时间内进行,最主要的任务是生产作业的支配与资源的具体安排,涉及实际生产环境的各种约束细11/4/2022生产调度生产调度与生产支配生产支配的制定以企业的利润最大化为目标,而生产调度则以生产过程的平稳过渡/顺畅接续为目标。生产支配的制定,一般是考虑静态状况。当生产因素比较稳定和比较志向时才能达到优化的预期目标生产过程是动态的,要求生产调度系统有确定的柔性,能适应生产过程中内、外因素的异动,以便精确而敏捷地完成生产支配;生产调度侧重于生产装置的安排利用和物料平衡。11/4/2022生产调度生产支配优化系统优化系统可依据企业的产、供、销状况,以企业综合效益为目标,建立合适的数学模
3、型,依确定方法求解,分别考虑企业内外约束,进而获得最优支配;支配的实施,必需充分利用现有资源,优化资源配置,提高生产决策的科学性,实现效益的最大化。11/4/2022生产调度生产调度系统的功能支配的分解:一般接受时间安排方法,即滚动支配;动态监控:实时监控,包括数据的采集、关键参数的历史趋势图分析、图表及工艺流程的显示。平衡协调,包括外部的生产和经营两大系统产供销,内部生产过程人员工位器具等11/4/2022生产调度生产调度系统的特点困难性;随机性;多约束;多目标。Q:修理作业调修理作业调度度系统特点的表达系统特点的表达?11/4/2022生产调度生产调度问题的一般描述语义描述:目标-任务集合
4、-资源集合-约束条件;数学描述数学描述调度问题的数学符号表达调度问题的数学符号表达。生产调度问题的性能指标1.实力指标:最大生产率、最短生产周期等;2.成本指标:最大利润、最小费用等;3.客户满足度指标:最短交付期(提前拖期惩处)等11/4/2022生产调度生产调度问题的分类1.依模型变量分类:1)连续变量问题;2)离散变量问题/组和优化问题(combinatorial optimization problem:COP)2.依生产过程输出:1)连续生产过程(连续的产品流);2)间隙生产过程(离散批量)/批处理过程批处理调度问题;3)离散生产过程(离散数量)车间调度问题3.按调度目标:总的作业时
5、间最短、总的延迟时间最小等4.其他:依人物特点:可否终端、加工时限、依次约束等11/4/2022生产调度问题的分类1.车间调度问题:车间调度加工设备的安排工件的加工时间与加工依次实质生产调度11/4/2022生产调度问题的分类2.流水车间调度问题:分类(基于加工时间或交付期):确定型、随机型和模糊型分类(基于加工时间或交付期):确定型、随机型和模糊型/满足型满足型生产调度11/4/2022NP难题工程近似可用解生产调度生产调度问题的分类3.作业车间调度问题:JSP问题可以接受整数线性规划模型描述。前问题可以接受整数线性规划模型描述。前提假设:全部的任务在零时刻都可用,且无设提假设:全部的任务在
6、零时刻都可用,且无设备故障,任务在机器上执行时间事先已知备故障,任务在机器上执行时间事先已知11/4/2022生产调度生产调度问题的分类4.间隙生产调度问题:分类:多产品(分类:多产品(multi-product)间隙生产过程)间隙生产过程全部全部产品生产依次相同,加工路径相同,整个生产过程分产品生产依次相同,加工路径相同,整个生产过程分成若干个生产阶段,每个阶段包含若干并行设备。类成若干个生产阶段,每个阶段包含若干并行设备。类似似Flow-shop和多用途或多目的(和多用途或多目的(multi-purpose)间隙生产过程间隙生产过程可以是不同的生产线、不同的路径、不可以是不同的生产线、不同
7、的路径、不同的工序,可通过设备的组织来调整。类似同的工序,可通过设备的组织来调整。类似Job-shop排序的排序的问题问题中间产品中间产品存储策略存储策略等待时间等待时间切换时间切换时间上层组织路经与时间安排上层组织路经与时间安排下层设备与资源安排决策下层设备与资源安排决策11/4/2022生产调度生产调度问题的分类5.动态调度问题:静态调度:调度环境和任务已知的前提下的所谓的事前调度方法例行修理作业动态调度:也称再调度,指在调度环境和任务存在不行预见的扰动状况下的调度方案,即依靠于事前调度环境和任务也与当前状态有关例行+非例行修理作业为适应生产过程的不确定性和随机性,一为适应生产过程的不确定
8、性和随机性,一般接受周期性调度和再调度相结合的策略般接受周期性调度和再调度相结合的策略11/4/2022生产调度生产调度问题的分类5.动态调度问题(续):动态调度形式:滚动调度(rolling scheduling)和被动调度(reactive scheduling)被动调度目标是尽可能被动调度目标是尽可能维持原静态调度水平,维持原静态调度水平,既保持原有的性能指标既保持原有的性能指标滚动调度:移动时间段内的生产调度;滚动调度:移动时间段内的生产调度;被动调度:随生产过程变更而不行行的调度的修正被动调度:随生产过程变更而不行行的调度的修正动态调度的动态调度的实时性要求实时性要求Q:变更(加工时
9、间、:变更(加工时间、任务、设备故障等)任务、设备故障等)调机作业调机作业11/4/2022生产调度生产调度方法分类:优化调度方法和启发式调度方法优化调度:精确求解解析模型而获得最优解、近似求解得次优解;基础:数学规划;适用:小规模优化问题启发式调度:包括基于规则的方法、基于人工智能的方法、随机搜寻方法、基于仿真的方法等,立足当前,追求局部最优而非全局最优方向:二者结合方向:二者结合启发推理启发推理11/4/2022生产调度生产调度方法(续)数学规划数学规划等式与等式与不不等式约等式约束束分支定界法分支定界法Lagrangian松弛法松弛法贝叶斯启发方法贝叶斯启发方法规则调规则调度方法度方法简
10、单规则简单规则复合规则复合规则启发式规则启发式规则动态调度动态调度依靠机器学习的依靠机器学习的动态选择规则动态选择规则利用神经网络实利用神经网络实现智能选择规则现智能选择规则基于人工基于人工智能方法智能方法启发式启发式搜索规则搜索规则基于规则与基于规则与知识的方法知识的方法智能求智能求解方法解方法ANNsGAFuzzy SetsModel-based and model-free11/4/2022生产调度的启发式算法启发式算法(heuristics algorithm)语义性描述:一个基于直观或者阅历构造的算法,在可语义性描述:一个基于直观或者阅历构造的算法,在可接受的代价下,给出待解决组合优
11、化问题的一个可行解接受的代价下,给出待解决组合优化问题的一个可行解未定义可行解与未定义可行解与最优解的距离最优解的距离11/4/2022生产调度的启发式算法启发式算法(heuristics algorithm)Johnson问题:以最大流程时间为目标的两台机器流问题:以最大流程时间为目标的两台机器流水车间调度问题水车间调度问题依依Johnson规则确定其最优调度规则确定其最优调度问题描述:问题描述:n 个工件在机器个工件在机器1和机器和机器2上的加工时间分别上的加工时间分别为为ti1和和ti2,目标是给出最短生产周期的产品序列,目标是给出最短生产周期的产品序列11/4/2022生产调度的启发式
12、算法启发式算法(heuristics algorithm)基于基于Johnson规则构造最优调度,步骤如下:规则构造最优调度,步骤如下:11/4/2022生产调度的启发式算法启发式算法(heuristics algorithm)例:例:工件123456机器1上加工时间10511379机器2上加工时间47981015问题的关键问题的关键是启发式规是启发式规则的建立则的建立启发式算法启发式算法通常是以牺通常是以牺牲计算时间牲计算时间为代价为代价11/4/2022生产调度的启发式算法启发式算法(heuristics algorithm)常用启发式规则:常用启发式规则:用优先安排规则来解决工序中可能的
13、加工冲突用优先安排规则来解决工序中可能的加工冲突(要求算法有识别全部加工冲突的实力)(要求算法有识别全部加工冲突的实力)基于随机安排规则的启发式算法:每一工序都对基于随机安排规则的启发式算法:每一工序都对应启发式规则集应启发式规则集/族中的随意规则,规则可重用,族中的随意规则,规则可重用,全部工序遍历一遍后即可找到生产活动调度全部工序遍历一遍后即可找到生产活动调度工序依次集工序依次集11/4/2022遗传算法遗传算法:借鉴生物界自然选择和自然遗传机制的随机算法p原理:始于多个初始解,然后通过确定规则原理:始于多个初始解,然后通过确定规则进行逐步迭代产生新的解,合成解集,通过进行逐步迭代产生新的
14、解,合成解集,通过对解集中解的性质的推断,筛出须要的解对解集中解的性质的推断,筛出须要的解11/4/2022遗传算法遗传算法:借鉴生物界自然选择和自然遗传机制的随机算法p算法设计的内容:算法设计的内容:p编码编码解空间解空间p适应度函数适应度函数解的质量的度量解的质量的度量/目标函数目标函数p选择策略选择策略大适值解对应大存活概率大适值解对应大存活概率/机会机会p限制参数限制参数种群规模、算法代数种群规模、算法代数/终止准则、遗终止准则、遗传操作概率等传操作概率等p遗传算子遗传算子选择选择/遗传、交叉、变异遗传、交叉、变异缺点:没有利缺点:没有利用目标函数梯用目标函数梯度等信息,造度等信息,造
15、成了解的无方成了解的无方向性向性11/4/2022基于遗传算法的车间调度问题遗传算法:把调度问题参数表达成按确定结构组成的染色体编码p部分算法设计内容:部分算法设计内容:p编码编码工件加工依次工件加工依次p适应度函数适应度函数完成加工作业可能的最大流程时完成加工作业可能的最大流程时间的倒数(流程时间越短越好)间的倒数(流程时间越短越好)p选择策略选择策略大适值解对应大存活概率大适值解对应大存活概率/机会机会p限制参数限制参数种群规模、算法代数种群规模、算法代数/终止准则、遗终止准则、遗传操作概率等传操作概率等p遗传算子遗传算子选择选择/遗传、交叉、变异遗传、交叉、变异11/4/2022基于遗传
16、算法的模糊车间调度方法主要解决提前/拖期费用调度问题利用模糊量表示客户对交货期的满足程度Q:航班延误问题:航班延误问题A1:可用随机规则调度法:可用随机规则调度法A2:也可用模糊调度法:也可用模糊调度法11/4/2022基于同一时间离散化生产调度把调度范围分成许很多多等长度的时间段民航修理作业标准工时下的派工问题,然后明确约束条件(安排约束、容量约束、物料平衡、公共及人力资源限制),最终可表达为以利润最大为目标函数的调度问题一个经典一个经典的调度问的调度问题题11/4/2022不确定性生产调度问题生产系统的不确定性:1)加工期的不确定性,如:备件与故障件的不匹配;2)存储容量的不确定性,如:最优库存容量问题即存储容量的上下限的确定;3)人的行为的不确定性不确定因素的处理方法:1)用精确数来表示不确定性,比如各类各级工程技术人员的标准人工时测度;2)随机概率分布函数表达,如机务工程作业中牢靠性/度的表达;3)模糊理论方法模糊冗余处理+学习过程11/4/2022感谢!11/4/2022