A branch-and-price algorithm to solve the molten iron allocation problem in iron and steel industry

作者：Tang Lixin^*; Wang Gongshu; Liu Jiyin

来源：Computers & Operations Research, 2007, 34(10): 3001-3015.

DOI：10.1016/j.cor.2005.11.010

• molten iron allocation
• integer programming
• column generation
• branch-and-price
• state-space relaxation
• dynamic programming

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.

• 出版日期2007-10
• 单位东北大学