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
  (Siehe online unter https://doi.org/10.1007/978-3-642-13036-6_18)
• 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.
  (Siehe online unter https://doi.org/10.1145/2390176.2390182)
• 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.
  (Siehe online unter https://doi.org/10.1007/s10951-011-0241-1)
• 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.
  (Siehe online unter https://doi.org/10.1016/j.tcs.2012.06.034)
• 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
  (Siehe online unter https://doi.org/10.1109/tc.2011.142)
• 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.
  (Siehe online unter https://doi.org/10.1016/j.tcs.2011.12.077)
• 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.
  (Siehe online unter https://doi.org/10.1007/978-3-642-31594-7_58)
• 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
  (Siehe online unter https://doi.org/10.1137/110844210)
• 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.
  (Siehe online unter https://doi.org/10.1137/1.9781611973105.9)
• 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.
  (Siehe online unter https://doi.org/10.1007/978-3-642-39206-1_63)
• 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.
  (Siehe online unter https://doi.org/10.1145/2422436.2422490)
• 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.
  (Siehe online unter https://doi.org/10.1109/rtss.2013.31)
• A Tight 2-Approximation for Preemptive Stochastic Scheduling. In: Mathematics of Operations Research 39.4 pp. 1297–1310.
  N. Megow and T. Vredeveld.
  (Siehe online unter https://doi.org/10.1287/moor.2014.0653)
• 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
  (Siehe online unter https://doi.org/10.4230/LIPIcs.STACS.2014.i)
• 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.
  (Siehe online unter https://doi.org/10.1007/s10878-012-9498-3)
• Clique partitioning with value-monotone submodular cost. In: Discrete Optimization 15 pp. 26–36.
  J. Correa and N. Megow
  (Siehe online unter https://doi.org/10.1016/j.disopt.2014.11.001)
• 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.
  (Siehe online unter https://doi.org/10.1007/978-3-662-48054-0_18)
• 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.
  (Siehe online unter https://doi.org/10.1007/978-3-662-48350-3_73)
• 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.
  (Siehe online unter https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.175)
• Universal Sequencing on an Unreliable Machine. In: Encyclopedia of Algorithms. Springer
  N. Megow and J. Mestre
  (Siehe online unter https://doi.org/10.1007/978-3-642-27848-8_543-2)
• 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.
  (Siehe online unter https://doi.org/10.1145/2996800)
• An O(logm)-Competitive Algorithm for Online Machine Minimization. In: Proceedings of SODA. pp. 155–163.
  L. Chen, N. Megow, and K. Schewior
  (Siehe online unter https://doi.org/10.1137/1.9781611974331.ch12)
• 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.
  (Siehe online unter https://doi.org/10.1007/978-3-319-24971-1_13)
• The Power of Migration in Online Machine Minimization. In: Proceedings of SPAA. pp. 175–184
  L. Chen, N. Megow, and K. Schewior
  (Siehe online unter https://doi.org/10.1145/2935764.2935786)
• 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.
  (Siehe online unter https://doi.org/10.1137/130917703)
• 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
  (Siehe online unter https://doi.org/10.1145/3422371)
• 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.
  (Siehe online unter https://doi.org/10.1137/16m1070049)
• 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.
  (Siehe online unter https://doi.org/10.1137/16m1088375)
• 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
  (Siehe online unter https://doi.org/10.1007/978-3-319-57586-5_3)
• 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
  (Siehe online unter https://doi.org/10.1137/17m116032x)
• Scheduling with Explorable Uncertainty. In: ITCS. Vol. 94. LIPIcs. 30:1–30:14.
  C. Dürr, T. Erlebach, N. Megow, and J. Meißner.
  (Siehe online unter https://dx.doi.org/10.4230/LIPIcs.ITCS.2018.30)
• Techniques for Scheduling on a Machine with Varying Speed. In: SIAM J. Discret. Math. 32.3 pp. 1541–1571.
  N. Megow and J. Verschae.
  (Siehe online unter https://doi.org/10.1137/16m105589x)
• 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.
  (Siehe online unter https://doi.org/10.1007/978-3-030-17953-3_11)
• 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
  (Siehe online unter https://doi.org/10.1016/j.orl.2019.03.007)
• 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
  (Siehe online unter https://doi.org/10.1016/j.tcs.2018.02.020)
• 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.
  (Siehe online unter https://doi.org/10.4230/LIPIcs.ECRTS.2019.16)
• 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.
  (Siehe online unter https://doi.org/10.1007/s00453-020-00742-2)
• 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.
  (Siehe online unter https://doi.org/10.4230/LIPIcs.MFCS.2020.18)
• 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
  (Siehe online unter https://doi.org/10.1145/3422371)
• 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.
  (Siehe online unter https://doi.org/10.1109/ipdps47924.2020.00112)
• 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.
  (Siehe online unter https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.37)
• Optimally Handling Commitment Issues in Online Throughput Maximization. In: ESA. Vol. 173. LIPIcs. 41:1–41:15.
  F. Eberle, N. Megow, and K. Schewior
  (Siehe online unter https://doi.org/10.4230/LIPIcs.ESA.2020.41)
• 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.
  (Siehe online unter https://doi.org/10.4230/LIPIcs.FSTTCS.2021.18)
• 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
  (Siehe online unter https://doi.org/10.1007/s10479-021-04059-3)
• 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
  (Siehe online unter https://doi.org/10.4230/LIPIcs.ESA.2021.10)
• 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.
  (Siehe online unter https://doi.org/10.1007/978-3-030-73879-2_20)
• Throughput Scheduling with Equal Additive Laxity. In: CIAC. Vol. 12701. LNCS. Springer pp. 130–143.
  M. Böhm, N. Megow, and J. Schlöter
  (Siehe online unter https://doi.org/10.1007/978-3-030-75242-2_9)
• Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty. In: ESA
  T. Erlebach, M. S. de Lima, N. Megow, and J. Schlöter
  (Siehe online unter https://doi.org/10.4230/LIPIcs.ESA.2022.49)
• 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.
  (Siehe online unter https://doi.org/10.1137/21m1425487)
• Online load balancing with general reassignment cost. In: Operations Research Letters 50.3 pp. 322–328.
  S. Berndt, F. Eberle, and N. Megow.
  (Siehe online unter https://doi.org/10.1016/j.orl.2022.03.007)
• 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.
  (Siehe online unter https://doi.org/10.1609/aaai.v36i9.21208)
• Speed-Robust Scheduling - Sand, Bricks, and Rocks. In: Mathematical Programming
  F. Eberle, R. Hoeksma, N. Megow, L. Nölke, K. Schewior, and B. Simon.
  (Siehe online unter https://doi.org/10.1007/s10107-022-01829-0)
• Throughput Scheduling with Equal Additive Laxity. In: Operations Research Letters 50.5, pp. 463–469.
  M. Böhm, N. Megow, and J. Schlöter.
  (Siehe online unter https://doi.org/10.1016/j.orl.2022.06.007)