A Branch and Price Algorithm for Crane Assignment and Scheduling in Slab Yard

In a steel industry, a slab yard plays a role of a buffer between continuous casting stage and rolling mill. An effective assignment and scheduling of cranes can guarantee the operation efficiency in the slab yard. This work studies a multicrane scheduling problem with noncrossing constraints of slabs. A mixed-integer programming model is used to formulate the problem that minimizes the whole traveling distance of all the cranes and ensures the workload balance among cranes. As it is an NP-hard problem, classical programming mathematical methods are difficult to get an optimal solution for large-size instances. Thus, we develop a branch and price algorithm to solve this problem. First, we formulate the model as a generalized set covering problem and a set partition problem. Then, we solve them and combine the solutions to obtain the solution of the original problem. Finally, we conduct computational experiments based on real data from an iron-steel plant. The comparisons of proposed methods with an exact solution method show its effectiveness. Note to Practitioners - This work deals with a multicrane scheduling problem. Aiming to minimize the total traveling distance of all the cranes, it establishes a mixed-integer programming model with a workload balance constraint on cranes. It presents a branch and price algorithm to solve the problem whose solution complexity grows exponentially with problem size. The integration of crane assignment and scheduling enables the better utilization of cranes and faster service in iron-steel enterprises and, hence, improving customer satisfaction. The experimental results reveal the effectiveness of the proposed approach. It can readily be put into use in the steel industry.