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.

Available are archives and datasets in XHSTT format, an evaluator for instances (by Jeff Kingston) and solutions in XHSTT, and a classification (by Nelishia Pillay) of high school timetabling.

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

News

  • 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