University Course Timetabling Problem

Description :

The University Course Timetabling Problem (UCTP) presents a combinatorial optimization challenge commonly encountered in educational institutions. Its objective is to allocate courses to specific time slots and rooms while adhering to a set of hard and soft constraints. These constraints encompass the avoidance of schedule conflicts between courses, limiting the overlap of classes for students, preventing consecutive teaching sessions for instructors, and many others. Each university follow a set of rules, procedures, and policies, and has its own set of requirements. Therefore, solving the UCTP is notably difficult due to its size that grow exponentially as the number of courses, students, and time slots increase, as well as the number of hard and soft constraints. UCTP is considered as a NP hard problem that cannot be solved using "brute force" approach. Optimization of the problem involve finding the best possible configuration of a set of variables, given a set of objectives. Many approaches such as meta-heuristic, hyper-heuristic has been used to produce effective results. One is to present an in-depth analysis of the UCTP from the perspective of a Constraint Satisfaction Problem (CSP). By using CSP we can eliminate an important part of the search space. The basic idea is to quickly narrow down the search space by identifying variable-value pairings that violate the constraints. In our work, we will present different approaches and methodologies that were applied to UCTP, formulate the UCTP as a CSP by considering the current university policies used at Saint Joseph University (USJ), and finally, try to optimize the existing algorithms used so far by working on the different sets of constraints in order to find better solution(s) that satisfies the university requirements.