EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

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

Invited abstract in session WD-49: Mathematical programming for machine scheduling, stream Lot Sizing, Lot Scheduling and Production Planning.

Wednesday, 14:30-16:00
Room: M1 (building: 101)

Authors (first author is the speaker)

1. Sebastian Wegel
Institut für Produktionswirtschaft, Leibniz Universität Hannover

Abstract

Continuous annealing is a core process in steel cold-rolling facilities, where order-specific pieces of flat steel, wound up to coils, are processed through an annealing furnace to achieve defined material properties. To enable a continuous process, the coils are welded together before entering the line. Whenever two consecutive coils are incompatible, a special dummy coil called stringer is used to connect them, which reduces efficiency and adds costs and emissions. We consider the scheduling of coils with specific due dates and alternative order-specific processing modes on parallel heterogeneous lines. The problem is to simultaneously assign coils to lines and sequence them on these lines with a defined processing mode with adherence to tardiness constraints while minimizing the number of stringers needed and the associated energy consumption. To address this problem, we formulate a mixed-integer linear program and propose a branch-and-price algorithm based on a Dantzig-Wolfe decomposition by lines to solve it. The pricing subproblems are solved using a labeling algorithm. The approach is implemented using the SCIP framework. We present the underlying problem decomposition, implementation, and some first numerical results using a heuristic and a state-of-the-art commercial solver as a benchmark.

Keywords

Status: accepted

Back to the list of papers