direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 08-2009

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Title
On Eulerian Extension Problems and their Application to Sequencing Problems
Authors
Publication
Coorpesponding publication to appear in the Journal of Scheduling as On Eulerian Extensions and their Application to No-wait Flowshop Scheduling.
Classification
not available
Keywords
Sequencing, Traveling Salesman Problem, No-Wait Flowshop, Machine Idle-Times, Eulerian Extension
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.
Source
Download as [PDF]
Title: Source

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe