Design and implementation of a course scheduling system using Random Search

Scheduling is a discipline that has always existed in many domains. This work is focused on a particular context: education at university level. The goal of course scheduling is to assign courses, also known as events, into a timetable formed of time slots, under a set of constraints. The University Course Timetabling Problem (UCTP) is a NP-hard problem. This means that it is not possible to solve it exactly in practical time. Carter and Laporte (1998) exposed different methods to solve different types of UCTPs, including Course Timetabling, Class-Teacher Timetabling, Student Scheduling, Teacher Assignment and Classroom Assignment. In 2012, Feizi-Derakhshi, Babei and Heidarzadeh provided a classification of methods to solve the UCTP, including Operational Research methods (Graph Colouring, Integer Programming, Constraint Satisfaction Programming), meta-heuristics (Evolutionary and Genetic Algorithms, Ant Colony Algorithms, Hill Climbing, Tabu Search, Simulated Annealing) and modern intelligent methods (hybridisation, hyper heuristics methods). Those methods will be reviewed in this paper, so as to present the current state-of-the-art on UCTP. Random Search is not a method that has been tested a lot. This procedure performs a swap between a course and a block of Time slots available to welcome the selected course. Both the course and its destination are randomly selected. To evaluate the evolution of the results, a penalty function has been set up. This function evaluates six constraints. Four of them should absolutely be respected: no teacher can have simultaneous courses, no students can have simultaneous courses, no teacher can have courses on both campuses on the same day, no courses requiring a specific room can be assigned to another room than the required one. These constraints are characterized as hard constraints. Their cost should equal zero at the end of the computation of the model. For the two last ones (avoiding courses late in the day and during lunchtime and fitting the capacity of the classroom with the number of students enrolled in the course assigned to that class), the procedure tries to reduce their cost as much as possible with a predefined number of iterations. They are characterized as soft constraints. This method is the core of this thesis and has been implemented at the UCLouvain, more specifically at the Louvain School of Management (the business engineering and management faculty of the university).