Some useful timetabling-related software and links

Page maintained by Peter Ross, phone ext 2766

Handy external links:

• page of the European Working group on timetabling, WATT. See the `Resources' section for bibliographies, links etc
• a list of commercial timetabling products
• a somewhat different list of commercial timetabling products
• GALib, a nice C++ toolkit for GA work, but which takes a while to learn properly. Well documented for programmers
• Mike Carter's collection of real-world university exam timetabling problems, online at Toronto. Includes some big problems
• Darrel Whitley's GA tutorial, online at Colorado School of Mines as uncompressed postscript (400Kb)
• the GA Archives, which includes links to many GA-related sites

• PGA version 4.0, a GA toolkit in C. It has a range of problems built in, including basic timetabling stuff, and is easy to extend. In gzipped tar format -- it is really intended for use on Linux/Unix boxes, but can also be used on Windows if you are prepared to edit it a bit to make the simple screen-handling stuff work.
• gatt version 1.8, a better GA-based timetabler. However, it still uses a `direct' representation; that is, a chromosome is an array such that entry N gives the number of the timeslot in which to put event (exam) N. In gzipped tar format.
• a paper, presented at PATAT2 and in the subsequent book, which explians what is wrong with the kind of representation used in gatt and PGA. In uncompressed Postscript form.
• another paper, in the proceedings of GECCO-99, which shows how you might use a GA to find a combination of heuristics for solving a ranfge of timetabling problems. In uncompressed Postscript form.
• clump.c, a C program to generate timetabling problems for gatt, but easily modified for other formats.
• sclique.c, another problem generator in C. This generates problems containing a number of cliques (that is, maximally-interconnected subsets within the constraint graph), but the connections between separate cliques are fairly sparse.
• pyramid.c, a C program to generate the `pyramidal chain' problems described in the PATAT2 paper above.
• clique-1.4, a program to analyse a graph (represented in a simple text-based form) to find the largest, or all, of the cliques -- a clique is a maximally-connected subset of the graph, that is, a subset such that all elements of it are connected to all the others in the subset. This is a fairly efficient but brute-force, exhaustive searcher. In gzipped tar format.