How can tasks be efficiently scheduled in factories, projects managed under tight deadlines, or timetables constructed in complex systems such as schools or hospitals? This course introduces the field of machine scheduling, which provides essential tools to address such challenges, connecting theoretical foundations with practical applications.

The course begins with a review of essential concepts in computational complexity, graph theory, mathematical programming, and algorithm design. It then introduces the definitions and classification of machine scheduling environments, including single-machine, parallel-machine, and dedicated-machine systems.

The course next focuses on the offline scheduling setting for each machine environment, where all problem data are known in advance. For each environment, we study the computational complexity of scheduling problems, highlighting the boundary between polynomially solvable and NP-hard cases. The focus is on identifying the complexity of each problem without going into the details of NP-hardness proofs. Key polynomial-time solvable problems are presented together with polynomial-time algorithms, while NP-hard problems are addressed using benchmark exact and approximation algorithms.

The course then turns to online scheduling, in which input data are revealed gradually over time. We introduce the basic models of online scheduling and the principles underlying online algorithms, and we discuss common techniques used to evaluate their performance.

Applications in manufacturing, project management, and timetabling are integrated throughout the course to illustrate the practical relevance of scheduling theory.

1) Model practical applications within machine scheduling environments.
2) Solve different scheduling problems using appropriate algorithms based on their
computational complexity in both offline and online settings.
3) Implement and evaluate algorithms for different scheduling problems.

Błażewicz, J., Ecker, K.H., Pesch, E., Schmidt, G. and Węglarz, J., 2007. Handbook on scheduling: from theory to applications. Berlin, Heidelberg: Springer Berlin Heidelberg.

Pinedo, M. and Hadavi, K., 1992. Scheduling: theory, algorithms and systems development. In Operations research proceedings 1991: Papers of the 20th annual meeting/vorträge der 20. Jahrestagung (pp. 35-42). Berlin, Heidelberg: Springer Berlin Heidelberg.