Simsttab: A timetabling engine for schools
Simsttab stands for Simplistic School Time-Tabler. It is a
timetabling engine that can generate timetables satisfying
requirements typical for secondary schools in Austria
("Gymnasium"-type), Germany and maybe other European countries.
Source code: simsttab.pl
SWI Prolog >= 5.6.50.
Simsttab uses constraint logic
programming to compute solutions.
If you install SWI Prolog from source, also compile and install
the SGML/XML-package as described in SWI Prolog's documentation.
Requirements are saved in XML-files. An example based on sample
requirements that ship with Tablix is available
Copy reqs.xml and simsttab.pl to the same
directory, and execute the program from the command line via
swipl -g "timetable('reqs.xml'),halt" simsttab.pl
You obtain a timetable
like timetable.txt, found in less than
5 seconds on a 2.4 GHz Pentium 4.
Have a look at the reqs.xml again to see
how requirements are specified.
It first states global requirements, in particular the
number of time slots that make up a week (typically in the range
of 25 to 35), and the number of time slots per day (typically
5-7). These parameters are fixed for all classes.
Next, there are lines of the form
<req subject="sjk" teacher="sjk1" amount="4"/>
<req subject="mat" teacher="mat1" amount="5"/>
Such a block is read as "Class 1a should be taught 'sjk' by teacher
'sjk1' 4 times a week (on distinct days); it is furthermore taught
'mat' by teacher 'mat1' 5 times a week (again on distinct days)", and
so on. You can choose subject and teacher names as you wish ('sjk1'
and 'mat1' are only used as convenient abbreviations). For instance, a
<req subject="Sociology" teacher="Mr. Socius" amount="4"/>
<req subject="Maths" teacher="Mr. Matho" amount="5"/>
would also be valid.
In addition to stating what subjects a class is to be taught, you
can also state which time-slots of a class are to be kept free
(starting from 0), like
Furthermore, you can enforce coupling of certain lessons (a
typical requirement for physical education lessons in Austria),
that is, two lessons of a subject have to be taught
contiguously. You can see this in the sample XML file, which
contains the line
<coupling subject="sjk" lesson1="2" lesson2="3"/>
which means that the week's third and fourth lesson of 'sjk' have
to be taught straight in a row (lesson numbering also starts
Example room allocations are:
<allocate class="1a" subject="sjk" lesson="0"/>
<allocate class="1a" subject="sjk" lesson="1"/>
<allocate class="4c" subject="mat" lesson="3"/>
<allocate class="4d" subject="mat" lesson="3"/>
This means: Room 'r1' is needed by class 1a in its week's first ("0")
and second ("1") lesson of subject 'sjk'; the same room is needed by
class 4c in its week's fourth lesson of 'mat' etc.
Specifying in which lesson a particular room is needed allows for
easy manual balancing of room allocations. For example, if it is
known that 2 classes, say 1a and 1b need a certain room at
least once a week each, in a subject that is held 4 times a
week, it could be advantageous w.r.t. calculation time to state in
advance that class 1a requires the room in its first lesson
of that subject, and class 1b in its 4th.
Teachers can have free days. On such days, no subjects will be
scheduled for the respective teacher. A free day is denoted as
<freeday teacher="ume1" day="4"/>
and days are also numbered starting from 0.