Scheduling

Scheduling, as a branch of combinatorial optimization and operations research, focuses on the timely allocation of tasks to limited resources in order to minimize a cost function. Scheduling problems are prevalent in various applications, including production planning, logistics, project management, healthcare, personnel planning, and operating computing systems. The resulting models serve as classic examples of combinatorial optimization problems.

This course will explore a range of scheduling contexts and models, including stochastic, online, and robust variations, as well as techniques such as greedy algorithms, network flows, polyhedral approaches, learning-augmented algorithms, and randomized algorithms. Additionally, the course will cover methods for classifying scheduling problems, determining their computational complexity, designing and analyzing both exact and approximate algorithms, and interpreting these problems geometrically.

Upon completing the module, students will know the fundamental scheduling problems, understand their classifications, and apply various techniques to solve them. They will be able to analyze the complexity of these problems, design optimal algorithms, or demonstrate NP-hardness. Additionally, students will be able to evaluate the worst-case performance of algorithms and prove their approximation factors.

In the written examination (90 minutes) or the oral examination (30 minutes), students will demonstrate their ability to model, classify, and solve scheduling problems. They will also demonstrate how to design efficient algorithms and provide proofs of their performance guarantees. No books, notes, or other materials are permitted during the exam.

CIT413041 Discrete Optimization

• - Elements of Scheduling, https://elementsofscheduling.nl/ - Principles of Sequencing and Scheduling, DOI 10.1002/9780470451793 - Scheduling: Theory, A;gorithms, and Systems, DOI 10.1007/978-3-031-05921-6 - Scheduling Algorithms, DOI 10.1007/978-3-540-69516-5 - Additional current literature/articles

The module is structured as a lecture accompanied by exercises. The content is presented using illustrative examples and engages students in discussions during the lectures. These lectures encourage students to actively engage with the topics and explore the relevant literature independently. After each lecture, exercise sessions are conducted, and exercise sheets and solutions are provided. This approach allows students to deepen their understanding of the methods and concepts taught and to independently assess their progress.