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

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

0.00 Avg rating0 Votes
Article ID: iaor20083249
Country: United Kingdom
Volume: 34
Issue: 10
Start Page Number: 3001
End Page Number: 3015
Publication Date: Oct 2007
Journal: Computers and Operations Research
Authors: , ,
Keywords: scheduling, programming: integer, programming: dynamic
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.

Reviews

Required fields are marked *. Your email address will not be published.