German "Kollegstufe"

[aliponte]

You'll find the data of a german "Kollegstufe" in the attachment. Kollegstufe means: A student has to pick a certain number of courses (about 10) out of a given set of available courses (about 70). At our school there are 136 students forming a FET-year. Every student is equivalent a FET-subgroup. All students attending the same course are forming a FET-group. The students' names are anomymized (Q001-Q136).

Only one year of this school is represented. I just wanted to know: Is FET able to make a timetable under the circumstances of Kollegstufe or not and if yes, how long would it take?

aliponte

[Volker Dirr]

Thank you for the file.
I don't know a reason why it shouldn't work.

I saw, that several subjects (your "Leistungskurse") have the same not allowed time constraint.
it is ok, if you add constraint that way, but maybe next time it is faster do add an activitiy tag (maybe name it "L" like "Leistungskurs") and tag the activities with that. so you need to add only one constraint to that activity tag and not to all subjects.

I also saw you used a few same starting time constraints. don't forget you should add them only if you 100% need them at the same time.
Setting this constraint has advantages and disadvantages:
generating the timetable will be faster if there is no other logical posibility.
generating will be slower, if there are many other logical possibilities.
if there are other possibilities you will also not find the best timetable with that constraints.

What is the idea of subject "."?

[aliponte]

Subject "." is the subject that I assign to special pseudo activities, e.g. the lunch break. Due to capacity limits of our school kitchen some classes have lunch during the 6th period, others during the 7th. Lunch breaks are garanteed by pseudo activities with oppropriate time slots. As the students should have enough seats in our canteen when they have lunch, rooms M01 to M16, which are virtual rooms of our canteen, are assigned to the lunch activities.

[Volker Dirr]

in hour 6 and 7 it is clear. i mean monday 9-11 and thursday 7-11.

Later edit:

ah. ok. i see now also for this you added flexible with min n day 100%. nice solution. that is a good variant.
you also limit the number of gaps per student by this.

if you add the whole dataset, you can maybe try to add only 1 hour for lunch per day and add a students max gaps per week constraint. this will be slower, but maybe find better tables (if you have enough rooms for lunch, because it doing it that way will mean students will be maybe some more times in the rooms to take lunch.)

[aliponte]

This is another step on my way mapping my school completely onto a FET data set. Since I discovered the power of activity tags everything went much faster. Now two thirds of the whole work is done. (Grades 5, 6, 7, 11, 12, 13 are done, 8, 9 10 are missing.)

The assignment of class rooms is of inferior importance and will be left out in this experiment. An optimization of teachers' gaps doesn't make sense at this stage, as the set of activities is not completely included.

I'm grateful, if experienced readers point me at flaws or mistakes and give me some hints to do it better.

[Liviu Lalescu]

This is another step on my way mapping my school completely onto a FET data set. Since I discovered the power of activity tags everything went much faster. Now two thirds of the whole work is done. (Grades 5, 6, 7, 11, 12, 13 are done, 8, 9 10 are missing.)

The assignment of class rooms is of inferior importance and will be left out in this experiment. An optimization of teachers' gaps doesn't make sense at this stage, as the set of activities is not completely included.

I'm grateful, if experienced readers point me at flaws or mistakes and give me some hints to do it better.

This one seems a bit more difficult.

I see you decided to make years 5a, 5b, etc, so add a real group=a FET year, different from previous style of 11, 12 and 13.

You have already donated us an input file into official examples. Should I also add this one? Remove the old one? Keep the same comments? What name should we give to this file?

I intend to release a new FET version in a few days. I would like to include your final file, if possible, and I agree to wait a bit more for that, but not too long. What do you think?

[Volker Dirr]

His "old" file is incomplete. So you should not include it as example and wait hopefully for new one.

The only missing thing is maybe that he need to care more careful about activities with duration 2.
So aliponte, please read also this and maybe also add that feature, because i fear you need it for subject sport, maybe even for art if you want.
http://lalescu.ro/liviu/fet/forum/index.php?topic=911.msg5303#msg5303


Later added comment: Following paragraph is not 100% correct (compare later entry)
His decision of different styles in lower and upper years is correct. That years are managedd different. Lower years are mostly managed by "classes" while upper years are managed by "courses". That is correct and a fine style.

[Volker Dirr]

I saw you tag all sport lessons with an activity tag to give that tag a space constraint.
you can do it this way, especialy you can also limit the max number of sport hours per day of a teacher that way.
In "normal" case you can also do it just with a space constraint to the subject, so you don't need to add an activity tag.
But keep it this way with sport.

But if you do it just with a subject to music, art, ... you safe some time while adding constraints (tables will be the same, also generating time will be the same.)

if you know that activities must be at the same time (i saw that a few times for sport in lower years), then you can also use a same starting time constraint to speed up generating a bit.
A saw you already knew this hint, because i saw you done that for subject religion in year 7.

The tables of lower years are filled 100% by your variant. I don't know if they are also filled in missing years. If not, you shouldn't add a same starting constraint so that courses and maybe add only a "no gaps" constraint to that years. That will slow down generating a bit, but you might find better solution.

[Volker Dirr]

Oh. I must correct me.
Liviu is right.
If you add year "5" and then add the group "5a" it is sweeter. it doesn't matter if you use your variant. FET also understood, but it is not sweetest one.
Did you know/use "divide year automaticaly"? you will save much work if you it that way.
check this:
http://www.timetabling.de/manual/FET-manual.en.html#id_12

But on the other hand i also saw you can't always use that easy, because for example in two classes sport is splitted between boys and girls, nut not in the third class.
so you understood correct how to split groups and you can't always use the divide year automaticly feature (without renaming them).
but next time it will be sweeter if you set classes not as a year, because i printed years table will be sweeter. (i guess you will need a print of that table in the teacher room.)

[aliponte]

Thank you, Liviu and Volker, for your kind interest in my work. After several kilo minutes I'm done with my first timetable now.
You know, it is an experiment and not something for the shop window. If you like it, you may publish it together with your next FET update. But I feel rather certain, with some time spent on it, I could improve the schedule. I did nothing to decrease the teachers' gaps, nor did I anything to improve the equidistribution of subactivities (belonging to the same activity) over a week.

Getting a timetable is not the question for me. I got one already. Now the more interesting part is going to come. How many additional constraints can be applied to the data to improve the schedule?

But please forgive me. I will not do that today. The wheather is excellent, deep blue sky over glittering snow covering the whole landscape. This won't come again soon on a weekend.

I'll answer all your questions around my strategies as soon as possible.

aliponte


P.S. Please be patient when you try the .fet file appending. It'll take appr. 20 min computing time until a timetable is found.

[Liviu Lalescu]

Thank you, Liviu and Volker, for your kind interest in my work. After several kilo minutes I'm done with my first timetable now.
You know, it is an experiment and not something for the shop window. If you like it, you may publish it together with your next FET update. But I feel rather certain, with some time spent on it, I could improve the schedule. I did nothing to decrease the teachers' gaps, nor did I anything to improve the equidistribution of subactivities (belonging to the same activity) over a week.

Getting a timetable is not the question for me. I got one already. Now the more interesting part is going to come. How many additional constraints can be applied to the data to improve the schedule?

But please forgive me. I will not do that today. The wheather is excellent, deep blue sky over glittering snow covering the whole landscape. This won't come again soon on a weekend.

I'll answer all your questions around my strategies as soon as possible.

aliponte


P.S. Please be patient when you try the .fet file appending. It'll take appr. 20 min computing time until a timetable is found.

I added this new file into FET examples. I hope that I will add your future files also, maybe in time for the new release.

I removed the old file and the old comments from the examples, I just mentioned that this is a difficult file, solves in ~10 minutes. If you want to add comments, feel free (but it is not necessary).

The time to solve the timetable, as it is now, is a good time? I mean, FET does a good job?

[Volker Dirr]

I added to that sample a max 4 gaps per week to all teachers constraint and solved the table in 45 minutes.
I don't know if max 4 gaps per teacher is good or bad with your samplefile, but it is possible.
But i recommend you to do it not that way, because some teachers don't need so less gaps. (for example trainee teachers (they also go with other teachers into lessons), the headmaster (work in his office), ...)
you can do it two different ways:
add max gap constraint to every single teacher (you have many, so maybe much to do and you might forget one, the interface is sadly not very clear with so many teachers)
or
add pseudo activities to teachers like that. so maybe do an subject "office" and add 15 hours (without min n day) activities with that subject. so if you add a min gaps to all teachers, the headmaster got up to 4+15=19 gaps.

[Liviu Lalescu]

I tried with max 6 gaps per week, max 2 per day for teachers. Seems too difficult. But I have a slower computer than Volker.

Just to be sure, because Volker said that the teacher's names may be sensitive information: if teacher's names are real ones in this file, could you please change them to fake ones? So that I can add this file to FET without any problems? I don't want to be forced to release another version of FET just to remove an example file.

Again, let me know if current file is 100% safe to add to FET or attach a new file and let me know about it if it is 100% safe to add to FET.

[Volker Dirr]

maybe it was just the max 2 per day.

i set max 4 per week and there are a few teachers that have 3 or 4 gaps at a single day. (but of course max 4 per week.)
that "difficult" teachers are: (of course "difficult" just in this single solution, maybe difficult is a combination of special teachers.)
FLE
FRL
ANG
HAN
HIN
RUC
SEI
STB

but aliponte will (maybe) know reason for that. (because of afternoon lessons maybe, ...)

[aliponte]

I did some improvements to the file I recently sent.

First of all I removed all pseudo activities for teachers. FET counts them as if they were real activities. Many constraints (like ConstraintTeacherMaxGapsPerWeek) would not work properly without them being removed.

Then I added "ConstraintTeacherIntervalMaxDaysPerWeek" nearly for every teacher to limit teaching in the afternoon.

FET seems to like timetables that show one ore two extremely busy days (up to 8 lessons a day) followed by days with nearly nothing to do (a single lesson). To avoid extremes like these I filled in "ConstraintTeacherMinHoursDaily = 2" for most teachers. (There are exceptions to be considered. A global constraint for all teachers may lead to an unsolvable data base.)

Timetable gaps are reduced by constraints I chose individually for every teacher. A common constraint wouldn't have helped.

With these constraints added computing time rose significantly. Now it takes more than 2 hours for FET to find a solution.

You find the new data and timetable file attached to this text. Maybe you'll like it better than my old one. All teachers' identifiers are 3 letter abbreviations of real names which are too short to find out what the real names are.

The seed of the pseudo random number generator of the timetable shown was 1548805687.

P.S. With seed 1763453941 it took only 40 minutes.