Home Page of KHE

A Software Library for High School Timetabling

and Nurse Rostering

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 and nurse rostering 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 also supports the XESTT nurse rostering format, which is an extension of XHSTT for nurse rostering. 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, Version 2.2, has many changes which should improve things but which will take time to adapt to. For a quick introduction to what to expect, consult file README in the root directory of the distribution. For the details, see the User's Guide.

Current version (Version 2.2, 22 May 2018, gzipped tar file, 6.8MB)
KHE User's Guide (PDF file)
NRConv User's Guide (PDF file)

Previous 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)

Solutions produced by KHE's solvers

KHE18 is my current solver, released in May 2018. There are links to solutions produced by KHE18 at the end of the XESTT home page. Its enhancements over my previous solver, KHE14, are all concerned with solving nurse rostering problems.

KHE14 is my previous solver, with which I obtained all my recent good solutions to high school timetabling problems. 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, but which was not accepted. 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