DFG Emmy Noether Group

Scheduling under Uncertainty: On Performance-Adaptivity Tradeoffs

Principal investigator: Nicole Megow (TU Berlin 2012-2015, TU Munich 2015-2016, U Bremen 2016-2022)

Project members:

Jens Schlöter, 2019-2022, PhD student, U Bremen
Martin Böhm, 2018-2020, Postdoc, U Bremen, now lecturer at the University of Wrocław
Ruben Hoeksma, 2017-2019, Postdoc, U Bremen, now assistant professor at U Twente, The Netherlands
Syamantak Das, 2016-2017, Postdoc, U Bremen, now assistant professor at Indraprastha Institute of Information Technology Delhi
Lin Chen, 2013-2015, Postdoc, TU Berlin and TU Munich, now assistant professor University of Houston, Texas, USA
Kevin Schewior, 2013-2016, Phd student and postdoc, TU Berlin and TU Munich, now assistant professor at University of Southern Denmark
Roman Rischke, 2012-2016, PhD student, TU Berlin and TU Munich, now researcher at Fraunhofer Institut for Telecommunications, Heinrich Hertz Hertz Institute (HHI)

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.

Online Algorithms

Online optimization deals with problems, where parts of the input are initially unknown. A prominent subcategory are problems, where parts of the input arrive over time and irrovocable decisions have to be made without knowledge of the future. For example, consider a scheduling problem where the jobs arrive over time and we have to decide immediately upon the arrival of a job on which machine we want to schedule it. We design and analyse algorithms for online problems in a worst-case setting, where we assume that an adversary fixes the still unknown input in a worst-case manner.

Universal and Robust Optimization

In robust optimization we are still dealing with uncertainty in the problem input, but are given a selection of scenarios that might occur. Our goal is to find solutions for the underlying problem that satisfy some performance guarantees or constraints for every given scenario. In contrast to online optimization, algorithms for robust optimization are often non-adaptive. That is, we ask for a single solution that performs well on any given scenario.

Stochastic Optimization

In stochastic uncertainty, we again consider problems with uncertainty in the input. In contrast to the online setting we assume that the uncertain parts of the input follow some (known or unknown) fixed probability distribution. Such probabilistic information models a priori knowledge on the uncertain parts of the input that, for example, may stem from past statistical information. As an example consider a scheduling problem where the processing times of the jobs are unknown but follow given probability distributions. The goal is to optimize the objective in expectation.

Explorable Uncertainty

In explorable uncertainty we consider problems with uncertainty in numeric input parameters. In contrast to the other models, new information on the uncertain parts of the input does not arrive passively over time, but we can actively obtain new information by querying it. As queries are costly, the goal is to minimize the number of queries necessary to obtain sufficient information to solve the underlying optimization problem.

Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty arxiv.org
Thomas Erlebach, Murilo Santos de Lima, Nicole Megow, Jens Schlöter
ESA 2022

Throughput Scheduling with Equal Additive Laxity sciencedirect.com
Martin Böhm, Nicole Megow, Jens Schlöter
Operations Research Letters

On Hop-Constrained Steiner Trees in Tree-Like Metrics arxiv.org siam.org pdf
M. Böhm, R. Hoeksma, N. Megow, L. Nölke and B. Simon
SIAM J. Discrete Math. 36(2):1249-1273, 2022.

Speed-Robust Scheduling: Sand, Bricks, and Rocks
Franziska Eberle, Ruben Hoeksma, Nicole Megow, Lukas Nölke, Kevin Schewior, Bertrand Simon
Mathematical Programming (accepted)

Non-clairvoyant Scheduling with Predictions Revisited arxiv.org
Alexander Lindermayr and Nicole Megow
SPAA 2022

Online load balancing with general reassignment cost pdf sciencedirect.com
Sebastian Berndt, Franziska Eberle, Nicole Megow
Operations Research Letters 50(3): 322-328, 2022

Robustification of Online Graph Exploration Methods arxiv.org
Franziska Eberle, Alexander Lindermayr, Nicole Megow, Lukas Nölke, Jens Schlöter
AAAI 2022

Double Coverage with Machine-Learned Advice arxiv.org
Alexander Lindermayr, Nicole Megow, Bertrand Simon
ITCS 2022

Explorable Uncertainty Meets Decision-Making in Logistics springer.com
Nicole Megow and Jens Schlöter
Dynamics in Logistics: 35-56, 2021 springer.com

Fully Dynamic Algorithms for Knapsack Problems with Polylogarithmic Update Time arxiv.org
Franziska Eberle, Nicole Megow, Lukas Nölke, Bertrand Simon, Andreas Wiese
Accepted for publication at FSTTCS 2021

Orienting (Hyper)graphs Under Explorable Stochastic Uncertainty pdf
Evripidis Bampis, Christoph Dürr, Thomas Erlebach, Murilo S. de Lima, Nicole Megow, Jens Schlöter
Accepted for publication at ESA 2021

Optimal Algorithms for Scheduling under Time-of-Use Tariffs pdf DOI
Lin Chen, Nicole Megow, Roman Rischke, Leen Stougie and Jose Verschae
Annals or Operations Research 304(1): 85-107, 2021

Throughput Scheduling with Equal Additive Laxity springer.com
Martin Böhm, Nicole Megow, Jens Schlöter
CIAC 2021

Speed-Robust Scheduling arxiv.org
Franziska Eberle, Ruben Hoeksma, Nicole Megow, Lukas Nölke, Kevin Schewior, Bertrand Simon IPCO
2021

Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments
Jacob Focke, Nicole Megow, Julie Meißner
ACM Journal of Experimental Algorithmics 25(1), Article 1.14, 2020

Computing a Minimum-Cost k-hop Steiner Tree in Tree-Like Metrics PDF
M. Böhm, R. Hoeksma, N. Megow, L. Nölke and B. Simon
In Proc. of the 45th International Symposium on Mathematical Foundations of Computer Science 18:1-18:15 (MFCS2020)

An Adversarial Model for Scheduling with Testing
Christoph Dürr, Thomas Erlebach, Nicole Megow and Julie Meißner
Algorithmica 82(12): 3630-3675, 2020

Online Minimum Cost Matching with Recourse on the Line PDF
N. Megow and L. Nölke.
In Proc. of the 23rd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems 37:1-37:16 (APPROX 2020)

Optimally Handling Commitment Issues in Online Throughput Maximization pdf dagstuhl.de
F. Eberle, N. Megow, and K. Schewior.
Proceedings of ESA 2020, pp. 41:1-41:15, 2020.

On the Complexity of Conditional DAG Scheduling in Multiprocessor Systems
A. Marchetti-Spaccamela, N. Megow, J. Schlöter, M. Skutella, and L. Stougie
Proceedings of IPDPS 1061-1070, 2020

A General Framework for Handling Commitment in Online Throughput Maximization pdf springer.com
L. Chen, F. Eberle, N. Megow, K. Schewior, and C. Stein.
Mathematical Programming 183(1): 215-247, 2020

A General Framework for Handling Commitment in Online Throughput Maximization pdf springer.com
L. Chen, F. Eberle, N. Megow, K. Schewior, C. Stein.
Proceedings of IPCO 2019, pp. 141-154, 2019.

Scheduling Self-Suspending Tasks: New and Old Results
J.J. Chen, R. Hoeksma, T. Hahn, N. Megow, G. von der Brueggen
Proceedings of ECRTS, 16:1-16:23, 2019.

On Index Policies for Stochastic Minsum Scheduling sciencedirect.com
F. Eberle, F. Fischer, J. Matuschke, N. Megow
Operations Research Letters, 47(3): 213-218, 2019.

Scheduling Maintenance Jobs in Networks PDF
F. Abed, L. Chen, Y. Disser, M. Groß, J. Meißner, N. Megow, A.T. Richter, R. Rischke
Theoretical Computer Science 754: 107-121, 2019. Special issue of STACS (invited).

Scheduling with Explorable Uncertainty PDF springer.com
C. Dürr, T. Erlebach, J. Meißner and N. Megow.
In Proc. of the 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), 30:1-30:14, 2018.

An O(log m)-Competitive Algorithm for Online Machine Minimization PDF siam.org
L. Chen, N. Megow, K. Schewior
SIAM Journal on Computing 47(6), 2057–2077, 2018.

Dual techniques for scheduling on a machine with varying speed PDF siam.org
N. Megow, J. Verschae
SIAM Journal on Discrete Mathematics 32(3): 1541-1571, 2018.

Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments PDF
J. Focke, J. Meißner, N. Megow
In Proc. of the 16th International Symposium on Experimental Algorithms (SEA 2017), LIPIcs, Article No. 22; pp. 22:1–22:14, 2017.

Scheduling Maintenance Jobs in Networks PDF
F. Abed, L. Chen, Y. Disser, M. Groß, J. Meißner, N. Megow, A.T. Richter and R. Rischke
In Proc. of the 10th International Conference on Algorithms and Complexity (CIAC 2017), LNCS 10236, pp. 19–30, 2017.

Randomization Helps Computing a Minimum Spanning Tree under Uncertainty PDF
J. Meißner, N. Megow, M. Skutella
SIAM Journal on Computing 46(4): 1217-1240, 2017.

Packing a Knapsack of Unknown Capacity PDF
Y. Disser, M. Klimm, N. Megow, S. Stiller
SIAM Journal on Discrete Mathematics 31(3): 1477-1497, 2017.

Universal Sequencing on an Unreliable Machine
N. Megow, Julian Mestre
Encyclopedia of Algorithms 2016: 2304-2308.

The Power of Migration in Online Machine Minimization PDF
L. Chen, N Megow and K. Schewior
In Proc. of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2016), pp. 175-184, 2016.

An O(log m)-Competitive Algorithm for Online Machine Minimization PDF
L. Chen, N. Megow and K. Schewior
In Proc. of the 27th ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), pp. 155-163, 2016.

A New Approach to Online Scheduling: Approximating the Optimal Competitive Ratio
E. Lübbecke, O. Maurer, N. Megow, A. Wiese
ACM Transactions on Algorithms 13(1), pp. 15:1-15:34, 2016.

The Power of Recourse for Online MST and TSP PDF
N. Megow, M. Skutella, J. Verschae, A. Wiese
SIAM Journal on Computing. 45-3, pp. 859-880, 2016

Universal Sequencing on an Unreliable Machine
N. Megow, Julian Mestre
Encyclopedia of Algorithms 2016: 2304-2308.

Randomization Helps Computing a Minimum Spanning Tree under Uncertainty PDF
J. Meißner, N. Megow and M. Skutella
In Proc. of the 23rd European Symposium on Algorithms (ESA 2015), LNCS 9294, pp. 878-890, Springer, 2015.

Stochastic and Robust Scheduling in the Cloud PDF
L. Chen, N. Megow, R. Rischke and L. Stougie
In Proc. of the 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2015), LIPIcs 40, pp. 175-186, 2015.

Optimal Algorithms and a PTAS for Cost-Aware Scheduling
L. Chen, n. Megow, R. Rischke, L. Stougie and J. Verschae
In Proc. of the 40th International Symposium on Mathematical Foundations of Computer Science (MFCS 2015), LNCS 9235, pp. 211-222, 2015.

Packing a Knapsack of Unknown Capacity PDF
Y. Disser, M. Klimm, N. Megow, S. Stiller
In Proc. of the 31st Symposium on Theoretical Aspects of Computer Science (STACS 2015), pp. 276-287, 2015

Meeting deadlines: How much speed suffices? PDF PDF
S. Anand, N. Garg, N. Megow
In Proc. of the 38th International Colloquium on Automata, Languages and Programming (ICALP 2011), LNCS 6755, pages 232-243, Springer, 2011.
Erratum for "Meeting deadlines: How much speed suffices?", 2015.

Clique partitioning with value-monotone submodular cost PDF
J. Correa, N. Megow
Discrete Optimization, Vol. 15, pp. 26-36, 2015.

Robustness and Approximation for Universal Sequencing
Gems of Combinatorial Optimization and Graph Algorithms 2015: 133-141.

Scheduling and Packing Malleable and Parallel Tasks with Precedence Constraints of Bounded Width PDF
E. Günther, F. König, N. Megow
Journal of Combinatorial Optimization, Vol. 27, pp. 164-181, 2014.

A Tight 2-Approximation for Preemptive Stochastic Scheduling PDF
N. Megow, T. Vredeveld
Mathematics of Operations Research, Vol. 39, pp. 1297-1310, 2014

An Gap example on the (W)SEPT Policy
W.C. Cheung, F. Fischer, J. Matuschke, N. Megow
2014.

Polynomial-time exact schedulability tests for harmonic real-time tasks PDF
V. Bonifaci, A Marchetti-Spaccamela, N. Megow, A. Wiese
In Proc. of the 34th IEEE Real-Time Systems Symposium (RTSS 2013), pp. 236-245, 2013.

Dual techniques for scheduling on a machine with varying speed PDF
N. Megow, J. Verschae
In Proc. of the 40th International Colloquium on Automata, Languages and Programming (ICALP 2013), LNCS 7965, pp. 745-756, Springer, 2013.

Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints PDF
N. Megow, J. Mestre
In Proc. of the 4th Conference on Innovations in Theoretical Computer Science (ITCS 2013), pp. 495-504, 2013.

A New Approach to Online Scheduling: Approximating the Optimal Competitive Ratio PDF
E. Günther, O. Maurer, N. Megow, A. Wiese
In Proc. of the 24st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013), pp. 118-128, 2013.

The Power of Recourse for Online MST and TSP
N. Megow, M. Skutella, J. Verschae, A. Wiese
In Proc. of the 39th International Colloquium on Automata, Languages and Programming (ICALP 2012), LNCS 7391, pages 689-700, Springer, 2012.

On Eulerian extensions and their application to no-wait flowshop scheduling PDF
W. Höhn, T. Jacobs, N. Megow
Journal of Scheduling, Vol. 15, pp. 295-309, 2012.

Algorithms and Complexity for Periodic Real-Time Scheduling PDF
V. Bonifaci, H.-L. Chan, A. Marchetti-Spaccamela
ACM Transactions on Algorithms, Vol. 9, pp. 601-619, 2012.

Scheduling real-time mixed-criticality jobs PDF1 PDF2
S. Baruah, V. Bonifaci, G. D'Angelo, H. Li, A. Marchetti-Spaccamela, N. Megow, Stougie, L.
IEEE Transactions on Computers, Vol. 61, pp. 1140-1152, 2012.

A note on sorting buffers offline PDF
H.-L. Chan, N. Megow, R. Sitters, R. van Stee
Theoretical Computer Science, Vol. 423, pp. 11-18, 2012.

Universal sequencing on a single unreliable machine PDF
L. Epstein, A. Levin, N. Megow, J. Mestre, A. Marchetti-Spaccamela, M. Skutella, L Stougie
SIAM Journal on Computing, Vol. 41, pp. 565-586, 2012.

Online graph exploration: New results on old and new algorithms PDF
K. Mehlhorn, N. Megow, P. Schweitzer
Theoretical Computer Science, Vol. 463, pp. 62-72, 2012.
Special Issue on Theory and Applications of Graph Searching Problems.

Updated by: Lukas Barning

RSS

Print page