Menu

• Team
  • Prof. Dr. Nicole Megow
  • Dr. Syamantak Das
  • Dr. Ruben Hoeksma
  • Franziska Eberle
  • Lukas Nölke
• Teaching
• Projects
• Research Seminar
• Offers

Scheduling Invasive Multicore Programs Under Uncertainty

This project is part of the Transregional Collaborative Research Center (TCRC) 89: Invasive Computing (InvasIC). It complements the project area A, Fundamentals, Language and Algorithm Research, with methods for coping with uncertainties. The goal is to explore algorithms and analytical techniques for scheduling and resource management using the invasive computing paradigm. More information can be found here.

Project head: Nicole Megow
Project term: 2018-2022
Funded by: German Research Foundation (DFG)

Query complexity meets optimization under uncertain input

The goal of this project is to explore the applicability of techniques from query complexity theory in the context of optimization under uncertain input when there is the option of exploring (querying) uncertain data at certain cost.

Project heads: Nicole Megow and Christoph Dürr
Project term: 2016
Funded by: Bayerisch-Französisches Hochschulzentrum (BFHZ)

Design and Operation of Infrastructure Networks under Uncertainty

This project deals with uncertainty exploration in complex planning processes such as in the design, operation and maintenance of metropolitan infrastructures. We particularly focus on network design and scheduling problems where parts of the input data underlie uncertainty. In contrast to standard models for data uncertainty, we assume that the unknown data can be explored at a certain cost, e.g. additional time, money, energy, etc. In this project, we develop algorithmic methods on how to balance the cost for data exploration with the actual benefit for the quality of solution to the optimization problem under consideration.

Project heads: Nicole Megow and Martin Skutella
Project term: 2014-2017
Funded by:  Einstein Foundation Berlin through ECMath - Einstein Center for Mathematics Berlin

Scheduling under Uncertainty: On Performance-Adaptivity Tradeoffs (Emmy Noether Group)

In this project we study fundamental theoretical questions on practically relevant algorithms for problems from stochastic, online, and real-time scheduling. We design algorithmic and analytic tools for solving scheduling problems with uncertain input, such as unreliable machines, stochastic job processing times, or unknown job arrival times. Our major goal is to study thoroughly the tradeoff between the performance of an algorithm and the amount of adaptivity it requires. On the one hand, we aim for best possible algorithms which are potentially highly dynamic, i.e., scheduling decisions may adapt arbitrarily to the instantiated problem data. On the other hand, we are interested in good but simple algorithms that respect practice-driven adaptivity restrictions.

Project head: Nicole Megow
Project term: 2012-2018
Funded by:  German Research Foundation (DFG), within Emmy Noether Programme

Scheduling on Unreliable Machines: On Performance-Adaptivity Tradeoffs

In this project, we study problems in the area of scheduling on unreliable machines which means that we assume that machines may change their processing speed up to full breakdowns. We develop algorithms with mathematically provable performance guarantees. We particularly focus on quantifying the tradeoff between the performance of an algorithm and the amount of adaptivity it requires to achieve this.

Principal investigator: Nicole Megow
Partner investigator: Julian Mestre
Project term: 2011-2012
Funded by:  German Research Foundation (DFG), bilateral cooperation

Shutdown and Turnaround Scheduling in Chemical Manufacturing

In this project we investigated the problem of scheduling large-scale maintenance in industrial plants that require the entire shutdown of production units for disassembly, comprehensive inspection, and renewal. We derived mathematical models and algorithms for this so-called turnaround scheduling that include different features such as time-cost trade-off, precedence constraints, external resource units, resource leveling, different working shifts, and risk analysis. A case study with real-world turnaround scheduling problems was carried out in cooperation with the management consulting company T.A. Cook Consultants and two of their customers at chemical manufacturing sites. Some of our methods have been succesfully integrated into SAP and MS Project Management software tools... More details can be found here and in our publication Decision Support and Optimization in Shutdown and Turnaround Scheduling (Informs J. on Computing, 2011).

Project head: Rolf H. Möhring
Principal investigators: Nicole Megow and Jens Schulz
Project term: 2006-2008
Partner:  T.A. Cook Consultants

Increasing Container Handling Efficiency at Port Botany

In this project we investigate the problem of operating a landside container exchange area that is serviced by multiple semi-automated rail mounted gantry cranes (RMGs) that are moving on a single bi-directional traveling lane. The gantry cranes are a scarce resource and handle the bulk of container movements. We develop algorithms to manage the container exchange facility, including the scheduling of cranes, the control of associated short-term container stacking, and the allocation of delivery locations for trucks and other container transporters. A computational evaluation shows that our methods can find effective solutions on real-world data (from Port Botany terminal in Sydney) that are at most 8% above a lower bound on optimal RMG utilization. Details can be found in our article Optimizing the Landside Operation of a Container Terminal.

Principal investigators: Gary Froyland, Thorsten Koch, Nicole Megow, and Emily Duane.
Project term: 2005
Partner:  Patrick Corporation Ltd.