钢铁生产与物流调度的时空建模和凸优化方法

发布时间：2020-07-29 18:27

【摘要】：钢铁生产调度是确定从原料到成品的物理、化学和机械性能转化过程中,物件在各工序生产设备上的组合、分配及生产时间;而物流调度是确定在工序间的存取、搬运、运输等作业中,物件在物流设备上的分配、时间安排及空间位置。科学地确定生产与物流调度能够有效提高大型生产和物流设备利用率、降低在制品库存、提升钢铁企业的智能化水平。由于生产与物流调度决策中包含大量的整数分配和排序变量,需要同时满足多个管理目标的需求以及复杂的生产工艺要求,使得如何准确刻画钢铁生产与物流调度成为国际上具有挑战性的科学问题。在工程上,建模的质量直接影响优化求解的性能,从而使得生产与物流调度的建模具有重要的实际意义。本文针对钢铁制造系统实际作业管理中提炼出的生产与物流调度问题进行研究,提出了时空网络建模方法和基于凸优化的求解方法。针对混合流水车间调度、考虑物流成本的板坯与合同分配、板坯与合同鲁棒重分配等生产调度问题,分别提出了时空网络建模、凸松弛、拉格朗日松弛和凸优化混合算法;针对钢卷库区吊机调度、钢铁产品转库调度等物流调度问题,分别提出了时空网络建模、近似动态规划、拉格朗日分解和凸优化混合算法。主要研究内容概括如下:(1)针对钢铁制造系统的混合流水车间调度问题提出一种时空网络建模方法。该建模方法通过将时空离散化成网格构造网络图,用图上的广义节点表示工件在机器上的分配,用图上的弧表示工件在两个相邻加工阶段之间的连接关系。提出了基于工件开始/结束时间和工件等待时间的两类降维策略加速模型求解。计算实验结果表明,该时空网络建模方法在计算效率和质量方面优于已有建模方法。(2)从钢铁企业制造管理过程中提炼出一类考虑物流成本的板坯与合同分配问题。该问题需要将炼钢工序产出的无委托板坯在满足板坯和客户合同之间适配性要求情况下分配给客户合同,使板坯利用率、板坯获取物流成本及客户满意度达到最优。针对该问题所建立的0-1整数二次规划模型常规优化方法难于求解的问题,提出了半正定松弛方法获得问题的下界,开发了基于凸优化的启发式算法获得问题的近优解。通过生产实际数据的计算实验验证了所提出方法的有效性。(3)从钢铁企业热轧生产管理中提炼出一类板坯与合同鲁棒重分配问题。该问题是针对实际生产出的板坯在质量、重量和尺寸方面与设计存在偏差导致板坯与合同原有分配关系需要进行重新优化。针对板坯与合同适配参数的不确定性,提出了鲁棒优化建模方法,将参数的鲁棒性刻画为一个椭球集合。针对该模型不能直接求解的困难,通过数学变换将其等价转化为混合整数二阶锥规划,使其能够直接通过主流优化软件CPLEX求解小规模问题,构造了最大和最小板坯需求个数有效不等式加速模型求解。对于大规模问题,提出了一种拉格朗日松弛和二阶锥混合算法能够近似求解。计算实验结果表明,所提出的算法性能优于主流优化软件CPLEX。基于所提出的模型和方法,开发了板坯与合同重分配决策支持系统,提高了合同完成率,降低了板坯切损量和合同余材量。(4)从钢卷库区的作业管理中提炼出一类吊机调度问题。该问题需要同时决策库区中吊机执行钢卷存取及倒垛任务的顺序以及钢卷需要移动到的位置,从而使得吊机物流效率最优。针对该问题复杂的工艺要求、物流逻辑以及调度的时空耦合特征,提出一种事件驱动的连续时间-空间网络模型,网络中的节点表示调度阶段结束时库区中的位置,弧表示一个阶段中吊机在两个位置间的移动。根据问题结构设计了一个基于带cut的二部图匹配的近似动态规划算法来求解大规模的实际问题。计算实验结果表明提出的模型求解效率优于传统建模方法,提出的近似动态规划算法效率优于主流优化软件CPLEX。(5)从钢铁企业物流环节中提炼出一类产品转库调度问题。由最后工序产出的产品存入末端库后需要定期转入成品库中进行物流配送。该问题需要在满足运输工具的能力限制和物流量的均衡要求下决策产品转入成品库的时间和区位。针对该问题建立了非线性整数规划模型,通过数学变换将物流均衡的非线性目标项等价转化为混合整数二阶锥约束,提出了基于拉格朗日分解和二阶锥规划的混合算法,构造了两类背包有效不等式用于加速子问题的求解。计算实验结果表明提出的算法在大规模问题的求解质量和效率方面优于主流优化软件。
【学位授予单位】：东北大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：TF31
【图文】：

时空网络,航班

看做是一种基于离散时间的方法，即计划周期被平均分成很多等长的时间单元，逡逑每项任务的开始和结束都发生在这些时间单元的起点和终点上。逡逑图１．３三地往返航班情况逡逑Ｆｉｇ．邋１．３邋Ｒｏｕｎｄ邋ｔｒｉｐ邋ｆｌｉｇｈｔｓ邋ａｍｏｎｇ邋ｔｈｒｅｅ邋ｃｉｔｉｅｓ逡逑下面以上海（ＳＨＡ）、北京（ＢＪＳ）、沈阳（ＳＨＥ）三地之间在一天内往返的部逡逑分航班调度情况为例，简要说明时空网络的构造方法。图］．３所示为问题考虑的逡逑航班情况，其中上海与北京之间往返三次航班，北京与沈阳之间往返两次航班。逡逑如图１．４所示为该问题的航班调度时空网络，其中水平坐标表示时间，垂直坐标逡逑表示地理位置。图中的箭头表示飞机在两地之间的航行，箭头上的两行文字分别逡逑表示航班号和飞机型号。逡逑空间４逡逑ＳＨＡ邋逦＾＾＾＾邋？ｖ逦＊２逦？逡逑＼逦＼邋Ｔ逦＾逦ＣＡ１８８４邋ｆ逡逑ＣＡ－６逦Ｖ逦ＣＡ，５．７邋Ａ３３0邋／逡逑Ｂ７８７逦／邋ＣＡ１５１８逦，逦＼Ｊ逡逑＼邋ｒＢ７＾邋Ａ逡逑ＢＪＳ邋逦逦＾＾９逦？逡逑ＣＡ１６５８逦ＣＡ１６２６逦ＣＡ１６５７邋ＣＡ１６２５逡逑Ｂ７３７逦

线性规划,几何解释

出现在非常多的领域和应用中，１９４７年美国数学家Ｄａ划的单纯形法，为这门学科奠定了基础。同年美国数学家ｖ，开创了线性规划的许多新的研究领域，扩大了它的应５０年代后对线性规划进行大量的理论研究，并涌现出一５４年Ｌｅｍｋｅ提出对偶单纯形法，１９５６年Ｔｕｃｋｅｒ提出互ｔｚｉｇ和Ｗｏｌｆｅ提出分解算法等，１９７９年苏联数学家Ｋｈａｃｈｉ的椭球算法，并证明它是多项式时间算法，１９８４年出求解线性规划问题的内点算法，这种算法是一种新的方法求解线性规划问题在变量个数为５０００时只要单纯形。逡逑的研究成果还直接推动了其他数学规划问题包括整数规划的算法研究。随着计算机技术的发展，出现了许多线

电缆网络,能源计划,时空滤波器,平衡配置

第１章绪论逡逑其中ＪＣ为《维决策变量，次和尸为矩阵参数，ｃ、匕、４、ｅ，和ｇ为向量参数，｜｜＊｜｜为逡逑向量的欧几里得范数。模型中的约束｜｜４ｘ邋＋邋６，｜Ｘ；ｃ邋＋邋ｅ，为二阶锥约束。图１．６所逡逑示为向量＾＝0：１，１２，１３）７＇表达的一个三维的二阶锥空间｛（；＾，：＾２，：＾）｜0１２＋；＜：２２广２＜：＞：３｝。逡逑Ｉ零逡逑图１．６邋—个三维的二阶锥逡逑Ｆｉｇ．邋１．６邋Ａ邋ｔｈｒｅｅ邋ｄｉｍｅｎｔｉｏｎａｌ邋ｓｅｃｏｎｄ－ｏｒｄｅｒ邋ｃｏｎｅ逡逑二阶锥规划是凸优化领域中发展最成熟的技术之一，因其优美的性质和有效逡逑求解算法使得这项技术广泛地应用在了很多领域，例如二阶锥规划已经被用来解逡逑决投资组合、调度、能源计划等不同领域的问题。逡逑Ａｌｉｚａｄｅｈ邋和邋Ｇｏｌｄｆａｒｂ［３ｌ］综述了邋ＳＯＣＰ邋的基本概念和应用。Ｋａｎｎｏ邋和邋Ｏｈｓａｋｉｆ３２］逡逑针对电缆网络的接触分析问题建立了二阶锥规划模型，并采用原始－对偶内点算法逡逑对其进行求解，获得了电缆网络的平衡配置。Ｙａｎ和Ｍａ［３３］将二阶锥规划建模方逡逑法应用于时空滤波器的最优设计问题，该方法克服了以往研究的缺点，提供了问逡逑题的全局最优解。８１１＾３５？0１１＾等［３４１将二阶锥规划方法应用于求解带噪声和丢失数逡逑据的支持向量机回归，数值实验结果验证了该方法的有效性。逡逑当二阶锥规划中的部分变量取值有整数限制时

【参考文献】