Scheduling theory investigates the assignment of tasks to resources with the intent of minimizing some cost.
A classical example is assigning jobs of various lengths to machines, so that the load of the machines
is as balanced as possible, for example by minimizing the load of the busiest machine. Naturally, scheduling
has a myriad of applications both inside and outside of computing, including logistics, operation management,
worker allocation as well as scheduling CPU-bound tasks and scheduling virtual machines in a cloud environment.
This course focuses on scheduling theory as a branch of theoretical computer science, and our main goal is to
design optimal algorithms -- or, if not optimal, then at least provably efficient ones.
Throughout the course, we shall introduce the main algorithmic tools used for in the area of scheduling theory,
and present select major results in the area which use these tools. In particular, we will focus on
optimal polynomial-time algorithms for scheduling problems, approximation algorithms, and online algorithms.
Sample topics:
* Introduction to scheduling theory, overview of the area, Graham notation.
* List scheduling, online list scheduling. List scheduling on machines with different speeds.
* Dynamic programming and its applications in scheduling.
* Preemptive list scheduling minimizing the sum of weighted completion times.
* Scheduling on unrelated parallel machines.
* Online throughput scheduling of unit and equal-size jobs.
* Semi-online scheduling: known optimum makespan, known sum of processing times.
The course is aimed at Master-level students of computer science, but advanced Bachelor-level students
with interest in algorithm design are also welcome. Knowledge of basic algorithms and data structures is required.
Basic familiarity with the theory of online computation and the theory of linear optimization will be useful at
later stages of the course, but is not mandatory.
The exercise sessions will consist of problem solving practice in class, and grades for the exercise sessions will
be determined by two larger homework sheets throughout the semester. An oral exam on the topics of the lecture
will determine the final grade.
The course will be taught completely in English.
Literature:
* M. L. Pinedo. Scheduling: Theory, Algorithms, and Systems. Springer, 2008.
* Peter Brucker: Scheduling Algorithms. Springer, 2007.
* D. P. Williamson, D. B. Shmoys: The Design of Approximation Algorithms. Cambridge University Press, 2012. Available online: https://www.designofapproxalgs.com/
* B. Chen, C. N. Potts, G. J. Woeginger: A review of machine scheduling: Complexity, algorithms and approximability. In D. Z. Du and P. M. Pardalos. Handbook of Combinatorial Optimization, 1998.
Similar courses at other universities:
* https://www.cs.dartmouth.edu/~deepc/Courses/S09/lectures.html
* https://www-m9.ma.tum.de/WS2015/Scheduling
