On Eulerian Extension Problems and their Application to Sequencing Problems

dc.contributor.authorHöhn, Wiebke
dc.contributor.authorJacobs, Tobias
dc.contributor.authorMegow, Nicole
dc.date.accessioned2021-12-17T10:08:38Z
dc.date.available2021-12-17T10:08:38Z
dc.date.issued2009
dc.description.abstractWe 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.en
dc.identifier.issn2197-8085
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/15673
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-14446
dc.language.isoenen
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.ddc510 Mathematiken
dc.subject.othersequencingen
dc.subject.otherTraveling Salesman Problemen
dc.subject.otherno-wait flowshopen
dc.subject.othermachine idle-timesen
dc.subject.otherEulerian Extensionen
dc.titleOn Eulerian Extension Problems and their Application to Sequencing Problemsen
dc.typeResearch Paperen
dc.type.versionsubmittedVersionen
tub.accessrights.dnbfreeen
tub.affiliationFak. 2 Mathematik und Naturwissenschaften::Inst. Mathematikde
tub.affiliation.facultyFak. 2 Mathematik und Naturwissenschaftende
tub.affiliation.instituteInst. Mathematikde
tub.publisher.universityorinstitutionTechnische Universität Berlinen
tub.series.issuenumber2009, 08en
tub.series.namePreprint-Reihe des Instituts für Mathematik, Technische Universität Berlinen

Files

Original bundle
Now showing 1 - 1 of 1
Loading…
Thumbnail Image
Name:
Report-008-2009.pdf
Size:
176.25 KB
Format:
Adobe Portable Document Format

Collections