Models, algorithms and complexity for scheduling under uncertainty: On the tradeoffs between performance and adaptivity

• Applicant: Professorin Dr. Nicole Megow
• Subject Area: Theoretical Computer Science ; Mathematics
• Term: from 2012 to 2022
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 201423354

• Final Report Year: 2023

Final Report Abstract

Scheduling is a major research area studied from both practical and theoretical perspectives in computer science, mathematical optimization, and operations research. Applications range from traditional production scheduling and project planning to emerging resource management tasks in Internet technology, such as distributed cloud service networks and virtual machine allocation. A major challenge in solving such problems lies in the uncertainty about input data in dynamic and data-driven real-world environments: job arrival times are unknown, execution times are over- or underestimated, resource availabilities or processing speeds may not be known, etc. It is of major importance to the system performance to design algorithms that perform well even under uncertainty. In this project, we made substantial contributions to the area of scheduling under uncertainty. We designed first, or new and improved algorithms in the common frameworks of online and stochastic optimization as well as universal and robust, and real-time scheduling. We developed algorithmic and analytic tools for solving scheduling problems with uncertain input, such as unreliable machines, stochastic job processing times, or unknown job arrival times. We solved longstanding open problems and gave first results for newly proposed practice-driven models. A particular focus was on analyzing the tradeoff between the performance of an algorithm and the amount of adaptivity it requires. On the one hand, we aimed 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 were interested in good but simple algorithms that respect practice-driven adaptivity restrictions.

Publications

• Universal sequencing on a single machine. In: Proceedings of the 14th Conference on Integer Programming and Combinatorial Optimization (IPCO). Vol. 6080. LNCS. Springer, pp. 230–243.
  L. Epstein, A. Levin, J. Mestre, A. Marchetti-Spaccamela, N. Megow, M. Skutella, and L. Stougie
  
• Algorithms and Complexity for Periodic Real-Time Scheduling. In: ACM Transactions on Algorithms 9 pp. 601–619.
  V. Bonifaci, H.-L. Chan, A. Marchetti-Spaccamela, and N. Megow.
  
• On Eulerian extensions and their application to no-wait flowshop scheduling. In: Journal of Scheduling 15.3 pp. 295–309.
  W. Höhn, T. Jacobs, and N. Megow.
  
• Online Graph Exploration: New Results on Old and New Algorithms. In: Theoretical Computer Science 463, pp. 62–72.
  N. Megow, K. Mehlhorn, and P. Schweitzer.
  
• Scheduling real-time mixed-criticality jobs. In: IEEE Transactions on Computers 61(8) pp. 1140–1152.
  S. Baruah, V. Bonifaci, G. D’Angelo, H. Li, A. M. Spaccamela, N. Megow, and L. Stougie
  
• The offline sorting buffer problem is NP-hard. In: Theoretical Computer Science 423, pp. 11–18.
  H.-L. Chan, N. Megow, R. Sitters, and R. van Stee.
  
• The Power of Recourse for Online MST and TSP. In: Proceedings of the 39th International Colloquium on Automata, Languages and Programming (ICALP). Vol. 7391. LNCS. Springer, pp. 689–700.
  N. Megow, M. Skutella, J. Verschae, and A. Wiese.
  
• Universal sequencing on a single machine. In: SIAM Journal on Computing 41, pp. 565–586.
  L. Epstein, A. Levin, A. Marchetti-Spaccamela, N. Megow, J. Mestre, M. Skutella, and L. Stougie
  
• A New Approach to Online Scheduling: Approximating the Optimal Competitive Ratio. In: Proceedings of the 24st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). pp. 118–128.
  E. Günther, O. Maurer, N. Megow, and A. Wiese.
  
• Dual techniques for scheduling on a machine with varying speed. In: Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP). Vol. 7965. LNCS. Springer, pp. 745–756.
  N. Megow and J. Verschae.
  
• Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints. In: Proceedings of the 4th Conference on Innovations in Theoretical Computer Science (ITCS). pp. 495–504.
  N. Megow and J. Mestre.
  
• Polynomial-Time Exact Schedulability Tests for Harmonic Real-Time Tasks. In: Proceedings of RTSS. IEEE, pp. 236–245.
  V. Bonifaci, A. Marchetti-Spaccamela, N. Megow, and A. Wiese.
  
• A Tight 2-Approximation for Preemptive Stochastic Scheduling. In: Mathematics of Operations Research 39.4 pp. 1297–1310.
  N. Megow and T. Vredeveld.
  
• Packing a Knapsack of Unknown Capacity. In: Proceedings of the 31st Symposium on Theoretical Aspects of Computer Science (STACS).. Ed. by E. W. Mayr and N. Portier. Vol. 25. LIPIcs.
  Y. Disser, M. Klimm, N. Megow, and S. Stiller
  
• Scheduling and Packing Malleable and Parallel Tasks with Precedence Constraints of Bounded Width. In: Journal of Combinatorial Optimization 27, pp. 164–181
  E. Günther, F. König, and N. Megow.
  
• Clique partitioning with value-monotone submodular cost. In: Discrete Optimization 15 pp. 26–36.
  J. Correa and N. Megow
  
• Optimal Algorithms and a PTAS for Cost- Aware Scheduling. In: Proceedings of the 40th International Symposium on Mathematical Foundations of Computer Science (MFCS). Vol. 9235. LNCS. pp. 211–222.
  L. Chen, N. Megow, R. Rischke, L. Stougie, and J. Verschae.
  
• Randomization Helps Computing a Minimum Spanning Tree under Uncertainty. In: Proceedings of the 23rd European Symposium on Algorithms (ESA). Vol. 9294. LNCS. pp. 878–890.
  N. Megow, J. Meißner, and M. Skutella.
  
• Stochastic and Robust Scheduling in the Cloud. In: Proceedings of the 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX). Vol. 40. LIPIcs. pp. 175–186.
  L. Chen, N. Megow, R. Rischke, and L. Stougie.
  
• Universal Sequencing on an Unreliable Machine. In: Encyclopedia of Algorithms. Springer
  N. Megow and J. Mestre
  
• A New Approach to Online Scheduling: Approximating the Optimal Competitive Ratio. In: ACM Transactions on Algorithms 15:1– 15:34.
  E. Lübbecke, O. Maurer, N. Megow, and A. Wiese.
  
• An O(logm)-Competitive Algorithm for Online Machine Minimization. In: Proceedings of SODA. pp. 155–163.
  L. Chen, N. Megow, and K. Schewior
  
• Robustness and Approximation for Universal Sequencing. In: Gems of Combinatorial Optimization and Graph Algorithms Ed. by A. S. Schulz, M. Skutella, S. Stiller, and D. Wagner. Springer, pp. 133–141.
  N. Megow.
  
• The Power of Migration in Online Machine Minimization. In: Proceedings of SPAA. pp. 175–184
  L. Chen, N. Megow, and K. Schewior
  
• The Power of Recourse for Online MST and TSP. In: SIAM Journal on Computing 45 (3), pp. 859–880.
  N. Megow, M. Skutella, J. Verschae, and A. Wiese.
  
• Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments. In: 16th International Symposium on Experimental Algorithms (SEA). LIPIcs. 22:1–22:14.
  J. Focke, N. Megow, and J. Meißner
  
• Packing a Knapsack of Unknown Capacity. In: SIAM Journal on Discrete Mathematics 31.3 pp. 1477–1497
  Y. Disser, M. Klimm, N. Megow, and S. Stiller.
  
• Randomization Helps Computing a Minimum Spanning Tree under Uncertainty. In: SIAM Journal on Computing 46.4, pp. 1217–1240.
  N. Megow, J. Meißner, and M. Skutella.
  
• Scheduling Maintenance Jobs in Networks. In: Proceedings of the 10th International Conference on Algorithms and Complexity (CIAC). Vol. 10236. LNCS., pp. 19–30
  F. Abed, L. Chen, Y. Disser, M. Groß, N. Megow, J. Meißner, A. Richter, and R. Rischke
  
• An O(logm)-Competitive Algorithm for Online Machine Minimization. In: SIAM Journal on Computing 47.6 pp. 2057–2077.
  L. Chen, N. Megow, and K. Schewior
  
• Scheduling with Explorable Uncertainty. In: ITCS. Vol. 94. LIPIcs. 30:1–30:14.
  C. Dürr, T. Erlebach, N. Megow, and J. Meißner.
  
• Techniques for Scheduling on a Machine with Varying Speed. In: SIAM J. Discret. Math. 32.3 pp. 1541–1571.
  N. Megow and J. Verschae.
  
• A General Framework for Handling Commitment in Online Throughput Maximization. In: Proceedings of IPCO. Vol. 11480. LNCS. pp. 141–154.
  L. Chen, F. Eberle, N. Megow, K. Schewior, and C. Stein.
  
• On index policies for stochastic minsum scheduling. In: Operations Research Letters 47.3 pp. 213–218.
  F. Eberle, F. A. Fischer, J. Matuschke, and N. Megow
  
• Scheduling maintenance jobs in networks. In: Theor. Comput. Sci. 754 pp. 107–121
  F. Abed, L. Chen, Y. Disser, M. Groß, N. Megow, J. Meißner, A. T. Richter, and R. Rischke
  
• Scheduling Self-Suspending Tasks: New and Old Results. In: ECRTS. Vol. 133. LIPIcs. 16:1–16:23.
  J. Chen, T. Hahn, R. Hoeksma, N. Megow, and G. von der Brüggen.
  
• An Adversarial Model for Scheduling with Testing. In: Algorithmica 82.12 pp. 3630–3675.
  C. Dürr, T. Erlebach, N. Megow, and J. Meißner.
  
• Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics. In: MFCS. Vol. 170. LIPIcs. 18:1–18:15.
  M. Böhm, R. Hoeksma, N. Megow, L. Nölke, and B. Simon.
  
• Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments. In: ACM J. Exp. Algorithmics 25 pp. 1–20.
  J. Focke, N. Megow, and J. Meißner
  
• On the Complexity of Conditional DAG Scheduling in Multiprocessor Systems. In: IPDPS. IEEE, pp. 1061–1070.
  A. Marchetti-Spaccamela, N. Megow, J. Schlöter, M. Skutella, and L. Stougie.
  
• Online Minimum Cost Matching with Recourse on the Line. In: APPROX/RANDOM. Vol. 176. LIPIcs. 37:1–37:16.
  N. Megow and L. Nölke.
  
• Optimally Handling Commitment Issues in Online Throughput Maximization. In: ESA. Vol. 173. LIPIcs. 41:1–41:15.
  F. Eberle, N. Megow, and K. Schewior
  
• Fully Dynamic Algorithms for Knapsack Problems with Polylogarithmic Update Time. In: FSTTCS. Vol. 213. LIPIcs. 18:1–18:17.
  F. Eberle, N. Megow, L. Nölke, B. Simon, and A. Wiese.
  
• Optimal algorithms for scheduling under time-of-use tariffs. In: Annals of Operations Research 304.1, pp. 85–107.
  L. Chen, N. Megow, R. Rischke, L. Stougie, and J. Verschae
  
• Orienting (Hyper)graphs Under Explorable Stochastic Uncertainty. In: ESA. Vol. 204. LIPIcs. 10:1–10:18
  E. Bampis, C. Dürr, T. Erlebach, M. S. de Lima, N. Megow, and J. Schlöter
  
• Speed-Robust Scheduling - Sand, Bricks, and Rocks. In: IPCO. Vol. 12707. LNCS. Springer,pp. 283–296.
  F. Eberle, R. Hoeksma, N. Megow, L. Nölke, K. Schewior, and B. Simon.
  
• Throughput Scheduling with Equal Additive Laxity. In: CIAC. Vol. 12701. LNCS. Springer pp. 130–143.
  M. Böhm, N. Megow, and J. Schlöter
  
• Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty. In: ESA
  T. Erlebach, M. S. de Lima, N. Megow, and J. Schlöter
  
• On Hop-Constrained Steiner Trees in Tree-Like Metrics. In: SIAM J. Discret. Math. 36.2 pp. 1249–1273.
  M. Böhm, R. Hoeksma, N. Megow, L. Nölke, and B. Simon.
  
• Online load balancing with general reassignment cost. In: Operations Research Letters 50.3 pp. 322–328.
  S. Berndt, F. Eberle, and N. Megow.
  
• Robustification of Online Graph Exploration Methods. In: AAAI. AAAI Press, pp. 9732–9740.
  F. Eberle, A. Lindermayr, N. Megow, L. Nölke, and J. Schlöter.
  
• Speed-Robust Scheduling - Sand, Bricks, and Rocks. In: Mathematical Programming
  F. Eberle, R. Hoeksma, N. Megow, L. Nölke, K. Schewior, and B. Simon.
  
• Throughput Scheduling with Equal Additive Laxity. In: Operations Research Letters 50.5, pp. 463–469.
  M. Böhm, N. Megow, and J. Schlöter.