Automatic Activity Planning?

Christoph Voelker · May 12, 2019, 05:15:09 PM

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

Well. Maybe yes.

Liviu Lalescu · May 12, 2019, 05:22:47 PM

I just had a look at the dolphins .fet file and I remembered better.

The matrix n_students_sets x 14*n_teachers will contain in each cell an activity or nothing/void. An activity will have no students specified, no teachers specified, only the subject specified. There will be at most 14*33 activities to be placed based on the preferences, specified by constraints preferred time slots, and by validity constraints (so that a teacher respects his maximum working hours and a students set studies with only a teacher a separate subject).

Please let me think a bit more. We might make only 2*n_teachers = 2*100 columns and 33 rows, if we consider a column for each teacher theory and practice, and the subjects (a subject for each activity) will be in the cells, or a cell will be empty. I will write after some thinking. It is a bit different from dolphins and Peter B, because (real) time is not important for you. This is why I did not think of this from the beginning.

Liviu Lalescu · May 12, 2019, 05:24:57 PM

And each activity in a cell will have a separate number, which is the real life duration, and the maximum for each teacher must be respected. I plan to use the activity number of students for this, and add a new constraint.

Liviu Lalescu · May 12, 2019, 06:08:01 PM

Yes, it seems possible with 33 rows and "only" 2*100 columns. Each teacher will have 2 columns, like: "Teacher t1 theory", "Teacher t1 practice", there are 33*7*2 activities. Each activity will have no students, no teachers, and only the subject specified (and the real duration and maybe activity tags for helping in the scheduling). Allocate these activities in the matrix. Each cell of the matrix will have an activity or will be void.

I will send you a small drawing I made by hand, let me know if you understand it. If you want (if there are no privacy problems), please post my drawing here.

Christoph Voelker · May 12, 2019, 06:36:45 PM

Thank you for your drawing, which I will attach here ...

Still I wonder how it is realised, that FET will know the "past activity plannings", because the actual activity planning shall be based on past ones. Do you know what I mean?

Maybe ALL groups (classes) from our school need to be included - so the groups x teacher will not be forgotten? And only these groups that need an actual activity planning get a tag or something?

Liviu Lalescu · May 12, 2019, 06:53:21 PM

Quote from: Christoph Voelker on May 12, 2019, 06:36:45 PM
Still I wonder how it is realised, that FET will know the "past activity plannings", because the actual activity planning shall be based on past ones. Do you know what I mean?

In my drawing, A1, A2, A3, and A4 are for students 19.1-B8. These activities will get preferred time slots 100% for the first row. So 100% forbidden for the rest of the rows.

Now you can add more preferred times constraints, strictly less than 100%, for say A1. If last time 19.1-B8 learned WiPo from PalM, you will add something like 95% (or less, or more, this is practically decided) for A1, slots "PalM t" and "PalM p" (so 95% forbidden for all the other 33*2*100-2 slots, and in fact 100% stronger forbidden wins for rows 2..33).

Preferred time slots constraints work by forbidding with the highest percentage from all the constraints for that activity and the opposite slots.

I hope I am not mistaking.

Please let me know if this is an acceptable method of working.

Quote
Maybe ALL groups (classes) from our school need to be included - so the groups x teacher will not be forgotten? And only these groups that need an actual activity planning get a tag or something?

So 8*33 rows? I am not sure I understand exactly, but if the above method does not work I will try to think about this.

Christoph Voelker · May 12, 2019, 07:28:49 PM

Hi there,

I think I will have to sleep over this as my head still buzzes.

For the last hour I was googling timetable stuff and found out that one can write PhD theses about this topic.

Just a little question: Your algorithm for solving - is it a genetic algorithm approach?

Good night!

Liviu Lalescu · May 12, 2019, 07:39:39 PM

Quote from: Christoph Voelker on May 12, 2019, 07:28:49 PM
I think I will have to sleep over this as my head still buzzes.

I am sorry

. I did not know from the start the best solution (which I hope we found). It is a new situation, and we need to apply tricks and customize.

Quote
For the last hour I was googling timetable stuff and found out that one can write PhD theses about this topic.

I did not yet meet a teacher to propose me for that, and also I am maybe more on the practical side. But I tried to describe the algorithm and to write clear code.

Quote
Just a little question: Your algorithm for solving - is it a genetic algorithm approach?

FET version <5.0.0 (2002-2007) was genetic, very weak algorithm, could not solve real-life timetables. Volker joined the project in 2006 and convinced me to hunt for a better algorithm to solve his real-life data file which could be solved by another program. And I found the good algorithm in 2007. It is heuristic, but a more clever heuristic, and you can read about it on the documentation page of the FET homepage.

Quote
Good night!

Good night!

Christoph Voelker · May 13, 2019, 07:17:38 AM

Hi there,

I am still not sure if I can image what will go on there ...

A1 to A4 are activities? And what do you mean by "time slot"? A table cell? Or a multidimensional table cell?

Maybe we should just try this out with some data and try to reproduce an activity planning?

Maybe we will then find out, that defining the contraints etc. will take as much time as doing a manual activity planning

But maybe not!

Liviu Lalescu · May 13, 2019, 07:28:43 AM

In the order of your questions:

Yes, A1...A4 are activities. These activities will have no students sets, no teachers, a subject, real duration (as a new variable to be added by me or using a trick: use for this the number of students, which is unused in real-life), and possibly activity tags to help us with the constraints.

(FET) "time slot" is a single table cell, from the 33 x 2*100 table.

OK, I will try to make a very small example for you, I think I will l do it now, for my example with A1...A4. I can also do a larger example, let me know.

I think I need to add two constraints: one so that the working hours of the teachers will not be higher than the limit, and one so that the theory for an activity will be preferred to be taught by the same teacher as the practice, if there are defined both activities.

I hope not. We can derive some automatic tools to create the .fet XML file for FET (you can open one example with a text or XML editor to see it). Then FET will generate the activity planning, which can be converted to another .fet XML file to be fed into FET official for the final scheduling.

Liviu Lalescu · May 13, 2019, 07:43:40 AM

I did a very small example, for my drawing. I attach it here. Please open it with FET official (neglect the warning, I have on my hard disk 5.37.6 unreleased yet) and generate. Then open fet-results/index.html, and see the activities.html. You cannot see the timetable from the FET interface, since there are no FET teachers or students sets.

Please see the data that I added in FET. And remember that I need to implement two new constraints, as I wrote previously.

The preferred times constraints with 95% weight are preferences from your timetable. You can use similar to keep the teachers from the previous timetable to the same students sets.

Christoph Voelker · May 13, 2019, 08:06:53 PM

Well, this sounds all good. Is the time ready that I can feed it with some more realistic data and check if something useful is generated?

Thanks and good night

Liviu Lalescu · May 13, 2019, 09:21:15 PM

You are welcome!

So you need to add maximum 2*7*33 activities, with maximum 33 rows (FET hours) and maximum 2*100 columns (FET days).

Hmm, the maximum number of FET days is 35, in FET official. I will need to increase these to 200. I will let you know when such a version is ready (I hope soon, it is an easy change).

You can add the data, but you miss the two constraints: teachers total number of working hours (and each activity will have a "real" duration) and that if a teacher teaches theory (or practice) for a students set and subject, it is preferred to teach practice (or theory) for the same students set and subject. These will take longer to implement.

Did you understand everything in my small example? Every activity and time constraint?

Liviu Lalescu · May 13, 2019, 10:52:31 PM

I made a version with max 200 FET days per week. You can get it from https://lalescu.ro/liviu/fet/download/custom/christoph-voelker/

Liviu Lalescu · May 14, 2019, 01:00:16 PM

I forgot a constraint: all activities are not overlapping. I added this constraint in my latest file (liviu2.fet, attached here).

Also, in this file, I thought of an improvement. The number of columns is 100 (one for each teacher), and the number of rows is 2*33 (two rows for each students set - theory and practice). See the attached file. In this way, a constraint is already implemented, so that a teacher prefers to teach both theory and practice to the same students: constraint activities same starting day, <100% (like 95%).

I need to increase the maximum number of FET hours to 2*33=66.

Please tell me what you think and I'll also do this (increase max FET hours to 66) soon.

Run the example and see activities timetable HTML.