Highly Constrained University Class Scheduling using Ant Colony Optimization

Solving University Class Scheduling Problem (UCSP) is a complex real-world combinatorial optimization task that has been extensively studied over the last several decades. Many meta-heuristic based techniques, including prominent swarm intelligence (SI) methods have been investigated to solve it in different ways. In this study, Ant Colony Optimization (ACO) based two methods are investigated to solve UCSP: ACO based method and ACO with Selective Probability (ACOSP). ACO is the well-known SI method that differs from other SI based methods in the way of interaction among individuals (i.e., ants); and an ant interacts with others indirectly through pheromone to solve a given problem. ACO based method considers probabilistically all the unassigned time slots to select next solution point for a particular course assignment. In contrast, ACOSP probabilistically selects next solution point for a particular course assignment from the selective probabilities. Such selective probability employment with ACO improves performance but reduces computational cost. The performances of the proposed methods have been evaluated comparing with Genetic Algorithm (GA) in solving real-world simple UCSPs. In addition, proposed methods are compared with each other for solving highly constrained UCSPs. Both the proposed methods outperformed GA and ACOSP was the best to solve the given problems.