Sequencing and Scheduling in Coil Coating with Shuttles

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.

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.

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?

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.

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.

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.

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.

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.

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.