TU Berlin

Elisabeth LübbeckePublications

Page Content

to Navigation

Publications

Disser, Yann and Klimm, Max and Lübbecke, Elisabeth
Scheduling Bidirectional Traffic on a Path.
In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP), pp. 406-418, 2015.  [pdf]


Günther, Elisabeth and König, Felix G. and Megow, Nicole
Scheduling and Packing Malleable and Parallel Tasks with Precedence Constraints of Bounded Width.
Journal of Combinatorial Optimization, Vol. 27, pp. 164-181, 2014.  [pdf]


Günther, Elisabeth and Maurer, Olaf and Megow, Nicole and Wiese, Andreas
A New Approach to Online Scheduling: Approximating the Optimal Competitive Ratio.
In Proceedings of the 24st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013), pp. 118-128, 2013.  [pdf]


Günther, Elisabeth and König, Felix G. and Megow, Nicole
Scheduling and Packing Malleable Tasks with Precedence Constraints of Bounded Width.
In Approximation and Online Algorithms: 7th International Workshop, WAOA 2009, Lecture Notes in Computer Science, Vol. 5893, pp. 170-181, Springer, 2010.  [pdf]


Technical Reports

Ship Traffic Optimization for the Kiel Canal
Citation key LuebbeckeLuebbeckeMoehring2014
Author Lübbecke, Elisabeth and Lübbecke, Marco E. and Möhring, Rolf H.
Year 2014
Number 4681
Month 12
Institution Optimization Online
Abstract We introduce, discuss, and solve a hard practical optimization problem which we call the ship traffic control problem (STCP). Since we plan bi-directional traffic, STCP relates to, and in fact generalizes train timetabling on single-track networks. The objective of finding quickest routes motivates the integration of recent algorithmic ideas from dynamic collision-free routing of automated guided vehicles. We offer a unified view of routing and scheduling which blends simultaneous (global) and sequential (local) solution approaches to allot scarce network resources to a fleet of vehicles in a collision-free manner. This leads us to construct a fast online heuristic. The STCP originates from the Kiel Canal which is the basis for the trade between the countries of the baltic area and the rest of the world. As traffic is projected to significantly increase, the canal is planned to be enlarged in a billion Euro project. Our work forms the mathematical and algorithmic basis for a tool to evaluate the different enlargement options. In view of computational experiments on real traffic data expert planners approved that our combinatorial algorithm is well-suited for this decision support. With the help of instance-dependent lower bounds we assess the quality of our solutions which significantly improves upon manual plans. We are confident that our ideas can be extended to other application areas like train timetabling and collision-free routing, also in more general networks.
Link to original publication Download Bibtex entry

Günther, Elisabeth and Maurer, Olaf and Megow, Nicole and Wiese, Andreas
A New Approach to Competitive Analysis: Approximating the Optimal Competitive Ratio.
Preprint 031, Technische Universität Berlin, Institut für Mathematik, 2011.  [pdf]


Günther, Elisabeth and König, Felix G. and Megow, Nicole
Scheduling and Packing Malleable Tasks with Precedence Constraints of Bounded Width.
Preprint 020, Technische Universität Berlin, Institut für Mathematik, 2009.
Approximation and Online Algorithms: 7th International Workshop, WAOA 2009, to appear as a volume of Lecture Notes in Computer Science, Springer-Verlag, 2009..  [pdf]


Extended Abstracts

Günther, Elisabeth and Lübbecke, Marco E. and Möhring, Rolf H.
Challenges in Scheduling when Planning the Ship Traffic on the Kiel Canal.
In Proceedings of the 10th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2011), 2011.  [pdf]


Günther, Elisabeth and Lübbecke, Marco E. and Möhring, Rolf H.
Ship Traffic Optimization for the Kiel Canal.
In Proceedings of the Seventh Triennial Symposium on Transportation Analysis (TRISTAN 2010), 2010.  [pdf]


Günther, Elisabeth and König, Felix G. and Megow, Nicole
The Bin Scheduling Problem.
In Proceedings of the 9th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2009), 2009.  [pdf]


Master's Thesis

Günther, Elisabeth 
Bin Scheduling: Partitionieren verformbarer Jobs mit Nebenbedingungen.
Master's thesis (Diplomarbeit), Technische Universität Berlin, Germany, December 2008.
(Awarded with a 3rd Clara von Simson-Preis 2009)

Copyright notice

The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe