Messages

You are welcome! Thank you, too!

I hope I found the problem and improved the file. Probably the constraint suggested by choko and Vangelis is not needed for this case (but it might be useful in other cases).

choko's file is now solvable much faster and easier. I am waiting for his feedback to make sure it is correct.

Yes. your suggestion and modification boosted the flexibility by removing redundant constraints in my situation. Despite some of the unsolved practical problems, the generation takes only a very acceptable time and the result is quite satisfactory.

Million thanks again

Thank you very much for the appreciation and kind words!

I would like to check the bottleneck you are reporting (FET not being able to swap the necessary activities in a short time), but I cannot do anything without your file.

I hope a good selection of space constraints will solve the problem. I could try to help you here, but again I need your file for this.

Just sent an email. Thank you so much again.

Hello, choko,

It seems you are a mathematician who has a good grasp of FET? You identified that FET will have difficulties moving activities in this situation. I would have hoped that FET would be clever here. I did my best to avoid cycling.

Really thank you so much for your appreciation. That really means a lot to me. And again, your work is very very much appreciated.

I am terrible sorry If I made you feel offended. I can assure you that it totally was not my intention at all.

I myself, as a graduate in Mathematics and computer science, actually tried to use linear programming to write an excel program that tried to generate a timetable. But it turned out that the pivot table was too large that I could never handle. And then I found FET very much useful and I have been using it and admiring you since then. Thank you so much for your help and reply.

Maybe you could force FET to place firstly D6..D50 and F6..F50, by using the option 'group activities in the initial order'. You can see the normal order of activities, see what activity is first, and group D6..D50 and F6..F50 with it (so you will have 91 activities in this group activities in the initial order item), or group D6..D50 and F6..F50 with another activity which is near them and before D1..D5 and F1..F5.

In my situation, those E1 to E4 are actually very large blocks. Simply speaking, each of E1 to E4 has to be held at the same time with, 7 more activities. And indeed, I have like 20 more activities like E1, making a totally of 8x5x3, 120, activities to be held at 21 time slots. Even worse, some of them have different duration. So I am not sure if it is a good idea to allocate these activities in the last steps. But I will try to see if it works.

Another solution is to use space constraints. Maybe you could share your file with us/me (here/my email) and I'll try to see it.

If you categorically don't want to use space constraints, then Vangelis' suggestion is exactly what you need? It is a nice constraint, but difficult to implement. I am not sure its algorithm of timetable generation is feasible for FET. But, as I said, if we find sponsors for it, I might give it a try. Until then, it is in the TODO list.

The space constraints have been used in my fet file. And I am still figuring out if there is anything I misunderstood. Will definitely try it again.

I am not sure I'll answer so fast in the next interval, I am preparing a new FET version tonight (very minor changes). But if your problem is urgent, please mention this and I'll see it sooner.

My problem is totally not urgent. Still trying to figure out if there is any other method that help.

Again, your work and help are very very much appreciated! Thank you so much.

I actually tried some methods over these years.

I tried to set E1 and D1 to be held at the same time, so as E2 and D2, E3 and F1, and E4 and F2. It significantly reduced the time needed to generate the whole timetable. But at the same time reduced quite a lot of flexibilities. And as we have a lot more similar situations (imagine that there are 30 classes just like E that need to use other classes' homerooms), this "same time" method also significantly increases the difficulties of the generation and it turns out that there might be no solution at all.

That is exactly why, at the first place, I think if we can have the constraint that E1 must overlap with any one (or at least one) of D1 to D5 and F1 to F5, the generation will be a lot easier.

I tried. Your point 1 totally works if E1 only uses the homeroom of D.
But my situtation is a bit more complicated.

Suppose

• D1 to D5 are Class D's activities that use another room R1;
• D6 to D50 are Class D's activities that use D's homeroom R2;
• F1 to F5 are Class F's activities that use another room R3;
• F6 to F50 are Class F's activities that use F's homeroom R4;
• E1 to E4 are Class E's activities that use R2 or R4;

That means if all E1 to E4 overlapp with some of D1 to D5 and F1 to F5, that's totally fine.

But it always happens that when D1 to D49 are set, leaving, for example, Period 1 of Monday unoccupied in D's student timetable, E1 is also allocated to this period 1 of Monday so that D50 has no place to go (as period 1 of monday is the only emply slot in D's student timetable while the homeroom R2 is being used by Class E).

It often takes a pretty long time for the program to figure out that it should move D1 or D2 or D3 or D4 or D5 to this period 1 of Monday so that D50 can be allocated to, for example, period 2 of Monday (at which D1 or D2 or D3 or D4 or D5 was originally allocated) to make all D1 to D50 being allocated. And if we have a number of such situation, the time needed multiplies.

So if E1 can be set to overlap with any one of D1 to D5, such problem will not exist any more.

So your point 1 totally works if there is only E1 (without E2 to E4) which use R2 only.



In my situation, with E1 to E4 using either R2 and R4, the "max slot" might not help too much.
Chances are that

• D1 to D5 and F1 to F5 might be occupying 10 timeslots when they don't overlap with any other at all; or
• D1 and F1 can be held at the same time while D2 to D5 and F2 to F5 don't overlap, occupying only 9 time slots; or
• D1 and F1 are held at the same time, so as D2 and F2, while D3 to D5 and F3 to F5 don't overlap, occupying only 8 time slots; and so on and so forth

So if E1 can be set to overlapp with any one (or at least one) of D1 to D5 and F1 to F5, so as E2, E3 and E4, the time needed will definitely be very much shortened.

In this situation, is there anything I can try?

Maybe the following can better picture the difficulties I encountered:

Suppose D1 to D5 are activities that Class D uses Room R2 while E1 is an activity that Class E uses Room R. And D6 to D50 are D's activities that use R as well.

If D1 to D49 are all set, then Class D has only one empty slot in the student timetable, say Period 1 on Monday, and if E1 is allocated at this Period 1 on monday that uses R, then D50 which should use R cannot be allocated to this period 1 on monday as the room has already been in use.

So if I can set E1 to overlap with any one of D1 to D5, then such situation can be avoided. That was my thought. As E1 will not be allocated in the period 1 on monday.

Sorry there were some typo.


I meant:

Suppose D1 is an activity that D uses the music room while E1 is an activity that E uses R. And D2 to D50 are D's activities uses R as well.

If D1 to D49 and E1 use up all the 50 R's slots, then D50 has no place to go.

1) Yes, it is possible, exactly as I said regarding the constraint activities occupy max time slots from selection.

Example: D has activities A1, A2, A3, A4 in other room than home room, and E has activity A5 to be in D's home room. Then add A1, A2, A3, A4, A5 in this constraint, select all slots (X or red), max occupied = 4 (if each activity has duration 1).

I think I misunderstood something at the first place. Sorry about that. I think this good method will work. Let me try. Thank you very much.

2) Considering your exact situation, maybe you could use space constraints. Home room R for D, and preferred room for that E's activity.

Suppose D1 is an activity that D uses the music room while E1 is an activity that E uses R. And D2 to D49 are D's activities uses R as well.

If D2 to D49 and E1 use up all the 50 R's slots, then D1 has no place to go.

So I am afraid it doesn't help much? Or is it me who overlooked or misunderstood something again?


Once again. FET itself and your help is very much appreciated. Thanks a lot!

For example, in a school, suppose there are 50 time slots and 50 activities for class D. But D's homeroom will occasionally be used by class E. Examples include "E can use D's homeroom when D is having their music lesson at the music room".

I found that when 49 of D's homeroom timetable slots are used by D while the remaining one is allocated to E, it takes a long time for fet to come up with a solution. And it turns out that a solution could be found only when E's activity (which uses D's homeroom) is held when D is having an activity which is not using its own homeroom (e.g. music, Art in the Art room, Science in the laboratory). So I want E's activities to overlap with D's science or music or art or any other subjects at which D won't use its homeroom.

Is it possible?

Let me clarify a bit.

At the time when activity A is being held, either activity B or C will be held as well.

Is there any solution to deal with it?
Thank you.

You could use a constraint activities occupy max time slots from selection.

Thank you for your reply. But I am afraid that the result might happen to be the activity won't overlap with any other activities at all.

Is there anything I can try?

Other than "a set of activities that are not overlapping with any other", is it possible to develop a new set of constraints that an activity must be overlapping with at least one activity from a set of activities"?

Setting two activities beginning at the same time same day is similar.