论文摘要
生产调度是指在满足一定生产约束条件下,为生产任务分配可用的生产资源,使得一个或多个目标最优。以往的研究主要集中在静态调度上,工件、设备等相关信息已知且不变。而在实际生产环境中往往存在大量实时扰动事件,如工件动态到达、机器故障、工件加工时间改变等,这些扰动事件会导致原调度变得很差甚至不再可行,需要重新生成新的调度方案以适应变化的生产环境和条件要求,这类问题可归结为动态调度问题。对动态调度的研究相比于静态调度更具实际意义,是工业界急需解决的难点。常规的静态调度方法主要是针对确定性静态调度问题求解,无法适应环境的变化,不再适合于动态调度问题。动态优化方法由于能够适应于环境的变化,寻找的是最优解的轨迹,而成为国际前沿热点研究方法。本文在动态因素分析的基础上,首先以单机生产调度为背景,对动态优化进行基础研究,提出动态差分进化算法；然后以炼钢-连铸生产调度为背景,对动态优化进行应用研究,提出增量式动态差分进化算法,最后以此为核心开发了相应的决策支持系统。具体内容概括如下：1) 针对动态调度中的动态因素进行分析。分别以一般生产环境和钢铁生产环境为背景,分析动态调度问题中存在的共性动态因素和针对钢铁生产的特殊性动态因素,总结了动态调度中的实时扰动事件及分类,对其产生原因及来源进行探讨,然后,根据扰动事件对问题的影响程度,采取不同的处理策略。2) 针对公共交货期下工件动态到达的单机提前／拖期（E/T）调度问题进行研究。该问题的任务是在公共交货期下,将多个按照不同到达时间动态到达的工件安排在一台机器上加工,目标是找到一个可行调度方案使工件提前／拖期总惩罚量最小。根据问题特点建立数学模型,并设计了基于工件排列的差分进化与分布估计算法（DE&EDA）混合方法。为了加强算法性能,将局部搜索方法应用到DE&EDA混合算法中,实验结果表明了算法的有效性。3) 针对准备时间与顺序相关的动态单机调度问题进行研究。该问题中工件随时间动态到达,工件的所有信息提前不可知,直到工件已经到达或者即将到达,其任务是将多个已到达的工件安排在一台机器上加工,目标是最小化最大延迟时间。根据问题特点建立了给定时间窗的数学规划模型,并提出动态差分进化算法在新工件到达时快速调整原调度以适应环境的变化。针对DE算法由于其连续性而不能直接求解调度问题的缺点,使用以工件排列为个体编码的算法结构。针对计算负担随着问题规模的增大而呈指数增长的问题,提出基于分解的加速方法来改进算法的效率。计算结果表明所提算法是快速有效的。4) 针对炼钢-连铸动态调度问题进行研究。该问题的目标是当发生不可预知的实时扰动事件时,快速动态调度生成新的调度方案以适应变化的生产环境和条件要求。考虑实际工艺约束和实时信息,将炉次的加工时间加入到决策变量中进行决策,建立了动态扰动下的炼钢-连铸动态调度模型,目标是最小化总惩罚费用,包含断浇损失惩罚费用、炉次总等待时间惩罚费用、加工时间偏差惩罚费用及最大完工时间惩罚费用四项。5) 上述的炼钢-连铸动态调度问题既具有动态调度问题的复杂性,又具有实际问题的工艺约束,非常难于求解。针对这个难题,提出增量式动态差分进化算法,其特征为：（1）以增量机制更新种群,将前一环境中的好解修复适应于新环境中,继而使用差分进化算法产生新调度；（2）引入新的记忆策略和外部存档策略,并且为了保证种群的多样性,加入随机搜索过程,提出一种改进的变异策略；（3）提出一种基于实数编码矩阵的个体表达。其中,记忆策略用来存储及使用两代前的种群信息,而外部存档策略用来保存最近搜索的优势解。基于随机生成数据和实际生产数据的计算实验结果证明所提算法的有效性。6) 以钢铁企业炼钢-连铸工序为背景,将上述炼钢-连铸动态调度问题模型及算法作为内核,开发了用于编制炼钢-连铸生产调度方案的决策支持系统,既能够解决静态调度问题,又能够在实时扰动事件发生时,接收生产实绩反馈,制定动态调度方案。通过对实际生产数据的测试,验证算法和系统可有效求解炼钢-连铸生产调度问题。
论文目录
相关论文文献
标签：动态优化论文; 差分进化论文; 动态单机调度论文; 炼钢连铸动态调度论文; 决策支持系统论文;