生产调度和智能优化chen.pptx

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,生产调度及智能优化,陈静杰,博士教授,航空自动化学院航空电子系中国民航大学数据分析研究所,jjchen24092499（O）/13652037939,10/2/,第1页生产调度,生产调度与运筹学,Q：区分？,联络？,生产调度,运筹学,10/2/,第2页,生产调度,什么是生产调度？,即按时间分配资源完成任务/作业过程或方法。要求：任务/作业必须是可分割。,生产调度问题,Q：现场有哪些？,10/2/,第3页,生产调度,生产调度与生产计划,都是对生产过程规划与控制（均考虑优化目标），主要区分是考虑时间尺度不一样，理论上均称调度问题；生产调度是生产计划可行性验证过程,生产计划侧重于经营计划和生产能力平衡，考虑时间以月或年计中长久,粗,生产调度则在较短时间内进行，最主要任务是生产作业安排与资源详细分配，包括实际生产环境各种约束,细,10/2/,第4页,生产调度,生产调度与生产计划,生产计划制订以企业利润最大化为目标，而生产调度则以生产过程平稳过渡/顺畅接续为目标。,生产计划制订，普通是考虑静态情况。当生产原因比较稳定和比较理想时才能到达优化预期目标,生产过程是动态，要求生产调度系统有一定柔性，能适应生产过程中内、外原因异动，方便准确而灵活地完成生产计划；生产调度侧重于生产装置分配利用和物料平衡。,10/2/,第5页,生产调度,生产计划优化系统,优化系统可依据企业产、供、销情况，以企业综合效益为目标，建立适当数学模型，依一定方法求解，分别考虑企业内外约束，进而取得最优计划；计划实施，必须充分利用现有资源，优化资源配置，提升生产决议科学性，实现效益最大化。,10/2/,第6页,生产调度,生产调度系统功效,计划分解：普通采取时间分配方法，即滚动计划；,动态监控：实时监控，包含数据采集、关键参数历史趋势图分析、图表及工艺流程显示。平衡协调，包含外部生产和经营两大系统产供销，内部生产过程人员工位器具等,10/2/,第7页,生产调度,生产调度系统特点,复杂性；,随机性；,多约束；,多目标。,Q:维修作业调度,系统特点表示?,10/2/,第8页,生产调度,生产调度问题普通描述,语义描述：目标-任务集合-资源集合-约束条件；,数学描述调度问题数学符号表示,。,生产调度问题性能指标,能力指标：最大生产率、最短生产周期等；,成本指标：最大利润、最小费用等；,客户满意度指标：最短交付期（提前拖期处罚）等,10/2/,第9页,生产调度,生产调度问题分类,依模型变量分类：1）连续变量问题；2）离散变量问题/组和优化问题（combinatorial optimization problem:COP）,依生产过程输出：1）连续生产过程（连续产品流）；2）间隙生产过程（离散批量）/批处理过程批处理调度问题；3）离散生产过程（离散数量）车间调度问题,按调度目标：总作业时间最短、总延迟时间最小等,其它：依人物特点：可否终端、加工时限、次序约束等,10/2/,第10页,生产调度问题分类,车间调度问题：,车间,调度,加工设备分配,工件加工时间与加工次序,实质,生产调度,10/2/,第11页,生产调度问题分类,流水车间调度问题：,分类（基于加工时间或交付期）：确定型、随机型和含糊型/满意型,生产调度,10/2/,第12页,NP难题,工程近似,可用解,生产调度,生产调度问题分类,作业车间调度问题：,JSP,问题能够采取整数线性规划模型描述。前提假设：全部任务在零时刻都可用，且无设备故障，任务在机器上执行时间事先已知,10/2/,第13页,生产调度,生产调度问题分类,间隙生产调度问题：,分类：多产品（multi-product）间隙生产过程全部产品生产次序相同，加工路径相同，整个生产过程分成若干个生产阶段，每个阶段包含若干并行设备。类似Flow-shop和多用途或多目标（multi-purpose）间隙生产过程能够是不一样生产线、不一样路径、不一样工序，可经过设备组织来调整。类似Job-shop,排序,问题,中间产品,存放策略,等候时间,切换时间,上层组织路经与时间分配,下层设备与资源分配决议,10/2/,第14页,生产调度,生产调度问题分类,动态调度问题：,静态调度：调度环境和任务已知前提下所谓事前调度方法,例行维修作业,动态调度：也称再调度，指在调度环境和任务存在不可预见扰动情况下调度方案，即依赖于事前调度环境和任务也与当前状态相关,例行+非例行维修作业,为适应生产过程不确定性和随机性，普通采取周期性调度和再调度相结合策略,10/2/,第15页,生产调度,生产调度问题分类,动态调度问题（续）：,动态调度形式：滚动调度（rolling scheduling）和被动调度（reactive scheduling）,被动调度目标是尽可能维持原静态调度水平，既保持原有性能指标,滚动调度：移动时间段内生产调度；,被动调度：随生产过程改变而不可行调度修正,动态调度,实时性要求,Q：改变（加工时间、任务、设备故障等）调机作业,10/2/,第16页,生产调度,生产调度方法,分类：优化调度方法和启发式调度方法,优化调度：准确求解解析模型而取得最优解、近似求解得次优解；基础：数学规划；适用：小规模优化问题,启发式调度：包含基于规则方法、基于人工智能方法、随机搜索方法、基于仿真方法等，立足当前，追求局部最优而非全局最优,方向：二者结合,启发推理,10/2/,第17页,生产调度,生产调度方法（续）,数学规划,等式与不,等式约束,分支定界法,Lagrangian松弛法,贝叶斯启发方法,规则调,度方法,简单规则,复合规则,启发式规则,动态调度,依靠机器学习动态选择规则,利用神经网络实现智能选择规则,基于人工,智能方法,启发式,搜索规则,基于规则与,知识方法,智能求,解方法,ANNs,GA,Fuzzy Sets,Model-based and model-free,10/2/,第18页,生产调度启发式算法,启发式算法（heuristics algorithm）,语义性描述：一个基于直观或者经验结构算法，在可接收代价下，给出待处理组合优化问题一个可行解,未定义可行解与最优解距离,10/2/,第19页,生产调度启发式算法,启发式算法（heuristics algorithm）,Johnson问题：以最大流程时间为目标两台机器流水车间调度问题依Johnson规则确定其最优调度,问题描述：,n,个工件在机器1和机器2上加工时间分别为,t,i1,和,t,i2,，目标是给出最短生产周期产品序列,10/2/,第20页,生产调度启发式算法,启发式算法（heuristics algorithm）,基于Johnson规则结构最优调度，步骤以下：,10/2/,第21页,生产调度启发式算法,启发式算法（heuristics algorithm）,例：,工件,1,2,3,4,5,6,机器1上加工时间,10,5,11,3,7,9,机器2上加工时间,4,7,9,8,10,15,问题关键是启发式规则建立,启发式算法通常是以牺牲计算时间为代价,10/2/,第22页,生产调度启发式算法,启发式算法（heuristics algorithm）,惯用启发式规则：,用优先分配规则来处理工序中可能加工冲突（要求算法有识别全部加工冲突能力）,基于随机分配规则启发式算法：每一工序都对应启发式规则集/族中任意规则，规则可重用，全部工序遍历一遍后即可找到生产活动调度工序次序集,10/2/,第23页,遗传算法,遗传算法：借鉴生物界自然选择和自然遗传机制随机算法,原理：始于多个初始解，然后经过一定规则进行逐步迭代产生新解，合成解集，经过对解集中解性质判断，筛出需要解,10/2/,第24页,遗传算法,遗传算法：借鉴生物界自然选择和自然遗传机制随机算法,算法设计内容：,编码解空间,适应度函数解质量度量/目标函数,选择策略大适值解对应大存活概率/机会,控制参数种群规模、算法代数/终止准则、遗传操作概率等,遗传算子选择/遗传、交叉、变异,缺点：没有利用目标函数梯度等信息，造成了解无方向性,10/2/,第25页,基于遗传算法车间调度问题,遗传算法：把调度问题参数表示成按一定结构组成染色体编码,部分算法设计内容：,编码工件加工次序,适应度函数完成加工作业可能最大流程时间倒数（流程时间越短越好）,选择策略大适值解对应大存活概率/机会,控制参数种群规模、算法代数/终止准则、遗传操作概率等,遗传算子选择/遗传、交叉、变异,10/2/,第26页,基于遗传算法含糊车间调度方法,主要处理提前/拖期费用调度问题利用含糊量表示客户对交货期满意程度,Q：航班延误问题,A1：可用随机规则调度法,A2：也可用含糊调度法,10/2/,第27页,基于同一时间离散化生产调度,把调度范围分成许许多多等长度时间段民航维修作业标准工时下派工问题，然后明确约束条件（分配约束、容量约束、物料平衡、公共及人力资源限制），最终可表示为以利润最大为目标函数调度问题,一个经典调度问题,10/2/,第28页,不确定性生产调度问题,生产系统不确定性：1）加工期不确定性，如：备件与故障件不匹配；2）存放容量不确定性，如：最优库存容量问题即存放容量上下限确实定；3）人行为不确定性,不确定原因处理方法：1）用准确数来表示不确定性，比如各类各级工程技术人员标准人工时测度；2）随机概率分布函数表示，如机务工程作业中可靠性/度表示；3）含糊理论方法含糊冗余处理+学习过程,10/2/,第29页,谢谢！,10/2/,第30页,