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 will introduce the field of machine scheduling, linking theoretical foundations with practical applications. The course will begin with a review of essential concepts in computational complexity, graphs, and algorithms, followed by the definitions and classification of machine scheduling environments (single-machine, parallel-machine, and dedicated-machine systems). For each environment, the course will examine computational complexity, highlighting the boundary between polynomially solvable and NP-hard cases. Important polynomial cases will be presented together with established efficient algorithms, while NP-hard problems will be addressed through benchmark exact and approximation methods. Applications in manufacturing, project planning, and timetabling will be integrated throughout to demonstrate the practical relevance of scheduling theory.
- Enseignant·e: Nour Elhouda Tellache