Comparing MAX-MIN and Rank-based Ant Colony Optimization Algorithms for solving the University Course Timetabling Problem

Abstract: The University Course Timetabling Problem (UCTP) is a scheduling problem regarding courses, time slots and rooms, and is often accompanied by a set of feature requirements. As non-trivial instances of the UCTP are NP-hard, traditional computational methods are ineffective. A meta-heuristic alternative is the Ant Colony Optimization (ACO) algorithm, which has previously been proven to successfully solve the UCTP. This paper investigates the relative effectiveness of the MAX-MIN ACO variation to the Rank-based ACO variation on UCTP problem sets of varying difficulty. They are also compared when using a local-search help function and a path attractiveness heuristic. This study shows that the ACO variations perform similarly well for all problem difficulties when utilizing the path attractiveness heuristic. Utilizing both local search and the heuristic produces the best results across the difficulties and ACO variations. There is, however, a need for further investigation into the parameters for both ACO variations to ensure the validity of the conclusion.