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

Simsttab requires 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.

Quick Start



Requirements are saved in XML-files. An example based on sample requirements that ship with Tablix is available as reqs.xml.

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.

Specifying Requirements

Lessons

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
      <class id="1a">
          <req subject="sjk" teacher="sjk1" amount="4"/>
          <req subject="mat" teacher="mat1" amount="5"/>
          ...
      </class>
    
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 block like
      <class id="1a">
          <req subject="Sociology" teacher="Mr. Socius" amount="4"/>
          <req subject="Maths" teacher="Mr. Matho" amount="5"/>
          ...
      </class>
    
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
      <free slot="0">
    

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 with 0).

Room allocation

Example room allocations are:
      <room id="r1">
          <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"/>
      </room>
    
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.

Free days

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.


Main page