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

[ChicagoPianoTuner]

I've used the standard FET program for several years, and I've used MAPR for two years to solve other little problems. Now I need help figuring out what version to use to help build a new type of timetable for my school. I'm thinking MAPR, but I don't know if there are other versions that are better, or if I am requesting a custom version. This is more for course planning than for actual timetabling.

The timetable has 7 blocks (A-G). Each block meets 5 times per cycle. So, in one cycle, there is A1, A2, ..., A5, B1, ..., B5, ... ,G1, ..., G5, not in that order. Most courses will meet during exactly one block (will occupy B1-B5 for example). A small number of courses meet for a fraction of one block (D1, D2, and D4, but not D3 or D5, for example). A small number of courses meet for one entire block and a fraction of another block (A1-A5 AND E3 and E4).

I need to place teachers and students in courses and place those courses in blocks. Here is my current plan for how to do it in MAPR:

FET hours are blocks (A-G)
FET days are the 5 meetings (1-5) forming a grid of A1 - G5
FET teachers are teachers
FET students are students, probably as subgroups, building groups in Excel and then importing them into FET
FET subjects are real subjects (e.g. physics)
FET rooms are sections of courses (physics_section_1, physics_section_2, etc.)
FET activities are students' choices and teachers choices. Each activity has a subject, and each subject is constrained to occur in a set of FET rooms (sections of courses above)
To teachers' choices I might include the constraint activities have the same starting time to make sure that each section occurs in the same block.
I will have to think about how to include the extra pieces for the courses that meet for more than one duration. I can think of a few ideas, but I don't know what's best.

Can anyone advise on which custom version would be best suited? Just MAPR?

For what it's worth, this model of scheduling is incredibly common in US schools. Developing a custom version that can fit this sort of schedule could have wide applications.

[Liviu Lalescu]

I must admit I did not read very thoroughly your email, I am a bit busy implementing and checking a new FET-official constraint. But I hope I got the idea.

FET-mapr: I hate it, and I don't want to use it. It usually does not generate results, it does not converge. It is difficult to use.

I think we could try with modifying FET-aat, or designing it from the beginning for you, starting from the future FET-official 5.39.0, which is newer and better.

Jude G, who proposed it, used it successfully, as far as I know. I think his problem is similar to yours.

The FET days will be real teachers, and FET hours will be the 35 = 7 x 5 blocks x cycles. Allocate activities (subject, activity tags, students) to time slots.

You have constraints activities same starting time and more.

Please let me know what you think. You might want to play a bit with the current FET-aat with the provided example (I hope it has).

[ChicagoPianoTuner]

OK, so here's my understanding:

Teachers are days, hours are 7x5 = 35 periods.
Students are students.
Set activities to duration = 5 if they occupy one full block.
If activities occupy less than one block, set duration = 3 or whatever.
If an activity occupies more than one block, I need two activities, one with duration = 5, and another with duration = 3 or whatever.
Constrain subjects to occur on specific days so if Mr. X and Mrs. Y teach physics then physics classes can only occur on their days.
Set activities preferred starting times to begin A1, B1, ... G1 for activities with duration = 5 so they only exist in one block. For shorter duration courses, they have no preferred starting time.
I need another activity with no students to represent a course. If there is only one section of that course, e.g. only one biology class for the entire school, then I can make sure the activities for students taking biology have the same starting time as the one above.
If there are two sections of a course, like physics above, I need to use one with Mr. X and one with Mrs. Y, and then use activities occupy max time slots from selection = 10 for Mr. X's course, Mrs. Y's, course, and all student activities for that course.

My question: how do I ensure that, if 35 students want to take physics, it doesn't end up with 30 in Mr. X's course and 5 in Mrs. Y's course?

[Liviu Lalescu]

OK, so here's my understanding:

Teachers are days, hours are 7x5 = 35 periods.
Students are students.
Set activities to duration = 5 if they occupy one full block.
If activities occupy less than one block, set duration = 3 or whatever.
If an activity occupies more than one block, I need two activities, one with duration = 5, and another with duration = 3 or whatever.
Constrain subjects to occur on specific days so if Mr. X and Mrs. Y teach physics then physics classes can only occur on their days.
Set activities preferred starting times to begin A1, B1, ... G1 for activities with duration = 5 so they only exist in one block. For shorter duration courses, they have no preferred starting time.
I need another activity with no students to represent a course. If there is only one section of that course, e.g. only one biology class for the entire school, then I can make sure the activities for students taking biology have the same starting time as the one above.
If there are two sections of a course, like physics above, I need to use one with Mr. X and one with Mrs. Y, and then use activities occupy max time slots from selection = 10 for Mr. X's course, Mrs. Y's, course, and all student activities for that course.

My question: how do I ensure that, if 35 students want to take physics, it doesn't end up with 30 in Mr. X's course and 5 in Mrs. Y's course?

I am not sure I understood all the problems in your data.

Yes, teachers are days, 35 hours per FET day. Then students, subjects, activity tags are for real. Students subgroups = real-life students.

Maybe I do not understand correctly the significance of blocks.

Yes, preferred time slots for Physics.

A very important question about something I do not understand: Do you need to have also the real-life times for the activities, or only the matrix teachers x 35 FET hours = organization into blocks?

Could you please download and use FET-aat, generate once for the provided example (see the examples directory)? And tell me the differences to your data?

Activities will have a subject and activity tags, and the involved students sets.

I think the duration of whole block activities will be 1+1+1+1+1, for duration 3: 1+1+1, then a possibly new constraint so that activities in a block will be on the same FET day = real teacher, and same block. Or two constraints: same starting day and a new constraint, same block.

I don't understand why activities without students.

I think you need this like FET-aat: - First customization: activities with common students cannot intersect in the real-life slots, so that
they cannot have overlapping FET hours.

One Biology activity for the entire school: add all the students in an activity.

I am not sure about your proposed occupy max 10 time slots. I need clarifications.

Your question: maybe two constraints activities occupy max time slots from selection, select a day of X (or Y), activities = all Physics of these 35 students, max occupied = 20 each.

I need some practical example, easy to understand. Maybe some very simple timetables. Or you could input some data and generate and tell me the problems which arise.

[Volker Dirr]

Do you have a sample data set already. Maybe in the fet-MAPR csv file format? If yes: Please sent me the dataset if you can. (i am only talking about the "activities" that you need to enter in FET: so subject votes of students and maybe also teachers activity planning)

[ChicagoPianoTuner]

Thanks for your reply. I will try to explain more clearly.

None of the timetable help needs to be related to real time. Only course planning.

One of the attached files shows the school's schedule. It is very simple. All that is left is to assign students' courses to blocks.

Students get a list of which blocks their courses fall into on the first day of school. Most courses occupy exactly one full block, meaning they meet 5 times in the school's seven-day cycle. All five meetings should occur in the same block (A1-A5, or B1-B5, etc.). Some courses occupy LESS than one full block of time, meaning they meet three times in the seven day cycle, but all three of those meetings should also be in the same block (C3-C5, for example). Some courses occupy MORE than one full block of time, so they should have 5 meetings in the same block and 2 meetings from another block (e.g. F1-F5 AND G1-G2). Please let me know if I can explain this more.

Look at the other file showing student choices. Students request certain courses (e.g. student 1 requests chemistry, biology, art & design, physics, economics, and Spanish - higher). In the activity tags column, you see the student has ranked his choices in the order I listed. Some activities are mandatory, for example every student must choose a foreign language and physical education. But for the other 5 requests, each student will only be assigned 4 courses. In the past, when I have used MAPR to solve similar problems, I create 5 extra meeting times and allow "extra" courses to be placed in there (maybe the student's reserve choice if he gets everything he wants, but sometimes his 4th choice if he can't be fully satisfied). Let me know if I can explain more.

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.

Once you start considering the courses that meet for duration 3 or 7, you can imagine there are many different scenarios - if there are 35 total meeting times, one student might meet 33 of those times, another student 28, another 35, etc.

Some courses, e.g. biology, are requested by many students (I think 44 in the data). Each biology class can only have max 20 students, so I need 3 different classes of biology. I need to make sure there are no more than 20 students in each section. If possible, I want to split the sections close to evenly (e.g. not 20-20-4).

Liviu, the answer to your question "why activities with no students?" Maybe you don't need it. I will think more.

In the FET-aat timetable, it appears each teacher is only working with one student at a time. I need multiple students assigned to a teacher simultaneously (creating a class).

Please let me know what other information I can provide.

[Volker Dirr]

hmm... the datafile looks impossible, because for example student "1" selected 7 subjects, but 2 of them have got 7 hours. So 2 of them need 2 lines. So you need in total at least 7+2= 9 lines (so from A to I, but you have only from A to G).

[Volker Dirr]

ahh... i guess you want to place the 7 hours exactly where you placed the 3 hours so fill it up to 5.  ok.. now i understand. hmmm... a very special situation.

[Volker Dirr]

hmm... but that also doesn't work, since student 1 have got only one activity with 3 hours, so you can save max 1 line. So you need at least from A to H. So that datafile should be impossible, isn't it?

[Liviu Lalescu]

Volker: The students are only choosing only 4 out of 5 courses, + 2 mandatory.

CPT: (sorry if these initials are not nice, please let me know)

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?

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.

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.

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

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?

[Volker Dirr]

it looks like they must choose sports.

the stupid stuff is that some students have chosen only courses with 5 hours, while other have chosen up to 2 courses with 7 hours. that is complicating stuff very much. it is easier at German schools, since all must choose 2 courses with 5 hours and 8-10 courses with 3 hours.

[Liviu Lalescu]

CPT: I hope it can be solved with an approach similar to FET-aat and some custom implemented constraints. FET days are real teachers, FET hours are the 35 time slots of the week. Each activity has a single students set (or more if you decide exactly the students in a set).

I am not sure if activities should be divided into components with duration 1 (so, 5 or 7 subactivities) or should have duration 5 (or 5+2). They can be forced to start at certain times, as you said.

So that a real teacher has maximum activities per real slot: all activities occupy max time slots from selection, select the whole FET day. It is possible to implement also minimum for this, as I did in FET-aap (not FET-aat).

Maximum 20 Biology activities per slot: activities max simultaneous in selected time slots. All Biology activities.

Minimum say 12 Biology activities per slot: might be possible with a custom constraint, derived from the above one.

What a teacher can teach: activities preferred time slots, for the subject.

A teacher is not teaching two or more activities at the same time: maybe the new constraint activity tags not overlapping or a custom constraint.

[Volker Dirr]

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

[Volker Dirr]

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.

[Liviu Lalescu]

CPT: Jude G gave me permission to attach a more elaborate version of a FET-aat input file. See the attached file.

Unfortunately, he needs to allocate the students to groups by hand. He might still have the same problem as you. I'll invite him to join this discussion, we might obtain better results together.