A branch-and-price algorithm to solve the molten iron allocation problem in iron and steel industry |
| |
Authors: | Lixin Tang Gongshu Wang Jiyin Liu |
| |
Affiliation: | 1. The Logistics Institute, Northeastern University, Shenyang, China;2. Business School, Loughborough University, Loughborough, Leicestershire LE11 3TU, UK |
| |
Abstract: | The molten iron allocation problem (MIAP) is to allocate molten iron from blast furnaces to steel-making furnaces. The allocation needs to observe the release times of the molten iron defined by the draining plan of the blast furnaces and the transport time between the iron-making and steel-making stages. Time window constraints for processing the molten iron must be satisfied to avoid freezing. The objective is to find a schedule with minimum total weighted completion time. This objective reflects the practical consideration of improving steel-making efficiency and reducing operation cost caused by the need for reheating. Such a problem can be viewed as a parallel machine scheduling problem with time windows which is known to be NP-hard. In this paper, we first formulate the molten iron allocation problem as an integer programming model and then reformulate it as a set partitioning model by applying the Dantzig–Wolfe decomposition. We solve the problem using a column generation-based branch-and-price algorithm. Since the subproblem of column generation is still NP-hard, we propose a state-space relaxation-based dynamic programming algorithm for the subproblem. Computational experiments demonstrate that the proposed algorithm is capable of solving problems with up to 100 jobs to optimality within a reasonable computation time. |
| |
Keywords: | Molten iron allocation Integer programming Column generation Branch-and-price State-space relaxation Dynamic programming |
本文献已被 ScienceDirect 等数据库收录! |