Optimizing University Course Timetabling Using Graph Coloring Techniques

Abstract

This research presents an innovative approach to the University Course Timetabling Problem (UCTP) through the application of graph coloring techniques aimed at achieving optimal scheduling accuracy. By partitioning the conflict graph into independent color classes, time slots are assigned to create a conflict-free timetable. The study utilizes data from the Ladoke Akintola University of Technology (LAUTECH) to construct a course conflict graph, where courses are represented as vertices and conflicts as edges. Venue allocation corresponding to the assigned time slots is accomplished using a first fit packing algorithm. The proposed model is implemented in Python and evaluated using Halstead complexity metrics, yielding results of Program Volume (PV) at 18.45 kbits, Program Length (PL) at 0.51, Program Effort (PE) at 1,037,684, Program Difficulty (PD) at 1.97, and Execution Time (ET) at 20.45 seconds. The findings demonstrate significant improvements over existing models, resulting in a more efficient conflict-free course timetable. This work contributes valuable insights for addressing various scheduling, optimization, and NP-hard computational challenges.