Real life scheduling is far more complicated than people think. Even those people writing about it on Wikipedia.
Those naive mathematical concepts described there are just too narrow.
In reality it’s much harder and much more complex. I’m not saying that it isn’t translatable into those models, but that translation would be a big problem on its own. Probably an even bigger problem than the scheduling itself.
So, how complicated does it actually get?
Look at a single teacher first – her/his requests. Start with the hours at which he is available to teach. Everybody is aware of this one.
But then it’s possible to determine how many waiting hours per week one would like to have. Let’s take 3 to 5 as an example. We can then say whether it’s better that the number is closer to the lower or upper bound (3 or 5). We can also skip that step and say that it doesn’t matter. Additionally we might also want to specify the maximum number of idle hours in a day.
Another possible specification is the maximum and minimum number of hours a specific teacher should teach per day, and after how many teaching hours a break is necessary for this or that particular teacher.
Given that there isn’t an unlimited supply of classrooms, and that all classrooms are not suitably equipped for all subject, we must also describe the hierarchy of location each teacher is able to use during each of his classes. It may also happen that multiple classrooms are required for a class. Any three classrooms in the first floor, for example.
Traveling from one place to another, one teacher might need one hour, while another, by bicycle or car, is able to make it during a short break, and a third one requires a long 20 minutes break on all days except Monday when he needs a whole hour.
Then, some will not teach two constitutive hours of biology if the lunch break falls between, because the children who would have been dissecting frogs just before eating might vomit, or at least lose concentration. So no block biology between the fourth and fifth hour; same goes for chemistry. A different teacher might be fine with his pupils eating at a desk occupied by a frog carcass, so his biology class doesn’t have the same restriction.
I don’t know, however, if they actually still dissect frogs or not.
Another teacher is very diligent and teaches even after class, if anyone is willing to listen. Therefore it’s important that nothing else be scheduled after certain hours – either for him or his students.
Of course, none of the above requirements can contradict if a schedule is to be possible.
But there is more. Perhaps a free day is scheduled for a certain teacher, but it is not determined which one. The algorithm should find the day which is most compatible with the rest of the schedule, but may not select Tuesday.
It would be very nice then, if a certain teacher uses whichever room allows him to stay as stationary as possible.
Then, some sequences or sets (where the order doesn’t matter) of classes are mandatory – some subject must follow another or some subjects must be clustered together in any order. Some associations between teachers in the same class, in the same group of students from various classes – or between the teachers from different classes. To be able to take over the teaching of both groups when one of them is ill or otherwise absent, and to have the class on the same hour for reasons of coordination of the teaching of math between those similar or not so similar groups. I’ve forgotten the reason why this last thing is beneficial.
As for the gym classes, doors should be opened once for entering and closed once for exiting the gym complex. The same applies for some labs. It’s forbidden for one group of students to attend for 2 hours in a row, while another group of students needs 3 hours in a row in a neighboring room, but not with another teacher who is less sensitive to distractions.
Of course there are more options just for teachers, but there are also options for classes, for groups of students from different classes, for groups of students from different years even, for individual students, for teacher groups with no students doing meta-teaching, for groups of teachers with groups of students, for room priorities, for availability of rooms, for subjects, for special events…
All of those are about as complex as teacher options.
Then there are also specifications regarding meals and transportation of students who eat at school and for those who need to be brought by buses. The cafeteria and the buses have their own capacities. The scheduling task should optimize them simultaneously with the rest school schedule, reducing the number of buses if possible.
In addition to all of this some other workers are also involved, and must be scheduled with the school process.
Quite a ridiculous amount of requirements!
I wanted to give you an impression of the complexity of the school scheduling problem where even solving the toy model is NP hard.
Curiously, our algorithm is strong enough to tackle it automatically, and there is no real competition yet.
protokol2020 