Description:
Scheduling is a vibrant and mathematically rich area at the intersection of combinatorics, optimisation, and algorithm design. Many mathematical and algorithmic techniques have been first developed for scheduling problems. The course therefore not only introduces students to the rich scheduling landscape, but also teaches various mathematical models and algorithmic techniques.
We begin with classical machine scheduling problems from relatively simple single machine problems to more intricate problems concerning multiple machines and highly heterogenous jobs. The course covers exact methods, (e.g., dynamic and linear programming), approximation algorithms and heuristics (e.g., local search and problem-specific algorithms).
Advanced topics include online scheduling, stochastic scheduling, and game-theoretic models, introducing students to modern research directions in the field. The course concludes with scheduling problems from practice and what type of algorithmic approaches have been taken to find solutions for them.
Prerequisites
- Bachelor level knowledge of analysis, linear algebra, and probability.
- General familiarity with formal proofs, preferably in the context of algorithm analysis.
- Linear programming (modelling, not necessarily solving, see, e.g., Chapter 1 of Linear Programming: Foundations and Extensions by Robert J. Vanderbei)
- Dynamic programming (see, e.g., Chapter 5 of Integer Programming by Laurence A. Wolsey).
- Familiarity with NP-Hardness and approximation algorithms (in week 1, material will be provided to repair any gaps in this prerequisite).
Note on compatibility with pre-fall-2026 Scheduling: Due to the large overlap, this course is not compatible with the course Scheduling that Mastermath offered until the spring semester of 2026.
Aim of the course
In this course, you learn several techniques and models from combinatorial optimisation through a broad variety of scheduling problems. After successful completion of this course you can
- recognise several models in the context of machine scheduling;
- apply and analyse known algorithmic techniques and design new algorithms based on these techniques;
- address questions related to the computational complexity of different scheduling problems.
Rules about Homework/Exam
A written exam accounts for 100% of the grade. With each lecture, a set of homework exercises needs to be solved in groups of three students. Students need a pass on the homework to participate in the exam.
Lecture notes/Literature
1. M.L. Pinedo (2012). Scheduling. Theory, Algorithms, and Systems. Fourth edition. Springer.
2. P. Brucker (2007). Scheduling Algorithms. Fifth edition. Springer.
3. M.L. Pinedo (2009). Planning and Scheduling in Manufacturing and Services. Second edition. Springer.
4. Additional lecture notes and scientific papers (provided)
All the books are freely available online through your university library.
- Docent: Ruben Hoeksma
- Docent: Tim Oosterwijk