Parallel Ant Colony Optimization on the University Course-Faculty Timetabling Problem in MSU-IIT Distributed Application in Erlang/OTP

Abstract

The University Course-Faculty Timetabling Problem (UCFTP) occurs in the Mindanao State University-Iligan Institute of Technology (MSU-IIT) as the delegation of classrooms for available subjects including time schedule and appropriate faculty personnel, taking into consideration constraints such as classroom capacities, location, and faculty preferences, etc. It is a more difficult variant of the classical University Course Timetabling Problem, which is an assignment problem and known to be NP-hard. This paper presents parallel Ant Colony Optimization Max-Min Ant System (ACO-MMAS) algorithm as an approach in solving the UCFTP instance in the institute. ACO employs virtual ants moving across a search space and using an indirect form of constructive feedback by depositing pheromones on the paths they traverse in order to influence other ants in their searches. We have developed an application to automate the timetabling process using Erlang/OTP, a functional language specializing in concurrent and distributed systems. UCFTP was successfully represented into a mathematical problem instance and solved using the ACO-MMAS algorithm applied on a distributed network setup under Parallel Independent Run and Unidirectional Ring topologies. Extensive testing was performed to properly analyze the search behavior under different parameter settings.