First Fit Algorithm: A Graph Coloring Approach to Conflict-Free University Course Timetabling

Abstract

Aims: Tackling scheduling issues with the most optimal graph coloring algorithm has consistently posed significant difficulties. The university scheduling problem can be expressed as a graph coloring problem, where courses are depicted as vertices and the connections between courses that have common students or teachers are represented as edges. Subsequently, the task at hand is to assign the vertices with the minimum number of colors. In order to accomplish this task, this paper present a graph coloring technique to conflict free university course timetabling using first fit algorithms. Methodology: The conflict graph is partitioned into a set of independent color classes to be assigned time slots and transformed into a conflict-free timetable. The Ladoke Akintola University of Technology (LAUTECH) University Course Timetabling Data was adopted. The allocation of venue based on the allotted time slots is done using first fit packing algorithm. The proposed model is implemented using Python programming language. The developed model had courses being represented as vertices and edges. The course conflict graph was created based on the acquired dataset using vertices-edges relationship diagram. The implemented model is evaluated in terms of Halstead complexity metrics: Program Volume (PV), Program Length (PL), Program Effort (PE), Program Difficulty (PD) and Execution Time (ET). The PV, PL, PE, PD and ET values obtained for the implemented model are 18.45kbits, 0.51, 1037684, 1.97 and 20.45 secs, respectively. Conclusion: The proposed model shows a significant improvement over the existing models by producing conflict-free course timetabling problem with better evaluation results. This work will be highly useful in solving various scheduling, optimization and NP-hard related computational problems.