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

[ChicagoPianoTuner]

Thank you all for your work. Sorry to be quiet, I was traveling and I am now home so can help more. CPT is a fine abbreviation for my name

The data file that I gave is incomplete. Our school is moving to a new system so I used some existing data to help explain the concept, but it does not reflect actual student choices or options. It would have taken too long to prepare sample data for you so I hope what I provided is enough to illustrate the concept.

Mathematics and English are not listed; these subjects are also mandatory for students. In the new system, students will take mathematics, English, physical education, and either 3 or 4 other subjects depending on duration (roughly 20 hours of duration, so either 3x7 or 4x5, or maybe 2x7 and 1x5, 3x5 and 1x7, or, in the worst case, 2x5 and 2x7). Physical education will always meet for 3 hours. The idea is that courses that have duration = 7 are more advanced and thus require more time, but no student is required to take any courses with duration = 7.

[ChicagoPianoTuner]

1) "so they should have 5 meetings in the same block and 2 meetings from another block (e.g. F1-F5 AND G1-G2)": do you mean D1-D5 and E3-E5?

That would be 5 meetings from the same block and 3 meetings from another block (E3, E4, E5). The meetings in another block don't have to be sequential (e.g. could be E2 and E4 or E1 and E5).

2) In FET-aat the user Jude G inputted students as subgroups, then he has groups and years. We have a more clear and bigger example, I wrote an email to Jude G asking him if I can send it to you or here. Let me know if I can email you. Also, I wrote him about this topic.

I have sent you data for one year of students. There would be 4 years total. Some courses would contain students from multiple years, some courses just contain students from one single year.

3) In FET-aat you schedule activities (students, no teachers) to teachers (FET days) and times (FET hours). In FET-aap you schedule activities (no students, no teachers) to teachers (FET days) and students (FET hours). I understood better your data using the two CSV files, but please allow me more time to think. Today I was busy releasing the new official version, but I hope I will have more time now.

I think FET-aat is more appropriate, but maybe you understand better than me.

4) How many total students do you have? How many teachers? How many subjects?

Roughly 60 students per year for 4 years, so 240. Number of subjects I'm not sure off the top of my head - maybe 50?

5) Is it possible a timetable with the first student's choices, or absolutely impossible and we need to allow sometimes the 5th choice instead of the 1st, 2nd, 3rd, or 4th?

Sometimes we need to allow a 5th choice, but we must 100% respect students' 1st and 2nd choice (so they may end up with choices 1, 2, 5 or 1, 2, 4 but never missing choice 1 or 2).

[ChicagoPianoTuner]

hmm... i still think that the dataset is impossible with only 35 hours.

have a look at student 1:
he has selected 4 times 5 hours = 20 hours
1 time 3 hours  (sports) = will occupy a part of a 5 times slot
2 times 7 hours; that mean
the 1st 7 hour course need a 5 hours slot and the Rest 2 hours might be placed in the 5th hour slot from sports (3 hours)
the 2nd 7 hour course need one full and a half 5 hours slot.
so he need even in best case 4+1+1+2=8 slots with 5 hours = 40 hours.

No, remember if activity tag = 5th choice, that's a backup ("revote"). So student 1 has 2x7 hours (choices 1 and 4), 3x5 hours (choices 2, 3, and MFL), and 1x3 hours (PE) for a total of 32 hours. The solution would look something like this:

Block A - Choice 1 (chemistry)
Block B - Choice 2 (biology)
Block C - Choice 3 (art & design)
Block D - Choice 4 (physics)
Block E - MFL
Block F - PE
Block G - empty

Then the remaining 2x2 hours (from duration 7 choices) would have to fit either both in block G or 1 in block F and 1 in block G.

[ChicagoPianoTuner]

Just because i am interested in: No maths at the school? So the other subjects must include needed math knowledge in their own hours?

Just to be specific, math would be a course as well, but the data I am using is from a previous year when all students must take math and English, and these choices reflect their requests for other subjects. This data comes from a system with more than 35 periods. In the new system, math would fall in students' choices 1-4.

[Liviu Lalescu]

1)

In the simplest possible case, a student ends up with a schedule that looks like this: A1-A5: History B1-B5: Spanish - Higher C1-C5: Geography D1-D5: no lessons E1-E2: physical education E3-E5: no lessons F1-F5: mathematics G1-G5: English. In that example, every course other than physical education meets 5 times. But you can imagine it gets more complicated if a student has a course that meets 7 times. Imagine in the example above Geography meets 7 times, so the extra 2 meetings can be anywhere in F1-F5, or they an be in E1-E2.

do you mean "D1-D5 AND E3-E5"? Because in F1-F5 is mathematics and in E1-E2 is physical education.

2) How many maximum teachers?

3)

and either 3 or 4 other subjects depending on duration

: but you said the students choose 6 out from 7 variants, without mathematics and English.

4) 240 maximum students is a very acceptable situation. Maximum 240*24 activities or we can use less if we say that duration 5 is for a single activity.

[ChicagoPianoTuner]

do you mean "D1-D5 AND E3-E5"? Because in F1-F5 is mathematics and in E1-E2 is physical education.

Yes, that's what I mean. Sorry.

2) How many maximum teachers?

50 I think.

but you said the students choose 6 out from 7 variants, without mathematics and English.

I think we are confused because of mathematics and English. They are treated no differently than any other subject. The data set I provided happens to not include any math or English because it is a leftover data set from another exercise. There are in total maybe 50 different courses available for choice. Some courses contain multiple instances (e.g. two different instances of physics) to accommodate students' needs. Sometimes the school has flexibility and can offer courses according to needs. Say one teacher can teach physics and chemistry. One year there may be 2 physics courses and 1 chemistry course, while the next year it is the other way around depending on requests. (I do not need FET to help with this part.) In other courses, it may be different. For example, the art teacher can teach exactly 2 art classes, so if more than 2x20 = 40 students want to take art, then some of them will have to choose something else (reserve choice/revote).

In truth things will be a little bit different - more than 240 students. Maybe I should tell the full truth: the situation I have described is for our senior school (high school). There is also the middle school which contains about 180 more students in 3 years. There are some cross-over teachers who teach in both schools. All that is necessary to make the two schools compatible is the ability to keep the cross-over teachers free during the same blocks, e.g. all cross-over teachers teach middle school classes in blocks B and C, so they are unavailable for high school during that time. Does that make sense?

[Liviu Lalescu]

50 teachers is very reasonable. I need to increase the FET days  per week (as in FET-aat). Also I hope FET will allow much more students than 240+180 with a reasonable time of solving the timetable.

I understand.

I think the best would be to generate the combined timetable data (middle + high-school) in a single file.

I am not sure of a way to allow choices for students. Maybe add all the 5 possible choices and create 40 FET hours (real-life time slots), and consider that the last 5 FET hours are invisible in the real timetable and preferred times 100% 1st and 2nd choices on FET hours 1..35, then 95% preferred choices 3rd and 4th choices on FET hours 1..35 (or something like this). (and the mandatory activities - preferred times only 1..35, 100%).

What do you think of this?

[ChicagoPianoTuner]

I think the best would be to generate the combined timetable data (middle + high-school) in a single file.

I can do that. We are trying to implement this new timetable 13 months from now so I have time to figure things out. Next week, I will compile a very realistic data set for all students in middle and high school.

I am not sure of a way to allow choices for students. Maybe add all the 5 possible choices and create 40 FET hours (real-life time slots), and consider that the last 5 FET hours are invisible in the real timetable and preferred times 100% 1st and 2nd choices on FET hours 1..35, then 95% preferred choices 3rd and 4th choices on FET hours 1..35 (or something like this). (and the mandatory activities - preferred times only 1..35, 100%).

What do you think of this?

What you describe is exactly how I solved the same problem using MAPR: set of activities has a set of preferred starting time, using activity tag as the criteria and then set the allowable periods. I first started with 1st choice = 100%, then 1st and 2nd = 100%, etc. Then finally 1st-3rd = 100% and 4th = 80%, 5th = 70% or something like that so FET does not treat 4th and 5th choices as equal.

There were two big problems with MAPR: first, there was no guess as to which activities should be scheduled first. Even if FET does not try to calculate the initial order, I would still request the ability to assign order of generation (as in the advanced option in standard FET).

The second problem is harder to explain. Assume students have 100% mandatory fulfillment for choices 1-3. Say FET places the activities by student, so student 1 has his activities placed first, then 2, etc. Maybe student 10 has to take 5th choice instead of 4th, but then when FET tries to schedule activities for student 50, now it is possible that student 10 can successfully take his preferred courses (e.g. 4th choice is now possible). FET has no way of knowing this since student 10's activities are successfully placed. The way I solved this problem is by going through the solved timetable again locking space/time for all choices 1-3 and allowing FET to try again choices 4-5 for best results, maybe changing the percentages for 4th/5th choice.

[Liviu Lalescu]

I can do that. We are trying to implement this new timetable 13 months from now so I have time to figure things out. Next week, I will compile a very realistic data set for all students in middle and high school.

OK, please consider that my analysis is not over. We might need to input in another way than you/we are thinking now.

What you describe is exactly how I solved the same problem using MAPR: set of activities has a set of preferred starting time, using activity tag as the criteria and then set the allowable periods. I first started with 1st choice = 100%, then 1st and 2nd = 100%, etc. Then finally 1st-3rd = 100% and 4th = 80%, 5th = 70% or something like that so FET does not treat 4th and 5th choices as equal.

Yes, I think I got this idea from you.

I think 1st-3rd 100%, 4th 99%, and 5th nothing.

There were two big problems with MAPR: first, there was no guess as to which activities should be scheduled first. Even if FET does not try to calculate the initial order, I would still request the ability to assign order of generation (as in the advanced option in standard FET).

I can customize in any way the initial order (like in students' order, subjects order, activity tags order, duration order, etc.). But I think there is no need.

The second problem is harder to explain. Assume students have 100% mandatory fulfillment for choices 1-3. Say FET places the activities by student, so student 1 has his activities placed first, then 2, etc. Maybe student 10 has to take 5th choice instead of 4th, but then when FET tries to schedule activities for student 50, now it is possible that student 10 can successfully take his preferred courses (e.g. 4th choice is now possible). FET has no way of knowing this since student 10's activities are successfully placed. The way I solved this problem is by going through the solved timetable again locking space/time for all choices 1-3 and allowing FET to try again choices 4-5 for best results, maybe changing the percentages for 4th/5th choice.

Yes, I know, this appears in FET official for preferred rooms <100% weight.

You can solve this by raising very much the weight for 4th, maybe to 99%.

[Volker Dirr]

I have similar problem with my rooms.
physics should be in a special room, but there is not enough space. so in worst case it can be also in chemistry room.

since my table it very difficult i only do:
physics 100% preferred both rooms.

At the end i have the same problem like you.

But i didn't check the timetable manually. I let fet do it like this:
load the dataset from the results folder.
unlock all rooms.
now add a physics room constraint with 99.99999% and let it run.
now it is nearly always in pyhsics room.

i think you should try the same trick.

[Liviu Lalescu]

Some more thoughts of this:

1) Maybe we should consider activities divided into 5 as duration 5, into 6(7) as duration 5+1(+1), and those into 3 as 1+1+1. Custom constraint same components without 5 should be on the same real-life block.

2) Number of FET hours per day: 35 (real-life) + 7 (invisible). Custom constraint component in one of those 7 invisible -> all of the container in those 7 invisible.

[ChicagoPianoTuner]

Some more thoughts of this:

1) Maybe we should consider activities divided into 5 as duration 5, into 6(7) as duration 5+1(+1), and those into 3 as 1+1+1. Custom constraint same components without 5 should be on the same real-life block.

2) Number of FET hours per day: 35 (real-life) + 7 (invisible). Custom constraint component in on of those 7 invisible -> all of the container in those 7 invisible.

Both of those suggestions make sense and would be helpful. You think 5+1+1 for duration 7 is better than just doing 5+2?

[Liviu Lalescu]

Both of those suggestions make sense and would be helpful. You think 5+1+1 for duration 7 is better than just doing 5+2?

I thought of this because by doing 5+2 we deny for instance (A1-A5 and C3,C5) for an activity with total duration 7. Are we losing feasible solutions? You know better than me. If there is a solution with (A1-A5 and C3,C5), is it very easy to swap and obtain (A1-A5 and C1-C2), considering also other activities?

I might sleep now.

[ChicagoPianoTuner]

Both of those suggestions make sense and would be helpful. You think 5+1+1 for duration 7 is better than just doing 5+2?

I thought of this because by doing 5+2 we deny for instance (A1-A5 and C3,C5) for an activity with total duration 7. Are we losing feasible solutions? You know better than me. If there is a solution with (A1-A5 and C3,C5), is it very easy to swap and obtain (A1-A5 and C1-C2), considering also other activities?

I might sleep now.

You are right - we might lose feasible solutions. Your way is better.

[ChicagoPianoTuner]

I have just thought about something that makes it easier to obtain a solution but harder to program. In the files I uploaded, look at the one with the school schedule that shows how A1, B1, etc. are distributed. I forgot that everything in the middle row (period 3) is actually TWICE AS MUCH TIME as the others. Now in the schedule it's a somewhat inconsistent grouping that has the extra time (C1, A2, F2, D3, B4, E4, G5), but I could just as easily make them A1, B1, etc. For now let's say that A1, B1, C1, ..., G1 are longer. Consider now there is an extra "hour" of real time in each block, even though there is not an extra period/lesson.

I am not yet certain of the effects of this on course length requirements. For example, I know that PE will still have duration = 3 hours (so either A1 and one of A2-A5 OR A2, A3, and A4), but I do not know if the PE teachers request specifically to have the long hour A1, or will request exactly the opposite, or one way for a certain year group and another for a different year group.

I know that courses that used to have duration = 5 will now be duration = 6 real hours, so they would still occupy one entire block A1-A5.

I know that courses that used to have duration = 7 will now have duration = 8 real hours. They can occupy all of one block (6 real hours) and either two short lessons from another block (B2 and B3) or one long lesson (B1). Perhaps different teachers would make different requests. Ideally FET could handle either request.

Is this possible? It doesn't sound incredibly difficult to me, but I can't quite see an easy trick.