Monte Carlo Optimization: Exam Timetabling

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.

I →  Domain

The Domain in this case are time slots. The way we implement time slots can vary. A University might decide that there should be 3 time slots per day except for Saturday that will have only two time slots.   In my implementation, each slot contains a list of exams and a unique ID.

K →  Constrains

Constraints can be of either two types:

• Hard Constraints → not meeting these constraints would be considered unacceptable. In this implementation, the only hard constraint was that no student is to sit for two exams in the same timeslot.
• Soft Constraints → these constraints are not a must, but ideally they should be met. In this case, the soft constraint was that for each student, the further apart the exams, the better.

In a more sophisticated exam timetabling program, other constraints would be taken into consideration such as the number of students seated for any exam cannot exceed the predetermined capacity.

Implementation

The program was implemented using C# using Visual Studio 2013 and running on an x64 Core i5-3330 processor, clocked at 3.00GhHz with 8.00GB of RAM. All exams, courses and time slots are pre-defined and no user input is required.

The program was implemented as follows:

1. The tuple was generated, containing the list of exams and timeslots. It would be recommended to first weight all the exams with a certain value called the conflict density. The more diverse students (from different courses), the higher the value. The list of exams would then be ordered by conflict density. For simplicity, it was assumed that the exams were already ordered.
2. For each exam, a random time slot was given. For now, exams are assigned to empty timeslots only.
3. If the number of exams was <= the number of timeslots, then each timeslot would have a maximum of 1 exam.
4. If otherwise, if n denoted the number of time slots, on the n+1th exam the algorithm would randomly add exams to timeslots alongside exams, as long as the hard constraint is met. Therefore before adding, it checks whether the exams in that timeslots contains students that are sitting for the current exam.
5. After adding all exams, the algorithm will check whether the soft constraints where satisfied. In order to do this, the algorithm would score how well the soft conditions were met by the following formula. The higher the score, the better.
   • F = final weighted score
   • N = number of courses
   • M = number of exams (related to course)
   • delta = number of timeslots
   • S = total number of students in faculty

*I created the formula, no reference.

The previous steps are repeated for a number of times (1000 in the given executable program) and a copy of the best score timetable is kept.

The given executable will first output this score (F), then the timeslots in order along with the exam code and courses sitting for the exam. The score is being printed for testing purposes.