Externally Funded Research Projects

Uncertainty in the input data or even lack of information are an omnipresent issue in real-life decision making. The framework of optimization under explorable uncertainty deals with problems where part of the input data is uncertain but can be obtained by a query operation at a certain cost. Challenging questions are: Which input elements shall be queried? How much information is required to achieve a certain solution quality?

The goal of this project is to develop new techniques for balancing the cost for data exploration and the benefit for the solution quality. Our focus lies on designing algorithms with mathematical guarantees on the quality of obtained solutions. We advance the state of the art by quantifying the power and limits of parallel decision-making and by studying new models beyond the classical worst-case considerations. We envision a unified methodology for coping with (stochastic) explorable uncertainty. We investigate also recent models such as learning-augmented algorithms taking error-prone predictions into account.

Project head: Nicole Megow
Project term: 2023-2026
Funded by: German Research Foundation (DFG)

Our proposal addresses the challenges arising in the deployment of robots to our everyday tasks including the human-machine interactions. These robots are required to work autonomously in natural environments, in the presence of other robots and humans. Autonomous robots, especially robots in the area of passenger transportation, social security, and last-mile delivery have to solve network design problems, routing issues and exploration problems. A key aspect of the proposal is the development of algorithms that run efficiently, decentralized, flexible for human intervention. We aim for decision support that is optimized, resource-efficient and fair to improve service quality of robots for humans.

Project heads: Nicole Megow, Daniel Schmand, Sebastian Siebertz
Project term: 2022-2023
Funded by: Minds Media Machines (MMM)

We investigate the school admission mechanism for entering a secondary school (grade 5) in Bremen. Families indicate up to three public schools of choice (Oberschule and/or Gymnasium). A centralized procedure allocates available school places to students according to their preferences and taking school priorities into account. We analyze the currently used allocation mechanism as well as alternatives and evaluate their solutions based on various criteria.

This project is part of a larger initiative to rigorously investigate the school admission process in Bremen including a quantitative, algorithmic study of the allocation mechanism, a study of the influence of the mechanism on social segregation and social composition at schools, and the identification of school selection criteria of families in Bremen.

Project head: Nicole Megow
Project partners: Kerstin Schneider (U Wuppertal, Wuppertal Research Institute for the Economics of Education) and Michael Windzio (U Bremen, SOCIUM Research Center in Inequality and Social Policy)
Project term: 2021
Funded by: Senator for Children and Education, Free Hanseatic City of Bremen

Timely allocation of scarce resources is essential in many applications. Our group developed efficient methods for scheduling and managing resources in the hot rolling mill of the steel manufacturer ArcelorMittal Bremen. We optimized the grinding process of worn-out rolls which involves the selection of appropriate profiles needed for future rolling programs as well as the scheduling of the complex grinding tasks on several machines.

Project head: Nicole Megow
Principal investigators: Lukas Nölke, Alexander Lindermayr
Project term: 2019
Partner: ArcelorMittal Bremen GmbH

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)

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)

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

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
Link: Emmy Noether

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

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
Funded by: T.A. Cook Consultants

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
Funded by: Patrick Corporation Ltd.