Seminar: Scheduling: Theory and Algorithms
General Information
Course instructors: Andreas S. Schulz, Felix Buld
Scheduling problems appear in many applications, from manufacturing and logistics to healthcare. In this seminar, we will look at various such problems, classical and modern, deterministic and stochastic, and strategies to solve them. We focus on applying techniques from combinatorial optimization and linear programming to develop beautiful and fast solution algorithms. Further, we will learn how to design good approximation algorithms for NP-hard problems and study modern frameworks as explorable uncertainty or learning-augmented algorithms in the scheduling world.
Some helpful advice for your presentation can be found here.
The seminar will take place on Tuesdays from 10:00 to 12:00 in the seminar room 01.06.011 (https://nav.tum.de/en/room/5606.01.011) in the MI-building.
Schedule
| March 14 | Send your topic preferences (e.g. A > B > C > D > E) to Felix Buld via e-mail. |
| April 29 | Kick-Off-Meeting and Introduction to Scheduling |
| May 06 | Deterministic Scheduling [A,C] |
| May 13 | Scheduling Under Uncertainty [D,F] |
| May 20 | Scheduling with Testing Budgets or Predictions [I,M] |
| May 27 | Explorable Uncertainty and Flow Shop Scheduling [K,G] |
| June 03 | Learning-Augmented Algorithms for Scheduling [N,O] |
Topics
| [A] | Jäger, S. and Warode, P., 2024. Simple Approximation Algorithms for Minimizing the Total Weighted Completion Time of Precedence-Constrained Jobs. In 2024 Symposium on Simplicity in Algorithms (SOSA) (pp. 82-96). Society for Industrial and Applied Mathematics. |
| [C] | Lambers, R., Pendavingh, R., Spieksma, F. and Swennenhuis, C.M., 2023. Scheduling jobs that change over time. arXiv preprint arXiv:2312.09683. |
| [D] | Pinson, N. and Spieksma, F.C., 2019. Online interval scheduling on two related machines: the power of lookahead. Journal of Combinatorial Optimization, 38(1), pp.224-253. |
| [F] | Skutella, M., Sviridenko, M. and Uetz, M., 2016. Unrelated Machine Scheduling with Stochastic Processing Times. Mathematics of Operations Research, 41(3), pp.851-864. |
| [G] | Hertrich, C., Weiß, C., Ackermann, H., Heydrich, S. and Krumke, S.O., 2020. Scheduling a proportionate flow shop of batching machines. Journal of Scheduling, 23(5), pp.575-593. |
| [I] | Damerius, C., Kling, P., Li, M., Xu, C. and Zhang, R., 2023. Scheduling with a Limited Testing Budget: Tight Results for the Offline and Oblivious Settings. In 31st Annual European Symposium on Algorithms (ESA 2023). Schloss-Dagstuhl-Leibniz Zentrum für Informatik. |
| [K] | Dürr, C., Erlebach, T., Megow, N. and Meißner, J., 2020. An Adversarial Model for Scheduling with Testing. Algorithmica, 82(12), pp.3630-3675. |
| [M] | Lindermayr, A. and Megow, N., 2022. Permutation Predictions for Non-Clairvoyant Scheduling. In Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures (pp. 357-368). |
| [N] | Liang, Y.C., Stein, C. and Wei, H.T., 2023. Learning-Augmented Online Packet Scheduling with Deadlines. arXiv preprint arXiv:2305.07164. |
| [O] | Lattanzi, S., Lavastida, T., Moseley, B. and Vassilvitskii, S., 2020. Online Scheduling via Learned Weights. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 1859-1877). Society for Industrial and Applied Mathematics. |