Scheduling
Lecture

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 algorithm, single and parallel machine models, flow shop and open shop problems.

Lectures: Prof. Dr. Nicole Megow
Tutorial management: Roman Rischke
Tutorials: Roman Rischke

News Schedule Lecture Notes Exercise Sheets Literature FAQ

News

The schedule for the oral exams can be found here. The oral exams will take place in room 02.04.040.

Schedule

Lectures

Day Time Room Lecturer
Wed 8:30-10:00 00.09.022 Prof. Dr. N. Megow

Tutorial Classes

Day Time Room
Wed 10:15-11:45 02.04.011

For participation in the tutorial classes, registration on TUMonline (Exercises for Scheduling [MA5219]) is mandatory.

Lecture Notes

pdf Introduction Oct. 14, 2015
pdf Single Machine Scheduling I Oct. 14, 2015
pdf Single Machine Scheduling II Oct. 21, 2015
pdf Parallel Machine Scheduling I Oct. 28, 2015
pdf Parallel Machine Scheduling II Nov. 4, 2015
pdf Complexity Theory Nov. 11, 2015
pdf List Scheduling I Nov. 18, 2015
pdf List Scheduling II Nov. 25, 2015
pdf Deterministic Rounding of LPs Dec. 2, 2015
pdf Polynomial-Time Approximation Schemes I Dec. 9, 2015
pdf Polynomial-Time Approximation Schemes II Dec. 16, 2015
pdf Min-Sum Objective I Dec. 23, 2015
pdf Min-Sum Objective II Jan. 20, 2016
pdf Min-Sum Objective III Jan. 27, 2016
pdf Scheduling on an unreliable machine Feb. 03, 2016

Exercise Sheets

pdf Exercise sheet 1
pdf Exercise sheet 2
pdf Exercise sheet 3
pdf Exercise sheet 4
pdf Exercise sheet 5
pdf Exercise sheet 6
pdf Exercise sheet 7

Literature

  • F. Jaehn and E. Pesch: Ablaufplanung. Einführung in Scheduling. Springer, 2014.
  • J. Y.-T. Leung. Handbook of Scheduling: Algorithms, Models, and Performance Analysis. Chapman & Hall/CRC, 2004.
  • M. L. Pinedo. Scheduling: Theory, Algorithms, and Systems. Springer, 2008.

  • R. L. Graham, E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan: Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics 5, pp. 287–326, 1979.
  • E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, D. B. Shmoys: Sequencing and scheduling: Algorithms and complexity. Chapter 9 in S. C. Graves, A. H. G. Rinnooy Kan, P. H. Zipkin. Logistics of production and inventory. Handbooks in Operations Research and Management Science 4, 1993.
  • 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, pp. 21–169, 1998.

FAQ