Conditional sharing of a multi-capacity gym depending on student year difference

[Eva Friederike]

First of all, thank you for developing and maintaining such a powerful and flexible timetabling tool — FET is truly an impressive application.

Hello,

I am trying to model the following situation in FET and would appreciate advice on how to implement it correctly.


Physical Situation

• We have 2 physical gyms:
• Main Gym
• Annex Gym
• Each gym can host 2 student groups simultaneously.
• Physically, each gym is one shared space, large enough for two parallel activities.

In FET, I modeled this by splitting each gym into two real rooms:

• Main-Gym-1
• Main-Gym-2
• Annex-Gym-1
• Annex-Gym-2

Required Constraint

Students are divided into 11 year cohorts (Grade 1–11).

Two groups may share the same physical gym at the same time only if their grade difference is at most 1.

In other words:

If two activities are placed in rooms belonging to the same physical gym, then enforce |gradeA − gradeB| ≤ 1.

Example:
If Grade 6 uses Main-Gym-1 and Grade 10 uses Main-Gym-2 at the same time, this must be forbidden, because both rooms belong to the same physical Main Gym.


Question

Is there a way in FET to model this type of conditional sharing of a multi-capacity room?

Thank you in advance.

[Liviu Lalescu]

Hello, Eva, and thank you for your kind words! 

I read your post, and I think this feature is not available in FET. I will think some more in the next interval and let you know if it is available in FET, using some usual methods or tricks.

Also, I cannot think of a way to add a new official FET constraint, because the requirement is very specialized, but it should be possible as a customization of FET.

[Eva Friederike]

Thank you for your answer, Liviu! I'm looking forward to your further suggestions, as we found it too restrictive to assign student groups manually along with the other constraints.

[Liviu Lalescu]

You are welcome, Eva!

I thought of a (complicated) trick, which might work:

1) Make the number of students of each students set = 1.

2) Add more constraints of type activities max total number of students in selected time slots:

  a) Add a constraint for all activities of gym of the first group of year 1, plus all gym activities of all groups of years 3, ..., 11. Select all time slots. Max total number of students = 3.

  b) Add a constraint as above, for the second group of year 1...
...
  c) Add a constraint as above, for the last group of year 1...

  d) Add a constraint for all activities of gym of the first group of year 2, plus all gym activities of all groups of years 4, ..., 11. Select all time slots. Max total number of students = 3.
...
  e) Add a constraint as above, for the last group of year 2
  f) Add a constraint for the first group of year 3, and then all groups of years 1, 5, ..., 11.
... and so on.

I hope I am not mistaking.

[Eva Friederike]

Thank you for the suggestion, Liviu!

I have read your message carefully. At the moment, I do not fully understand how this trick should work in practice, mainly because this is a new type of constraint for me and I have not used it before.

After installing the latest version of FET, I noticed that this constraint is marked as "potentially very SLOW". Which is also a little bit scary 


Question regarding the "max total number of students" value

I would like to better understand why, in your example, the
"Activities max total number of students in selected time slots"
constraint uses the value 3.

As I understand it, each student set has its number of students set to 1, so each scheduled activity counts as 1 student. Therefore, a maximum value of 3 means that at most three such activities may take place simultaneously within the selected group of activities.

However, I am not sure what prevents the algorithm from producing a placement like the following:

• Group 05a in Main-Gym-1
• Group 07a in Main-Gym-2
• Group 06a in Annex-Gym-2
• No activity in Annex-Gym-1

In this case, there are exactly 3 activities in the same time slot, so the total number of students is 3.
Therefore, the constraint "max total number of students = 3" is not violated.

However, the ±1 year difference condition is violated, because Grade 05 and Grade 07 are simultaneously inside the same physical Main Gym (Main-Gym-1 and Main-Gym-2).

So my confusion is:

How does this constraint actually prevent incompatible grades from sharing the same physical gym, rather than simply limiting the total number of simultaneous activities?

I would appreciate clarification on this point, because I may be misunderstanding how the constraint interacts with the selected activity sets.

Thank you again for your time and patience.

[Liviu Lalescu]

You are welcome, Eva!

First of all: as you noticed, as I noticed also 15 minutes ago, we could better use the constraints of type activities max 3 simultaneous in selected time slots, instead of the number of students. It might be more efficient.

"potentially very SLOW" - I wrote that when adding the constraint, but I am not sure. Testing is needed (maybe a comparison with max simultaneous in selected time slots, suggested above).

My suggestion was done to ensure that in each slot there exists a legal placement of the groups in the gym. Yes, my small mistake, you might need to swap some groups in the gyms, but it should be easy and possible in the final timetable.

If you really need a perfect solution, I think a customization is needed.

[Eva Friederike]

Hello, Liviu!

I just wanted to write a short follow-up message to express my gratitude after some time.

At first, I wasn't completely sure about your solution and decided not to implement it. However, as time passed—a month —I began to better understand its value.

A few days ago, I finally implemented it — and it worked very well. It may not be a perfect solution, but it is absolutely a great and very useful one.

Thank you very much again for your help!

[Liviu Lalescu]

Hello, Eva,

Thank you for your feed-back! I am glad it works! 

[Eva Friederike]

For anyone who would like to implement this in their institution, here is what I did:

Instead of using the constraint
"Activities max total number of students in selected time slots",
I used
"Activities max simultaneous in selected time slots" with max: 3.

The rest of Liviu's suggested approach remained unchanged.

Happy timetabling!

[Liviu Lalescu]

Thank you! If it is not private, could you tell us your institution, or region? Does it have a website with the produced timetable?

[Volker Dirr]

If you timetable is not too difficult, i suggest to just select 2 groups and set the "same staring time" constraint.
Advantage: The physical education teachers might even mix the groups. For example if they want to do different physical educations for boys and girls and since you set an "same staring time" constraint this will be also fine, if you need to generate a new timetable later.
disadvantage: maybe a bit more difficult to solve