Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14446
For citation please use:
Main Title: On Eulerian Extension Problems and their Application to Sequencing Problems
Author(s): Höhn, Wiebke
Jacobs, Tobias
Megow, Nicole
Type: Research Paper
URI: https://depositonce.tu-berlin.de/handle/11303/15673
http://dx.doi.org/10.14279/depositonce-14446
License: http://rightsstatements.org/vocab/InC/1.0/
Abstract: 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. For the new flowshop scheduling problem we give a full complexity classification for any machine configuration.
Subject(s): sequencing
Traveling Salesman Problem
no-wait flowshop
machine idle-times
Eulerian Extension
Issue Date: 2009
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2009, 08
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Report-008-2009.pdf
Format: Adobe PDF | Size: 176.25 kB
DownloadShow Preview
Thumbnail

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.