A branch-and-price algorithm for scheduling parallel continuous steel annealing lines

Continuous annealing is a crucial and characteristic process in the production of high-quality flat steel. Integrated decisions on the selection of processing modes for steel strips, their allocation to parallel lines, and sequencing on these lines, taking into account tardiness and sequence constraints, render the scheduling of this process a highly complex problem. Since it is an operational problem, heuristic approaches are used in practice to quickly generate efficient schedules. However, to evaluate such heuristics, an exact solution of the problem is also of interest. We present an exact branch-and-price algorithm based on a set-partitioning formulation that decomposes the problem by lines and exploits the similarities of the problem structure to the generalized vehicle routing problem. The pricing problems are solved with a tailored labeling algorithm. We also present several acceleration techniques. A computational study shows that our algorithm finds exact solutions to the problem faster and more reliably than a commercial solver. The performance of the algorithm depends on the specific production setting, characterized by the number of lines and coils to be scheduled and the tardiness requirements. Our approach performs particularly well when the number of parallel lines is high and tardiness is not allowed.