Solving a Real Examination Timetabling Problem

This project was a collaboration with my friend for the combinatorial optimization course, instructed by Dr. Hooshmand. Our task was to create a mid-term exam schedule for the entire MCS department at the AmirKabir University of Technology.

The primary challenge was to devise a schedule that accommodated all students, ensuring that no student had more than one exam on any given day and that there were adequate gaps between exams. Given that each student had a unique set of courses, satisfying everyone’s schedule was a complex problem.

For data preprocessing, we used Numpy and Pandas, and we used the Python API of GAMS to solve our Mixed-Integer Non-Linear Programming (MINLP) models.

Decision Variables and Parameters

Formulation 1: Non-Linear and Slow

In our first attempt, we used a non-linear model to penalize dense exam schedules. The model aimed to maximize the gap between exams within a two-week period. However, we quickly found that a two-week schedule was not feasible.

After extending the scheduling period to four weeks, we were able to find a feasible solution. We also identified 118 students whose schedules created conflicts. By excluding them, we found a two-week integer solution after running the model for seven hours.

Formulation 2: Linear and Fast, but Suboptimal

Our second approach was a linear model that minimized the maximum number of exams per week for each student. While this model was much faster, it didn’t adequately penalize dense exam schedules within the same week.

Formulation 3: The Best of Both Worlds

Our final formulation combined the ideas from the previous two models.

This model produced an integer solution after six hours. When we excluded the 118 problematic students, we found an optimal two-week schedule in just 15 minutes.

The complete source code is available in this GitHub repository.