1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
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).
|
