Development of examinations scheduling algorithm using graph colouring: A Case of Sokoine University of Agriculture

Examination Timetabling Problem (ETP) is a real life problem encountered in academic institutions and attracted the attention of reseach communities since 1960’s. This study intends to develop a graph based algorithm for ETP at Sokoine University of Agriculture (SUA). In this study, a Recursive Largest First (RLF) algorithm for graph colouring is used to solve the ETP at SUA. We discuss in detail the step-by-step process that is taken to implement our timetabling-by-graph-coloring procedure, from the assembling of university exam data, to creating an exam conflict graph based on the assembled data, to colouring the conflict graph, to transforming this colouring to a conflict-free timetable, to finally assigning exams to classrooms. Using the two semester data sets from the case study, computational experiments are conducted based on the developed algorithm and obtained the promising results. Sample Computational results, using actual data provided by students’ records office of SUA, are documented. Our algorithm is very flexible, since it. allows the user to define the basic problem data which are courses to examined, courses’ enrolment, rooms and their respective capacities. Its performance is quite satisfactory, considering that it is an algorithm that has to run twice a year for the construction of the examination timetable of a specific educational organization. Some improvements on it such as applying metaheuristics approach with it, will certainly enhance the algorithm’s functionality