TU Berlin

Talk 25.05.2011

isti-logo

Inhalt

zur Navigation

Es gibt keine deutsche Übersetzung dieser Webseite.

On Eulerian Extension Problems and their Application to Sequencing Problems

Wiebke Höhn (TU Berlin)

We introduce a technique for solving several sequencing problems. We consider Gilmore and Gomory's variant of the Traveling Salesman Problem and two variants of no-wait flowshop scheduling, the classical makespan minimization problem and a new problem arising in the multistage production process in steel manufacturing. Our technique is based on an intuitive interpretation of sequencing problems as Eulerian Extension Problems: Given some directed (multi-) graph, one aims at finding minimum cost set of additional arcs such that the resulting graph is Eulerian. This interpretation reveals new structural insights and leads to elegant and simple algorithms and proofs for this ancient type of problems. As a major effect, we compute not only a single solution; instead, we represent the entire space of optimal solutions. For the new flowshop scheduling problem we give a full complexity classification for any machine configuration.

This is joint work with Tobias Jacobs (National Institute of Informatics, Tokyo) and Nicole Megow (MPII, Saarbrücken).

date
speaker
location
language
25.05.2011 14:15
Wiebke Höhn
FR 6510
german/
english*

* Language is depending on the audience.

Back to the research colloquium site.

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe