Seminar: Scheduling: Theory and Algorithms
General Information
Course instructors: Andreas S. Schulz, Maximilian von Aspern, Felix Buld
Scheduling problems appear in many applications, ranging from manufacturing processes to healthcare.
In this seminar, we will look at various such problems, new and old, 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 in the world of scheduling.
Schedule
| October 21 | Submit your topic preferences on our Moodle Page |
| January 12 | Submit your presentation draft on Moodle to receive feedback |
| February 06 | Presentations |
Topics
[A] Bosman, Thomas, et al. "Fixed-order scheduling on parallel machines." Integer Programming and Combinatorial Optimization: 20th International Conference, IPCO 2019, Ann Arbor, MI, USA, May 22-24, 2019, Proceedings 20. Springer International Publishing, 2019.
[B] Jäger, Sven, Alexander Lindermayr, and Nicole Megow. "The Power of Proportional Fairness for Non-Clairvoyant Scheduling under Polyhedral Constraints." arXiv preprint arXiv:2408.14310 (2024).
[C] Jäger, Sven, and Philipp Warode. "Simple Approximation Algorithms for Minimizing the Total Weighted Completion Time of Precedence-Constrained Jobs." 2024 Symposium on Simplicity in Algorithms (SOSA). Society for Industrial and Applied Mathematics, 2024.
[D] Lambers, Roel, Rudi Pendavingh, Frits Spieksma, and Céline MF Swennenhuis. "Scheduling jobs that change over time." arXiv preprint arXiv:2312.09683 (2023).
[E] T’kindt, Vincent, Federico Della Croce, and Alessandro Agnetis. "Single machine adversarial bilevel scheduling problems." European Journal of Operational Research 315.1 (2024): 63-72.
[F] Vijayalakshmi, Vipin Ravindran, Marc Schröder, and Tami Tamir. "Minimizing total completion time with machine-dependent priority lists." European Journal of Operational Research 315.3 (2024): 844-854.