Bipartite Modeling for Solving the University Timetable Problem

Resumen

The University Timetabling Problem (UTP) is a combinatorial optimization challenge classified as NP-hard. It involves allocating resources — usually professors, courses and rooms — while meeting multiple institutional constraints. Wren [2] describes it as a specific scheduling case, where the solution space grows exponentially, rendering manual resolution difficult. This complexity is compounded by the unique institutional characteristics [1]. To address the allocation challenges within the Institute of Computing (IC) at UFRJ, this work proposes a bipartite optimization model as a minimum viable product (MVP). Unlike traditional approaches that solve the assignment of professors, courses, and rooms in a unified decision structure [3], our model separates the problem into two interconnected subproblems: (1) assigning professors to courses and (2) allocating courses to rooms. This separation offers greater flexibility, allowing each model to be used independently or jointly. In the IC case study, the output of the first model feeds into the second to produce a complete, synchronized schedule. The modular structure also facilitates adaptation to other departments, particularly as a centralized tool for improving room utilization and avoiding underuse of shared spaces. The approach emphasizes structured decision-making automation via mathematical optimization rather than computational performance. In the course allocation model, the objective function maximizes expected academic performance by considering professor aptitude and the satisfaction of both students and faculty, while incorporating soft constraints. These include penalties for not meeting the minimum workload requirements for both permanent and substitute professors. The model also enforces hard constraints related to institutional rules—such as workload limits, scheduling conflicts, and qualification requirements—as well as specific conditions for manual allocations and maximum workloads. To enhance flexibility, a fictitious professor named DUMMY is introduced. As DUMMY is exempt from all constraints, the model remains feasible even when no qualified or available professor can be assigned to a given course. The final result is a mixed-integer linear programming model. Meanwhile, the room assignment model uses the output of the previously defined model or the pre-established schedule planning. The main variable represents room allocation for a session. The objective function maximizes the sum of allocations while minimizing the difference between room capacity and session vacancies, with a coefficient prioritizing institutional allocations. The constraints include room usage, exclusive occupation, room type compatibility, and room preferences for first-year students, as well as restrictions on specific resources. The final modeling results in a Mixed Integer Quadratic Program, which characterizes it as a non-linear problem. [...]