direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 01-2009

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Sequencing and Scheduling in Coil Coating with Shuttles
Published as Integrated Sequencing and Scheduling in Coil Coating in Management Science 57(4), pp. 647-666, 2011.
Finalist for the EURO Excellence in Practice Award 2009.
not available
coil coating, sequencing, scheduling, real-world application, steel
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 coatings may necessitate time-consuming setup work. In most coating stages one can choose between two parallel color tanks in order to reduce setup times. As a complicating consequence, setup times for a coil may depend on the whole sequence of predecessors. 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 scheduling. It is instrumental for building a fast heuristic which 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.
Download as [PDF] [ps]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe