The exam timetabling problem is a classic real life problem faced by all education institutions. When given a period of time, it is required to allocate all exams into specific timeslots without creating any collisions. There are many ways of implementing an exam timetabling algorithm, however one efficient way is to implement a Monte Carlo optimized Hyper-Heuristic algorithm. Hyper heuristics can be considered a type of nearest neighbour (or Greedy) algorithm with the only difference being that it seeks to automate the selecting process through machine learning.
Check out my GitHub for the implementation.
We are first required to define the necessary parameters and present them as a tuple in order to solve this algorithm. These are:
- E → The set of events
- I → The domain
- K → Constraints
E → Set of Events
In this case, the set of events are examinations. In the classic exam timetabling problem, for each exam we are required to define the set of all students which need to sit for the exam. Since this is a simple implementation, it is assumed that students in the same course do not have electives, therefore each student in the same course will sit for the same exam. In the programming implementation, each exam will list which courses are to sit for the exam.
A Course class and Exam class were created. The course class for this implementation contains the course name and number of students. The exam class on the other hand contains a list of courses that are to sit for the exam and the exam code.
Continue reading “Monte Carlo Optimization: Exam Timetabling”
Patrick Buhagiar 