UTFacultiesEEMCSDisciplines & departmentsMORDMMP - High School Timetabling Project (HSTT)

Benchmarking project for (High) School Timetabling

Benchmarking project for (High) School Timetabling

The research in (High) School Timetabling was lacking the availability of exchangeable benchmarks in a uniform format. For this reason a group of researchers agreed on an xml-standard to exchange their datasets. At this moment there are around 50 datasets available. We reported on this project in the PATAT conferences of 2008 and 2010 (page 347). See also the publications in Annals of OR 2012, Volume 194, Number 1, pp. 385-397, and Annals of OR 2014, Volume 218, Number 1, pp. 295-301.
For a (hopefully) gentle introduction to the format, please consult the tutorial.

Available are archives and datasets in XHSTT format, and an evaluator for instances (by Jeff Kingston) and solutions in XHSTT.

If you want to submit new best solutions, please follow the guidelines.

News

  • January 15, 2023. Wiesław Dudak (Wieslaw Dudek Timetables, Krakow, Poland) submitted new solutions for All11 and and All15. The solution for All11 improved from infeasibility value 32 to 9 and All15 from 197 to 39.

  • November 16, 2022. Wiesław Dudak (Wieslaw Dudek Timetables, Krakow, Poland) submitted several best solutions, notably for England StPaul bringing it down to 2 infeasibilities, and improving the objective value to 1410. In addition, Kottenpark2008 now has a feasible solution. And... there are now solutions for All11 and All15. Very impressive results.

  • April 18, 2019. Martin Klemsa (Skolaris Software, s.r.o.) submitted a new best solution for England StPaul bringing it down to 4 infeasibilities, and en passant improving the objective value considerably. The original (hand-made) solution was feasible, and the instance was recreated by reverse engineering. Can we recover it?

  • March 29, 2019. Martin Klemsa (Skolaris Software, s.r.o.) exported a nice Czech instance from the timetabling system Skolaris Czech Village School. The optimality gap is still 3...

  • September 13, 2017. Martin Klemsa (Skolaris Software, s.r.o.) submitted a new best solution to Westside2009 along with a proof of optimality. Very nice!

  • July 21, 2017. George Fonseca submitted (already 3 months ago...) 9 new best solutions to instances of XHSTT-2014 along with 3 new lowerbounds. Some instances costs reduced over 50 percent, impressive!

  • March 8, 2016. Just a few days after the previous update, George Fonseca submitted a new solution of cost 20 to TES99. At the same time, George claims to have achieved that 20 is a lowerbound as well. Hence this instance is solved to optimality now. Hence another instance is solved to optimality.

  • March 4, 2016. The Australian instances have been changed to solve some inconsistencies in splitting rules of linked events (thanks George Fonseca!). As a consequence also some previously best solutions were either removed or changed. Though the instances are more strict now than before the UFOP-GOAL team found a solution to SAH96 with cost 0. Hence another instance is solved to optimality.
    Please update your local versions of the Australian instances.

  • January 29, 2016. New best solutions to 3 instances in XHSTT-2014 have been submitted by the UFOP-GOAL team. An (optimal) solution with cost 0 is now obtained for Finland Highschool (FI-WP-06). This is remarkable because the best known solution was at cost 1 from the beginning, 2011!

  • January 4, 2016. Matias Sørensen submitted a new solution with cost 335 to Spain School (ES-SS-08). Still 1 to go...

  • November 11, 2015. Matias Sørensen submitted a new lower bound to Western Greece University Instance4 (GR-PA-08). This instance is thus solved to optimality.

  • September 10/12, 2015. New lower bounds and best solutions to Brazil Instance5 and Brazil Instance7 by Árton Dorneles. Brazil Instance5 is now solved to optimality.

  • July 20, 2015. New best solutions to 8 instances in XHSTT-2014 have been submitted by the UFOP-GOAL team. An optimal solution is now obtained for Italy Instance4 (IT-I4-96).

  • April 4/5, 2015. New best solutions to Brazil Instance1 and Brazil Instance3 have been submitted by Matias Sørensen. This restores the situation of before April 1, 2015, where optimal solutions to these instances were found by the same method.

  • April 3, 2015. New best solutions, sent by Emir Demirovic (February 20, 2015), George Fonseca (Feb 23, 2015) and Ahmed Kheiri (March 31, 2015) have been administrated. The results are profound: almost all non-optimal solutions in XHSTT-2014 have been improved, and 2 instances, Finland SecondarySchool and Kosovo Instance1, have been brought to optimality.

  • March 2015. Emir Demirovic and Nysret Musliu submitted a solution to Brazil Instance6 (BR-SN-00) of cost 34, which is below a submitted lowerbound It turned out that the solution was correct (of course), but the instances admitted an event of 2 times to start on the last time of the day (at cost 1). Consultation of Haroldo Santos led to the conclusion, that this constraint should have been hard. All Brazilian instances have been changed accordingly, and some best solutions have been removed.

  • Older news ...

  • For further information, please contact Gerhard Post