摘要
研究了连铸–轧制在热装、温装和冷装混流生产模式下的一类新型轧批调度问题.以最小化温装钢坯(热钢锭)缓冷(等待)导致的热能损失和连轧机架切换带来的产能损失为目标,建立了整数规划模型.由于商业优化软件难以在有限时间内直接求得模型的最优解甚至可行解,提出利用Dantzig-Wolfe分解技术将原模型分解为主问题和子问题,采用列生成算法对主问题和子问题进行迭代求解得到原问题的紧下界,最后以列生成算法作为定界机制嵌入分支–定界框架中形成分支–定价算法,执行分支搜索过程以获得整数最优解.本文还从影响分支–定价算法性能的要素出发提出改进策略.针对主问题,提出列生成和拉格朗日松弛混合求解策略来抑制单一列生成算法的尾效应.针对价格子问题,在动态规划算法中提出了基于占优规则和标号下界计算方法来及早消除无效状态空间,加速求解过程.以钢铁企业的实际生产数据和扩展的随机算例进行了数值实验,结果显示所提出改进策略能够突破求解能力的限制,使分支–定价算法在可接受计算时间内求得工业规模问题的最优解.
This paper studies a new type of rolling batch scheduling problem arising in continuous casting and rolling processes which are linked by the hybrid production mode of direct hot charge rolling （DHCR）, hot charge rolling （HCR） and cold charge rolling （CCR）. The problem is formulated as an integer programming model with the objective of minimizing heat energy loss due to cooling （Waiting） of HCR slabs （Hot ingots） and productivity loss caused by changeover of rolling shelves. Since the commercial optimization software is difficult to obtain an optimal solution or even a feasible solution of the model within a limited CPU time, the model is decomposed into a master problem and a set of subproblems using the Dantzig-Wolfe decomposition. The master problem and subproblems are iteratively solved through column generation algorithm to obtain a tighter lower bound of the original problem. Finally, the column generation algorithm acting as a bounding mechanism is embedded into the branch-and-bound framework to form a branch-and-price algorithm which performs the branch search process to obtain an integer optimal solution. Furthermore, key factors affecting the performance of the algorithm are analyzed and corresponding improvement strategies are proposed. For the master problem, a solution strategy of hybriding column generation and Lagrangian relaxation is proposed to restrain the tailing-off effect of column generation. For the pricing subproblem, a dominance rule and label lower bound calculation based method is proposed to eliminate non-promising state space early in the dynamic programming algorithm such that the solution procedure is speeded up. Numerical experiments are carried out on actual production data provided by a steel company and random instances extended from actual production data. The results show that the proposed improvement strategies can break through the limitation of the solving ability and enable the branch-and-price algorithm to solve industrial scale problem optimality within an acceptable CPU time.
出处
《自动化学报》
EI
CSCD
北大核心
2017年第7期1178-1189,共12页
Acta Automatica Sinica
基金
国家自然科学基金(71672032
71621061
71202151)
国家重点研发计划(2017YFB0304100)资助~~
关键词
连铸–轧制
混流生产
列生成
分支–定价
动态规划
Continuous-casting and rolling, hybrid production, column generation, branch-and-price, dynamic programming
