Suggestion about a new set of constraints

[choko]

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.

[Liviu Lalescu]

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

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

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

Please use a constraint activities same starting time (day+hour).

[choko]

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?

[choko]

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.

[choko]

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?

[Vangelis Karafillidis]

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.

Liviu, I think we have already discussed this issue. Sometimes, constraints of the type "a set of activities share min common time slots with any of another set of activities" (and maybe in selected time slots). As you told me, this type of constraint is extremely difficult to be implemented. But it seems this type of constraint is quite useful...

Vangelis.

[Liviu Lalescu]

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?

I think there are two solutions:

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

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

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.

Liviu, I think we have already discussed this issue. Sometimes, constraints of the type "a set of activities share min common time slots with any of another set of activities" (and maybe in selected time slots). As you told me, this type of constraint is extremely difficult to be implemented. But it seems this type of constraint is quite useful...

Vangelis.

Thank you, Vangelis! I will search the TODO and if this suggestion is not already in, I'll add it. However, I hope that choko's problem can be solved by my solutions above.

I would be opened to give a try to implement the more general suggested constraint if I would be sponsored.

[choko]

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!

[Liviu Lalescu]

1) You are welcome! No problem.

2) I am not sure I understand correctly your words. First of all, D2..D49 and E1 form 49 activities, not 50.

Then, D1 will not be in R. If you add a constraint home room for D as being R, and a constraint preferred room for D1 as being R2, then D1 will be in room R2 (home room constraint is ignored if an activity has a preferred room constraint for it).

Thank you for the appreciation!

[choko]

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.

[choko]

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.

[Liviu Lalescu]

You can use space constraints (as in my point 2) or, if you don't use space constraints and rooms, a constraint activities occupy max time slots from selection (as in my point 1). FET will consider the constraints while allocating, no need for the user to be worried.

[choko]

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?

[choko]

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.

[Liviu Lalescu]

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.

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.

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.

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.