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.
Author
(s) Details
Ogunkan
Stella Kehinde
Department of Computer Science, Ladoke Akintola University of Technology
(LAUTECH), Ogbomoso, Oyo, Nigeria.
Peter
Olalekan Idowu
Department of Electronic and Electrical Engineering, LAUTECH,
Ogbomoso, Oyo, Nigeria.
Orukotan
Felicia Funmilayo
Department of Computer Science, Ladoke Akintola University of
Technology (LAUTECH), Ogbomoso, Oyo, Nigeria.
Ogunniyi
Olufunke Kemi
Department of Computer Science, Ladoke Akintola University of
Technology (LAUTECH), Ogbomoso, Oyo,
Nigeria.
Elijah
Olusayo Omidiora
Department of Computer Engineering, LAUTECH, Ogbomoso, Oyo,
Nigeria.
Please see the book here:- https://doi.org/10.9734/bpi/mcscd/v5/2159
No comments:
Post a Comment