TU Berlin

FG Kombinatorische Optimierung und Graphenalgorithmen2009

COGA 5-Wheel


zur Navigation

Preprints 2009

On Eulerian Extension Problems and their Application to Sequencing Problems
Zitatschlüssel Report-008-2009
Autor Höhn, Wiebke and Jacobs, Tobias and Megow, Nicole
Jahr 2009
Nummer 008
Monat feb
Notiz Corresponding publication to appear in the Journal of Scheduling
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung We introduce a new technique for solving several sequencing problems. We consider Gilmore and Gomory's variant of the Traveling Salesman Problem and two variants of no-wait two-stage 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. This view 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.
Link zur Publikation Download Bibtex Eintrag



Schnellnavigation zur Seite über Nummerneingabe