基于反馈校正机制的优化算法设计及其在薄板轧制调度中的应用

论文摘要

组合优化问题广泛存在于科学研究和工程应用中的各个领域。设计快速、可靠的最优化算法一直是研究者不懈努力的目标。随着现代社会日益增多的复杂问题,传统的确定性最优化方法存在计算复杂性方面的局限性,而启发式算法,包括现代智能优化算法在内,尽管简单、通用,但是不能保证解的质量。因此如何设计一种集成两种算法优点并应用于实际问题的混合算法正成为学术界关注的热点问题之一。而在钢铁生产中,尤其是在轧制调度问题中,存在着大量的组合优化问题。轧制过程是钢铁生产过程中的关键工序之一,优化钢铁轧制过程直接关系到成品的质量、库存的成本、客户的满意度。因此,该研究具有重要的经济意义。本文提出了基于反馈校正机制的混合优化算法,并分别针对薄板生产过程中的热轧调度问题和冷轧连续镀锌生产线调度问题做了深入的研究,其创新点主要概括有如下两个方面:从建模的角度,考虑了轧辊和轧件之间的耦合效应,建立了基于时变参数的调度模型。建模的难点是由于不同的轧件调度会造成不同程度的轧辊磨损,轧辊的磨损程度会直接影响轧件的性能,从而影响后续的调度结果。轧件和轧辊的耦合效应在连续镀锌线的平整机生产过程中体现的尤为明显。从算法的角度,设计了基于反馈校正原理的集成数学规划和启发式算法的混合算法框架。目的在于利用数学规划的精确性和启发式算法的快速性求解组合优化问题。反馈校正算法的原理是通过算法之间的大量信息交互,使得在不影响最优解的前提下简化问题。具体研究内容包括以下几个方面:(1)提出了解决非对称旅行商问题(ATSP)的基于反馈校正原理的优化算法框架。ATSP是许多工业生产调度问题原型,也是热轧问题需要解决的一个关键子问题。该方法核心是依据ATSP问题松弛模型对偶关系推断ATSP最优解被排除弧集合的弧排除算法。算法框架以ATSP问题的弧集合作为“参考输入”,以ATSP最优解的上下界求解算法作为“控制对象”,以弧排除算法作为“反馈校正控制器”,其“反馈输入”是“控制对象”的上下界差值。算法迭代过程中,上下界差值缩小,排除弧集合增加,算法呈现出自收敛性。该框架将数学规划方法和元启发式算法系统的集成在一个统一的框架之中,无论从理论上和还是从仿真上都充分说明该自收敛算法是非常有效的。(2)建立了热轧计划、调度问题的基于多路径、多目标的数学模型。与以往热轧模型不同之处在于:(i)将同宽度连续轧制数量的限制建立为资源约束模型;(ii)通过递阶目标层次结构,将原问题分解为易于解决的子问题求解。提出了基于数学规划与启发式方法相结合的混合策略。针对大型工业调度问题,以求近优解为出发点。算法的主要思想是根据对问题的宏观分析,松弛模型的复杂约束,通过数学规划定位最优解或者近优解的理想区域,然后由启发式算法进行后续寻优或者修复不可行解。相对与一般的混合算法,这种策略不仅可以找到相当出色的次优解,并且能够给出下界,可对解的性能做有效的评估。(3)针对复杂的连续镀锌生产线调度问题,考虑了轧辊性能与轧件之间耦合约束,并建立了时间相关旅行商问题(TDTSP)的调度模型,提出了基于反馈校正机制的上、下界并行求解算法。以第二章提出的框架为基础,在该框架之中嵌入了次梯度算法,使得在求解原始松弛问题的对偶问题过程中出现的大量对偶信息能够被有效的利用以降低问题的规模,并在此基础之上,归纳了解元素集排除过程及其算法实施的一般形式。而在一般的求解整数规划过程中,是根据对偶理论求解原问题松弛问题的对偶问题获得下界。如果该下界对应的解是可行的,则已经找到了最优解。若不可行,则采用分支定界或其他修复策略获得最优或者近优解。这种串行处理策略,只利用到了最后的下界信息,而没有利用到求解对偶问题过程出现的大量对偶信息。因此,如果不能充分利用计算获得的问题内部信息作为指导,算法性能会降低。本文对钢铁生产中的关键问题之一批量轧制调度问题从建模和算法设计两个方面都做了较为深入的探讨,研究成果可为优化钢铁生产物流水平,提高生产作业计划与调度的效率和质量提供理论与技术支持。本文研究工作受国家自然科学基金项目(No. 60574063)和香港城市大学基金(No. CityU122305)的资助。

论文目录

• 摘要
• Abstract
• 目录
• 图表目录
• 专业术语表
• 第一章 绪论
• 1.1 引言
• 1.1.1 组合优化理论及分类
• 1.1.2 组合优化算法研究的关键问题
• 1.2 研究背景、意义及现状
• 1.2.1 钢铁生产流程概述
• 1.2.2 钢铁生产作业计划调度问题特点及主要内容
• 1.2.3 钢铁轧制过程及其调度研究现状
• 1.3 生产调度问题与组合优化的关系
• 1.3.1 生产中的标准问题
• 1.3.2 生产调度优化研究中的成果、途径与不足
• 1.4 本文主要研究内容
• 第二章 并行反馈校正优化算法基本原理及ATSP 问题应用
• 2.1 引言
• 2.2 ATSP 问题的数学模型
• 2.3 并行反馈校正算法原理及其实施
• 2.3.1 反馈校正算法基本原理
• 2.3.2 算法的原理及其实施
• 2.3.3 ACO 及B&B 概述
• 2.3.4 PATCH 原理
• 2.3.5 弧排除原理
• 2.4 算法的性能分析
• 2.4.1 初始上、下界性能分析
• 2.4.2 算法整体收敛性分析
• 2.5 仿真分析与算法比较
• 2.6 本章小结
• 第三章 基于启发式&列生成算法的HSM 调度问题求解
• 3.1 引言
• 3.2 HSMP 数学模型
• 3.3 基于递阶成本结构的模型分解及算法流程
• 3.4 MRMCP 问题的Lagrangian 松弛策略
• 3.5 MRMCP 问题基于改进的列生成算法
• 3.5.1 典型节点选择问题
• 3.5.2 基于Lagrangian 松弛的RC-ESPP 问题求解
• 3.5.3 基于Volume 算法的Lagrangian 对偶问题求解
• 3.5.4 APTP 问题到ATSP 问题的转换
• 3.5.5 混合分支策略
• 3.5.6 用于评估的MRMCP 问题的下界生成
• 3.6 KP 问题的最大Prize-Collecting 优化
• 3.7 生产超前、拖期成本的优化
• 3.8 数据分析与算法比较
• 3.9 本章小结
• 第四章 基于并行反馈校正算法的CGL 调度问题求解
• 4.1 引言
• 4.1.1 CGL 调度问题概述
• 4.1.2 算法总体设计框图
• 4.2 CGL 生产调度建模
• 4.3 基于TDTSP 的CGL 生产调度模型
• 4.4 TDTSP 问题研究现状
• 4.5 基于多层网络图的等价模型变换
• 4.6 对偶问题求解
• 4.6.1 标准次梯度优化
• 4.6.2 变目标值次梯度优化
• 4.7 基于DP 的最短路径计算
• 4.8 弧排除原理
• 4.8.1 TDTSP 问题分析
• 4.8.2 弧排除过程的计算复杂度分析
• 4.8.3 对一般性组合优化问题的推广
• 4.9 上界求解
• 4.9.1 基于受限空间的DP 初始上界求解
• 4.9.2 基于ACO 的迭代上界求解
• 4.10 数据分析与处理及算法比较
• 4.10.1 定单数据预处理
• 4.10.2 数据仿真与算法比较
• 4.11 本章小结
• 第五章 总结与展望
• 5.1 本文总结
• 5.2 研究展望
• 5.3 结束语
• 参考文献
• 3）的 Primal-Dual 算法'>附录A 基于最短增广路径问题（SAPP）的线性分配问题（LAP）的 O（N³）的 Primal-Dual 算法
• 附录B 相关算法设计框图
• 附录C-HSM&CGL 评价值表
• 附录D 攻博期间设计的钢铁生产调度软件
• 致谢
• 攻读博士学位期间发表、录用和完成的学术论文
• 攻读博士学位期间科研情况