Single-Day Schedule / US Scheduling

[wcmvusd]

Good morning,

I am looking at if I can use FET for scheduling of classes, but I'm not sure it is the right tool. We have 7 Periods that repeat daily, so this can be thought of as scheduling for a single day. I have Courses (Subjects), Teachers, and Students. There are 7 available Period slots per student, and each teacher may have up to 6 Periods (Sections) they teach. For each Course I can associate those Teachers who can teach it and maximum number of students per Period per Course. For each Student I can associate the Courses they should be enrolled in. What I need from FET is to place each student in a Period for each Course they should be taking and assign each Course Period a teacher. The goal is to maximize the number of Classes each student is successfully assigned to by minimizing conflicts with other Classes.

As an example, if I have 20 courses, 100 teachers, 1500 students and allow up to 20 students per period I can have up to 100 * 6 = 600 teacher periods (sections) able to accommodate up to 12,000 student period assignments per day. With 1500 students taking up to 7 classes per day I have up to 10,500 student periods to assign. Some courses may have all 1,500 students enrolled, others may have only 100. Some courses may only have 1 teacher, others may have several with the most populous courses needing up to 13 teachers to handle all the enrolled students. It is possible that more students may desire a course than slots are available, so if not all students can be slotted in to their desired courses that is okay.

Given these parameters, can FET assign a teacher to each Period Slot (section) and distribute students among all the available Period Slots for each Course (Number of Teachers who teach this Course * 6 Periods per day) in a way that maximizes how many students are enrolled in as many of their selected Courses as possible while minimizing how many students miss out on a course because it conflicts with another in the schedule?

Thank you for any assistance.

[Liviu Lalescu]

Good evening,

I have read and thought much about it, and I hope it can be done. This looks like the Block-Planning mode. The number of "hours per day" is 7 + a number of "overflow" hours which you will allow (maybe 1, maybe more, certainly <= 7). The number of "days per week" is the number of teachers.

Then, each activity will have a student, and schedule it to a FET hour (real-life hour or overflow means it will be skipped) and to a FET day (real-life teacher).

There are many constraints in this mode created just for your case (like max activities from a set in overflow, max activities from a set per real day, min/max activities from a set in a set of selected time slots, preferred times for activities - which enable which teacher can teach which subject, and so on).

I am very interested in your problem, since it seems a commonly case in the US. So please let me know.

But please forgive me if you will work on something and then we discover we need to change the data. It is a research problem.

You have some examples for the Block-planning mode in the FET examples.

[wcmvusd]

Thank you for your help, this is definitely in line with the kind of output I'm trying to generate.

I'm a bit stuck on the Overflow though. For testing I have 5 teachers (days) and 3 periods (hours) +1 overflow in the day and 15 students (activities). I created constraints for max total of 4 activities in each time slot, and then set each tag of activities (my subjects) to certain days (teachers). So each teacher can have at most 12 students. Two of my subjects have two teachers, but one only has one teacher so it must overflow. I'm not sure how to limit the overflow to just those students who couldn't be placed elsewhere though, the distribution of students among teacher periods is a bit uneven (ideally students would be distributed as evenly as possible over all possible/valid slots rather than minimizing the number of slots used) and the overflow period for each teacher may have students while the actual periods are not full.

edit: I think I made progress on the overflow? I set a soft constraint of preferred start time that's after the Overflow period, now it only has students if there are no other slots.

[Liviu Lalescu]

I am reading your post and might answer again later. But:

1) Students are students, and each student has more activities for him (because you wrote 15 students (activities)). How many students and how many activities do you have?

2) Could you show me your file? If it is private, by email.

3) To control the amount of activities in overflow, I think it is not good from the efficiency point of view the preferred times, but you need to use an increasing approach with the constraint max total activities from set in selected time slots, add all the activities, select all overflows - see the block planning example in the FET-6-block-planning example - and keep decreasing the max total activities in the overflow while you find new timetables. This was Darren's approach in that example.

EDIT: 4) I think each FET day should have the number of hours of the students (= the number of hours of the teachers + 1) and some overflows to help you. So you might want to make 5 FET hours per day, in which one is an overflow? I am not sure. Then limit the number of hours per day for each teacher with the constraint activities occupy max time slots from selection. This is different from Darren's example?

[wcmvusd]

Here is my test file:

https://file.io/RzvNFcc5FgI0

I have 15 students, each is in 1 activity.


For the max total activities, the limits are known in advance, eg English I may have 30 students, Calculus may only have 20, etc. Going over these limits would need to be done manually after the base timetable is generated.

If there were some number of unplaceable students due to capacity limits that is fine, I only need to know who they are so that I can update my database with that information. We usually have Alternate courses that students may take, especially for electives, if their first choice is not available. My thinking is to tackle the schedule in multiple passes, locking in the students after each pass then attempting to assign students their alternates in successive passes until the alternates are exhausted. After that I would have some small number of students with gaps in their schedules that can be dealt with manually.

[wcmvusd]

Here's what I mean with the overflow, I allowed teacher 4 to teach both science and English while teacher 5 only teaches English, yet one student was placed in the overflow even though there was space for them elsewhere in the schedule.

[Liviu Lalescu]

It would be best to use the forum attachments type. I attach here my file.

1) Overflow - it might be best if you began with allowed hours, then put the overflow last (just change the order of the FET hours).

2) I simplified and improved your file. Please see the all time constraints list in my attached file. Check my comments. I don't understand, because it solves even with 0 overflow activities allowed (but I left it with 1 overflow activity allowed).

3) There are 14 students and 30 activities.

[wcmvusd]

That was a big help, I've made some changes and added more students to make it more realistic. I've also given the students gender so that I can balance classes along gender lines to prevent any one class from having all boys or all girls. I'm attaching my latest iteration below, it seems to be generating exactly the kind of output I need.

One thing I found is it would be great if there was an 'A Set of Activities has minimum simultaneous in selected time slots' constraint so that I could group all students into gender groups and set each gender group to have a minimum per period instead of assigning each activity to the constraint individually. Something like the 'A Set of Activities has a Set of Preferred Time Slots' constraint, but for Min/Max?

You cannot view this attachment.

[Liviu Lalescu]

I saw your file. It seems that the minimum number of activities in the overflow is 24. There is a better constraint for this, see my attached file with the comment. You might work with preferred times, then switch to max activities in selected slots. But remember that preferred times might not yield the best result and might take more time (breaking a constraint takes time).

I will add your suggestion in the TODO. But I hope you can work with the current constraints. Because I prefer to keep the number of types of constraints to a minimum, and also your suggestion leads to dynamically changing activities, which might be tricky for a user to manage.

[wcmvusd]

Okay, I see what you mean with the preferred time vs putting a maximum in the overflow slot now, that makes sense. In my source system I would know the maximum students for each teacher & period slot (my sections) and the total students I need to assign to each subject. It is easy math then to figure out exactly how many students will have to overflow if there are more students who want say Art than there are Art teachers available to support them. Is there any way to allow activities to overlap only in a specific period? It would be fine if in the Overflow period math and English students were co-mingled under one teacher for example. I think I may need to add extra overflow periods otherwise with a more complex set of subjects.

Thank you very much for your help with tuning my file. The next challenge, which I think I've handled, is teachers with multiple subjects. I've a removed the dedicated English teacher (Teacher 5) and given their students to Teachers 1 and 2. I set constraints that require each of those teachers to have 1 period of English and 2 periods of Math, using the A Set of Activities Occupies Min Time Slots from Selection and A Set of Activities Occupies Max Time Slots from Selection constraints for each group of students by subject and teacher. It seems to work exactly as expected which is great. In this case a constraint of 'A set of activities occupies X time slots from selection' would be great, as generally we will know for example that Teacher A has 3 English I classes, 2 English II classes, and 1 AP English class, while Teacher B has 4 English II classes and 2 AP English classes, and so on. The end result being the rules allow a class to be placed anywhere among all the teachers who teach that subject but no teacher has more or fewer classes of any one subject than they should.

I also added an upper bound on how many students of each gender may be in one class for each subject as I was still getting one class all girls. I can probably play with that ratio a bit such such as making Min = Floor(Stus/Sections) - 2 and Max = Ceiling(Stus/Sections) + 2 to give a spread of 4, so that each class isn't forced to be an exactly perfect split. That's just fiddling with a parameter on my end at this point.

Is there any way to have the command-line tool only output the timetable.csv file (and set a specific name for the csv file)? My end goal is to generate a valid FET file by php script, execute fet-cl.exe on it, and ingest the resulting timetable to fill a couple of SQL database tables. Even better if I can feed in the contents of the fet file as a parameter and get the csv formatted timetable back as output directly to the terminal so I can pipe it into my script, but I don't see anything like that in the program's /? info.

[Liviu Lalescu]

Okay, I see what you mean with the preferred time vs putting a maximum in the overflow slot now, that makes sense. In my source system I would know the maximum students for each teacher & period slot (my sections) and the total students I need to assign to each subject. It is easy math then to figure out exactly how many students will have to overflow if there are more students who want say Art than there are Art teachers available to support them. Is there any way to allow activities to overlap only in a specific period? It would be fine if in the Overflow period math and English students were co-mingled under one teacher for example. I think I may need to add extra overflow periods otherwise with a more complex set of subjects.

As I remember, cannot allow to overlap in specific slots. I think you need to add more overflows. That is why I recommended to keep the overflows as the last slots. And it looks also nicer.

Thank you very much for your help with tuning my file. The next challenge, which I think I've handled, is teachers with multiple subjects. I've a removed the dedicated English teacher (Teacher 5) and given their students to Teachers 1 and 2. I set constraints that require each of those teachers to have 1 period of English and 2 periods of Math, using the A Set of Activities Occupies Min Time Slots from Selection and A Set of Activities Occupies Max Time Slots from Selection constraints for each group of students by subject and teacher. It seems to work exactly as expected which is great. In this case a constraint of 'A set of activities occupies X time slots from selection' would be great, as generally we will know for example that Teacher A has 3 English I classes, 2 English II classes, and 1 AP English class, while Teacher B has 4 English II classes and 2 AP English classes, and so on. The end result being the rules allow a class to be placed anywhere among all the teachers who teach that subject but no teacher has more or fewer classes of any one subject than they should.

I added also this in the TODO, but there are reasons why I am reluctant to make it. I hope the input procedure is not too difficult for you.

I also added an upper bound on how many students of each gender may be in one class for each subject as I was still getting one class all girls. I can probably play with that ratio a bit such such as making Min = Floor(Stus/Sections) - 2 and Max = Ceiling(Stus/Sections) + 2 to give a spread of 4, so that each class isn't forced to be an exactly perfect split. That's just fiddling with a parameter on my end at this point.

I am not sure I understand how you got a class all girls, if you made min boys = 1. But you might know better here.

Is there any way to have the command-line tool only output the timetable.csv file (and set a specific name for the csv file)? My end goal is to generate a valid FET file by php script, execute fet-cl.exe on it, and ingest the resulting timetable to fill a couple of SQL database tables. Even better if I can feed in the contents of the fet file as a parameter and get the csv formatted timetable back as output directly to the terminal so I can pipe it into my script, but I don't see anything like that in the program's /? info.

It can be customized, but best is to use the official FET, to have always access to the latest version.

Unfortunately, the only possible thing is to output as CSV with a predefined name (you can change the output directory though with --outputdir=DIR). To output CSV: --exportcsv=ECSV. To suppress other timetables: --writetimetablesdayshorizontal=WT4 and the likes. Please run fet-cl from the command-line prompt to see the options (or read the README file near the end).