The refining scheduling problem with crane non-collision constraint in steelmaking process

This paper studies the refining scheduling problem in which there are two or more overhead traveling cranes with non-collision constraint for handling material in the steel plant. This scheduling problem is formulated as a mixed integer programming model. We show that the scheduling problem is strongly NP-hard and present some properties of the optimal solution. We develop the heuristic algorithms to find the near-optimal solutions. We derive two lower bounds and analyze the worst case performance of the heuristic algorithms. Computational experiments are carried out to evaluate the performance of the heuristic algorithms. The numerical results show that some of the heuristic algorithms can find effective solutions for most problems of realistic sizes.