Some useful timetabling-related software and links
Page maintained by Peter Ross, phone ext 2766
Handy external links:
Handy links to some Napier-local stuff:
- 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.