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.11. 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.11 (7 March 2024, gzipped tar file, 4.3MB). You will also need the KHE User's Guide (PDF) and possibly the NRConv User's Guide (PDF).

Old versions

KHE Version 2.10 (15 February 2024, gzipped tar file, 4.3MB) and KHE User's Guide (PDF) and NRConv User's Guide (PDF).
KHE Version 2.9 (21 December 2023, gzipped tar file, 4.2MB) and KHE User's Guide (PDF) and NRConv User's Guide (PDF).
KHE Version 2.8 (16 June 2023, gzipped tar file, 3.3MB) and KHE User's Guide (PDF) and NRConv User's Guide (PDF).
KHE Version 2.7 (31 March 2022, gzipped tar file, 3.3MB) and KHE User's Guide (PDF) and NRConv User's Guide (PDF).
KHE Version 2.6 (3 March 2021, gzipped tar file, 2.8MB) and KHE User's Guide (PDF) and NRConv User's Guide (PDF).
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

KHE24 is my current solver, released in March 2024. There are links to solutions produced by KHE24 and its predecessors at the end of the XESTT home page.

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

• KHE14 [XML 21MB] (19 August 2014). Solutions to the instances of the XHSTT-2014 archive.
• KHE14x8 [XML 21MB] (19 August 2014). As above, only using KHE14x8. Publication and RunningTime categories added by hand on 3 October 2014. KHE14x8 [Zipped]

Solutions to the XHSTT-2013 archive

• KHE14 [XML 18MB] (8 February 2014). Solutions to all but three of the instances of the XHSTT-2013 archive, found by KHE14, as reported in my PATAT14 submission.
• KHE14x8 [XML 18MB] (8 February 2014). As above, only using KHE14x8.

Solutions to the AU-BG-98.xml instance

• A solution to AU-BG-98.xml with cost 3.00400 (10 February 2014). The best of 32 solutions found by KHE14, modified with a new repair for avoid split assignments defects plus a way of trying a limited number of alternative orderings for the layers.
• A solution to AU-BG-98.xml with cost 3.00311 (20 February 2014). Found in much the same way as the previous solution, using repairs that will move a meet in order to repair a split assignment, and then continue with a general time repair ejection chain initiated by that move.
• A solution to AU-BG-98.xml with cost 2.00340 (27 February 2014). Found in much the same way as the previous solutions, the main change being a simple randomization of the starting point when trying lists of alternative times, resources, etc.
• A solution to AU-BG-98.xml with cost 1.00386 (13 March 2014). Best of 8 solutions found after further incremental improvements to the solver.

Solutions to the AU-SA-96.xml instance

• A solution to AU-SA-96.xml with cost 0.00024 (6 May 2014). The best of 8 solutions found by KHE14. Encouragingly, no new modifications to the algorithm were needed to get this solution.

Solutions to the AU-TE-99.xml instance

• A solution to AU-TE-99.xml with cost 0.00125 (29 June 2014). The best of 8 solutions found by KHE14.

Solutions to the BR-SA-00.xml instance

• A solution to BR-SA-00.xml with cost 0.00028 (18 March 2014). Best of 128, which is quite feasible, since KHE14 solves this instance very quickly: wall clock time to find the 128 solutions on my quad-core was 43 seconds. This solution is better than the solution on Gerhard's web site with cost 0.00038 found by Haroldo Santos, but it is a long way behind the remarkable solution with cost 0.00005 found by Kristiansen et al., and claimed by them to be optimal. The key to finding a good solution to this instance is to have fewer meets of duration 2 than the distribute split events constraints request. This solution was found by including a repair operation which splits meets.
• A solution to BR-SA-00.xml with cost 0.00025 (21 March 2014). As above, enhanced with an experimental repair operation for cluster busy times defects which uses ejection trees rather than ejection chains.
• A solution to BR-SA-00.xml with cost 0.00022 (30 April 2014). Best of 32. Otherwise as above, with further incremental improvements.
• A solution to BR-SA-00.xml with cost 0.00020 (18 May 2014). Best of 128.
• A solution to BR-SA-00.xml with cost 0.00014 (18 August 2014). Best of 128. Wall clock time to find the 128 solutions on my quad-core was 28 seconds. This solution is three limit idle times defects behind the solution with cost 0.00005 found by Kristiansen et al. and claimed by them to be optimal.

Solutions to the DK-FG-12.xml instance

• A solution to DK-FG-12.xml with cost 0.03310 (22 August 2014). Found by the current standard version of KHE14x8.

Solutions to the DK-HG-12.xml instance

• A solution to DK-HG-12.xml with cost 12.03124 (18 August 2014). Running time 111 minutes. Gerhard's web site asserts that 7.00000 is a lower bound for this instance.

Solutions to the DK-VG-09.xml instance

• A solution to DK-VG-09.xml with cost 2.04097 (22 August 2014). Found by the current standard version of KHE14.

Solutions to the IT-I4-96.xml instance

• A solution to IT-I4-96.xml with cost 0.00061 (2 March 2014). Found in much the same way as the previous solutions, with further incremental improvements to the solver.
• A solution to IT-I4-96.xml with cost 0.00060 (7 March 2014). Found in much the same way as the previous solutions, with further incremental improvements to the solver.
• A solution to IT-I4-96.xml with cost 0.00056 (12 March 2014). The main improvement here was a re-implementation of the Kempe meet move operation which improved its handling of meets of varying durations. The best of 8 solutions found by KHE14.
• A solution to IT-I4-96.xml with cost 0.00054 (13 March 2014). More incremental improvements. Again, the best of 8 solutions.
• A solution to IT-I4-96.xml with cost 0.00050 (1 May 2014). More incremental improvements. Best of 128 solutions.
• A solution to IT-I4-96.xml with cost 0.00040 (8 May 2014). More incremental improvements. Best of 128 solutions.

Solutions to the NL-KP-03.xml instance

• A solution to NL-KP-03.xml with cost 0.01032 (1 July 2014). The best of 8 solutions found by a variant of KHE14 that ran very slowly (1-2 hours per solution).
• A solution to NL-KP-03.xml with cost 0.00866 (8 July 2014). The best of 8 solutions, found using an improved repair for limit busy times underloads.
• A solution to NL-KP-03.xml with cost 0.00700 (11 July 2014). The best of 8 solutions, found using a lucky variation on the previous method.
• A solution to NL-KP-03.xml with cost 0.00617 (16 August 2014). The best of 8 solutions, again due to luck (the second best had cost 0.00897, which is more typical of the results I have been getting lately for this instance). I have been mainly working on reducing run times. I found the whole set of 8 solutions in under 35 minutes wall clock time on my quad-core.

Solutions to the US-WS-09.xml instance

• A solution to US-WS-09.xml with cost 0.00677 (22 August 2014). Found by the current standard version of KHE14x8.