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

摘要

铁钢区的批量计划和物流调度是钢铁企业生产运作管理中急需解决的重大关键问题，科学的制定有利于提高生产效率和资源利用率、降低生产成本和能源消耗。由于铁钢区的批量计划和物流调度问题都可归结为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)针对考虑复杂因素的实际炼钢-连铸批量计划问题，通过分析问题的工艺、管理约束和要求，抽取问题的关键特征，建立符合生产实际的数学模型，提出有效的启发式和禁忌搜索算法，并以模型算法为核心开发决策支持系统，进行实际应用验证。通过对实际数据的测试，验证算法的有效性和系统的稳定性。