This document was written by Liviu Lalescu. Fair use of this document is allowed/encouraged/expected.
Begin: 2011.
Last modified on: 29 December 2019.
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).
Constraints:
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"):
1) Sort the activities, most difficult first. Not critical step, but speeds up the algorithm maybe 10 times or more.
2) Try to place each activity (A_i) in an allowed time slot, following the above order, one at a time. Search for an available slot (T_j) for A_i, in which this activity can be placed respecting the constraints. If more slots are available, choose a random one. If none is available, do recursive swapping:
2 a) For each time slot T_j, consider what happens if you put A_i into T_j. There will be a list of other activities which don't agree with this move (for instance, activity A_k is on the same slot T_j and has the same teacher or same students as A_i). Keep a list of conflicting activities for each time slot T_j.
2 b) Choose a slot (T_j) with lowest number of conflicting activities. Say the list of activities in this slot contains 3 activities: A_p, A_q, A_r.
2 c) Place A_i at T_j and make A_p, A_q, A_r unallocated.
2 d) Recursively try to place A_p, A_q, A_r (if the level of recursion is not too large, say 14, and if the total number of recursive calls counted since step (2) on A_i began is not too large, say 2*n), as in step (2).
2 e) If successfully placed A_p, A_q, A_r, return with success, otherwise try other time slots (go to step (2 b) and choose the next best time slot).
2 f) If all (or a reasonable number of) time slots were tried unsuccessfully, return without success.
2 g) If we are at level 0, and we had no success in placing A_i, place it like in steps (2 b) and (2 c), but without recursion. We have now 3 - 1 = 2 more activities to place. Go to step (2) (some methods to avoid cycling are used here).