Scheduling Theory

Course in Winter 2017/18

Scheduling involves the timely allocation of tasks to scarce resources with the objective to minimize some cost function. Such problems appear in various applications, e.g., in production planning, logistics, project management, or when operating computing systems. This lecture will cover: a classification of scheduling models, complexity of scheduling problems, the design and analysis of exact and approximation algorithms, single and parallel machine models, flow shop and open shop problems. The focus lies on the design and mathematical analysis of algorithms using combinatorial techniques, dynamic programming and linear programming.

Prof. Dr. Nicole Megow (Email)
M.Sc. Franziska Eberle (Email)
Time & Room:

Lecture: Mon 14-16 in room MZH 1110 (Megow)
Exercise: Mon 16-18 in room MZH 1110 (Eberle)

The first lecture is on Monday, October 23, 2017.
The first exercise class is on Monday, October 30, 2017 and starts at 16:00 (sharp).
Date Topic Material
23/10/2017 Introduction, three field notation, single machine, Smith's rule orga slides, introduction, notes by J. Winter
30/10/2017 Single machine: 1|(prec)|L_max (EDF), 1|prec|f_max (Lawler's algorithm) notes by T. Hahn
06/11/2017 Single machine: 1||sum U_j (Moore Hodgson), parallel machines: P||sum C_j (SPT), R||sum C_j (matching), P|pmtn|C_max (McNaughton Wrap around) notes by J. Cepok
13/11/2017 no lecture, no exercise
20/11/2017 Q|pmtn|C_max (Horvath, Lam, Sethi 1977), short intro to linear programming notes by M. Speer
27/11/2017 Complexity of scheduling problems notes by T. Hahn
04/12/2017 Intro approximation algorithms, P|(prec)|C_max: list scheduling, LPT
11/12/2017 Optimal poly-time alg for P2|prec,p_j=1|C_max, fast single machine relaxation for P|r_j,pmtn|sum w_jC_j notes by T. Haslop
18/12/2017 P|r_j,pmtn|sum w_jC_j preemptive WSPT 2-approx, conversion technique, alpha-points
08/01/2018 randomized algorithms, 1|r_j|sum w_jC_j randomized scheduling by alpha-points [Chekuri et al.], [Skutella]
15/01/2018 Bin packing, PTAS for makespan minimization notes, paper by Hochbaum, Shmoys
22/01/2018 FPTAS for makespan minimization, FPTAS for knapsack notes

Lecture Notes: For writing the lecture notes in LaTeX, please use this template together with the package scribe. If you have troubles accessing the lecture notes, please send an email to Franziska.

Homework: Please hand in the exercises before the lecture on the indicated date with your name and immatriculation number written on your solution.
Exercise Sheet Hand in in the lecture on Exercise Class
Exercise 1 October 30 October 30
Exercise 2 November 6 November 6
Exercise 3 November 20 November 20
Exercise 4 November 27 November 27
Exercise 5 December 4 December 4
Exercise 6 December 11 December 11
Exercise 7 Solution 7.1 Solution 7.2 December 18 December 18
Exercise 8 January 8 January 8
Exercise 9 January 15 January 15
Exercise 10 January 22 January 22
Exercise 11 January 29 January 29
Literature: The course is based on parts of the literature below and recent research articles that will be added later.
  • M. L. Pinedo. Scheduling: Theory, Algorithms, and Systems. Springer, 2012.
  • J. Y.-T. Leung. Handbook of Scheduling: Algorithms, Models, and Performance Analysis. Chapman & Hall/CRC, 2004.
  • F. Jaehn and E. Pesch: Ablaufplanung. Einführung in Scheduling. Springer, 2014.