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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
|
This file modified 1 Oct. 2007
Adding 1 Oct. 2007:
The idea of timetable generation is good. But the implementation of algorithm is not very good right now
(1 Oct. 2007). There is room for many improvements. I'll try to resolve this soon, but I cannot be sure
of a fast solution. If you try to understand the algorithm, do not take for granted every part of code in
generate.cpp, the parts in function randomwap() which compute for each constraint the list of conflicting
activities is badly written. I'm sorry, ideas came after writing it. I might probably release many testing
versions before releasing these modifications, so if you want feel free to join mailing list to see
when testing versions are released.
Some words about the algorithm:
FET uses a heuristic algorithm, placing the activities in turn, starting with the most difficult ones.
If it cannot find a solution it points you to the potential impossible activities, so you can
correct errors. The algorithm swaps activities recursively if that is possible in order to make
space for a new activity, or, in extreme cases, backtracks and switches order of evaluation.
The important code is in src/engine/generate.cpp. Please e-mail me for details or
join the mailing list. The algorithm mimics the operation of a human timetabler, I think.
When placing an activity, I choose the place with lowest number of conflicting activities and
recursively replace them. I use a tabu list to avoid cycles.
The maximum depth (level) of recursion is 14.
The maximum number of recursive calls is 2*nInternalActivities (found practically - modified 18 Aug. 2007).
I tried with variable number, more precisely the 2*(number of already placed activities+1). I am not sure about
the results, it might be better with variable number, but not sure.
The recursion chooses only one variant from depth 5 (modified 15 Aug. 2007) above, then it returns.
How to respect the students gaps (possible in combination with early)? Compute the number of
total hours per week for each subgroup, then when generating, the total span of lessons
should not exceed the total number of hours per week for the subgroup. The span is
computed differently if you have no gaps or if you have no gaps+early
Adding - 16 Aug 2007, modified 22 Aug 2007:
The structure of the solution is an array of times[MAX_ACTIVITIES] and
rooms[MAX_ACTIVITIES], I hope you understand why. I begin with unallocated. I
sort the activities, most difficult ones first. Sorting is done in
generate_pre.cpp. In generate_pre.cpp I also compute various matrices which
are faster to use than the internal constraints list. Generation is
recursive. Suppose we are at activity no. permutation[added_act] (added_act
from 0 to gt.rules.nInternalActivities - permutation[i] keeps the activities
in order, most difficult ones first, and this order will possibly change in
allocation). We scan each slot and for each slot record the activities which
conflict with permutation[added_act]. We then order them, the emptiest slots
first. Then, for the first, second, ... last slot: unallocate
the activities in this slot, place permutation[added_act] and try to place
the remaining activities recursively with the same procedure. The max level of
recursion is 14 (humans use 10, but I found that sometimes 14 is better) and
the total number of calls for this routine, random_swap(act, level) is 2*nInternalActivities
(found practically - might not be the best).
If I cannot place activity permutation[added_act] this way (the 2*nInternalActivities limit is
reached), then I choose the best slot, place permutation[added_act] in this
slot and pull out the other conflicting activities from this slot and add
them to the list of unallocated activities. added_act might decrease this
way. Now I keep track of old tried removals and avoid them (they are in the
tabu list - with size tabu_size (nInternalActivities*nHoursPerWeek for now)) - to avoid cycles.
The routine random_swap will only search (recursively) the first (best)
slot if level>=5. That is, we search at level 0 all slots, at level 1 the same,
..., at level 4 the same, at level 5 only the first (best) slot, at level 6 only
the first (best) slot, etc., we reach level 13, then we go back to level 4 and
choose the next slot, etc. This is to allow FET more liberty, I think. This
trick was found practically to be good. It might not always be good.
Adding - 26 Sept. 2007:
Please consider that the best implemented part is teachers min hours daily,
please follow its mechanism and imagine other constraints should be like it
(in file generate.cpp, function randomswap)
Adding - 1 Oct. 2007:
Not even teachers min hours daily is not too good implemented. I only
consider that the replaced activities are at the beginning or end of a day.
But it might be that I could only take an activity from the middle of a day
because first and last are swapped already.
Why don't I make this improvement right now: much testing and analysis of code
would be needed. I prefer to wait until I'll improve all the constraints
to be like it, then do a lot of testing again.
|
