SOLVING UNIVERSITY TIMETABLING PROBLEMS BASED ON A MULTI-CONSTRAINT ENVIRONMENT

FERNANDO S. VIRAY JR.
Page No. 1-14

The key to finding an optimum solution for a gargantuan problem such as the University Timetabling Problem (UTP) which is considered an NP-hard problem is to implement a "divide and conquer" mechanism. In this research, the sub-problems of UTP are considered and input data, factors, and parameters were classified and organized to model several stages or phases of the solution process. Meta-heuristic approaches were implemented in finding an overall feasible solution to the UTP by initiating a specific AI-based local search and optimization algorithm with little human intervention in every phase of the solution process. Algorithms to be utilized as a part of the meta-heuristics include Tabu Search, Greedy Algorithm, Integer Linear Programming, and Bi-Partite Graph Approach. Simulation results revealed that the proposed multi-stage solution process model, by incorporating multi-constraint inputs, is a promising model when paired with any of the subject algorithms as it significantly aids in finding an optimum solution faster in terms of elapsed time and computation resources.
Keywords: Timetabling Problem (TP), University Class Scheduling Problem (UCSP), local search and optimization techniques