The University Examination Timetabling Problem with Uncertain Timeslot Capacity: A Two-stage Stochastic Programming Approach

In this work, we extend the original Uncapacitated Examination Timetabling problem by introducing capacity constraints that limit the number of exams schedulable per timeslot and, to take into account possible unexpected disruptive events, by considering such a capacity as a random variable. We propose a two-stage Stochastic Programming approach for this stochastic variant in which recourse actions allow rescheduling exams in successive timeslots or moving students to spot-market rooms. Then, we conduct an in-depth analysis of the impact of uncertainty on solutions using a deterministic equivalent Mixed-Integer Linear Programming formulation. Additionally, we plan to develop a Progressive Hedging algorithm, leveraging the efficiency of a specialized optimizer [4], to address the computational challenges posed by the stochastic nature of the problem even for small-medium size instances. Preliminary results are promising, underscoring the significance of accounting for stochasticity in the problem formulation.