Scheduling of parallel continuous annealing lines with alternative processing modes to optimize efficiency under tardiness constraints

Continuous annealing is a core process in steel cold-rolling facilities. It is used to set desired material properties by passing coils of flat steel through a high-temperature furnace in a precisely controlled manner. High efficiency is achieved by feeding the steel through the furnace in the form of a continuous strand. For this purpose, the coils are welded together before being fed into the furnace. 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. To address this problem, we formulate a mixed-integer linear program based on a model from the literature and propose a two-phase heuristic solution procedure. The procedure combines an opening phase using shortest path algorithms and local search with an improvement phase based on problem-specific decompositions according to the principles of an Fix-and-Optimize procedure. The results show that our heuristic outperforms a state-of-the-art commercial solver in finding good solutions in short computation time. Based on a sensitivity analysis for several industry-inspired data sets, we observe a trade-off between efficiency and tardiness which strongly depends on the operating conditions.