连铸-轧制混流生产模式下轧批调度问题的分支-定价算法

发布时间：2018-04-25 15:34

本文选题：连铸 + 轧制　；参考：《自动化学报》2017年07期

【摘要】：研究了连铸轧制在热装、温装和冷装混流生产模式下的一类新型轧批调度问题.以最小化温装钢坯(热钢锭)缓冷(等待)导致的热能损失和连轧机架切换带来的产能损失为目标,建立了整数规划模型.由于商业优化软件难以在有限时间内直接求得模型的最优解甚至可行解,提出利用Dantzig-Wolfe分解技术将原模型分解为主问题和子问题,采用列生成算法对主问题和子问题进行迭代求解得到原问题的紧下界,最后以列生成算法作为定界机制嵌入分支定界框架中形成分支定价算法,执行分支搜索过程以获得整数最优解.本文还从影响分支定价算法性能的要素出发提出改进策略.针对主问题,提出列生成和拉格朗日松弛混合求解策略来抑制单一列生成算法的尾效应.针对价格子问题,在动态规划算法中提出了基于占优规则和标号下界计算方法来及早消除无效状态空间,加速求解过程.以钢铁企业的实际生产数据和扩展的随机算例进行了数值实验,结果显示所提出改进策略能够突破求解能力的限制,使分支定价算法在可接受计算时间内求得工业规模问题的最优解.
[Abstract]:A new type of batch scheduling problem for continuous casting rolling in hot, warm and cold mixed flow production mode is studied. An integer programming model is established to minimize the loss of heat energy caused by slow cooling (waiting) of warm billet (hot steel ingot) and the loss of production capacity caused by the switching of continuous rolling mill frame. Because commercial optimization software is difficult to find the optimal solution or even feasible solution of the model directly in a finite time, the Dantzig-Wolfe decomposition technique is proposed to decompose the original model as the main problem and sub-problem. The compact lower bound of the original problem is obtained by iterative solution of the main problem and the sub-problem by using the column generation algorithm. Finally, the column generation algorithm is used as the boundary setting mechanism to embed the branch pricing algorithm into the branch-and-bound framework. Perform a branch search process to obtain an integer optimal solution. This paper also proposes an improved strategy based on the factors that affect the performance of the branching pricing algorithm. For the main problem, a hybrid solution strategy of column generation and Lagrange relaxation is proposed to suppress the tail effect of single column generation algorithm. Aiming at the price subproblem, a new method based on dominant rule and lower bound is proposed to eliminate invalid state space and speed up the solution process in dynamic programming algorithm. Based on the actual production data of iron and steel enterprises and extended random examples, numerical experiments are carried out. The results show that the proposed improved strategy can break through the limit of solving ability. The optimal solution of the industrial scale problem is obtained in acceptable computing time by the branching pricing algorithm.
【作者单位】：东北大学工业与系统工程研究所;东北大学数学系;
【基金】：国家自然科学基金(71672032,71621061,71202151) 国家重点研发计划(2017YFB0304100)资助~~
【分类号】：O221;TG338

【相似文献】