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

The current version of KHE is Version 2.6. 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.

KHE Version 2.6 (3 March 2021, gzipped tar file, 2.8MB). You will also need the KHE User's Guide (PDF) and possibly the NRConv User's Guide (PDF).


Old versions

KHE Version 2.5 (20 January 2020, gzipped tar file, 2.5MB) and KHE User's Guide (PDF) and NRConv User's Guide (PDF).
KHE Version 2.4 (20 January 2020, gzipped tar file, 2.5MB) and KHE User's Guide (PDF) and NRConv User's Guide (PDF).
KHE Version 2.3 (20 April 2019, gzipped tar file, 4.3MB) and KHE User's Guide(PDF) and NRConv User's Guide(PDF).
Previous version (22 May 2018): User's Guide (PDF, 1.2MB) and software (gzipped tar file, 1.2MB)
Previous version (6 February 2016): User's Guide (PDF, 1.2MB) and software (gzipped tar file, 1.2MB)
Previous version (28 January 2016): User's Guide (PDF, 1.2MB) and software (gzipped tar file, 1.2MB)
Previous version (29 December 2015): User's Guide (PDF, 1.2MB) and software (gzipped tar file, 1.2MB)


Solutions produced by KHE's solvers

KHE20 is my current solver, released in January 2020. There are links to solutions produced by KHE20 and its predecessor KHE18 at the end of the XESTT home page. Their enhancements over my previous solver, KHE14, are all concerned with solving nurse rostering problems.

KHE14 is an earlier solver, with which I obtained all my 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