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

• Antragstellerin: Professorin Dr. Nicole Megow
• Fachliche Zuordnung: Theoretische Informatik ; Mathematik
• Förderung: Förderung von 2012 bis 2022
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 201423354

• Erstellungsjahr: 2023

Zusammenfassung der Projektergebnisse

Scheduling ist ein wichtiges und etabliertes Forschungsgebiet welches hauptsächlich aus der Sicht der Informatik, der mathematischen Optimierung und dem Operations Research untersucht wird. Die Anwendungen reichen von klassischer Produktionsund Projektplanung bis hin zu moderner Ressourcenverwaltung in der Internettechnologie, wie z.B. in verteilten Cloud-Service-Netzen oder der Zuweisung virtueller Maschinen. Eine große Herausforderung bei der Lösung solcher Probleme liegt in der Unsicherheit in den Eingabedaten in dynamischen und datengetriebenen Praxissituationen: Die Aufträge sind im Vorhinein unbekannt, die Ausführungszeiten werden über- oder unterschätzt, die Verfügbarkeit von Ressourcen oder die-Prozessorgeschwindigkeit sind nicht bekannt usw. Für die Performanz von Systemen ist es von immenser Bedeutung, Algorithmen zu entwerfen, die auch unter Unsicherheit gut funktionieren. In diesem Projekt wurden wesentliche Beiträge im Gebiet des Scheduling unter Unsicherheit geleistet. Es wurden verschiedene Arten von Unsicherheit adressiert: Online- und stochastische Optimierung, universelle und robuste Optimierung und Real-time Scheduling. Es wurden neue algorithmische und analytische Methoden entwickelt zur Lösung von Schedulingproblemen mit Unsicherheit im Input, wie unzuverlässige Maschinen, stochastische Ausführungszeiten oder unbekannte Ankunftszeiten. Es wurden fundamentale offene Probleme in klassischen Modellen gelöst sowie erste Resultate für neue praxisorientierte Modelle erzielt. Ein besonderer Schwerpunkt lag auf der Analyse und Quantifizierung des Tradeoffs zwischen der Güte eines Algorithmus und der dafür erforderlichen Adaptivität, d.h. wie stark Entscheidungen an die instanziierten Problemdaten angepasst werden können. Einerseits wurden Algorithmen mit bestmöglicher Güte angestrebt, die potenziell hochdynamisch sind und andererseits wurden gute, aber einfache Algorithmen gesucht, die die praxisbedingten Einschränkungen der Adaptivität berücksichtigen.

Projektbezogene Publikationen (Auswahl)

• 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.