This document was written by Liviu Lalescu. Fair use of this document is allowed/encouraged/expected.

Begin: 2011.
Last modified on: 23 February 2025.


References for the idea of the algorithm used in FET: please see the REFERENCES file from the main directory or
the interface menu FET > Help > About > References.


This is the description of the timetable generation algorithm used by FET.

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"; it might also be related to the manual timetabling method):

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