PLACE: FAMNIT-1-MP2 at 16:00

LECTURER: Nevena MITROVIč, Student of the Computer Science Master’s Program UP FAMNIT

TITLE: The University Timetabling Problem – Complexity and an Integer Linear Programming Formulation: a Case Study of UP FAMNIT

ABSTRACT:
In the first part of the seminar we will describe a university timetabling problem, the problem of assigning courses to time intervals with respect to certain conditions. The problem is known to be NP-hard so no efficient solution methods are known for it. We will present some well known approaches for solving timetabling problems, such as graph coloring, integer linear programming, neural networks, heuristics, etc.
The second part will be devoted to show how a real-world example of a timetabling problem, namely the UP FAMNIT Timetable Design, can be solved in practice. The UP FAMNIT Timetable Design (FTD) will be treated as a natural generalization of the actual timetabling problem for the Faculty of Mathematics, Natural Sciences and Information Technologies at the University of Primorska (UP FAMNIT). We will sketch the proof of NP-completeness of FTD and present an integer linear programing model for FTD. At the end we will compare the timetable obtained as a result of implementation and the one that is prepared manually.

Welcome!