TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 23.05.2012


Page Content

to Navigation

2-Union Graphs in Concurrent Setup Scheduling

Wiebke Höhn (Ph.D. Student TU Berlin)

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. In this talk, we focus on the underlying graph
theoretical model for concurrent setup scheduling. We show that the
problem can be formulated as Independent Set Problem in a special
class of 2-union graphs. For graphs corresponding to a constant number
of coating stages  we propose a polynomial-time dynamic programme. In
contrast when the number of stages is part of the problem input, we
show the problem to be strongly NP-hard. This is joint work with Felix
König, Marco Lübbecke and Rolf Möhring.

23.05.2012 16:15
Wiebke Höhn
TEL 512

Back to the research colloquium site.


Quick Access

Schnellnavigation zur Seite über Nummerneingabe