Home Page of KHE

A Software Library for High School Timetabling

KHE is an open source ANSI C software library, written by Jeff Kingston, whose main aim is to provide a fast and robust foundation for solving instances of high school timetabling problems. It supports the XHSTT high school timetabling data format, based on XML, that was created in 2009 by a working group led by Gerhard Post, and it underlies the HSEval timetable evaluator.

Users of KHE may read and write XML files, create solutions, and add and change time and resource assignments using any algorithms they wish. It is also possible to interface directly to KHE (that is, without going via XML). The cost of the current solution is always available, kept up to date by a hand-coded constraint propagation network.

KHE is distributed under the GNU General Public License, Version 3.


Current version

Releases of KHE are not guaranteed to be backward compatible, because KHE is a research vehicle as well as a production system, so it must be able to incorporate new ideas freely. The current version (6 February 2016) is identical to the 19 May 2015 version except for a few bug fixes and some tightening up of the specification of KheArchiveWrite (for which see the Guide).

Current version (6 February 2016): User's Guide (PDF file, 1.2MB) and software (gzipped tar file, 1.2MB)
Previous version (28 January 2016): User's Guide (PDF file, 1.2MB) and software (gzipped tar file, 1.2MB)
Previous version (29 December 2015): User's Guide (PDF file, 1.2MB) and software (gzipped tar file, 1.2MB)
Previous version (22 December 2015): User's Guide (PDF file, 1.2MB) and software (gzipped tar file, 1.2MB)
Previous version (19 May 2015): User's Guide (PDF file, 1.2MB) and software (gzipped tar file, 1.2MB)
Previous version (3 October 2014): User's Guide (PDF file, 1.2MB) and software (gzipped tar file, 1.2MB)
Previous version (7 May 2014): User's Guide (1050KB) and software (gzipped tar file 861KB)


Solutions produced by KHE's solvers

KHE14 is my current solver, which incorporates my previous work on timetabling structures, the global tixel matching, layered time assignment, and polymorphic ejection chains. KHE14x8 runs KHE14 eight times in parallel and keeps the best of the eight solutions.

KHE14 is the subject of a paper I submitted to PATAT14 in February 2014. I then continued to work on it until August 2014, producing some good individual solutions and the full sets of solutions to the XHSTT-2014 archive immediately below. This later work has been incorporated into a revised version of the PATAT14 paper which I submitted to the post-conference selected papers volume, unsuccessfully I believe. The 16 September 2014 version of KHE was used to obtain these solutions.

Solutions to the XHSTT-2014 archive, found using the 16 September 2014 version of KHE

Solutions to the XHSTT-2013 archive

Solutions to the AU-BG-98.xml instance

Solutions to the AU-SA-96.xml instance

Solutions to the AU-TE-99.xml instance

Solutions to the BR-SA-00.xml instance

Solutions to the DK-FG-12.xml instance

Solutions to the DK-HG-12.xml instance

Solutions to the DK-VG-09.xml instance

Solutions to the IT-I4-96.xml instance

Solutions to the NL-KP-03.xml instance

Solutions to the US-WS-09.xml instance