This project was a joint work of me and my friend for the combinatorial optimization course, which was instructed by Dr.Hooshmand.
In this project, we had to schedule mid-term exams of the entire MCS department at the AmirKabir University of Technology.
More precisely, we had a list of students that had taken some courses. Our job was to find the best examination schedule for all students so that there is at most one exam for any student in one day and there is a suitable gap between exams from students’ point of view.
Because each student could have a different set of courses, our biggest challenge was to make everyone happy with their examination schedule!
It is worth mentioning that we used Numpy and Pandas for preprocessing and the python API of GAMS to solve our MINLP models.
Note:
- We couldn't schedule any exams on the weekend.
- Each exam had to be scheduled in its own course time.
Definition of decision variables and parameters:
The first formulation - It worked, but it wasn’t fast enough! :
In this model, we tried to specify some penalties for more dense exams in a non-linear fashion. Since we had to schedule all the exams in two weeks, the two inner summations helped us consider the gap between each t and t’ pair in these weeks. When we first ran the above model, we observed that there was no feasible solution for two weeks.
Later we realized there was no feasible solution until we considered four weeks for examination. (project1_experiment1.gms)
We also identified 118 students that prevented our model from finding a feasible solution. (project1_experiment2.gms)
We ran this model for seven hours without the forementioned students, and we found a two-week integer solution.
We also tested this model on a smaller subset of 6 students, and we confirmed it is trying its best to meet the conditions of our problem:
The second formulation - It was linear and fast, but it wasn’t good enough! :
In our second try, we defined a linear model. It had to minimize the maximum number of exams in a week for each student. Our idea was that the model would try to distribute exams between weeks as uniformly as possible to reach a lower objective.
The main disadvantage of this model was it did not consider any penalty for dense exams in a week.
Here is a schedule we found with this model:
The third formulation - It had the best of both worlds! :
Combining the ideas of the previous formulations, we came up with the following model:
To avoid complexities, we skipped some details regarding indexes’ limitations. (For more information, please check out project1_v1.6.gms)
We ran the model for 6 hours, and we reached the following integer solution:
We also tried to ignore the 118 students we identified by our first experiment, and we got the following optimal solution for two weeks in 15 minutes!
The complete source code is available in this repository.