New models and algorithms for the timetables of Italian high schools

The thesis investigates new timetabling problems, which are motivated by the com- plex case of Italian schools. Generally speaking, the High School Timetabling Problem is aimed at giving the right order to the meetings between groups of students and teachers. However, it requires to pre-assign teachers to the classes, i.e. establishing which teacher will teach each subject in each class. This problem is called Class Teacher Assignment Problem and is faced by a mixed integer programming formulation, which also aims at easing the solution of the following High School Timetabling Problem. Moreover, the thesis shows that Class Teacher Assignment Problem can also be adapted to face the case where teachers must give lectures in more than one school (Multi-school Timetabling Problem). In particular, this thesis investigates a complex variant of the High School Timetabling problem w.r.t. a given assignment of teachers to classes. This problem presents requirements, which en- force to (i) provide teachers with the same idle times, (ii) avoid consecutive days with heavy workload, (iii) limit multiple daily lessons for each class, (iv) introduce shorter time units to di↵erentiate entry and exit times. An integer programming model is presented for this problem, which is denoted by Italian High School Timetabling Problem [IHSTP]. However, requirements (i), (ii), (iii) and (iv) cannot be expressed according to the current XML High School Time-Table [XHSTT] standard. Since the [IHSTP] model is very hard to solve by an off-the-shelf solver, a two-step optimization method is presented: the first step optimally assigns teachers to lesson times and the second step assigns classes to teachers. An extensive experimentation is performed on the model by realistic and real instances from Italian schools, as well as benchmark instances from the literature. Finally, the experiments show that the method is effective in solving both this new problem and the simplified problem without the new requirements.