This work introduces a complex variant of the timetabling problem, which is motivated by the case of Italian schools. The new requirements enforce to (i) provide the same idle times for teachers, (ii) avoid consecutive \emph{heavy} days, (iii) limit daily multiple lessons for the same class, (iv) introduce shorter time units to differentiate entry and exit times. We present an integer programming model 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 XHSTT standard. Since the IHSTP model is very hard to solve by an off-the shelf solver, we present a two-step optimization method: the first step optimally assigns teachers to lesson times and the second step assigns classes to teachers. The computational experimentation shows that the method is effective in solving this new problem and the simplified problem without the new requirements.
Citation
Department of Mathematics and Computer Science University of Cagliari