基于列生成的铁钢区批量计划与物流调度

基于列生成的铁钢区批量计划与物流调度

论文摘要

铁钢区的批量计划和物流调度是钢铁企业生产运作管理中急需解决的重大关键问题,科学的制定有利于提高生产效率和资源利用率、降低生产成本和能源消耗。由于铁钢区的批量计划和物流调度问题都可归结为NP-Hard的组合最优化问题,因此,探讨适合这类问题的有效和实用算法已成为学术界和工业界关注的热点研究课题。列生成作为一种重要的最优化技术,与其他算法相结合已经成功地求解许多NP-Hard的经典组合最优化问题,获得问题的最优解或次优解。本文从影响列生成算法性能的要素出发,分别针对算法体系结构、价格子问题的求解以及整数解的获取三个方面进行了理论和改进研究;并以从铁钢区提炼出来的炼钢—连铸Lot批量计划问题、炼钢—连铸浇次批量计划问题、铁水流向分配问题、铁水机车调度问题为背景,对列生成方法进行了应用研究。针对铁钢区的实际炼钢—连铸批量计划问题,设计并提出了有效的智能优化算法,以此为核心开发了相应的决策支持系统。具体内容概括如下:1)算法体系结构改进。将基于次梯度的拉格朗日松弛(LR)算法嵌入列生成算法框架中,形成拉格朗日松弛和列生成的混合算法。该算法包含双重迭代,在内环通过求解拉格朗日松弛子问题和基于次梯度更新乘子来获得LR对偶问题的下界同时生成列;在外环将内环生成的负消减费用列加入限制主问题,通过求解获得其最优解(对应LR对偶问题的上界)以及影子价格,并将影子价格同历史最好次梯度乘子进行加权组合并传递给内环作为初始乘子。以炼钢—连铸Lot批量计划问题为研究对象,对该算法进行了应用研究。对该问题建立一个混合整数规划模型,通过松弛模型中一组耦合约束获得拉格朗日松弛问题,并将其分解为两级子问题,分别设计了有效动态规划算法,进一步将LR对偶问题等价转换为适合列生成的粗放型线性规划模型,从而结合基于次梯度的拉格朗日松弛算法和列生成算法,形成LR&CG混合算法,共同求解LR对偶问题。2)求解价格子问题方法的改进。提出三种不同改进策略,包括:状态空间松弛技术、降低搜索空间策略以及基于启发式生成列的策略。(1)状态空间松弛技术以消弱主问题的下界为代价,来降低价格子问题的复杂度,从而加速价格子问题的求解。以铁水流向分配问题为研究对象,进行了该策略的应用研究。通过对NP-Hard单机调度子问题的状态空间进行松弛而设计了一个伪多项式动态规划算法,同时允许单机子问题的伪调度(列)加入限制主问题,从而对子问题求解的加速和主问题下界的削弱进行了折衷,提高了算法的整体性能。(2)降低搜索空间策略主要是针对那些采用探索技术获得价格子问题最优解的方法,通过对价格子问题性质的分析,识别那些不可能扩充为最优解的部分解,将其尽早排除,从而节约搜索无效空间带来的计算时间。以炼钢—连铸浇次批量计划问题和铁水机车调度问题为研究对象,分别进行了该策略的应用研究。炼钢—连铸浇次批量计划问题列生成算法的价格子问题可归结为带有资源约束“族单元”最短路径问题,为该问题设计了广义Dijkstra算法,提出统治规则和标签下界估值来抑制标签的快速增殖,从而限制了无效的搜索空间,提高价格子问题的求解效率。这个策略还可扩展到铁水机车调度问题列生成算法的价格子问题,归结为带有非线性目标函数和时间约束的“单元”最短路径问题。(3)基于启发式生成列的策略是在列生成算法迭代的初始阶段,采用启发式生成负消减费用列,从而降低价格子问题最优求解的复杂性,节约计算时间。以炼钢—连铸浇次批量计划问题列生成算法的价格子问题为例,针对当前基变量对应的列,采用贪婪思想进行先插入后删除,由此形成新的负消减费用列,并加入限制主问题。以炼钢—连铸Lot批量计划问题的拉格朗日松弛子问题为例,通过对子问题进一步松弛获得松弛子问题的最优解,基于此改造获得子问题的可行解,从而搜寻合适的下降方向和负消减费用列。3)整数解的获取。提出三类不同方法获取最优或次优整数解,即分枝—定界,基于列生成的分数解改造策略和基于拉格朗日松弛问题解的改造策略。(1)通过探究原模型同Dantzig-Wolfe分解模型之间变量的等价关系和问题自身的性质,提出有效分枝策略,从而实现基于列生成的分枝—价格算法获取最优解,应用于炼钢—连铸浇次批量计划问题、铁水流向分配问题以及铁水机车调度问题。(2)通过改造列生成算法所获得的最优分数解来获取原问题的整数解(上界),包含两种不同类型的改造。针对炼钢—连铸浇次批量计划问题,基于当前分数解,采用一种过滤策略获取部分整数解,剩余的列和行构成降维问题,进行新一轮的列生成。最后对获得的整数解进行局域搜索来获得改进,并且仅在根节点处执行该策略,不执行分枝操作。针对铁水机车调度问题,在每个分枝节点都针对分数解进行改造,首先通过计算任务和机车之间的分配关系,然后按照字典序关系将任务插入机车调度。这种策略试图在分枝树上搜寻较好上界,以帮助修剪分枝节点、抑制分枝树的规模。(3)拉格朗日松弛算法中,常对拉格朗日松弛问题的最优解进行改造来得到原问题的可行解,称为LR启发式,但LR启发式没有固定的实现模式。在炼钢—连铸Lot批量计划问题的LR&CG混合算法中,通过固定Lot的选取,以及松弛部分约束,将原问题转化为线性规划的运输问题,获得分数解后再进行舍入取整获取可行整数解。4)针对考虑复杂因素的实际炼钢—连铸批量计划问题,通过分析问题的工艺、管理约束和要求,抽取问题的关键特征,建立符合生产实际的数学模型,提出有效的启发式和禁忌搜索算法,并以模型算法为核心开发决策支持系统,进行实际应用验证。通过对实际数据的测试,验证算法的有效性和系统的稳定性。

论文目录

  • 摘要
  • 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 线性规划的Dantzig-Wolfe分解
  • 1.3.3 整数规划和列生成
  • 1.3.4 集划分问题和列生成
  • 1.3.5 列生成的基本方法综述
  • 1.3.6 列生成方法的改进综述
  • 1.4 本文的技术路线及主要工作
  • 1.4.1 本文的技术路线
  • 1.4.2 本文的主要工作
  • 第二章 铁钢区生产物流的工艺及管理背景
  • 2.1 铁水运输的工艺背景
  • 2.2 铁水运输的作业计划
  • 2.2.1 铁水分配作业计划
  • 2.2.2 TPC调度作业计划
  • 2.2.3 机车调度作业计划
  • 2.3 炼钢—连铸生产的工艺背景
  • 2.4 炼钢—连铸生产计划与调度
  • 2.4.1 炉次批量计划
  • 2.4.2 浇次批量计划
  • 第三章 基于LR&CG混合算法的炼钢—连铸Lot批量计划问题
  • 3.1 引言
  • 3.2 问题描述及数学模型
  • 3.2.1 问题描述
  • 3.2.2 数学模型
  • 3.3 拉格朗日松弛算法
  • 3.4 LR对偶问题的等价模型及列生成算法
  • 3.5 拉格朗日松弛和列生成(LR&CG)混合算法
  • 3.5.1 混合策略分析及算法框架
  • 3.5.2 第一级子问题的求解改进策略
  • 3.5.3 LR启发式构建可行解
  • 3.6 算法性能实验
  • 3.7 结论
  • 第四章 基于HCG算法的炼钢—连铸浇次批量计划问题
  • 4.1 引言
  • 4.2 问题描述及数学模型
  • 4.2.1 问题描述
  • 4.2.2 数学模型
  • 4.3 分枝—价格算法
  • 4.3.1 Dantzig-Wolfe分解
  • 4.3.2 价格子问题
  • 4.3.3 主问题的有效不等式
  • 4.3.4 初始限制主问题
  • 4.3.5 分枝—定界
  • 4.4 HCG算法
  • 4.5 算法性能实验
  • 4.6 结论
  • 第五章 铁水运输调度的分枝—价格算法
  • 5.1 引言
  • 5.2 铁水流向分配问题
  • 5.2.1 问题描述和数学模型
  • 5.2.1.1 问题特性
  • 5.2.1.2 数学模型
  • 5.2.2 铁水流向分配问题的分枝—价格算法
  • 5.2.2.1 集划分模型
  • 5.2.2.2 价格子问题
  • 5.2.2.3 分枝策略
  • 5.2.3 算法性能实验
  • 5.3 铁水机车调度问题
  • 5.3.1 问题描述
  • 5.3.2 数学模型
  • 5.3.3 铁水机车调度问题的分枝—价格算法
  • 5.3.3.1 集划分模型
  • 5.3.3.2 价格子问题
  • 5.3.3.3 分枝策略
  • 5.3.3.4 启发式上界
  • 5.3.4 算法性能实验
  • 5.4 结论
  • 第六章 实际炼钢—连铸批量计划问题
  • 6.1 问题背景
  • 6.2 实际炉次批量计划问题数学模型
  • 6.2.1 问题的特点及建模要素
  • 6.2.2 模型表达
  • 6.3 实际浇次批量计划问题数学模型
  • 6.3.1 问题的特点及建模要素
  • 6.3.2 模型表达
  • 6.4 实际炼钢—连铸批量计划问题的求解策略
  • 6.4.1 炉次批量计划问题的动态规划启发式
  • 6.4.2 浇次批量计划问题的禁忌搜索算法
  • 6.4.3 板坯炉次调整改进
  • 6.5 算法性能实验
  • 6.6 结论
  • 第七章 炼钢—连铸批量计划与生产调度决策支持系统开发
  • 7.1 引言
  • 7.2 炼钢—连铸批量计划决策支持系统
  • 7.2.1 系统的设计思想
  • 7.2.2 系统的总体结构及接口
  • 7.2.3 系统的功能模块和界面
  • 7.2.4 系统的操作流程
  • 7.2.5 系统实施效果
  • 7.3 炼钢—连铸生产调度决策支持系统
  • 7.3.1 炼钢—连铸生产调度的理论方法
  • 7.3.2 系统的设计思想
  • 7.3.3 系统的功能模块和界面
  • 第八章 结束语
  • 参考文献
  • 致谢
  • 作者博士期间发表和录用的论文
  • 作者博士期间科研情况
  • 个人简历
  • 相关论文文献

    标签:;  ;  ;  ;  ;  ;  ;  ;  ;  

    基于列生成的铁钢区批量计划与物流调度
    下载Doc文档

    猜你喜欢