Combinatorial Optimization & Graph Algorithms group (COGA)Coil Coating

# Sequencing and Scheduling in Coil Coating with Shuttles

Project director: Prof. Dr. Rolf H. Möhring Wiebke HöhnDr. Felix G. KönigDr. Marco E. Lübbecke PSI Metals GmbHSalzgitter Flachstahl GmbH DFG Priority Programme 1307 "Algorithm Engineering" 2008 - 2009

## Problem Description

The final product in integrated steel production are so-called coils of sheet metal. In the last processing step before filling customer orders, these coils are coated with some from several hundreds of coating materials on the coil coating line.

Schematic view of the coil coating line.

In the current effort of many manufacturing industries to outsource basic production steps not considered their core competence, buyers of sheet metal increasingly often demand that the coils they buy already be coated to their specifications. For instance, the sheet metal used for car bodies already has an anti-corrosion coating before it arrives at the automotive plant for pressing; or the metal used for home appliances already has its typical white coating when it is bought from the steel supplier. This forces steel manufacturers to deal with an increasingly complex variety of coatings in the coil coating process.

As is typical for paint jobs, the coil coating process may be subject to long setup times, mainly for the cleaning of equipment, and thus very high setup cost. In order to reduce this cost, so-called shuttle coaters have been introduced. In our application, four coaters apply one of two required coating layers to either the top or the bottom side of a coil. Three of these coaters are shuttle coaters, i.e., they possess two separate tanks which allow to hold two different coatings at the same time. The advantage is twofold: The shuttle can be used to switch between two different coatings on the same coater at (essentially) no setup cost; or alternatively, the unused tank can be set up already while coating is performed from the other tank in the meantime.

Coils of different widths as they are processed in the coating line (from left to right), with and without shuttle coater. Setup work (such as color or roller changes) has to be performed whenever a coil has to be coated with another color or is wider tha

## Challenge

The introduction of shuttles significantly changes the flavor and the complexity of the sequencing problem. It necessitates the solution of an integrated resource allocation and scheduling problem for the evaluation of a given sequence: Which tank do we use for which coil, and how do we schedule setup work, possibly concurrently with production, without exceeding available work resources?

Components of necessary non-productive time.

## Tank Assignment Model

A good tank assignment aims to satisfy two, in a sense opposite, requirements: On the one hand, try to keep a roller and/or color for a subsequent coil in order to avoid setup whenever possible. On the other hand, try to use idle times on the tanks to perform setup work during regular production which otherwise might increase the makespan. Hence, try to maximize concurrent setup work that is accomplished by the scarce work resource. Clearly, the quality of a tank assignment w.r.t. the second goal can hardly be assessed without scheduling the scarce work resource to perform concurrent setup whenever made possible by the tank assignment.

Given a fixed sequence of coils, we model all possible tank assignments with feasible concurrent setup schedules as weighted nodes of a 2-union graph, i.e. a graph whose edge set is the union of edge sets of two interval graphs. In this model, a maximum weight independent set (MWIS) in the graph corresponds exactly to an optimal tank assignment and concurrent setup schedule.

Correspondence of conflicting saving rectangles and adjacent nodes in the 2-union graph.

We prove, that the MWIS problem in 2-union graphs remains strongly NP-hard, even when the graphs have a certain special structure resulting from the above model. Still, will describe a dynamic programming approach which is fixed-parameter tractable in the number of coaters.

## Algorithm

Because of the enormous complexity of the task, an optimal solution is currently out of reach. On top of that, quick computation times are indispensable for the practical usability of our algorithms: A plan covering 24 hours must be computed within 180 seconds. This is why intelligent heuristics are our design of choice: We use a classical genetic algorithm for generating sequences, exploiting the special cost structure for choosing the initial population. We repeatedly solve the tank assignment and scheduling problem for the evaluation of sequences by a fast heuristic for MWIS in 2-union graphs based on our fixes-parameter tractable algorithm.

As a final result, our algorithm produces high quality, fully detailed production plans for the entire coil coating problem.

## Lower Bounds

In order to asses the quality of our heuristic solutions, we have devised a mixed integer program (MIP) formulation of a special combinatorial relaxation of the problem. Setup cost for a coil depends - in the extreme case - on the entire solution, in particular on the entire tank assignment, prior to running it. Our relaxation now limits this dependency in limiting the number of coils which are considered when computing global setup cost, i.e. we don't look back too far. More precisely, we concatenate subsequences containing a constant number of coils, for which we exactly compute setup cost. In between subsequences we only consider local setup cost.

We were able to solve the resulting MIPs to (near) optimality. The computed solution values prove that our solutions are within 5-15% of a theoretical optimum for all tested instances. We have reason to believe that our solutions are actually even better than that.

Detail of the visualization of an integer optimal solution to our integer program with subsequences with 4 coils each.

In the visualization, each block represents one shuttle coater with its two tanks; the dark rectangles reflect the coils in the coating sequence. It is clearly visible that the integer program ignores global setup cost in between subsequences. The expert planner can also see where and when which type of setup has to be performed.

## Usage at Salzgitter Flachstahl

Our model takes into account all relevant aspects of production reality, including the subtasks of sequencing the coils and scheduling the color tanks and the scarce work resources to perform setup work. The integrity of the plans computed and the correctness of cost calculations have been verified by the planners in charge of the coil coating line at Salzgitter Flachstahl GmbH, Germany.

Compared to previous plans, the optimized solutions yield double-digit percentage reductions in makespan, greatly exceeding what was deemed possible.

Our optimization module has been in use for day-to-day planning at Salzgitter Flachstahl GmbH since December 2009.

## Publication

Citation key HoehnKoenigLuebbecke+2011 Höhn, Wiebke and König, Felix G. and Lübbecke, Marco E. and Möhring, Rolf H. 647–666 2011 10.1287/mnsc.1100.1302 Management Science 57 4 Finalist for the EURO Excellence in Practice Award 2009 Informs We consider a complex planning problem in integrated steel production. A sequence of coils of sheet metal needs to be color coated in consecutive stages. Different coil geometries and changes of colors necessitate time-consuming setup work. In most coating stages one can choose between two parallel color tanks. This can either reduce the number of setups needed or enable setups concurrent with production. A production plan comprises the sequencing of coils and the scheduling of color tanks and setup work. The aim is to minimize the makespan for a given set of coils. We present an optimization model for this integrated sequencing and scheduling problem. A core component is a graph theoretical model for concurrent setup scheduling. It is instrumental for building a fast heuristic that is embedded into a genetic algorithm to solve the sequencing problem. The quality of our solutions is evaluated via an integer program based on a combinatorial relaxation, showing that our solutions are within 10% of the optimum. Our algorithm is implemented at Salzgitter Flachstahl GmbH, a major German steel producer. This has led to an average reduction in makespan by over 13% and has greatly exceeded expectations.