自动化学报2017，Vol.43Issue(7)：1178-1189,12.DOI:10.16383/j.aas.2017.c160316
连铸-轧制混流生产模式下轧批调度问题的分支-定价算法
Branch-and-price Algorithm for Rolling Batch Scheduling Problem in Continuous-casting and Rolling Processes with Hybrid Production Mode
摘要
Abstract
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.关键词
连铸-轧制/混流生产/列生成/分支-定价/动态规划Key words
Continuous-casting and rolling/hybrid production/column generation/branch-and-price/dynamic programming引用本文复制引用
汪恭书,刘静宜,唐立新..连铸-轧制混流生产模式下轧批调度问题的分支-定价算法[J].自动化学报,2017,43(7):1178-1189,12.基金项目
国家自然科学基金(71672032,71621061,71202151),国家重点研发计划(2017YFB0304100)资助 Supported by National Natural Science Foundation of China(71672032,71621061,71202151) and National Key Research and Development Program of China (2017YFB0304100) （71672032,71621061,71202151）
