FET generation algorithm - "recursive swapping"

[Liviu Lalescu]

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

[Liviu Lalescu]

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.

[Liviu Lalescu]

I made again minor adjustments (to the initial post).

[Liviu Lalescu]

I made a minor change in step 2 f) (see the modified initial post).

[khalilahmad]

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.

[Liviu Lalescu]

Please see the initial post, then Documentation section of FET, then fet-v.v.v/doc/algorithm directory.

[ibrahim ragab]

"Lots of other constraints (excluded here , for simplicity)."
where can i find this constraints list? please

[Liviu Lalescu]

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

[liquid]

What do you mean:

Sort activities, most difficult first.

How do you measure "difficulty"?

[Liviu Lalescu]

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.

[hitesh]

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.

[Liviu Lalescu]

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.

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

[hitesh]

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.

[Liviu Lalescu]

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

[hitesh]

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.