Automatic Activity Planning?

[Christoph Voelker]

Hello there,

first of all: Thank you very much for your good work!

I have a little suggestion - or maybe rather a "wish":

I am a teacher at a vocational school (Berufsschule). Here, every four weeks a new "activity planning" and then a new timetable is needed.

I know the "activity planning" (appointing teachers to classes/courses mainly depending on their hour contracts) is a responsible job, which maybe should not be done automatically by a computer but with a lot of wisdom.

But as it is needed every four weeks at our school, I wondered if it is possible to automatically generate some suggestions for this "activity planning". Of course there would have been some constraints, that need to be defined, like:

- individual contracts for each teacher regarding hours/week (workload)
- general approach, that the teachers stay "in their classes"
- every teacher with only one subject in the same class
- some teachers may only be appointed to "lower" courses
- some teachers may not be appointed to class XYZ
etc.


What do you think? Is that somehow possible?

Many greetings from northern Germany,
Christoph

[Liviu Lalescu]

Hello, Christoph, and welcome to the forum!

So, apart from the tedious handmade activity planning, did you use FET with success in your institution?

I think that if you have decided on a definitive activity planning, FET will find a better optimized timetable (such as lower gaps number) than if you would create an automatic activity planning and scheduler. But I might be wrong.

There is FET mapr, where a real teacher = a FET room. I hate it, really. Because in some cases it did not produce useful results. Because it is difficult to work with. Because it is old. Because each time I use it I need to read again its documentation, as it is difficult and I forget how to use it.

With FET mapr your 5 requests might be manageable. For the first one, a FET room = a real teacher has a constraint of maximum load per week. It might be sufficient (without the minimum load per week)? For the second approach, I am not sure I understand correctly, but it might be possible. The third - might be possible with a new constraint or as it is now. The 4th and 5th, I think it is possible with preferred FET rooms = real teachers constraints.

It might be possible with other tricks. Recently, I worked with Peter B from the forum, with success. Please see https://lalescu.ro/liviu/fet/forum/index.php?topic=3961.0 (only the beginning is in German). Unfortunately, I cannot show you his file, it is private. I devised these tricks: FET hours = real teachers, FET days = real hours (he has a timetable for only a day, but it might be possible to extend for 5 or more days). Then allocate activities with students to these time slots, and having time preferences.

Or maybe other tricks. You might also have some ideas.

I am willing to continue this discussion and try to help, as possible. I am also willing to make some customizations, as possible. But I do not promise anything (in both).

You might want to share your data or model of timetable with us. If it is private, you can send it by email.

[Christoph Voelker]

Hello Liviu,

thank you very much for your answer.

Apart from playing around - I didn't use FET for serious timetabling in our institution yet. We actually use "Untis" for this purpose - and a big Excel sheet for the "activity planning".

You asked about my second request for the wanted "automatic activity planning" (the general approach, that the teachers stay "in their classes") - so I will write a little about our institution:

The students make a "dual education". They normally work at their business, but within 3 years, the students will have to visit our school for altogether 8 times - always for 4 weeks. That means, every 4 weeks we need a new activity planning and a new timetable.

On average we have 30 classes simultaneously at school. They are all different regarding their progress ( course 1 to course 8 ). I guess this would be "years" in FET.

For example, let's say we have 5 classes there for the first time (course 1), none for the second course, ...

5 classes in course 1
0 classes in course 2
5 classes in course 3
10 classes in course 4
8 classes in course 5
2 classes in course 6
0 classes in course 7
0 classes in course 8

4 weeks later it will look very differently. And another 4 weeks later, a class will maybe return, but is now in the next course.

Now let's talk about the subjects. They depend on the course number. For example, in course 1 you have "audiology" with 4 hours, and "psychology" with 2 hours. In course 2, you maybe have "audiology" with 6 hours and no "psychology" at all, but another subject.

And now concerning the teachers: It is desired, that the same teacher teaches the same class in the same subject for all the 8 courses. This is sometimes not possible, because of the teachers "target hours". And also because of the teacher's qualified subjects. For example, a teacher can teach "audiology" in course 1-4, but not from course 5 upwards.

So maybe it would be helpful to define the subjects together with the course number? For example "audiology1", "audiology2" etc.?



So, I just wanted to add these information to make the wish maybe a bit more handy.


So - what could we check out first? FET mapr, that you hate?

Or maybe the FET Peter B. version?


Many greetings and thanks,
Christoph

[Liviu Lalescu]

I will now read more thoroughly, but it is difficult, since I was never involved in real-life timetabling.

Please tell me what is a class. A student, a set of students? Let's try to use FET notation, as students set, room, teacher, subject, activity and activity tag. The students in FET are organized in years, groups and subgroups. Does not matter too much, you can think of a tree. You can even input only years, but adding years like V, VI, VII, and VIII containing groups is easier.

Are students' gaps or teachers' gaps constraints necessary?

I would find very useful some pages of your final timetable, and maybe the list of activities, to be attributed to teachers.

It is best if we consider the smallest students set (maybe FET group, and not use FET subgroups) as all the students having the same activities (I don't understand exactly what is a block, I will read more carefully).

I don't know yet if we could try Peter B method, mapr or another new method with tricks. Let me read/think some more and maybe you can send me some pictures, tables, and schemas.

[Christoph Voelker]

Hello,

I will attach a screenshot of an old "activity planning". These plans build always the base for our time table.

You will see the data for 12 classes (18.Q-B7 to 19.E-B5). The list in real is longer, it contains 32 classes.

A class like "18.Q-B7" is a "set of students", about 30 real young wonderful persons consisting of flesh and blood

The "18" means that they will make their exam in 2018.
As we have many, many classes, that will make their exam in 2018, we have 18.A to Z and also 1-9.
The "B7" means that they are in the 7th course. As I wrote earlier, each class has to come to school eight times for eight courses, B1 to B8.

Back to the attached graphic:

Each class has a class teacher, e.g. the 18.Q-B7 has teacher "CocU".
Sometimes this changes: The 18.O-B6 now has MueD, but in the course 5 (B5), it was SchC. That is what # before a name means.

Now to the subjects:

You see 6 subjects: a) PO/WiPO, b) BW/GA - in the table columns.

And you see the teachers, that teach these subjects with how many hours in the table cells.

For example, teacher Fues teaches AK/SI in 18.Q-B7 with 8 hours.

You can also see, that in course 5 (classes with *-B5), the subject AK/SI is not needed, because the cell is empty.

To make it more complicated, for many subjects, we have "theory lessons" and "practical lessons", which sometimes the same teacher does (which is wanted). Sometimes this is not possible because of teachers target hours, then another teacher does the practise lessons.

For example: KolA teaches AL theorie in 19.B-B5 (8 hours) and KolA also teaches AL practise in 19.B-B5 (4 hours).

So, I guess I will need a program to fill the table cells with teacher names. Generally trying to keep the teachers in the class and respecting the other constraints that I wrote in my first post.


Thanks a lot for the offer to think this through.


Many greetings

[Liviu Lalescu]

Thank you for the clarifications! Very on-target ones, and clear.

One question: you said there were 32 rows (real classes = FET students sets). But A..Z and 1..9 is 26+9=35 > 32?

I will try. Maybe we'll obtain something. Maybe like Peter B's used tricks. I also thought of another FET custom version with tricks which was very successful: https://lalescu.ro/liviu/fet/forum/index.php?topic=1782.0 and which resembles your data. In fact for dolphins I used FET official, only customized the output HTML files.

I will be back tomorrow. Now it is late in Romania

PS: Of course I need to re-read your post. I think I will print the picture and your post.

[Christoph Voelker]

Hello,

regarding your question:

The activity plan with xxx rows changes every 4 weeks. The xxx (e.g., 32) stands for the classes, that are actually physically present in the actual 4 week-slot. This number xxx changes every 4 weeks. For example in May, we might have 32 classes present, in June maybe 34 or 31.

The other thing (A-Z, 0-9) was regarding the *notation* of the classes. We have 18.A to 18.Z and numbers and even some special characters. This only means, that we have many many classes, that will make their exam in 2018.

So, two different things: a) amount of actual classes present for 4 weeks and b) total amount of classes in one exam year.


Thanks and good night for now

[Liviu Lalescu]

Please tell me:

1) The thing with # in your previous post, it is for 18.O-B6, and you say course 5 (B5). I do not understand. I thought this class (=FET students set) has course 6.

2) Maybe you could post the picture in a better format, so I can see the print better (this point is not critical).

3) Please tell me the maximum number of students sets and teachers you can have in the table. There are always n_students_sets rows and 6 (n_subjects) columns?

4) For instance in 18.Q-B7 and AL. There are 3 rows in that cell. Can we consider only 2 rows (KauM with 8 and BabA with 4)?

5) I don't understand the role of column KLehr.

6) Very important: teachers have a _maximum_ limit on the number of hours they teach per week. I think I cannot devise a constraint for the _minimum_ number of hours they teach per week. Is that OK?

I am thinking now of two possible approaches.

a) One follows the idea of FET-mapr but is simpler: allocate n_students_sets*6 activities which are fixed in time to n_teachers rooms, permitting maximum 2 activities in a room at the same time. An activity will have the number of students equal to the duration in hours and the FET rooms = real teachers will have a capacity in number of students.

b) The other one follows the idea of Peter B and dolphins custom versions, but is a bit more complicated because of the fact that cell activities have a duration. Consider FET number of hours = n_students_sets, and FET number of days = 2*6*n_teachers (2 times because of practical and theoretical). Put the n_students_sets*6 activities to these slots, careful not to overwhelm teachers.

[Christoph Voelker]

Hello,

5) every class (=every group) has a "KLehr" , the "class teacher". the class teacher has some extra tasks/duties with his/her class. Maybe it can be defined as a subject, but with 0 hours, I don't know. The class teacher also has to teach the group in one (real) subject.

1) True, 18.O-B6 means, that this group is actually in course 6. But before that, this group was in course 5. And when they were in group 5, they had SchC as class teacher. The # always means that there is some kind of change with respect to the previous course. Because the class teacher (and all other teachers) are supposed to stay the same for each group over the 8 courses, but this is sometimes not possible. This means that somehow FET must know about the past when making an automatic activity planning(?).

2) I will send you an actual activity planning as a pdf privately.

3) The max number of groups is actually 33. sometimes we only have 32. that depends on another planning regarding the whole school year.

The n_subjects should maybe be 7*2+1 = 15. This should lead to the following, that we will only have one teacher per cell.

4) Let's try to increase n_subjects, so we will have only one teacher per cell (see point 3).

6) I think this minimum_ number is not a problem for now.


I hope this cleared some stuff. Wow, but while I wrote these lines, I realized, that this whole task might be quite complicated


Many greetings!

[Liviu Lalescu]

Hello,

Please tell me the maximum number of total teachers (who can appear in the timetable). It was a question in my previous post in (3), but you might not have seen it.

[Christoph Voelker]

Ah, sorry, you mean the total amount of actual teachers at our school? I guess, we have something like 90 or so. Maybe you should set the maximum to 100 

[Liviu Lalescu]

It might be possible, but we need to work a bit on this.

I think maybe in a manner similar to Peter B's and dolphins' tricks.

We need 33 FET hours = real students sets. But the number of FET days will be very large. n_subjects * n_teachers. So 1500. But don't be scared too much. This might be done automatically. I need maybe to add one or a few new simple time constraints. And increase the maximum number of FET days per "week" to 1500.

The output will be made smaller, you won't see 1500 columns, but 15, like I did for dolphins. Or directly output to a .fet XML file to be opened by the official FET and solved (I did not think of this, yet, it might be more complicated).

Each activity will have a number, which represents the real duration (4, 8, 2, or 6, or ...). I think we could use the FET's activity number of students, so that I don't need to implement a new variable. And a teacher will have the target number of hours, and implement a constraint so that the sum of the table 33 rows x 15 columns for this teacher will be maximum this teacher target number of hours.

You can add preferred time constraints from previous years. You can use the constraint activities preferred time slots with weight under 100%. So that FET will try to keep previous course teachers for the students sets.

I think the class teacher can simply be ignored, since you can have duplicates like for students sets 20.7-B5 and 20.A-B3 in your private file? (I did not write here the name of the teacher on purpose).

It is a very large matrix, 33x1500. Say activity A (students set 19.1-B8, subjet WiPo, no FET teacher) will have real duration 4 and can be scheduled only on the columns with heading WiPo for all teachers. So 100 columns will be allowed in the preferred times constraint for this activity and 1400 columns will be forbidden. And the sum of the real durations of activities in the 15 columns of each teacher must be at most the number of total working hours per week for this teacher (I think I need to add a new constraint for this, might not be that difficult). And on each row (students set), a teacher must teach a single subject (so can occupy only one or two columns - these two columns for theory and practice).

These tasks might (in fact should, we can't really think of clicking the mouse inside a matrix with 1500 columns!) be automated, from another program outputting the .fet XML file for this custom FET.

It is a large matrix, but mainly empty. So the solving time might be acceptable. I cannot know for sure.

Please tell me what you think.

[Christoph Voelker]

Hello there,

first of all, it sounds good what you write. And I even might begin to understand what's going on But my head is buzzing ...

This time we don't want to have a 3-dimensional time table (FET days x times/periods (FET hours) x group) with teachers in each cell.

This time we need another (2-dimensional?) table: groups x subjects - also with teachers in each cell.

Still a table is a table, so the algorithm to solve it, should work here aswell. Is that kind of right?

But when I read your post again ... and again ...

Well, I understand 33 FET hours as real student sets (="y-axis"). But then you write: FET days ("x-axis") would be 1500. From my understanding, it would be only n_subjects (like 15 or so).

It seems like I have not fully understood. The new table will maybe be also 3-dimensional, right? My head buzzes ...

Anyway ...

Regarding the "class teacher": Yes, one teacher can be the class teacher for group A (actually in course X) and also for group B (actually in course Y). Like the class teacher from 20.7-B5 and 20.A-B3.

I'm not sure if we can ignore this feature. Each group needs a class teacher. And this class teacher extra duty shall be uniformly distributed over all teachers.

Thanks a lot Liviu for the whole brain work.

[Liviu Lalescu]

I want to show you how I did with dolphins. The custom version (old) is on https://lalescu.ro/liviu/fet/download/custom/dolphins/ . There is an example file there.

I attach the outputs of FET for dolphins. The first one is "compressed" for human reading (generated with FET-dolphins custom version), the second one is output using FET-5.37.6 unreleased yet from my hard drive - uncompressed (the two timetables are not equal - I could not do this, since the algorithm changed a bit between the versions). Open the 2 HTML files with the internet browser.

It allocates patients to dolphins in time slots. Please let me know if you need more details to understand the idea. Only the idea, not the exact details. You can also see the constraints list.

What I have in mind is having a 2 dimensional matrix, but in which columns are like: "first_teacher WiPo theory", "first_teacher WiPo practice", "first_teacher GA theory", ..., "first_teacher OP/Engl/OP practice" (7*2=14 until now), then for second_teacher, then ..., then for the 100th teacher. The rows are simply the students sets.

About class teachers: isn't it very easy to choose a teacher from the 7 (subjects) for each students set?

Let me know what you think now.

[Christoph Voelker]

Thank you very much! This made it very clear for me. So, many many columns!

And inside the cells will be the hours, right? But then 7x2=14 rowsums must be build for each teacher. And this sum(rowsums) must be fit to the target hours of each teacher, right? is that possible?

And we will of course have many cells with a 0.