A Column Generation Based Diving Algorithm for Slab Assignment Problem Considering Order Completeness

Abstract

We address the slab assignment problem arising from the steelmaking industry. A Slab is the first solid intermediate product in the steel production process, both as an output of steelmaking and as a raw material for hot rolling. In steel plants, a common operational task involves assigning slabs to customer orders as raw material for subsequent production. Slabs that are not linked to any specific order are referred to as unassigned slabs. During production, a large number of unassigned slabs are inevitably generated, leading to significant material waste and high inventory costs. Therefore, it is essential to assign them to unfilled orders, in order to enhance slab utilization and reduce overall production costs. In this paper, we investigate a slab assignment problem that maximizes slab utilization and customer satisfaction. To characterize the problem, a binary integer linear programming model is formulated. To obtain high-quality solutions effectively, we develop a diving heuristic based on column generation, accelerated by a column generation stabilization strategy. The performance of the proposed algorithm is validated through computational experiments on slab assignment instances. The results show that the proposed algorithm outperforms the general MIP solvers for both small and large scale problems.