Modelling and a segmented dynamic programming-based heuristic approach for the slab stack shuffling problem

摘要

This paper studies the slab stack shuffling (SSS) problem in the slab yard, which is a key logistics problem between the continuous casting stage and the hot rolling mill in the steel industry. The problem is to choose appropriate slabs for a sequence of rolling items, from their respective candidate slab sets (families) with a view to reducing the resulting shuffling workload. Although the SSS problem has been investigated by a few researchers, the problem under consideration has several new features. One of them is that the shuffled slab will not return the original stack but remain at the new position. Another requires that every selected slab be taken out in time, which will result in balancing the crane workloads among the storage areas of the slab yard to a degree. In addition, the local similarity of slab families is also considered, the closer the items in the rolling sequence, the more the common slabs between the corresponding families. For the problem, an integer programming model is proposed by considering the above features and requirements. For small-scaled problem, a dynamic programming approach is first constructed to obtain its optimal solution. For the practical scale, due to its intractability, we propose a segmented dynamic programming (SDP)-based heuristic, which partitions the sequence of items into a series of segments, each of which corresponds to a subproblem. The subproblems are solved sequentially using the dynamic programming. And the reassignment strategy of common slabs and the exchange strategy of candidate slabs are designed to improve the heuristic. Two interesting properties of the problem are also derived to speed up the SDP-based heuristic approach. The experiment results show that the heuristic is very close to the optimum in average solution quality for the small-scaled problem, obviously better than the CP Optimizer for the medium scale, and can reduce the crane workload by 10.76% on average for the practical scale.