SUBJECT
Title
Scheduling theory
Type of instruction
lecture
Level
master
Faculty
Part of degree program
Credits
3
Recommended in
Semesters 1-4
Typically offered in
Autumn/Spring semester
Course description
Classification of scheduling problems; one-machine scheduling, priority rules (SPT, EDD, LCL), Hodgson algorithm, dynamic programming, approximation algorithms, LP relaxations. Parallel machines, list scheduling, LPT rule, Hu's algorithm. Precedence constraints, preemption. Application of network flows and matchings. Shop models, Johnson's algorithm, timetables, branch and bound, bin packing.
Readings
T. Jordán, Scheduling, lecture notes