A Case of Study: Proposal of Three Integer Linear Programming Models for the Improvement of a University Timetable Processing

Resumen

This poster summarizes the work towards the development of a solution to the whole extent of the Timetabling Problem found at a Mexican university, providing significant insight into the Timetable Processing. The first step taken to reach a solution was to identify a data structure that later allowed the development of an Integer Linear Programming Model - ILP Model. Afterwards, the main operational rules of the aforementioned institution were studied and modeled as constraints, while the decision variables were represented by binary ones. The present research provides three ILP models which generate the university calendar and improve the efficiency of the administrative area scheduling process.

The first model is used only when it is necessary to allocate the courses for an appropriate room. The obvious issues with this process are the time spent by administrative staff to verify the feasibility of the schedule made by the coordinators, and the work spent by coordinators to reschedule owing to the timetable´s impracticality. The second model tries to handle a set of complex constraints to ensure that students do not cancel extracurricular courses due to parallel assignment of core courses; some special considerations were taken into account, such as special schedules, types of courses, availability of faculty staff in multiple time slots, room and special equipment availability, and lastly, consecutive and single periods of time, along with groups of students. The third model works in two stages, and seeks the assignment of core courses by considering the same aspects as in the previous model. During the first
phase, this model finds the optimal course assignment to time slots. During the second phase, each combination of resulting course – timeslot is assigned to the appropriate type of room.

This study shows that an ILP Models can be used for improved performance of this administrative task at the University. As shown the Timetabling Problem is highly constrained, however, it was possible to obtain feasible results. It's recommended used of the second model in order to comprehensively solve the timetabling problem. Even though, the main limitations that would exist are the scarcity of trained human resources and lack of the computational resource. This model improves timetable feasibility and guarantees average allocation of 86 %.Finally, the work for the future work will be to implement these Models in the University and thoroughly assess their effectiveness.