This document was written by Liviu Lalescu. Fair use of this document is allowed/encouraged/expected.
Begin: 2011.
Last modified on: 29 December 2019.

The description of the FET timetable generation algorithm:

History: The FET project began on 31 October 2002, using a genetic algorithm. That algorithm was slow and only able to solve easy timetables. On 24 June 2007 the current algorithm was discovered, which is fast and able to solve difficult timetables. This algorithm was used starting with FET version 5.0.0. It is heuristic, probably simulating the manual procedure of finding a timetable.


The algorithm is heuristic.

Input: a set of activities A_1...A_n and the constraints.

Output: a set of times TA_1...TA_n (the time slot of each activity. Rooms are excluded here, for simplicity). The algorithm must put each activity at a time slot, respecting constraints. Each TA_i is between 0 (T_1) and max_time_slots-1 (T_m).


C1) Basic: a list of pairs of activities which cannot be simultaneous (for instance, A_1 and A_2, because they have the same teacher or the same students);

C2) Lots of other constraints (excluded here, for simplicity).

The timetabling algorithm (which I named "recursive swapping", although it might be related to the algorithm known as "ejection chain" or the more generalized "ejection tree"):