关键词: 批量轧制调度问题, 参数耦合, 分散搜索, 动态规划, K-最短路径问题

Abstract: There existed parameter coupling between rolled pieces and roll during rolling process of cold rolled temper mill. Aimming at this problem, a mathematical model for batch rolling scheduling problem under dynamic equipment changes was constructed. By taking roll wear function as the breakthrough point, the complex scheduling problem was divided into three tractable sub-problems through piecewise linearzation simplifying of roll wear curve. A hybrid strategy which combined discrete search with dynamic programming was developed：rolled pieces were assigned into different stages according to their roughness firstly, and then the K-Constrained Shortest Path Problem (K-CSPP) of each stage was solved by scatter search, and finally combined the solutions of sub-problems into a feasible solution by dynamic programming. Effectiveness of the proposed algorithm was verified by real production data of big steel mill.

Key words: batch rolling scheduling problem, parameter coupling, scatter search, dynamic programming, K-constrained shortest path problem