A Comparative Analysis of Operational Research and Metaheuristic Approaches to University Course Timetabling Problems

Abstract

The University Course Timetabling Problem (UCTP) is a critical challenge in educational resource management, involving the complex task of assigning courses, students, faculty, and resources to specific time slots while satisfying numerous constraints. As educational institutions grow in complexity, with increasing student numbers and diverse course offerings, the need for efficient timetabling solutions becomes paramount. This thesis provides a comprehensive analysis of UCTP, examining its components, constraints, and evaluation metrics. The study focuses on two main solution approaches: Operational Research (OR) based techniques and Single-Solution Metaheuristics. Specifically, it investigates graph coloring, integer linear programming, mixed integer linear programming, and simulated annealing methods. Through a comparative analysis, the research highlights the strengths, weaknesses, and applicability of each approach. The findings reveal that while exact methods like integer programming provide optimal solutions for small to medium-sized problems, metaheuristics like simulated annealing offer better scalability for large, real-world instances. However, consistent enhancements are not always achieved across all scenarios. This work contributes to the ongoing dialogue on optimizing educational resource allocation in higher education. It emphasizes the need for continued research to address the challenges associated with UCTP and to develop robust techniques that can adapt to different environments and conditions. The thesis concludes by identifying current trends and suggesting future research directions, including the exploration of hybrid approaches and the integration of machine learning techniques.