Custom FET BP - block planning (Need help choosing a custom version)

[Liviu Lalescu]

I just released a new version, updated from the official 5.44.4, and with a new constraint suggested by Darren McDonald, using ideas from CPT and me: max total activities from set in selected time slots. This way the user can make progressive approach to minimize the activities scheduled in the fake/overflow slots.

[Darren McDonald]

The Mac version of FET 5.44.4-BP is now available for download here.

[Liviu Lalescu]

I released version 5.44.9-bp. It has a different icon than the official (suggested by Darren McDonald) and searches for crtversion-bp.txt (so it has a dedicated search for updates on startup).

[Darren McDonald]

The Mac version of FET 5.44.9-BP is now available for download here.

[Volker Dirr]

Not sure if needed, but i compiled the 32 bit version:
https://timetabling.de/download/32bit/

[ChicagoPianoTuner]

I am not sure if this is the right place for this question as it is about FET in general, but I will ask it here anyway. Let me know if you want me to move it.

Let's say FET has scheduled N activities, and it goes to schedule activity N + 1. Activity N + 1 has some constraint with weight < 100%, let's say 95% for example. Let's also assume that it is impossible for FET to schedule the activity in such a way that it satisfies the constraint without altering any of the first N activities. Let's also say that there's some other activity, maybe activity N - 1, with a constraint of weight 99% that has been satisfied.

Moreover, let's say that FET "realizes" it can EITHER break the constraint associated with activity N + 1, or it can break the constraint associated with activity N - 1. Will it always break the constraint with the lower weight (N + 1), or will it break the constraint of the first activity it scheduled (N - 1) to accommodate the new activity?

I hope that question is clear. I'll rephrase if not.

[Volker Dirr]

it will place N+1 and unallocate N-1, no matter if the weight of N-1 is 0% or 100%, since in that moment the algorithm don't know if it can place N-1 at an other location with or without breaking a constraint.
But Liviu knows better than me.

[ChicagoPianoTuner]

Ah, okay, if that is true, it might lead to some solutions that are 'less good' than others, right? I think you and I have spoken about this in the past regarding room placements.

[Liviu Lalescu]

Yes, as Volker said. In 95% of cases it places N+1 without breaking its constraint, in 5% of cases it breaks N+1's constraint. It does not care about the other activities' constraints.

[ChicagoPianoTuner]

Thank you for clarifying. I will explain my use case (it is simpler than before) and my plan for using constraints. If you can think of a better way, can you please tell me?

• There are real 8 blocks (A-H).
• Students in grades 9 and 10 take one course in each block (8 courses total).
• Each student in grades 9-10 has 6 "mandatory" courses that must be scheduled in a real block with weight 100% - easy to implement, set of activities set preferred starting times, using a tag.
• The remaining courses are listed in preference order. There are 4 preferences, ranked 1-4. It is desired that 2 of these fall in the real blocks. The other 2 may be considered 'reserve' choices and should hopefully fall in fake blocks.
• It may be the case that some students request courses that are impossible (even when considering the reserve choices), so any FET constraints must be sensitive to this and "allow" the student to only take 7 courses in real blocks. (We would then ask those students to submit different choices, or, more likely, choose from the available options.) So something like "activities occupy max/min slots from selection" will not work, I do not think, because that must have weight 100%

The only strategy I can think of is, for those 4 remaining courses, set activities preferred starting time "first choice" = 99.9% in real hours, "second choice" = 99% real hours, "third choice" = 98%, "fourth choice" = 95% or something like that. But it might be the case that FET places "fourth choice" in real hours by unscheduling "second choice". Moreover, it may be the case that FET places all four in fake hours. As I mentioned above, I could use activities occupy max slots from selection, select each student's ten choices, max occupied hours = 2, selected hours = fake hours, but some students may have made impossible choices. I could try this approach and manually changing constraints for students/activities that cause FET to 'get stuck,' but the activity where FET 'gets stuck' may not be on the activity that is actually impossible, if you know what I mean.

My best plan is to not use activities occupy min/max slots at all, and just generate multiple timetables, and choose the one with the lowest weighted conflict score.

Is there a better way?

[Liviu Lalescu]

Did you see in the latest FET-BP the new constraint "max total activities in selected time slots"? Might help with a progressive approach.

[Darren McDonald]

Following Liviu's suggestion to consider the "max total activities in selected time slots" constraints, you might try something like the following.

Set up 8 "real" blocks A–H, then have 4 "overflow" blocks, say F1–F4. (This would allow a student to get their 6 mandatory courses in "real" blocks, with the worst case scenario of 4 unallocated courses occupying F1–F4.)

Using "A set of activities has a set of preferred starting times" constraints, restrict all compulsory courses to blocks A–H, restrict all preference 1 choices to be allowed in A–H and F1, preference 2 choice to fall in A–H and F2, etc. So, a preference two choice that isn't timetabled will appear in block F2.

Now you can use four "max total activities in selected time slots" constraints. Assuming you've got 300 students, if you select all block F1 slots and set "max total activities in selected time slots" to allow at most 50 activities in block F1, you're tolerating at most 50 students not getting their preference 1 choices. Lower this number until timetables are impossible to generate, and you've got your optimal preference 1 arrangement. Then, use this same constraint approach on blocks F2–F4 in that order, and you should get optimal blocks.

[ChicagoPianoTuner]

Using "A set of activities has a set of preferred starting times" constraints, restrict all compulsory courses to blocks A–H, restrict all preference 1 choices to be allowed in A–H and F1, preference 2 choice to fall in A–H and F2, etc. So, a preference two choice that isn't timetabled will appear in block F2.

Now you can use four "max total activities in selected time slots" constraints. Assuming you've got 300 students, if you select all block F1 slots and set "max total activities in selected time slots" to allow at most 50 activities in block F1, you're tolerating at most 50 students not getting their preference 1 choices. Lower this number until timetables are impossible to generate, and you've got your optimal preference 1 arrangement. Then, use this same constraint approach on blocks F2–F4 in that order, and you should get optimal blocks.

This is a very clever approach and is not one I thought of. Thank you for your suggestion - I'll try it tomorrow. I didn't totally understand the use of "max total activities in selected time slots," but now I do. Very helpful - thanks all!

[Darren McDonald]

Thanks for your input here too—when I was working on my block plan for this year, Liviu suggested that it might be possible to use a "fake" overflow block for courses that couldn't be timetabled—a strategy that he mentioned you had used. It was through working with that approach (when trying to optimize the resulting block plans) that led to the development of that new constraint. So, it's appropriate that the new constraint is now useful to you! 

[ChicagoPianoTuner]

It's definitely a team effort

I just thought of something. Right now, for example, teacher T1 (really a FET day) teaches subjects S1, S2, and S3. Constraint "activity tags not overlapping," where the subject = the tag, prevent those subjects from, well, overlapping. So it's impossible that teacher T1 teaches S1 and S2 simultaneously.

The problem is those constraints (tags not overlapping) also exist in F1-F4, but we don't want that to be the case in those slots - anything should be able to overlap in fake blocks. Any suggestions for how to achieve the same result?