The school that we used for our performance test ZonabitOrario actually exists. The following timetable was used for the school year 2007-2008 (all teachers' names were changed for their privacy).
The timetable is generated on a recent PC (2 or 3 GHz of Cpu), and it complies with the didactic conditions and the teachers' personal constraints (see side), according to the following times:
solving all the constraints before removing free hours : 1 - 2 min.
removing free hours (apart from parents' reception and allowed free hours): 10 - 20 min.