Solving the university course scheduling problem using recursive largest first algorithm and simulated annealing - Pahang, Elaine (2013)
Abstract: This study is about solving the course scheduling problem using a hybrid approach of graph coloring and Simulated Annealing. The course scheduling problem is a timetabling problem wherein resources such as courses, teachers and students were allocated to an appropriate schedule without conflict with other resources. This study created a scheduling system for UP Cebu, dealing with three unit courses only. An initial solution was generated using the Recursive Largest First (RLF) graph coloring algorithm. RLF generated a feasible solution, meaning no hard constraints were violated although some classes were unscheduled; however, the quality of the solution was poor given the greedy nature of the algorithm. The initial solution was then optimized using Simulated Annealing. During optimization, classes were rearranged and swapped to other time slots and facilities to generate a new solution. Generated solutions were evaluated using a cost function to determine their feasibility. Tests showed that Simulated Annealing indeed optimized the graph coloring generated schedule in terms of cost ? SA generated solutions have lower cost than RLF generated solutions - but with the tradeoff of having more unscheduled classes. All in all, the scheduling system produced a feasible and optimized timetable where no resource conflicts with another.