I added another (better) description of the FET generation algorithm, on the FET documentation page ( http://lalescu.ro/liviu/fet/doc/ ) and inside the FET package. You can read it there.
As an interesting note, I began working on FET in November 2002, and found the algorithm in June 2007 (though I was very near the solution in February 2007, a few bugs keeping it hidden for 4 more months). It took me about 5 years to discover this algorithm contained in a half page description, containing 9 simple steps. Also, I must mention that a few phrases in two papers helped me (they are listed in the references section of FET on the documentation page).
And I must admit that it was Volker Dirr's persistence which convinced me to begin and continue hunting for the better algorithm.
I also write it here, for convenience:
-----------------
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", though it might be related to the algorithm known
as "ejection chain"):
1) Sort 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).
I updated step 2 d), I forgot to write about a restriction on the total number of recursive calls to stop when placing activity A_i.
I made again minor adjustments (to the initial post).
I made a minor change in step 2 f) (see the modified initial post).
Sir i am a student of the Computer Science, and sir i want the details information about the Algorithm which are used in the FET.
Please see the initial post, then Documentation section of FET, then fet-v.v.v/doc/algorithm directory.
"Lots of other constraints (excluded here :-\, for simplicity)."
where can i find this constraints list? please :-[
Quote from: ibrahim ragab on March 17, 2013, 06:45:04 PM
"Lots of other constraints (excluded here :-\, for simplicity)."
where can i find this constraints list? please :-[
All the constraints, not including the basic ones.
For instance, teachers max days per week. If we have a constraint for teacher T, max 4 days (5 days week), and the timetable for T is occupied with 4 days and FET tries to put an activity of teacher T into the 5th day, then we need to unallocate all the activities of T for another day.
These are taken care of in generate.cpp, one at a time (but some constraints are taken in combinations, because they depend on each other).
Let me know if you understood or I need to detail some more.
What do you mean:
QuoteSort activities, most difficult first.
How do you measure "difficulty"?
See generate_pre.cpp, lines 7721-8471, function sortActivities(...). An activity is difficult for instance if its room is not available in some slots, or if its teachers/students sets are highly occupied. Or if it is not allowed in some slots; etc.
Hii...Can you please help me implementing the last two steps in your algo.I am using in my project work of school. How are last two steps implemented?
2 f) If all (or a reasonable number of) time slots were tried unsuccessfully, return without success.
>>>> Now A_p and A_q and A_r are not able to place. We will go back to A_i and look for A_i???
(is this how it should work)?
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).
(If A_i is left unplaced. We should place A_p,A_q and A_r iteratively. What if still it not able to place?? And what are other possible things which can be done here?)
Please help ASAP.Thanks in advance.
Quote from: hitesh on January 08, 2015, 06:33:17 PM
Hii...Can you please help me implementing the last two steps in your algo.I am using in my project work of school. How are last two steps implemented?
2 f) If all (or a reasonable number of) time slots were tried unsuccessfully, return without success.
>>>> Now A_p and A_q and A_r are not able to place. We will go back to A_i and look for A_i???
(is this how it should work)?
I think you got the wrong idea. Leave A_p, A_q and A_r in their place, and A_i is still unallocated and return. You are still trying to place A_i.
Quote
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).
(If A_i is left unplaced. We should place A_p,A_q and A_r iteratively. What if still it not able to place?? And what are other possible things which can be done here?)
Please help ASAP.Thanks in advance.
Again I think you got the wrong idea. A_i
can be placed if you make A_p, A_q and A_r unallocated.
Also, you can see the code in generate.cpp (I admit it looks scary, but you can jump over similar parts which are very long).
Okay. But in the last step. We unallocate A_p,A_q and A_r and allocated A_i in that slot.Right?
And this time we try to place A_p,A_q and A_r iteratively?Right?
Actually am not that comfortable in C++. Am trying this in PHP.
Thanks for a quick reply. :)
Quote from: hitesh on January 08, 2015, 06:53:42 PM
Okay. But in the last step. We unallocate A_p,A_q and A_r and allocated A_i in that slot.Right?
And this time we try to place A_p,A_q and A_r iteratively?Right?
We will do step (2) for each of A_p, A_q and A_r (3 steps instead of a single one, for A_i).
ohh. I am totally lost now I think. Then in step 2(d)-> Were we trying to place (A_p , A_q , A_r)as a whole(simultaneously) and where A_i already placed.
And in the last step:
We are trying to place for each of A_p, A_q and A_r?
(I know am taking a lot of time to understand, Please clear things a little bit). I have been studying/working on this since a month.
In (2 d) we place A_p, A_q and A_r in turn, one at a time, recursively, at level+1 (if A_i is at level+0).
In (2 g), we are at level=0. Place A_i, and we have to place A_p, A_q and A_r at level=0, in turn, in step (2) (in order, one at a time).
Parenthesis:
In step (2), level=0.
I hope I am not mistaking.
But again. In 2(g). -> A_p or A_q or A_r itself can go to further recursion if there are conflicts in every slot?
//some_code_earlier
Foreach(conflicts to A_i)
{
while(level!=0)
{
return;
}
if(level==0)
{
function(conflict,level);
}
}
Are you saying something like this?
Quote from: hitesh on January 08, 2015, 07:38:54 PM
But again. In 2(g). -> A_p or A_q or A_r itself can go to further recursion if there are conflicts in every slot?
in (2 g) we unallocate A_p, A_q and A_r. It is now possible to place A_i. level=0. Start with level=0 and place recursively A_p. Then start with level=0 and place A_q, then A_r also recursively at level 0.
Quote
//some_code_earlier
Foreach(conflicts to A_i)
{
while(level!=0)
{
return;
}
if(level==0)
{
function(conflict,level);
}
}
Are you saying something like this?
Sorry, I don't understand.
Okay. And in 2(d) we were calling A_p,A_q and A_r at Level+1. Difference is in the levels only? Right?
Quote from: hitesh on January 08, 2015, 07:53:42 PM
Okay. And in 2(d) we were calling A_p,A_q and A_r at Level+1. Difference is in the levels only? Right?
I think yes.
Thanks a lot Liviu. :) Will implement this.
You're welcome! :) I advise you to take a look at the function generate.cpp randomSwap(...), its beginning and its end.
Hii..liviu!
Can you help in knowing that is it possible to create n different timetables from this algorithm?
Start n generations with different random seeds. If you have multiple cores, you can even put a single timetable on a single core.
What is the interpretation of random seeds? Thanks.
XX and YY in timetable_defs.cpp. Read also the FET Settings Random seed dialog Help button.
Quote from: Liviu Lalescu on January 08, 2015, 07:55:54 PM
Quote from: hitesh on January 08, 2015, 07:53:42 PM
Okay. And in 2(d) we were calling A_p,A_q and A_r at Level+1. Difference is in the levels only? Right?
I think yes.
Hi Liviu, I'm a bit confused about the difference between (2 d) and (2 g)?
What are the levels being referred to here?. Thank you
Quote from: Winnie on February 27, 2015, 01:41:06 PM
Quote from: Liviu Lalescu on January 08, 2015, 07:55:54 PM
Quote from: hitesh on January 08, 2015, 07:53:42 PM
Okay. And in 2(d) we were calling A_p,A_q and A_r at Level+1. Difference is in the levels only? Right?
I think yes.
Hi Liviu, I'm a bit confused about the difference between (2 d) and (2 g)?
What are the levels being referred to here?. Thank you
I don't know how to explain this better.
At level (2 d) the level of recursion is between 0 and 13. At level (2 g) if the level is 0 we do our displacements and placement.
Thanks for you reply. Quick question though, When does an activity(which from the manual is a lecturer+student group+subject) conflict with other activities, is it when they all have the same particular time-slot as the preferred one?
Quote from: Winnie on March 02, 2015, 08:03:55 PM
Thanks for you reply. Quick question though, When does an activity(which from the manual is a lecturer+student group+subject) conflict with other activities, is it when they all have the same particular time-slot as the preferred one?
An activity is incompatible with another one if they have common teachers or subgroups. If two activities overlap in time (they occupy at least a common time slots), we have a basic conflict.
Thank you. I'm trying to modify FET to suit my schools needs, hence trying to understand the algorithm so I know how to modify it.
You are welcome :)
What is missing? What do you need?
I'm just seeing your Message.
I need to be able to make FET split an activity into 3 across 3 days, where the first two days are not consecutive eg. Monday-Wednesday-Friday or Tuesday-Thursday-Friday. The third split should always occur on a Friday.
Quote from: Winnie on March 17, 2015, 06:07:16 PM
the first two days are not consecutive eg. Monday-Wednesday-Friday or Tuesday-Thursday-Friday.
Min 2 days between activities.
Quote
The third split should always occur on a Friday.
Subactivities preferred time slots, or activity preferred time slots.
Thanks for your quick reply. However I meant to write Monday-Wednesday-Friday and(not or) Tuesday-Thursday-Friday. Activities that occur on Monday should occur at the same time on Wednesday. Same for Tuesday and Thursday. Thank you
Quote from: Winnie on March 17, 2015, 09:16:42 PM
Thanks for your quick reply. However I meant to write Monday-Wednesday-Friday and(not or) Tuesday-Thursday-Friday. Activities that occur on Monday should occur at the same time on Wednesday. Same for Tuesday and Thursday. Thank you
Then add also a max 2 days between activities, and same starting hour?
Thank you. I'll try that
Hi Liviu, is it possible to make the number of periods or hours for one particular day be different from the other days
Hallo Winnie, please use a better fitting topic next time. Your questions doesn't fit into this one.
Are you asking as a coder or as a user?
As a coder: Of course you can do that, but in my opinion it isn't needed since there are easy workarounds.
As a user: Please see this topic:
http://lalescu.ro/liviu/fet/forum/index.php?topic=1876.0
Let us know if/why you can't use one of that workarounds in the other topic.
Thank you, will use a better topic next time.
What about space constraints and their interaction with time constraints?
I think this point is very important in the algorithm and the explanations are very few or very simple!
I also think that space constraints have an impact that can not be neglected on the work of the program and its performance in general?
Quote from: Benahmed Abdelkrim on April 13, 2018, 06:59:22 PM
What about space constraints and their interaction with time constraints?
I think this point is very important in the algorithm and the explanations are very few or very simple!
I also think that space constraints have an impact that can not be neglected on the work of the program and its performance in general?
The algorithm firstly cares about time constraints, then immediately cares about the space constraints. These stages look similar.
The algorithm succeeds in putting activities first, but when the table is full there is difficulty in completing the table due to the interaction of time constraints with space constraints. Sometimes he moves forward and then back and it may take a long time!
Often, in some tables, this is due to space constraints, or to misuse by the user, which occurs because of the user's ignorance of his dataset..
So it is better to know the dataset well, and choose the appropriate constraints.
You are right.
I take care when computing the initial order of time and space constraints both.
Quote from: Liviu Lalescu on April 14, 2018, 06:47:57 AM
You are right.
I take care when computing the initial order of time and space constraints both.
Yes, the initial order has a very important impact on the good performance, and also on the speed of production.
Can we know how the algorithm calculates the initial order?
How do you know the algorithm that certain activities are difficult and ranked in the first order?
Is there an equation that helps to calculate the initial order?
I think this point needs to be lit up to better understand it
In some complex tables I make a simple change in the initial order, which improves program performance in terms of output speed. I think this is interesting! and It needs a deep interpretation.
you can read that in engine/generate_pre.cpp. Have a look at "sortActivities".
in fact there are 2 things:
a) number of free time slots. if the activity has got only a low number of free slots, than it must be first
b) number of conflicts to other activities. if an activity can't be placed with many ohter activities at the same time, than it must be first
currently it is a mix of a) and b). Sometimes a) is more highly needed but sometimes b) is highly needed.
you are right: the algorithm isn't always the best in that part. i noticed myself that a) is sometimes undervalued and i set it many first. but it is difficult to give a nice rule for this.
improving this is not just coding it. you need to check that with a lot of different datasets/constraints a lot of different times.
so i guess this is a work that need to least several weeks of testing to check if it is better or not than the current variant.
In step 2 g) We have now 3 - 1 = 2 more activities to place...should it be 4-1=3 more activities to place in your example? You placed A_i to T_j, then 3 activities A_p, A_q, A_r will be unallocated and need to be placed latter.
Hmm, indeed! :-[
I wonder why nobody else found this bug until now.
I will correct for the next FET version and on the FET homepage.
No. It is correct 3-1=2, because I am referring to the difference between the initial state and the next state.
Here is an example: A1, A2, A3, A4, A5 placed, A6 to be placed (A6 is unallocated). Say A6 is placed and displaces A1, A3, and A4. Then these are placed: A2, A5, and A6, and unallocated: A1, A3, and A4. So there are 3 - 1 = 2 more activities to be placed compared to the initial situation.
You are right, there are 2 more activities to be placed compared to the initial state. There are 3 activities need to be placed. I have got other questions about the generate.cpp. What are the functions of the following variables used in randomSwap:
1.swappedActivities.
Does swappedActivities[ai]=true mean activity ai has been allocated? If it does, "swappedActivities[permutation[added_act]]=true" in generate.cpp line 3007 (version-5.37.5) means that permutation[added_act] is allocated, but to my understanding, this activity has not been allocated to any time yet until this statement.
2.triedRemovals.
Does triedRemovals(i,j) mean how many times activity i has been allocated in timeslot j? What does this variable do in the randomSwap()?
Thanks a lot.
1. It means that the activity was already tried to be placed in another slot. If an activity is swapped, it cannot be displaced anymore (to try to avoid a kind of cycling). The activity permutation[added_act] cannot be placed and then displaced. Before randomSwap(permutation[added_act], 0) all activities are not swapped, without permutation[added_act], which is swapped. Then if in the recursive calls we displace some activities and place them in another slot, in the continuation of the recursive calls, with a greater level, the swapped activities cannot be displaced anymore. If we get back from this level, swappedActivities[a_p] becomes false again (I think in line 10286).
2. triedRemovals(i, j), if I remember correctly, means the number of times we deallocated activity i from slot j at level 0 in the last tabu_size = nInternalActivities*gt.rules.nHoursPerWeek. We will prefer the smallest number triedRemovals when choosing in which slot to place A_i at level 0 (step (2 g) ), to avoid cycling.